Changes

No, by no means, evolution may be of great help to him; at least if it could be simulated on his computer. The natural evolution uses an [[inversion operator]], which - in principle - is taylored for finding good solutions to the problem. A part of the card deck - chosen at random - is taken out, turned in opposite direction and put back in the deck again like in the figure below with 6 towns. The hometown (nr 1) is not counted.

No, by no means, evolution may be of great help to him; at least if it could be simulated on his computer. The natural evolution uses an [[inversion operator]], which - in principle - is taylored for finding good solutions to the problem. A part of the card deck - chosen at random - is taken out, turned in opposite direction and put back in the deck again like in the figure below with 6 towns. The hometown (nr 1) is not counted.

web.telia.com/~u91131915/resor7.GIF

http://web.telia.com/~u91131915/resor7.GIF

If this inversion takes place where the tour happens to have a loop, then the loop is opened and the salesman is guaranteed a shorter tour. The probability that this will happen is greater than 1/(60*60) for any loop if we have 60 towns, so, in a population with one million card decks it might happen 1000000/3600 = 277 times that a loop will disappear.

If this inversion takes place where the tour happens to have a loop, then the loop is opened and the salesman is guaranteed a shorter tour. The probability that this will happen is greater than 1/(60*60) for any loop if we have 60 towns, so, in a population with one million card decks it might happen 1000000/3600 = 277 times that a loop will disappear.

This has been simulated with a population of 180 card decks, from which 60 decks are selected in every generation (using MATLAB, the language of technical computing). The figure below shows a random tour at start

This has been simulated with a population of 180 card decks, from which 60 decks are selected in every generation (using MATLAB, the language of technical computing). The figure below shows a random tour at start

web.telia.com/~u91131915/resastart60.GIF

http://web.telia.com/~u91131915/resastart60.GIF

After about 1500 generations a tour with no loops has been found and the length of the random tour at start has been reduced to 1/5 of the original tour. The human eye can see that some improvements can be made, but probably the random search has found a tour, which is not much longer than the shortest possible. See figure below.

After about 1500 generations a tour with no loops has been found and the length of the random tour at start has been reduced to 1/5 of the original tour. The human eye can see that some improvements can be made, but probably the random search has found a tour, which is not much longer than the shortest possible. See figure below.

web.telia.com/~u91131915/resa250.GIF

http://web.telia.com/~u91131915/resa250.GIF

In a special case when all towns are equidistantly placed along a circle, the optimal solution is found when all loops have been removed. This means that this simple random search is able to find one optimal tour out of as many as 10^80. This random process is also similar to evolution in the sense that it uses random variation and selection in cyclic repetition. This also means that the cyclic repetition of random variation and selection of individuals is a very important principle for creating a huge amount of [[information]]. See Goldberg, 1989.

In a special case when all towns are equidistantly placed along a circle, the optimal solution is found when all loops have been removed. This means that this simple random search is able to find one optimal tour out of as many as 10^80. This random process is also similar to evolution in the sense that it uses random variation and selection in cyclic repetition. This also means that the cyclic repetition of random variation and selection of individuals is a very important principle for creating a huge amount of [[information]]. See Goldberg, 1989.