Tilted Forum Project Discussion Community - View Single Post

gregor · 11-22-2006, 01:35 AM

I believe in evolution. The only way for me to believe in God is if I can believe that God created the natural evolution. This, of course, is not completely obvious.

I would like to use this thread to explain the reasons for my belief and hopefully discuss the issues with other debaters. I have a website on this, but I prefer stepwise advances starting with 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, (i. 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 below 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 below 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 below.

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.

So, why should God hesitate to use random search?

11-22-2006, 01:35 AM	#1 (permalink)
gregor Upright Location: Sweden, Stockholm	Did God create evolution? I believe in evolution. The only way for me to believe in God is if I can believe that God created the natural evolution. This, of course, is not completely obvious. I would like to use this thread to explain the reasons for my belief and hopefully discuss the issues with other debaters. I have a website on this, but I prefer stepwise advances starting with 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 605958...43 (about 10 raised to 80, 10^80, (i. 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 below 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/(6060) 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 below 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 below. 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. So, why should God hesitate to use random search? Last edited by gregor; 12-31-2006 at 02:32 AM..