Genetic Algorithm Notes

See the textbook discussion of genetic algorithms for a basic intro. It’s pretty reasonable. In the following notes some techniques specific to solving the Traveling Salesman Problem (TSP) using a genetic algorithm (GA) are given.

The Python file tsp.py contains various helper functions and example algorithms. This is new code, and so has not been thoroughly tested. So please be on the lookout for errors, and share any fixes on Canvas.

Representing a Solution

The goal of the TSP is to find the shortest tour that visits a set of cities in a way that minimizes the sum of the distances between adjacent cities (and also the first and last city). We assume that we know the distance between any two cities, e.g. if we are given the (x, y) location of all the cities then we can calculate the distance between two cities using the regular Euclidean distance function.

A solution to the TSP can be represented as a permutation of city names. For example, suppose an n=4 TSP has 4 cities named 1, 2, 3, and 4. Then the permutation 3,1,2,4 means start at city 3, then go to city 1, then city, and finally stop at city 4. We also include the distance between city 4 and 3, so you can imagine always ending up in the starting city.

For a GA, a permutation representation works well. In what follows, we will refer to solutions as permutations, and we when we talk about the “score” of a permutation, we mean the length of the tour as described above.

In tsp.py, the function total_dist(city_perm, city_locs) returns the total length between all adjacent cities (plus the first and last city). In addition to the permutation of cities, it needs a list of city locations that has the same format as the list returned by load_city_locs(fname). The load_city_locs(fname) function reads a file of TSP names and locations that is formatted like this:

1 9 -2
2 5 8
3 20 20

Each line consists of three integers: the first is the name of the city, and the next two are the (x,y) location of that city.

Random Permutations

As a warm up, lets try solving the TSP by creating many random permutations, keeping track of which one is shortest. This is note a good way to solve the TSP, but it is good practice for learning about the basic data structures, and it also gives us a baseline: if any of your algorithms score worse than random, then you know it’s not very good.

In pseudocode:

Input: n cities named 1, 2, 3, ..., n
   dist, a function that returns the distance between any 2 cities

p <-- random permutation of 1, ... ,n
best <-- p
for some number of iterations do:
   p <-- random permutation of 1, ... ,n
   if score(p) < score(best) then:
       best <-- p
print best

The “number of iterations” is set by you, the programmer. You can set this as high as you like, as long as you are willing to wait for the program to end.

In tsp.py, see the function rand_best for an implementation of this algorithm.

Mutating Permutations

Now lets write an algorithm that uses a population of permutations. By that we mean a list of some number of permutations, and you can think of each permutation as being a member of the population. The size of the population is up to you. Generally, bigger populations are better, but they take longer to process than smaller populations. You should experiment with different population sizes.

The first list of individual permutations is called the first generation, and you can create it by adding randomly generated permutations. After that, the basic idea is to create the next generation by somehow modifying the current generation.

One way to get a member of the next generation is to copy, without change, some members of the current generation. For instance, you might copy (without any modification) the individual with the best score into the next generation. This ensures the best permutation seen so far will be in the current generation.

Instead of copying an individual as-is into the next generation, you could make a mutation of an individual (i.e. change it in some way), and then add the mutated copy to the next generation.

For a TSP permutation, a mutation must change the permutation in a way that keeps it a valid permutation. Individuals must always be a valid permutation of 1 to n (no duplicates, no missing numbers).

With this constraint in mind, a common mutation of a TSP permutation is to swap the positions of two randomly chose cities. This doesn’t add or remove cities, and so it remains a permutation. In pseudocode:

mutate_permutation(p):   # p is a permutation of 1, 2, ..., n
                         # p is assumed to be a list/vector/array

        i <-- randomly chosen index of p
        j <-- randomly chosen index of p
        swap p[i], p[j]

This is surely not the only possible random mutation: you can probably think of other ways to mutate a permutation.

Now we could write a search algorithm as follows. We assume the cities are named 1 to n:

mutate_seach(pop_size):  # pop_size is the number of permutations in a generation

  curr_gen <-- pop_size random permutations
  for some number of iterations do:
      best <-- lowest scoring permutation in curr_gen
      next_gen = [best]   # copy best permutation to next generation
      while len(next_gen) < pop_size do:
          temp <-- copy of best
          mutate_permutation(p)
          next_gen.append(p)
      curr_gen <-- next_gen

This is not necessarily a very good algorithm, but it shows the general structure of a GA. Even in this simple version, there are a number parameters to play with, e.g. the population size, the number of iterations, and how the permutations are mutated (maybe calls to mutate_permutation would be better?).

In tsp.py, see the function rand_best for an implementation of this algorithm.

Crossover: Breeding Permutations

One of the distinctive ideas of GAs is their use of crossover. The idea of crossover is to take two “parent” permutations and somehow combine them up to make two new “offspring” permutations, each contain parts of the parents. This is inspired by how, with animals, the genetic material from the mother and father gets combined into their offspring.

For the TSP, we can’t, for instance, just cut the parent permutations in half, and re-combine the halves to make new permutations. The problem with that is that the offspring might not be valid permutations of 1 to n. So crossover must be careful to ensure the children are valid permutations.

One crossover method (there are others) for permutations is called PMX. It’s a bit tricky to explain in general, but it is clear how it works if you work through an example. The following example comes from this this paper

Suppose the two permutations you want to apply crossover to are s=5713642 and t=4627315. First, we pick a random crossover point (marked by |):

s=571|3642
t=462|7315

Two offspring will be created by the PMX crossover.

The first offspring is created as follows: make a copy of s called s', and write s' above t (t won’t change). Then go through the first 3 cities of s' and swap them (in s') with the city underneath in t:

    swap        swap        swap
    +-----+     +---+       +----+
    |     |     |   |       |    |
s'= 571|3642   471|3652   461|3752   462|3751 (first offspring)
t = 462|7315   462|7315   462|7315   462|7315

So 4627315 is the first offspring.

The second offspring is created similarly, but this time s stays the same and a copy t' of t is made:

s = 571|3642   571|3642   571|3642   571|3642
t'= 462|7315   562|7314   572|6314   571|6324 (second offspring)
    |      |    |  |        |   |
    +------+    +--+        +---+
    swap        swap        swap

Thus 5716324 is the second offspring.

In tsp.py, see the function pmx for an implementation of this.

With PMX crossover in hand, we can now use it, along with mutate_permutation, to create new permutations for the next generation. For example, you would create the next generation of by crossing over pairs of randomly chosen permutations from the best 50% of the current generation.

In tsp.py, the function crossover_search gives an example of a similar algorithm. Again, no claim is being made that this is a good way to search for TSP solutions. Experimentation with different parameters and variations is needed to find out what works best.

Roulette Wheel Selection

Finally, we mention one more idea, called roulette wheel selection, for choosing permutations to go into the next generation. Instead of choosing permutations at random, choose them in a weighted random way, where lower-scoring permutations have a proportionally higher change of being chosen. This tends to copy the best permutations, but not always: sometimes lower-scoring permutations might be chosen, and sometimes they may lead to better results (or at least that’s the hope!).

tsp.py does not contain any code for roulette wheel selection, but it is not hard to create (or find on the web — just make sure to tell us where you found it).

Traditional genetic algorithms combine mutation, crossover, and roulette wheel selection into a single algorithm structured like crossover_search. Determining how best to set the various parameters, and exactly how to combine everything, takes some experimentation.