Adapting my existing GA code to a radically different problem provided me an excellent opportunity to ensure its robustness and flexibility. The problem was the classical traveling salesperson problem, in which one must determine the shortest length hamiltonian tour through a connected graph. It is symmetrical because it is assumed that it is of equivalent cost to go from a to b and b to a.
Encoding is done by mapping each piece of the chromosome into a possible destination. A simple walk along the nodes suggested, including the wrap around gives a full tour, as long as nodes are only specified once.
Selection is standard roulette wheel selection. It is optimized for speed through a binary search but is otherwise unremarkable.
I am using standard partially mapped crossover (PMX) which in simplest analogy is the process determining a piece of the chromosome to cross and instead of actually crossing it (which produces duplicated alleles and invalid tours) perform the appropriate swaps within the chromosome to match up that section. This is well documented and rather intuitive. This is optimized in my code by ways of a using a buffered index to replace linear searching.
I used two independent mutation operators, running on different probability. See the results section for graphs.
1) Exchange - Simply taking a pair of cities and swapping them. This failed to produce effective results beyond the first few generations, which led to attempts at improvement through the other mutation operator.
2) Displacement - Instead of simply swapping locations I experimented with shifting a location. This proved to be significantly more effective and led to better results. In fact by replacing the original entirely with this the best results where obtained.
The combination of local search heuristics and genetic algorithms has been shown to be an effective approach for finding near-optimum solutions to tsp. Discouraged by then ineffective mutation I added an operator where by the chromosome takes a set of 3 sequential locations and sorts them into there most efficient arrangement. This had very discouraging results, although it speeded initial improvement and helped improve the average member of the population it entirely destroyed diversity and almost never improved the best individuals. Also the processing cost of doing the local exploration was considerable, adding to the time taken by the ga by 30-40%. Traditionally used local search operators (which are all well documented)
The GA's average performance on a problem is determined by its ability to get within some percentage of the optimum answer. Some of the useful accuracies are as below. These are all for the eil76 problem over 50 runs.
Quality is a percentage over the optimal solution.
Reliability is the chances of any given run producing a best individual better then that quality.
Speed is the mean number of evaluations to produce that individual.
The optimum on this problem is 538.
100-> The ga never achieved the true optimum, but its a ga.
Quality = 90 -> The 90% mark is 598. This is very high precision, and its usually not reached
Quality = 80% -> The mark is 672. This a nice reasonable number so the speeds are much improved.
This problem is easily solved by my ga, it has no problems quickly converging on good solutions. On 50 out of 50 runs it found the solution for the 80%. 90% is still too high and gives problem.
Quality = 89% - > The mark is 480.
This is 89 versus 90% because there are a large number of optimums near the 90% (474). The ga often settles in the 474-480 range so I extended it.
Quality = 80% -> The mark is 533
The 80% quality belies the best strength of this algorithm, it can very quickly find answers reasonably close to the optimum, 453,000 evals is about 10 seconds, which is more then enough for doing real time decision support. For say perhaps some ticket seller planning the best route of travel for an impatient traveling salesperson.
There are two interesting results to ask about, the GA's ability to efficiently produce good results, and the GA's ability to produce excellent results over an extended search. I will answer each one in turn. Also the effect of the various operators is interesting so I will compare and contrast them. Unless that particular operator is being examined all of this data was collected with the following parameters. The major results are tested on the standard problems eil51, eil76, and lin318. This provides a nice blend of an easy, moderate and difficult problem for the ga to solve.
Population = 50
Displacement Prob (per bit) = .005
Exchange Prob = 0
One elitist per Gen.
Fitness are linearly mapped from 1 -> 4
No memetic Step
No random insertions.
The GA's ability to continue to progress, even past 500,000 generations shows that it has enough generality to continue to find better solutions to this huge problem. The optimum is known to be 42029, and this ga is still at twice that, but it continues to make steady progress. It is 86% over the optimum when it finishes there.
This is a comparably small problem, and the ga quickly comes to a good answer (500ish versus 425 Optimum). This is within 10% of the optimum.
This is the standard problem, under standard conditions over 50 runs. The max solidly approaches wherever point it converges too. Convergence usually occurs around 20,000 generations on a major local optimum. This is equivelent to the 20% quality shown above.
The mutation graphs shows a small advantage towards using displacement mutation.
The memetic comparison shows a strong favor towards not using the local search. In all situations the GA without the local search is performing better.