Some Attempts at solving the traveling salesman problem with AI Search
Having looked at the possible ways of solving the travelling salesmen problem it was my intention to use implementations that use simulated annealing and Genetic Algorithms, as they appeared to be the best options looking at the problem from varying levels of intelligent choice.
>Initial Work on simulated annealing
In my work on simulated annealing I initially experimented with variation of the thread / Crystal count and the maximum temperature of the second annealing. From this I found that using a large amount of threads produced better results, though when looked at, all this is throwing more and more attempts at problem until a better solution is found, which though we must admit works, and will require an exponential increase in computing power in relation to results.
When adjusting the maximum temperature of the second annealing I found that higher temperatures made small consistent positive difference to fitness of tours.
>Initial Work on Genetics
My initial work on Genetics suffered problems in that my solutions would plateau far above an optimal solutions. In an effort to solve this I tried to give it a ‘head start’ by constructing tours Intelligently before feeding them into the population , this worked exceptionally well as it could produce an optimal or close to optimal tour (around 49k for file 535)about in ~0.06 seconds. However this then caused significant problems in genetics as in an attempt to diversify the population it destroy the patterns within these close to optimal tours and within 20 generations or so would return to level of the original plateau. This was solved by creating a more intelligent mutation and breeding algorithms designed for maximum pattern preservation within the tour, and convergence on a local optima.
My new mutation algorithm works by attempting to break the pairs of cities with the greatest distances between them. So the pair with longest distance AB and second longest distance XY swapped iff AVG(D(AY),D(YC),D(XB),D(BZ))<AVG(D(AB),D(BC),D(XY),D(YZ))
D(AB)=Distance between A and B
If my algorithm cannot find a pair AB XY to swap such the above condition is satisfied then will attempt a number of random order reversals of sub tours within the tour, and pick the fittest of these to return to the population, but not affect the tour designated to be mutated.
My new breeding algorithm in an attempts to preserve patterns by taking a length(35-50%) of the tour from each parent and comparing the fitness of each subsection, and adding the fittest sub section to a child repeating this until we have a child which has a complete tour, It produces around 20 children like this and returns the fittest of them to the population
>Final Simulated Annealing Algorithm
My final Simulated Annealing begins by constructing semi-optimal tours then passing them to Crystals/Threads. It runs with 10 concurrent threads, updating to a synchronized HashMap located in the Annealer Class which always them to dynamically update how fit they are relative to other thread this is then passed to annealing schedule with from a produces from this input and on the current stage of the annealing schedule a temperature.
Based on this temperature a crystal with ether adds a city to the tour, remove a city from the tour, reorder the parts of the city or do nothing
>Final Genetics Algorithm
My final genetics algorithm constructs 10,000 possible tours as this only take about 6 minutes and takes the best pre constructed tour as the base of its population. It then forms a population of clones of this tour each with different mutation to provide local genetic diversity as soon as possible.
The Population is run though a number of peaks controlled by a growth factor, so that the population should vary though the peak as a bell curve
Each peak it made out of cycles where each cycle is composed of in order Deaths, Mutations, and Breeding at
After all the cycles have finished the population is quick sorted and the tour with the highest fitness is output.
In comparing the two it is clear from the results that the genetics produces better results.
However getting the best results may not be the only criteria on which base evaluation, as for example the simulated annealing ran in ~ 15 minutes on file535 much less than the ~1hour and 25 minutes required for the genetics to run. In commercial applications of software computer time is expensive and time is valuable so quick and cheap, less than perfect results often more valuable than slow, expensive and close to perfect/perfect results. Route planners are a good example of this being close to the Traveling salesman in nature. Many commercial pieces of software produce less than optimal routes as can been seen by sometimes making small Intelligent adjustments as the user and producing a shorter/ more optimal solutions. However they run fast, you do not want to sit around all day waiting for a solution that can save you an extra 2 miles, getting it right now and also close optimal is ‘good enough’. It can be also argued that the non-deterministic nature of these algorithms makes optimizing their running times more important as its gives them a greater degree of reliability.
>>Intelligent vs. Non-Intelligent
For the purposive of the following I will define an algorithm as Intelligent if it makes its actions based, at least partially on a value (A fitness function) of a set of data.
In their pure form and by my definition, Simulated Annealing is Non-Intelligent as it makes random realignments, and genetics performs all actions based on the preserved fitness of a solution.
Fitness allows in many ways allows better decisions to be made about the next action to be made on a set of data including weather to perform an action or if to reverse a previous action made. However this also comes with several problems the first and most obvious of these is the cost of calculating the fitness in the genetics used here the FitnessFactor Function is O(n2) which means for file535 a cost of around 148k calculations per call . This can be solve to some degree with estimated fitness functions of reduced complexity, or by storing the fitness and only updating it when the data is changed, but with these you may not get as accurate results. The second main problem is convergence towards local optima i.e as fitness is always relative so if a set of data starts to converge towards to fitness the algorithm maybe be unable to move it towards a more global optima, as it designed such that it does not allow actions which have a negative effect upon that data’s fitness but may prove important to a global optima.
In respect of my algorithms introducing a small amount of decision making into my Simulated annealing in the form of its re-order parts function which mimicked that of my genetic algorithms mutate function, allowed for large improvement in results.
Drawing from this it would seem that an algorithms resource consumption vs results rely heavily on the amount in which it is called to make intelligent decisions, the more complex the decision making functions the more resources are required but the more likely you are to make a possible step towards a optimal solution.
It would also appear that that making positive decisions is more important in large the sets of data, as the number of solutions increases factorially with size, but for most problems there is only one or a few optimal solutions, so for larger and larger sets of data it become less and less likely that an algorithm will stumble upon the correct solution or ‘path’ to it.
Thus in conclusion I would be my believe that simulated Annealing is a the most useful tool if the search space or available resources are small, but genetics will fare better with large state spaces, were resources are not at a premium.
Software Applications AI Search Assignment by Gwilym Newton is licensed under a Creative Commons Attribution-Share Alike 2.0 UK: England & Wales License.
Based on a work at personal.vacau.com.