TSP
The selected representation for this problem was a standard ordinal list representation of length 20. Fitness was calculated in units of km-1 normalized to 100,000/km. Population size was a fixed 100, with k=50 (50 individuals selected for crossover at pc=0.7), and all individuals went through mutation at pm=0.1. The selection method was fitness-proportionate. The xo method that was used was cycle crossover, and the mutation method was swap-two-random-numbers. The simulation was run over 1000 generations for several times, and also a few times over 5000 generations. The simulation platform was asp3 with javascript, and the plotting was done with Chestysoft DrawGraph. To minimize use of RAM during the runs, the fitness results of all individuals at each generation were stored in an ACCESS database table, and queried at the end of the simulation for the plotting of best individual. Here's the code for the simulation. The best recorded individual was a 6852 km tour. It was achieved after about 600 generations. Here are plots of average fitness vs. best individual fitness.
Conclutions: The selected representation (ordinal) does not bring flashing results in solving this problem. Also, the population reached an unwanted stand-still at a certain point, as viewed in the last plot, where the average fitness was unchanged about 2500 generations. The poor results support the claim that this problem is NP-Complete.
Maximizing f(x)=(2x+1)5 at [0,1]
The selected representation for this problem was, as suggested, a bit string of length 8, where bi represents +bi*2-i. Fitness was obviously the value of f(x) where x is the number represented by the bit string. Another aspect that was covered in these experiments was the precentage of individuals belonging to the scheme 110*****. All 3 experiments had a fixed population size of 20, ran for 100 rounds, with pc=0.7, and pm=0.1 for each bit of every individual.Experiment a sported a fitness proportionate method with k=10.
Experiment b sported tournament selection with k=2.
Experiment c sported rank selection with beta=2.
The xo method that was used in all 3 experiments was single-point-crossover, and the mutation method was the common bit-flip. The simulation was run over 100 generations for all 3 experiments. The simulation platform was asp3 with javascript, and the plotting was done with Chestysoft DrawGraph. Here's the code for the simulation. The best recorded individual was, of course, 11111111 with a fitness value of 240. Here are plots comparing 5 consecutive runs of each method, and the plots showing precentage of individuals belonging to the scheme 110***** for each run.
A. Fitness proportionate selection
B. Tournament selection
C. Rank selection
Conclusions: Both fitness proportionate selection and tournament selection produced very good results. In both cases the maximum fitness was achieved after a few generations and soon after "infected" the whole population. The third method, rank solution, produced very "ranc" results for average fitness, as seen in the last two plots. This is actually not very surprising, since the first two methods support eliticism in their capitalistic approache, while rank selection favours a more socialistic selection method, which enables the weaker individuals to survive a little longer. As for the scheme 110*****, the results have nothing to do with it, since this scheme does not contain the best individuals.
Solving a mini Sudoku puzzle
The selected representation for this problem was a linear list of numbers representing the missing numbers from left to right, top to buttom. Fitness was, as suggested, the number of errors in a solution created from an individual, which means the lower the better, 0 being the optimal fitness. The numbers were first randomly selected from [1,MAX] for each individual. The selection method was tournament-selection with k=5. Tournament-selection was chosen for this problem because in the case of minimizing fitness, it's easier to calculate than fitness-proportionate-selection. Population size was a fixed 100. At each generation 50 individuals were selected for crossover, and 50 were selected for reproduction. All selections were unattached (i.e. an individual can be selected more than once). The xo method that was used was single-point-crossover. All selected individuals went through a "number-flip" mutation (i.e. each number in the string was replaced with a new random number at pm=0.3). The simulation was run several times over 50 generations for the 4X4 puzzles, and 1000 generations for the 6X6 puzzles. The simulation platform was asp3 with javascript, and the plotting was done with Chestysoft DrawGraph. To minimize use of RAM during the runs, the fitness results of all individuals at each generation were stored in an ACCESS database table, and queried at the end of the simulation for the plotting of best individual. Here's the code for the simulation. The best recorded individual managed to solve a 6X6 puzzle with 12 errors. It was achieved after about 600 generations. Here are plots of average fitness vs. best individual fitness for each puzzle.
Conclusions: These experiments produced very good results for the small 4X4 puzzles, reaching optimum after only a few generations. However, this representation did not bring the goods for the 6X6 puzzles. The search-domain for a typical 4X4 puzzle in this representation is 412, which is about 1.7*107, appearantly not a very big number for evolution. The search-domain for a typical 6X6 puzzle in this representation is around 623, which is about 8*1017, appearantly too big a number for this experiment.
Back to the drawing board...
I tried a different genome encoding all over again, hopefully one that will reduce the search-domain by far. The idea was to use the right numbers, only not necessarily in the right order. The representation is still the same, and so are all the parameters. The difference was in selecting the random numbers at first, and in the mutation method. All other parameters remained unchanged (including the xo operator). The new mutation was swap-two-numbers. This mutation preserves the desired invariant, which is: "All the right numbers for the optimal solution are present at all times in each individual." The search-domain for a typical 6X6 puzzle in this encoding is around 23!/(6*4!), which is about 3.5*1017, half the naive encoding's search-domain, but still very big. This time the results were a little better. The best individual was 4 errors short of a perfect solution for a 6X6 puzzle.Back again to the drawing board...
I preserved the former improvement, (picking the right numbers, not in the right order), while improving the invariant even more, and altered both the mutation operator and the xo operator. The new invariant states that "All the right numbers for each row in the optimal solution are present at all times in each individual." The new xo operator was "swap-rows" (i.e. one offspring inherits a single board-row selected at random from the first parent, and all the other board-rows from the second parent, while the second offspring takes the opposite rows respectively). Obviously this operator does not spoil the new invariant, because it doesn't change anything within the rows, but rather swaps the rows entirely. The new mutation operator was "permute-row", which randomly selects one board row, and shuffles it once, thus creating a permutation of the row, hopefully a better one than the previous permutation. This operator does change the order of the missing numbers in a certain row, but still preserves the new invariant. The search-domain for a typical 6X6 puzzle in this new encoding is no more than 6!, which is 720. Naturally this new encoding produced much better results, as shown below.
Conclusions: This time the optimal solution for the first 6X6 puzzle (the "difficult" one) was reached after only 6 generations. So I decided to try it out on a 9X9 puzzle, and see how it fairs. The search-domain for a typical 9X9 puzzle in this encoding is no more than
