Faculty of Computers and Information
Cairo University
Final Exam
Department: Computer Science
Course Name: Genetic Algorithms Date: 11/1/2016
Course Code: CS464 Duration: 2 hours
Examiner(s): Prof. Dr. Amr Badr Total Marks: 60
ANSWER ALL QUESTIONS
1-Given a medical cancer information system with governing variables x1, x2 and x3. It is required to infer the
decision D. The following information is provided,
x1 range 0..100 with fuzzy sets L, M, H.
x2 range 0..100 with fuzzy sets L, M, H.
x3 range 0..100 with fuzzy sets L, M, H.
and D with decisions Malignant: M and Benign: B.
The following decision blocks apply,
DB1:
IF x1=L AND x2=L THEN y=L
IF x1=M AND x2=H THEN y=H
DB2:
IF x3=L AND y=L THEN D=B
IF x3=M AND y=H THEN D=M
Intermediate variable y is
y range 0..100 with fuzzy sets VL, L, M, H, VH
determine the decision D for x1= 30, x2=70 and x3=30.
(10 points)
2- A seller has 3 parameters A, B, C affecting his market Risk,
A range 0..100 with fuzzy sets L, M, H.
B range 0..100 with fuzzy sets L, M, H.
C range 0..100 with fuzzy sets L, M, H.
And Risk: -100..100 with fuzzy sets VL, L, M, H, VH
The following rules govern,
IF A = L AND B=M AND C = H THEN Risk = L
IF A= M OR B= L AND C = H THEN Risk = M
Estimate Risk, A= 40, B=30, C=70.
(7 points)
3- Taking the reproductive schema growth equation of schema theory,
eta(S, t+1) = eta(S, t). eval(S, t)/ averagePopFitness(t) [1-Pc.d(S)/(m-1)-o(S).Pm]
assume that o(S).Pm = 0 and d(S) = m-1, then the equation becomes:
eta(S, t+1) = eta(S, t). eval(S, t)/ averagePopFitness(t) [1-Pc]
Discuss the mechanics of the algorithm when Pc = 0 and Pc = 1 under the following conditions:
a- low population size
b- high population size
c- Elitism
(7 points)
4- The correct representation of a problem is vital to its solution.
a-Taking the problem of function optimization, discuss the suitability of binary and floating point
representations.
[3 marks]
b-Calculate the number of bits necessary to represent a precision of 6 decimal places over a range of [1, 5].
[3 marks]
1
5-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.
(6 points)
6-DNA methylation problem is one of the causes of cancer. It is exemplified in thousands of CpG sites
distributed over genes in the DNA. Patients suffering from cancer have their DNA sequenced and analyzed as
database of their genes and associated CpG sites. It is required to design a genetic system to identify sites and
genes responsible for cancer.
(6 points)
7-Given a Network load simulator, it is required to design a genetic system that evolves a fuzzy model for
network load balance. The simulator takes as input several parameters and responds with a measure that
represents the network load status.
(6 points)
8-Clustering of data is an important problem. Given a dataset of parameters x1, x2, …, xm it is required to
design a genetic system that clusters the rows of the dataset into an unknown number of clusters (determined by
the genetic system), that maximizes inter-clusters distances and minimizes intra-cluster distances.
(6 points)
9-Consider the vehicle routing problem. We have N trucks each with capacity C. All trucks are loaded and start
their journey from the same source. They distribute products to P supermarkets where P > N. It is required to
design a genetic system that will allocate trucks to supermarkets and minimize the overall distance covered by
trucks.
(6 points)
