This assignment involves using the genetic algorithm (GA) to find the solutions to boolean constraints. Each problem consists of 20 boolean variables (A0 - A19) and a set of constraints. The goal, in each case, is to find truth assignments for each variable such that all constraints are satisfied. The programs for each of the 3 cases below should be almost identical, with only small differences in the fitness functions.
For each of the runs below, plot the fitness graph (min,max and avg) using the fitness-graphviewer object as described in the EVOKE documentation. The questions asked below assume that you'll base your analyses upon these graphs.
1.1) The 5 constraints are:
A0 and A1 and A2 and A3
A4 and A5 and A6 and A7
A8 and A9 and A10 and A11
A12 and A13 and A14 and A15
A16 and A17 and A18 and A19
a) Describe the differences in the behavior of the GA when you use a population of size 100 versus 20. Use 50 generations in each case, a mutation rate (pmut) of 0.01 and a crossover rate (pcross) of 0.75.
b)Use a population of size 50, 50 generations, pmut = 0.01 and 3 different crossover rates: 0.1, 0.3 and 0.8. What are the differences in behavior in the three runs?
c) What is the size of the search space for 1.1? Is the fitness landscape smooth or rugged? Explain.
1.2). The 10 constraints are:
A0 and A1 A2 and A3
A4 and A5 A6 and A7
A8 and A9 A10 and A11
A12 and A13 A14 and A15
A16 and A17 A18 and A19
1.2a) Run these constraints with the same conditions as in 1.1a. What are the differences in behavior between the 1.1 and 1.2 cases. Why are they different even though the constraint sets are logically equivalent?
1.2b) Use a population of size 100, 100 generations, pcross = .75. Run with two different values of pmut: 0.1 and 0.01. What are the differences in behavior? Can you explain why these differences occur?
1.2c) Compare the fitness landscapes in1.1 and 1.2.
1.3. The 11 constraints are:
A0 or A1 or A2 or A3
not (A0 and A1) not(A0 and A2)
not(A0 and A3) not(A1 and A2)
not(A1 and A3) not(A2 and A3)
A4 and A5 and A6 and A7
A8 and A9 and A10 and A11
A12 and A13 and A14 and A15
A16 and A17 and A18 and A19
1.3a) The setting are: population = 100; generations = 100; pcross = .75; pmut = 0.1. Compare this run to the corresponding run of 1.2b. Are they any different? Would you expect them to be different? Why or why not?
1.4 Compare the fitness landscapes of 1.2 and 1.3? Should these differences affect the behavior of the GA? Why or why not?