In this blog post I want to give a brief introduction into genetic algorithms and show how this class of algorithms can be used to find good solutions for the traveling salesman problem (TSP). The presented algorithms are written in Java and can be found in my github repository. In the end, I will shortly evaluate the genetic algorithm approach with an exact solver in terms of computation time and optimality.
Genetic algorithms in a nutshell
Genetic algorithms are approximation algorithms imitating biological evolution to find good solutions for a typically hard to solve problem. The general steps of a genetic algorithm are shown in the following code snippets. The algorithm works on a set of (non-optimal) problem solutions, called population, and tries to find better solutions by intelligently combining the existing ones in a sequence of evolution steps until a termination condition is reached. In a first step, the population is usually initialized with random solutions of the problem. In the repeated evolution step, the next generation is created as follows:1. Selection
Parents for recombination (also called crossover) are selected by a selection procedure mostly based on the fitness of the individuals. The goal of this procedure is to ensure that better solutions are more probably taken for recombination and thereby applying some selection pressure (less fit individuals die out).2. Crossover/Recombination
The previously selected parents are merged into one or more new individuals, the offspring. This procedure highly depends on the chosen representation for the problem’s solutions. The goal is to preserve useful parts from both parents in the resulting offspring.3. Mutation
The resulting offspring is mutated with some probability by randomly modifying small parts. In this way the search space is further explored and the algorithm gets a chance to escape local optimums and find the global one.4. Replacement
The last step replaces the old generation by the newly created one. Typically the best individual(s) in the old generation is preserved in the new one in order to not loose its genetic material (this is called elitism).The evolution process is performed until a termination condition is reached. This can be a fixed number of generations or the observation that the population did not improve during the last generations.
GeneticAlgorithm<T>
ga = new GeneticAlgorithm<T>();
Population<T>
pop = new Population<T>(POP_COUNT);
ga.initialize(pop);
while (!terminate()) {
ga.evolve(pop);
}
T solution = pop.getFittest();
Code Snippet 1. Outer loop of genetic algorithm
public void evolve(Population<T> oldPopulation) {
Population<T>
newPopulation = new Population<T>(oldPopulation.size());
for (int i = 0; i < newPopulation.size(); i++) {
// selection
T
parent1 = getSelection().execute(oldPopulation);
T
parent2 = getSelection().execute(oldPopulation);
// crossover
T
offspring = getCrossOver().execute(parent1, parent2);
// mutation
getMutation().execute(offspring);
newPopulation.setIndividual(i, offspring);
}
//
replacement
oldPopulation =
getReplacement().execute(oldPopulation, newPopulation);
}
Code Snippet 2. Evolution step
A genetic algorithm for solving TSP
Finding a suitable genetic algorithm for the TSP is an active research area which resulted in several proposals for appropriate selection, crossover and mutation operators. In this section I will describe the solution representation and operators I have chosen to find good solutions in a reasonable time.Representation
The solution of a TSP can be represented by an ordered list of unique cities where two subsequent cities (as well as the last and the first one) are meant to be connected by an edge, thus forming a Hamiltonian cycle. This representation is termed path representation and chosen in order to facilitate an efficient implementation of the used operators.Population
The population consists of a number of individuals which represent solutions by using the above mentioned path representation. The population is initialized with completely random cycles.Selection
As selection procedure deterministic Tournament Selection with a tournament size of 3 is chosen. In Tournament Selection a fixed number (here 3) of individuals is selected which then compete against each other in a tournament. In deterministic tournament selection the fittest individual (here the shortest cycle) wins.Crossover
As crossover procedure Sequential Constructive Crossover as proposed in [1] is implemented. The following figure depicts the recombination process.
The SCX operator takes two parents and creates a single offspring by taking edge costs into account. Starting with an initial city, it searches for the next not yet used successor city in the two parents. In the example, a successor for city 7 is asked. In the cycle denoted by parent 1, it is city 4. In parent 2, it is city 5 since city 1 is already used in the created offspring. The city which is nearer to city 7 is then determined as successor in the offspring. This procedure is carried out repeatedly until the offspring is complete. In addition, each created offspring is optimized using the 2-opt search algorithm to further improve the solution.
Mutation
As mutation operator edge inversion is used with a mutation rate of 50%. In edge inversion, two cities are selected randomly and the order of all cities between them is reversed. The rather high mutation rate of 50% is determined by several tests and due to the greediness of the SCX operator and its resulting loss of population diversity.Replacement
As replacement procedure, all individuals are replaced by the newly created ones apart from the best individual, the elite. This procedure is termed Elitism.Termination
In the conducted tests, the algorithm is terminated when it fails to improve the best solution within 30 subsequent generations. Hence, the algorithm runs as long as the solution can be improved within a reasonable time. Increasing the window might yield better results, but only in the detriment of computation time.Comparison with exact solver
To evaluate the quality of the presented genetic algorithm, I compare it with an exact TSP solver using the Held-Karp algorithm as implemented in [2] in two sample scenarios taken from the TSP library provided by the University of Heidelberg.
Benchmark
|
Exact
Solver
|
Genetic
Algorithm
(average
over 10 runs)
|
||
Cycle
Cost
|
Computation
Time
|
Cycle
Cost
|
Computation
Time
|
|
att48
|
33523.71
|
10 sec
|
33546.76 (+0,07%)
|
1 sec
|
kroD100
|
21294.29
|
241 sec
|
21416.59 (+0,57%)
|
13 sec
|
As the results show, for a problem with 100 cities the genetic algorithm finds on average solutions which are 0,57% off the optimum while taking 13 seconds on my machine. The exact solver however needs roughly 4 minutes! Due to the different complexity classes of the algorithms, this difference highly increases with problem size.
Next steps
The described algorithms can be found in my github repository. However, the presented solution can still be improved by using more intelligent operators. One problem is the high greediness of the SCX operator which decreases the population diversity and hence tends to converge in a local optimum only. Using a high mutation rate (here 50%) is only one counter-measurement. Better results may be achieved when using operators that adapt themselves depending on the population's diversity. For example, increasing mutation rates and decreasing selection pressure (by using different selection strategies) when convergence is observed.Feel free to play around with the code. You will find some JUnit tests to trigger the execution of the algorithm under different configurations as well as a simple graphical user interface.
References
[1] Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator, Zakir H. Ahmed, Department of Computer Science, Al-Imam Muhammad Ibn Saud Islamic University, P.O. Box No. 5701, Riyadh-11432, Kingdom of Saudi Arabia.[2] http://stackoverflow.com/questions/7159259/optimized-tsp-algorithms
Keine Kommentare:
Kommentar veröffentlichen