Evolutionary Algorithms Class,
Final Project:
Using
Genetic Programming
to solve
The Traveling Salesperson Problem
~ Paul A Hansen ~
Throughout this class, I have been using Genetic Programming (GP) to solve assignments, with varying success. The main obstacle to using GP on these assignments is that the problems are geared towards fixed answers rather than more general processes. For example, when working on the Traveling Salesperson Problem (TSP) assignment, the goal is to find the optimal (lowest cost) path that visits each city exactly once.
When working on TSP, GP individuals were able to come very close to the solution (usually within five percent), but could not reach it. However, working with GP there are more options: instead of producing a fixed answer specific to a single problem, the final product is actually a problem-solving computer program. This project tests how well GP individuals trained on a variety of TSP problems perform when tested on the four TSP problems given to the class.
For those familiar with Evolutionary Algorithms (EAs), or with Genetic Algorithms (GAs) in particular, here is a brief overview.
Genetic Programming (GP) is a subset of the general EA paradigm. Like all EAs, GP maintains a population of individuals that are tested against an environment to determine their average fitness. Once tested, individuals are selected from the population based on fitness and modified using recombination to produce new individuals for the next generation. New individuals can also by modified by mutation and other operators after they are created.
What sets GP apart from the rest of the EA community is the use of computer programs as individuals, rather than bit strings or numeric vectors as are common for GAs. Individuals are tested by running the program and analyzing the output. Recombination and mutation happen at the level of the program: swapping execution trees, changing methods, etc.
The GP implementation used for this project was a prototype of a new GP engine being written in C#. The implementation is a bit simplified as compared with others, since methods are limited to returning either void or bool and cannot take any arguments. Because of this restriction, the only structural statements available are if(), if(!) (negating the if condition), and if()..else.
All individuals are derived from a single base class written for the problem being tested (in this case, TSP), which contains implementations for all of the actions (void methods that perform some action) and perceptions (bool methods that check on the individual's or environment's state; used in condition (if) statements) available to the individuals. Individuals are created by overwriting the base's Execute method with whatever combination of actions and perceptions the individual has evolved. During testing, the Execute method is looped until a solution is found or the loop limit is passed. The initial population is made up of individuals randomly generated from the available methods.
The individuals for the TSP problem contained three internal variables: a list of cities that had not yet been visited; an array of cities, initially empty, containing the path produced by the individual; and a position pointing to one of the unvisited cities (this value was initialized to a random position once, with all individuals using the same random position). Individuals had the following action (A) and perception (P) methods available:
Initially, the RandomJump was available only in the first few tests and was intended as a comparison against the later deterministic individuals. However, due to the superior performance of the RandomJump individuals, the method was returned.
For comparison, two manually coded individuals were created — Random and Greedy — which have been reproduced below. (TSPChooser is the name of the individual base class used for the TSP problems which contained the methods and variables described above.)
public class Greedy : TSPChooser {
public override void Execute() {
while( RunIncomplete() ) {
MoveToCheapest();
Choose();
}
}
}
public class Random : TSPChooser {
public override void Execute() {
while( RunIncomplete() ) {
Choose();
RandomJump();
}
}
}
The unvisited city positions for these two classes were initialized to the first city in the unchosen cities list and their Execute methods were called, building a path with the initialized position as the first city. This was repeated for each position, creating paths starting from each city. The cheapest paths found during this process were used for comparison with the GP individuals.
Four TSP problems given in class were used for the training and testing of individuals. These problems had (a) 29, (b) 58, (c) 120, and (d) 561 cities, respectively (click here to download the cost matrices used, including an explanation of the file format). 19 separate runs were made, training individuals using all combinations of the four problems (including four extra runs for those individuals without RandomJump, as indicated by “1x (no rand)” in the run labels).
In the results that follow, runs were named by the number of problems the individuals were trained on and which problems. For example, run 2ac was trained with two TSP problems: a = 29 city problem, and c = 120 city problem.
Each set was run for 500 generations (0 to 499). Population started at 1600 and was reduced by 10% each generation until the population reached 400. This was done to decrease run time, since earlier runs had shown that reducing population had little effect on the outcome (possibly due to the gradual decrease in diversity of individuals as the EA concentrates on greater-fitness individuals). If no improvement in fitness was made for 25 consecutive generations, the population was reset to 1600 with random individuals. Fitness was measured by averaging the individual's performance over all of the training set problems.
Once all 500 generations had been tested, the best individual produced out of all 500 generations was recompiled and tested against each of the four TSP problems. 100 tests were made for each environment, each initialized with a different random number and position, and the best score was recorded.
Unfortunately, due to time constraints only one run was made for each training set, instead of averaging results over a series of runs.
Click here to view the results and my wild speculation on their meaning.
Click here to view an example evolved program.