At first you might think that all you have to do is apply random changes to the more successful solutions to evolve a solution close to the optimum. You might also be forgiven for assuming that lots of changes would bring you quickly to that solution. The problem is that gross changes simply result in the creation of new solutions that are effectively random themselves and the chances of hitting on the best solution using random selection are very low – as any Lotto player will tell you.

Remarkably similar eyes have been independently evolved by different animal groups in the history of this planet. An eye is quite a complex object and it is just about impossible to believe that one could be evolved through a single random mutation – no, eyes were evolved set by step. Each evolutionary step along the way making small but significant improvements to the organ that eventually became an eye.

We have therefore to apply a sequence of changes to the routes that allow beneficial changes to be capitalised upon and those that do not help us achieve our goals to be eliminated.

Several different mutations designed to help solve the Traveling salesman problem (among others) have been devised – some however look like their designers have been “stacking the cards” and applying a heuristic which rather defeats the object of this particular exercise. Nothing against heuristics as they can provide added dimensions to the artificial “niche” that we want our software to inhabit but in this instance we are just exploring the potentials. The Adit Traveling Salesman simulation allowed us to apply and test a selection of mutations that were “blind” to the problem.

So let’s define our mutations in two sections. Genetic Algorithms that are based upon combinations of two parents and Evolutionary algorithms that are mutations of a single parent. When genetic algorithms are applied to a population they have the tendency to reduce the overall variation within that population – the solution to this being to either apply such algorithms sparingly or to use very large populations.

We tried the following Evolutionary algorithms in our Traveling Salesman experiments:

Random swap

A simple swap of two randomly selected cities.

Sequence Reverse

Two random points in the sequence are selected and the sequence of cities between the points is reversed.

Position Change

The position of a single randomly selected city is changed to another random point in the sequence without otherwise changing the sequence

Sequence Position Change

The position of a randomly selected sub section of the sequence is moved to another randomly selected point.

Sequence Randomisation

The sequence of cities between two randomly selected points in the overall sequence is effectively randomised.

We tried two Genetic Mutations:

Sequence Crossover

This involved selecting random points in both parents and then completing the sequence from those points using the sequence from the other parent – avoiding duplicates.

Point Crossover

This was similar to the above but a single point was selected from which the cross-over was performed.

See our section on generating random integers on our Random Number page.

[ Home] [About Us] [Systems] [Software Review]