Gentior: A Genetic Traveling Salesman Solution

The Traveling Salesman Problem (TSP) is one of the most famous NP-Complete problems. If somehow you have not heard of it, the general idea is this: Given a number of points on some coordinate system, is there a Hamiltonian cycle of length n? Though it has evolved now to asking for the smallest n, rather than a given n.

The Gentior algorithm is specified in a 1990 paper by D’Ann Fuquay and Darrell Whitley, Genetic Algorithm Solutions for the Traveling Salesman Problem. The paper covers several modern (for the time) approaches to the TSP, and then proposes a new method of creating children that has pretty promising results. I’m not familiar with the state of the art genetic algorithm techniques or TSP solutions, so I can’t say if this is the gold standard today. Instead, this project was done with the aim of learning about the TSP, genetic algorithms, and to play around and explore the results.

Genetic Algorithms

This is my first experience with genetic algorithms and Go has proven to be a pretty good tool for the job so far. For those of you who, like me, have had little-to-no experience with genetic algorithms, they work something like this:

  1. You start by randomly generating a number of solutions to your problem. Store these solutions in a sorted “population” with a fixed size.
  2. Using some method, you select who “parent” solutions.
  3. With two parents selected, combine them through some method to create a third solution called a “child”.
  4. With some probabililty the child can mutate, introducing new search space into the population.
  5. Add the child back into the population. Since the population is sorted and maintains a fixed size, the worst solution is automatically evicted. Ideally the evicted solution is not the new child.
  6. Repeat steps 2 - 4 some number of generations.
  7. Chose the first sample from the population as the final solution. Since the list is sorted this will be a best solution.

Parameters such as parent selection, parent combining, population size, and number of generations can have a significant on the performance of the algorithm. These parameters balance the algorithm’s ability to maintain a large search space, and converge in a timely fashion. Too small the population, the search space is small and you converge very quickly. Too large and your search space failt to converge in a sane number of generations. Similarly if your parent selection algorithm is too biased, if the likelyhood of choosing a better parent is too high, your converge on a solution quickly. Fast convergance could miss out on a very good edge that occurs in a poor solution, so it is important to find some balance convergance and runtime.

Gentior and the Edge Recombination Operator

Gentior offers a method for child creation that outperforms previous heuristics and rivals algorithms for solutions to the TSP. The Edge Recombination Operator works as follows:

  1. Having selected two parents, construct an edge list of the vertices. The edge list for a vertex is the vertices that appear adjecent to that vertex in either of the parent tours.

    For example, if p1 = (6, 2, 2, 3, 4, 5) and p2 = (1, 2, 3, 5, 6, 4) then the edge list would look like

    1. 6 2 4
    2. 1 3
    3. 2 4 5
    4. 6 1 3 5
    5. 6 3 4
    6. 1 4 5
  2. With the dge list constructed we select one of the parents at random. Chose this parent’s first vertex as the child’s start vertex.

  3. To determine the next vertex, use the edge list. With vertex i, we examine edgelist[i]. The next vertex in our path is some j in edgelist[i], where j has the smallest edge list edgelist[j] of any entry in edgelist[i].

  4. The newly chosen vertex becomes the current vertex, and stepts 3 - 4 are repeated N - 1 times.

Results

Writing this in Golang, I was able to heavily use concurrency in this solution and the result was quite good. Running the program on the 48 mainland U.S. capitals, it produced results competitive with the known optimal solution (pictured).

I ended up running the program against many differnent datasets (some randomly generated) with varring population sizes and generations. Those datasets and results can be found in /data/ in the project repository. I hope to one day explore the results data to gain some insight into population size and generational convergance, but things take time.

Further Research Ideas

  • Genetically select parent selection methods
  • Genetically select bais methods
  • Congregate data into one place
  • Further research into parallelism of the algorithm
  • Research into a distributed version of the algorithm

If you have any thoughts, questions, or suggestions, please feel free to email me at andrew.thorp.dev@gmail.com