Evolutionary Computation and Artificial Life

Exercise 2

Roee Zahor 013701362

Itai Barami 037172632

Date: 21/11/2004

Question 1

In this question we tried to maximize the function f(x1,x2) = 21.5 + x1 * sin(4*pi*x1) + x2 * sin(20*pi*x2) over the range -3.0 to 12.1 for x1 and 4.1 to 5.8 for x2.

We made three experiments: fitness-proportionate selection, rank selection (with beta=1.1) and tournament selection (with k=7).

Experimental results:

For all experiments: population size = 100, number of generation = 300, p_c = 0.7, p_m = 0.001.

Fitness-proportionate selection

Rank selection (beta=1.1)

Tournament selection (with k=7)

Conclusions:

1. The problem can be easily solved using a GA.
2. All selection methods showed good results in finding the best individual and keeping it stable during the experiment.
3. The main difference is in the average fitness. Rank and Tournament selections showed extremely high convergence rates.

Question 2

In this question, we tried to create magic squares using a GA. The genome representation we used is an array of n*n numbers in the range [1,n]. Each number in each cell represents this number in the matching cell in the square.

The fitness function is calculated as follows:

1. Calculate the series of sums of each row, each column, and the two diagonals in the square.
2. Calculate the average of the sums from section 1.
3. Calculate the series of differences between the series from section 1 to the average from section 2.
4. Sum the series from section 3.
5. Subtract from (n²*(n²+1)/2) the sum from section 4. This is the fitness.

Experimental results:

For all experiments: population size = 200, number of generation = 200, p_c = 0.7, p_m = 0.1.

n=3 (fitness 45 is perfect match)

2	9	4
7	5	3
6	1	8

n=4 (fitness 136 is perfect match)

4	7	13	10
9	14	8	3
16	11	1	6
5	2	12	15

n=5 (fitness 325 is perfect match)

9	19	11	25	1
15	13	12	23	2
10	7	22	6	20
17	5	16	3	24
14	21	4	8	18

Conclusions:

1. The problem can be easily solved using GA.
2. Many runs of the experiment succeeded to create a legal magic square or an almost magical square.

Question 3

Experimental results (fitness normalized to [0,1] scale):

For all experiments: population size = 100, number of generation = 200, p_c = 0.4, p_m = 0.001.

n=10, M=29

n=11, M=36

n=12, M=41

n=13, M=46

n=14, M=52

n=15, M=58

n=16, M=60

Observations:

1. Not even one combination of n and M yielded a sorting network that could sort 100% of the inputs.
2. Higher values of n yielded much poorer results.

Conclusions:

1. The problem is much harder to solve using GA than the problems we have encountered so far.
2. The poor results can be explained because of limited population sizes, which barely cover 10^-15% of the search space. This also explains why higher values of n yielded much poorer results.
3. The experiments should be repeated with much larger population sizes. We could not accomplish this because of the extreme CPU time required to run the experiments, especially when using high values of n.

Question 4

In this question we chose to implement the TSP problem using a representations similar to the one we used in question 2.

The only difference is the fitness function. The fitness is calculated as 20000 – (total path length).

Experimental results:

We tried to run the experiments with 3 different parameters sets:

1. population size = 500, number of generation = 1000, p_c = 0.4, p_m = 0.001.
2. population size = 500, number of generation = 1000, p_c = 0.4, p_m = 0.01.
3. population size = 500, number of generation = 1000, p_c = 0.7, p_m = 0.001.

We will display the results from the third series of experiments, which yielded the best results.

The graph shows the fitness of the three best runs, and the average fitness of all 10 runs.

Best path found:

Leg #	From	To	Leg distance	Accumulated distance
1	Venezia	Trieste	157	157
2	Trieste	Trento	290	447
3	Trento	Bologna	295	742
4	Bologna	Milano	210	952
5	Milano	Torino	138	1090
6	Torino	Aosta	110	1200
7	Aosta	Genova	245	1445
8	Genova	Firenze	225	1670
9	Firenze	Ancona	262	1932
10	Ancona	Perugia	139	2071
11	Perugia	Roma	192	2263
12	Roma	L'Acquila	113	2376
13	L'Acquila	Campo Basso	199	2575
14	Campo Basso	Napoli	160	2735
15	Napoli	Potenza	158	2893
16	Potenza	Palermo	668	3561
17	Palermo	Catan zaro	383	3944
18	Catan zaro	Bari	362	4306
19	Bari	Venezia	818	5124

Conclusions:

1. The problem is much harder to solve using GA than the problems we have encountered so far.
2. The poor results can be explained because of limited population sizes, which barely cover 10^-15% of the search space. This also explains why higher values of n yielded much poorer results.
3. The experiments should be repeated with much larger population sizes. We could not accomplish this because of the extreme CPU time required to run the experiments, especially when using high values of n.