AI assignment 3

 AI assignment 3

Question 1:

Suppose a genetic algorithm uses chromosomes of the form x = abcdefgh, with a fixed length of

eight genes. Each gene can be any digit between 0 and 9. Let the fitness of individual x be

calculated as:

f(x) = (a + b) − (c + d) + (e + f) − (g + h)

and let the initial population consist of four individuals

with the following chromosomes:

x1 = 6 5 4 1 3 5 3 2

x2 = 8 7 1 2 6 6 0 1

x3 = 2 3 9 2 1 2 8 5

x4 = 4 1 8 5 2 0 9 4

a) Evaluate the fitness of each individual, showing all your workings, and arrange them in order with the fittest first and the least fit last.

🔹 x1 = 6 5 4 1 3 5 3 2

• (6 + 5) − (4 + 1) + (3 + 5) − (3 + 2)
  = 11 − 5 + 8 − 5 = 9

🔹 x2 = 8 7 1 2 6 6 0 1

• (8 + 7) − (1 + 2) + (6 + 6) − (0 + 1)
  = 15 − 3 + 12 − 1 = 23

🔹 x3 = 2 3 9 2 1 2 8 5

• (2 + 3) − (9 + 2) + (1 + 2) − (8 + 5)
  = 5 − 11 + 3 − 13 = -16

🔹 x4 = 4 1 8 5 2 0 9 4

• (4 + 1) − (8 + 5) + (2 + 0) − (9 + 4)
  = 5 − 13 + 2 − 13 = -19

---

✅ Sorted Fitness (Fittest to Least Fit):

1. x2 = 23 ✅

2. x1 = 9

3. x3 = -16

4. x4 = -19

b) Perform the following crossover operations:

i) Cross the fittest two individuals using one–point crossover at the middle point.

Parents: Fittest 2 individuals = x2 and x1
x2 = 8 7 1 2 | 6 6 0 1
x1 = 6 5 4 1 | 3 5 3 2

One-point crossover means:

• Child1 = First half of x2 + second half of x1 = 8 7 1 2 3 5 3 2

• Child2 = First half of x1 + second half of x2 = 6 5 4 1 6 6 0 1

ii) Cross the second and third fittest individuals using a two–point crossover (points b and f).

Parents: 2nd and 3rd fittest = x1 and x3
x1 = 6 5 4 1 3 5 3 2
x3 = 2 3 9 2 1 2 8 5 

Child1:

= 6 5 9 2 1 2 3 2

Child2: 
= 2 3 4 1 3 5 8 5 

iii) Cross the first and third fittest individuals (ranked 1st and 3rd) using a uniform crossover.

Parents ranked 1st and 3rd = x2 and x3
x2 = 8 7 1 2 6 6 0 1               ⇒        O5= 27126201
x3 = 2 3 9 2 1 2 8 5               ⇒        O6= 83921685

Question 2:

Consider a genetic algorithm in which individuals are represented using a 6-bit string of the form s1s2s3s4s5s6. An example of an individual is 100110 for which s1=1, s2=0, s3=0, s4=1, s5=1 , s6=.0

The fitness function is defined over these individuals as follows: f(s1s2s3s4s5s6) = s1 + s2 + s3+ s4+ s5 + s6 + AND(s1,s2,s3,s4,s5,s6), where AND(s1,s2,s3,s4,s5,s6)=1 if s1=s2=s3=s4=s5=s6=1; and AND(s1,s2,s3,s4,s5,s6)=0 otherwise.

Answer the following questions. Show each step of your work.

(a)  Complete the following table showing the probabilities of selecting each of the 6 individuals below according to the standard selection method. Also, calculate the Total fitness.

Individual	Fitness/Quality	Standard "fitness" or probability of being selected
100110	3	3/17=0.176
110011	4	4/17=0.235
111111	7	7/17=0.412
101100	3	3/17=0.176
000000	0	0/17=0.000

 

Total Fitness = 3+4+7+3+0=17

 

(b)  Suppose that a single crossover point will be used for crossover. This point has been chosen as the point between the 2nd and the 3rd bits (i.e. between s2 and s3). Demonstrate the two offspring that will result from crossing over the following two individuals:

 

                                 PARENTS             OFFSPRING

First parent:               100110                     101011

Second parent:          101011                      100110

 

(c)   Explain how the standard mutation method is applied after selection and crossover to form the "next" generation of a population and why is it essential.

Answer:

How Mutation is Applied:

• Mutation is applied after crossover, to the new offspring.

• Each bit in an individual has a small probability (e.g., 0.01 or 1%) of being flipped (i.e., 0 → 1 or 1 → 0).

• This is done randomly and independently for each bit.

Example:
If we have an offspring 101011 and bit 3 is chosen for mutation, the bit flips:

• Before: 101011

• After: 100011 (bit 3 flipped from 1 → 0)

Why it's important:

• Maintains diversity in the population

• Prevents early convergence to bad solutions

• Helps explore new parts of the search space