The distrust of randomness

One ordinary obstacle for using evolution as an outlook on life seems to be the distrust of randomness. It is hard to believe that evolution as a random search process can be of any good. A common view seems to be that it is hopelessly inefficient and unable to create the order and information apparent in the biological sphere. In fact, the main result of randomness is disorder in agreement with a well known law of nature; the second law of thermodynamics (entropy law).

For a start, let us look at the efficient solution of a difficult combinatory problem by simple random search using the evolutionary principles of random variation and selection in cyclic repetition ; the traveling salesman problem. See also Goldberg, 1989, in references.
The traveling salesman problem

The salesman should visit a number of towns, one at a time, and wants to know in what order they should be visited in order to make the tour as short as possible. Suppose that the number of towns is = 60. For a random search process, this is like having a deck of cards numbered 1, 2, 3, ... 59, 60 where the number of permutations is of the same order of magnitude as the total number of atoms in the universe. If the hometown is not counted the number of possible tours becomes 60*59*58*...*4*3 (about 10 raised to 80, 10^80, 1. e. a 1 followed by 80 zeros).

Suppose that the salesman does not have a map showing the location of the towns, but only a deck of numbered cards, which he may permute, put in a card reader - like in the childhood of computers - and let the computer calculate the length of the tour. The probability to find the shortest tour by random permutation is about one in 10^80 so, it will never happen. So, should he give up?

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 extremely well suited 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 to the left with 6 towns. The hometown (nr 1) is not counted.




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.






I have simulated this 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 to the left shows a random tour at start.


After about 1500 generations all loops have been removed 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 to the left.



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. So generally, there is no reason to distrust random developmental processes.

The given example shows how random search can solve a combinatorial problem efficiently.