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

Exercise 2

Question 1: Traveling Salesman Problem (TSP)

Select a representation method, a crossover operator, and a mutation operator from those studied in class (for the TSP problem), OR AN ORIGINAL IDEA OF YOUR OWN. State the operators you use (or describe them if they're new ones). Apply the GA to finding the minimal tour of the following 28 cities in France, starting (and ending) in Paris. Use the distances UNDER the diagonal (kilometers).

Run your algorithm 10 times for 1000 generations. If you get the exact same results each time -- use a different random seed.
Submit: A plot with the best three runs (i.e., three curves of best fitness versus time + three curves of average fitness versus time), and the best tour you found (an ordered list of the 28 cities, along with the tour length).

Run your algorithm a few times for 5000 generations and with a larger population. Is there any difference?

What is your BEST result, i.e., shortest tour?

2-point bonus for those who find the shortest route.

Question 2: Solving Sudoku Puzzles using a GA

In a Sudoku mini puzzle you have to complete the grid so that every row, column, and 2x2 (or 2x3) box contains every digit from 1 to 4 (or 1 to 6).

A simple genome encoding is as follows: A row-ordered list of the empty cells in the grid, with each cell having possible values in the range 1..4 (or 1..6). For example, in the first (top-left) 2x2 puzzle below the genome will contain 10 values, the first 3 for the first row, then 2 for the second row, then 2 for the third row, and then 3 for the fourth row.

Fitness value: For each cell count the number of penalties, where a penalty point is given if there is an identical value in the same row, column, or box. Thus, each cell can accumulate up to 3 penalty points, and the worst score is 48 for the 2x2 puzzles (3 X 16) and 108 (3 X 36) for the 6x6 puzzles. The objective is to minimize fitness to zero.

The other paramters (selection, crossover, mutation) -- decide on your own.

As usual, besides solutions, submit plots of runs and some discussion of results.

4-point bonus: Define (and use) a different genome encoding (and possibly fitness, crossover, and mutation). Are the results obtained better than those of the above genome?
1-point bonus: What is a schema in your newly defined genome?
3-point bonus: Solve a few 3x3 puzzles.

Here are the 6 puzzles to solve:

Question 3: A GA for the Bin Packing Problem

Bin packing is one of the classic problems in optimization. Suppose you have a truck that can carry any number of boxes, so long as their total weight is no greater than W. In a warehouse, you have an unlimited supply of items of different types. Each type of item i has a weight w_i and a value v_i. Your problem is to determine what combination of objects gives the highest value, without exceeding the maximum allowed weight. For example, if the weights and values of the items are:

then a truck capable of carrying a total weight W=200 might carry:

Clearly, the best strategy here is to carry as many boxes of oranges as possible, and fill any remaining space with books. In more complicated problems, however, the number of items of each type to carry may be much harder to determine.

In this exercise you are to solve instances of the bin packing problem, with total weight W=500 and the parameters given below. You must design a genome. Provide a clear description of it.

Note: As opposed to the knapsack problem of ex. 1, here items can appear multiple times.

Run the GA for 500 generations (or more if needed) 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?

Test your GA on the following four parameter files (weight,value):

Notes:

1. The total number of runs is 20: 5 parameter settings  x  4 files per setting.
2. Your report should include a comparison of the different parameter settings.

Question 4: Programming a Simple Robot with a GA

Consider the following maze:

A robot entering the maze needs to navigate it until it comes out at the exit.

Let's assume the robot can execute at each time step one of four actions:

• Move Forward 1 box
• Move Backward 1 box
• Move Left 1 box
• Move Right 1 box

You need to design your GA: fitness function, genome, selection, crossover, mutation. Then run it several times and see how well you program the robot.

The fitness function should provide a measure of the efficiency of a particular sequence of actions, e.g., number of steps required to navigate the maze, perhaps a penalty for navigating into a wall, etc'. The genome should define a sequence of the above four actions.

Submit a report including your results, a discussion, and an illustration of the optimal evolved path.

Remark by Yonatan: This exercise brings into mind an article about lemmings.