Cairo University Final Exam
Faculty of Computers & Information Jan 2007
Dept of Computer Science Time 3 hrs
Soft Computing
Answer ALL Qusetions:
1- Discuss the role of selection, crossover and mutation in genetic algorithms using
schema theory.
2- Crossover and mutation are the main operators of a Genetic Algorithm.
a- Differentiate between single-point and multiple-point crossover, on both binary and
floating point representations.
b- Show by example- using binary strings- how can a 2-point crossover be carried out.
c- Explain the operation of the mutation operator on both binary and floating point
representations.
d- Discuss the mechanics of non-uniform mutation on floating point representation-
Apply using the following function:
t
( t , y ) y. ( 1 r( 1 T ) )
where r is a random number from [0..1].
3- What is the total payoff after 10 cycles in the prisoner's dilemma of TIT for TAT
(cooperate for cooperate, and defect for defect) playing against:
a- a strategy that always defects
b- a strategy that always cooperates
c- ANTI TIT for TAT (cooperate for defect, and defect for cooperate)
d- a strategy that makes random moves (what is the excpected average payoff?)
4- a- Prove that any string of length m is an instance of 2 m different schemas.
b- Define the fitness f of bit string x with length m = 4, to be the integer represented
by the binary number x. (eg. f(0011)=3, f(1111)=15). What is the average fitness of
the schema 1*** under f? What is the average fitness of schema 0*** under f?
5- Given a population of PopSize Individuals, which are bit-strings of length L. Let
the frequency of allele 1 be 0.3 at position i, that is 30% of all individuals contains a 1
and 70% a 0. How does this allele frequency change after performing k crossover
operations with one-point crossover?
6- Calculate the probability that a binary chromosome with length L will not be
changed by applying the usual bit-flip mutation with Pm=1/L.
7- Given the following feedforward neural network with weights,
X1
+1
+1
-1
Y
-1
+1
X2
+1
and applying the following activation function,
1 x 0
f ( x)
0 x 0
Compute the outputs Y for inputs (X1, X2) equal to the following,
(0,0), (0,1), (1,0), (1,1).
What function do you think this network emulates.
8- Given the following exemplars to be encoded in a BAM,
X1 = (101010) Y1 = (1100)
X2 = (111000) Y2 = (1010)
a- Compute the weights matrix M.
b- Recall the output of the BAM when presented with X = (111010). Comment on the
result.
c- Recall the output of the BAM when presented with X = (000111). Comment on the
result.
9- Construct an autoassociative BAM with the following training vectors:
x1=(100101) and x2=(111000)
Determine the output using x= (111101) and x= (011010). Comment on the result.
10- Differentiate between linear and nonlinear activation functions in the performance
of training feedforward neural networks.
11- Design a fuzzy controller with two input variables:
SPEED with range: 0 to 120 and 5 fuzzy sets: Stopped, Very Slow, Slow,
Medium Fast and Fast.
And
DISTANCE with range:0 to 2500 and 5 fuzzy sets: At, Very Near, Near,
Medium Far and Far.
The output variable is BRAKE with range: 0% to 100% and fuzzy sets: No, Very
Slight, Slight, Medium and Full.
The following fuzzy rules govern the actions of the system:
IF SPEED=Very Slow and DISTANCE=At THEN BRAKE = Full.
IF SPEED= Slow and DISTANCE=At THEN BRAKE = Full.
IF SPEED=Very Slow and DISTANCE=Very Near THEN BRAKE =
Medium.
IF SPEED= Slow and DISTANCE=Very Near THEN BRAKE = Medium.
Using a Mamdani approach, show how the output is computed.
12- Show how fuzzy rules that model a particular system can be evolved using genetic
algorithms. (Note: This question is bonus!)
