Evolutionary Computation and Artificial Life (202-1-5171), Semester A, 2006/7

Exercise 1

Question 1. Which schemata does the bitstring 000 belong to?

Question 2. Define the fitness f of bit string x of length l=4 to be x³+7 (e.g., f(0011)=3³+7=34), f(1111)=15³+7=3382). Compute the average fitness of the following schemata, assuming all strings are present in the population:

1. 1***
2. 0***
3. 1111
4. ****
5. 00*0
6. 11*1

Question 3. Implement a genetic algorithm (GA) with fitness-proportionate selection, roulette-wheel sampling, population size 100, single-point crossover rate p_c=0.7, and bitwise mutation rate p_m=0.001. The goal is to maximize the function x*|tan(x)| in the range [0,256] radians. Define (and describe) genome representation. Run the GA five times for 1000 generations and plot the fitness of the best individual found at each generation as well as the average fitness of the population at each generation. Submit your program and plots for each experiment.

Question 4. Describe three ways a genetic algorithm can be made to run faster.

Question 5. A GA for the 0/1 Knapsack Problem.

Description. A thief has a knapsack of a certain capacity. He looks around and sees different items of different weights and values. He would like the items he chooses for his knapsack to have the greatest value possible yet still fit in his knapsack. The problem is called the 0-1 Knapsack Problem because the thief can either take (1) or leave (0) each item.

Formal Description. Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible.

The 0/1 knapsack problem restricts the number of each items to zero or one.

Formulation:

Maximize sum(x(i)*p(i))

Subject to sum(x(i)*w(i)) <= C

x(i) = 0 or 1, p(i) is the profit or item value, w(i) is the weight

The maximal capacity of the knapsack is 625. You are to solve this problem with a genetic algorithm.

The genome is a bitstring of size 50, where 1 indicates presence of item and 0 absence.

Run the GA for 500 generations and plot the fitness of the best individual found at each generation as well as the average fitness of the population at each generation. Repeat the experiment five times with the following parameters:

1. single-point crossover rate p_c=0.7, and bitwise mutation rate p_m=0.001.
2. p_c=0.4, p_m=0.001
3. p_c=0.1, p_m=0.001
4. p_c=0.7, p_m=0.01
5. p_c=0.7, p_m=0.1.

Submit: your program, plots for each experiment, and an answer to the question: What are your conclusions from these experiments?

How close can you get to 625?

The list of items is given below as (item no, item value, item weight):

0,47,23,
1,21,3,
2,20,2,
3,34,6,
4,23,22,
5,22,43,
6,24,4,
7,2,24,
8,32,13,
9,9,10,
10,10,43,
11,6,6
12,21,22,
13,22,35,
14,11,42,
15,12,13
16,18,7,
17,12,31 
18,5,7,
19,41,23,
20,22,18,
21,32,5,
22,21,32,
23,28,13,
24,0,32,
25,25,11,
26,23,29,
27,5,3,
28,12,32,
29,41,16,
30,28,11,
31,41,47,
32,21,9,
33,32,29,
34,18,26,
35,14,42,
36,46,42,
37,2,15,
38,31,30,
39,31,34,
40,15,5,
41,48,44,
42,39,3,
43,4,0,
44,30,45,
45,23,20,
46,16,23,
47,17,40,
48,31,5,
49,19,39,