Genetic Algorithm Assignment

Due February 18th, 1999 at 4:00 PM

Objective:

You and your team (of up to 4) are to implement a Genetic Algorithm to solve certain problems from the traveling salesperson domain. You will examine and report on the effects of varying different parameters and changing the mechanims of crossover. As before, you are allowed to use the programming language of your choice to solve this problem.

Introduction:

The traveling salesperson problem is stated as:

A salesperson must take a trip to each of a set of N cities. Not enjoying traveling, the salesperson wishes to visit each city only once and minimize the total distance that is travelled. In the most general version and the version we shall use, travel can occur between any two cities and the distance between any two cities is symmetric. The salesperson should finish in the same city that was started from intially.

I have provided 5 different data files to work with for this problem which are formatted as follows.

Each data file begins with an integer (N) stating the number of cities in the problem
Next, N city names are listed
On the remaining N lines are a distance matrix reporting the distances from a given city to all other cities in the example

For example, if the first line of distances reads 0 3 5 2, then the distance from city1 to city2 is 3, the distance from city1 to city3 is 5 and so on.

Here are the data files you will use. (You should feel free to construct simpler examples for testing of your code).

You will create 4 different algorithms by which to solve this problem.

Greedy Search

Pick a random start city as the current city
repeat until all cities have been visited

find the city that is closest to the current city and has not already been added to the tour
add the city to the tour and make it the current city

The remaining 3 are all Genetic Algorithms varying only in the type of crossover performed. I will first describe the general GA that I wish you to implement and then I will describe each of the three variations.

Genetic Algorithm

Your GA should contain the following 4 parameters

crate - crossover rate, a floating point number between 0 and 1
mrate - mutation rate, a floating point number between 0 and 1
popSize - population size, an integer between 1 and 500
gens - numbers of generations, an integer

Use an ordinal representation of your cities (i.e (1 2 3 4 5))
Fitness is defined as the total distance travelled in a tour
Begin with a random initial population of posSize
During each generation

repeat until (crate*popSize) children are created

Using a simple selection mechanism (described below) select 2 parents for crossover
crossover the parents

select individuals from the old population until the new population is filled
for each of the individuals in the new population mutate it with probability mrate

mutation will simply be the swapping of two randomly selected cities within a tour

Continue the process for gens generations
The select mechanism should be as follows

Find the largest tour length in the population and call it max
Reassess each fitness as newFitness = max - oldFitness
Sum all the newFitness values and call this totalFitness
Divide each newFitness by totalFitness to get its probability of selection
Assign a segment from 0 to 1 to each probability and pick a random number to choose each individual you need to select (this is just the standard selection method described in class)
Example: If the probabilities are .5 .4 .1 and 0 then (0-.5) would be tour1, (.5-..9) would be tour2, and (.9 - 1) would be tour3. Tour4 would have 0 likelihood of being selected.

Simple CrossOver

Select 2 parents (a mother and a father)
Pick a split point in the mother and create a child left half from the mother, and the right half the remaining cities in the tour kept in the same relative order as in the father (eg. (1 2 3 4 5) and (5 4 2 3 1) with split after the 2nd element yields (1 2 5 4 3) as the new child)
Create a second child from the left half of the father using the same split point

Partially Matched Crossover (PMX)

Select 2 parents
Pick two random split points
These split points define an interior swap zone. For each of these interior points create a new child from the mother by swapping within the mother that value at each of the interior points with the value at the corresponding point in the father.
Create a second child from the father.
Example m = (1 2 3 4 5) f = (4 1 2 3 5), swap1 = 2, swap2 = 3 (inclusive and zero based)

In the mother swap the 3 with the 2, and 4 with the 3
(1 2 3 4 5) = > (1 3 2 4 5) = > (1 4 2 3 5)
In the father, swap the 2 and the 3, and the 2 and the 4
(4 1 2 3 5) = > (4 1 3 2 5) = > (2 1 3 4 5)

Knowledge Based Crossover

Select 2 parents
Pick a random city as the start
repeat until the tour is full

assess the distance from this city to the next city in the mother and in the father
select the next city from the parent that had the smallest next distance
if this city in already in the tour, pick a random city that is not
add the new city to the tour

For each Algorithm you have created do the following

Get baseline fitness values from the greedy algorithm by making 5 tours from random start cities for each data file
Solve each example file 5 times for each GA algorithm and record the average fitness of the best solution from each run
Record average fitness for each of the GA algorithms for each of the following set of parameters listed as (crate, mrate, popSize, gens)

(.8,.2,,50,200)
(.8,.2,100,200)
(.8,.2,200,200)
(.8,.2,300,200)
(.8,.05,200,200)
(.8,.4,200,200)
(.8.6,200,200)
(.8,.8,200,200)
(.4,.2,200,200)
(.2,.2,200,200
(1,.2,200,200)
(0,.2,200,200)

Answer the following questions

Which algorithm consistently performed best? Hypothesize reasons for this behavior.
What were the effects of each of the 3 parameters you modified? Using this knowledge can you come up with a set of parameter values that produces better results for each problem. Why or why not?

Extra Credit: What happens if you start each of the GA's with a random population generated by the greedy algorithm?

Turnin:

Turnin in as normal to a subdirectory called ga in your turnin directory
Place a README file in the directory explaining how to use your program. Make it very easy for someone to modify any of the 4 major parameters.
Turn in the final writeup to me either in class or in my office.