Genetic algorithm

Here are some details of the genetic algorithm used to obtain lower bounds for [math]\displaystyle{ c_n }[/math] and [math]\displaystyle{ c'_n }[/math]. The genetic algorithm was designed and implemented by Kareem Carr. The following text is his account of the thinking behind the design. Futher details can be gained by contacting him directly.

Lookup Table

I created a lookup table for each c_n on which I ran the genetic algorithm. This speeds up checking if a chromosome is line-free tremendously, making this tractable. (Any ideas about efficient ways to do this will have a very large effect on the speed of the algorithm).

Details

For each element, I figured out the two other elements that are needed to make a line. For instance, 123 means that both 122 and 121 can’t be in the set. For each element, I have all possible pairs that would conflict if they were both elements of the set. If I do a simple transformation of 1->0,2->1 and 3->2 then I get numbers in base three which can then of course be representable as numbers in base 10. Thus I can represent each pair that I need to avoid as two numbers. (This is good as integers can be stored easily in a big table.) So that’s how I store them, I number everything from 0 to 3^n-1 and for each element I have a list of pairs that I have to check for. I store all this in an array where the nth row contains each pair in order.

The solutions are represented as binary numbers of length 3^n where if the mth element of [3]^n is a member of the set then the mth binary digit is set to 1 otherwise it is set to zero.

To check if a solution valid, for each position p, I check row p of my lookup table. I check pair by pair looking at the binary digits corresponding to each pair and making sure they aren’t both set to 1.

For example, my look up table for c_2 is the following:

1 2 3 6 4 8
0 2 4 7 -1 -1
0 1 5 8 -1 -1
0 6 4 5 -1 -1
0 8 1 7 3 5
2 8 3 4 -1 -1
0 3 7 8 -1 -1
1 4 6 8 -1 -1
0 4 2 5 6 7

The -1’s mark the end of the list so my program knows when the list of pairs has ended.

Encoding Solutions

Chromosome structure: I code the solutions as a list of ones and zeros of length 3^n. The elements are ordered in this way 1…11, 1…12, 1…13, 1…21 and so on. A 0 in position 1 means element 1…11 is not in the set, otherwise it is.

Making a new generation

Selection: Any solutions below the mean of the population are completely ignored. The rest are selected with a probablity related to their score.

Crossover operator: I pick a random number, m between 2 and (3^n) - 1 and I make a new chromosome with the first m elements of a one chromosome and the last (3^n) - m elements of another chromosome.

Mutation operator: I pick a few points at random and flip them.

I check any new chromosomes to make sure they are valid. I do this by going through the chromosome elements in a random order (visiting each one) and removing points that conflict with other points.

Population size

I use elitism. (I keep the best 5 or sometimes 10 between generations.)

Population size: 60

I make more children than I can use (somewhere between 60-80) making the algorithm somewhat Malthusian. I take the best of the children and use them to replace the rest of the population.

Non-standard addition

An extremely effective trick has been to use a greedy algoritm on the list of all solutions to:

1. pick a small but fixed number of points in each chromosome and flip them if they improve the score.

2. run the greedy algorithm on the whole chromosome, going through all positions in a random order, and flipping any that make an improvement.

I vary the number of times I use 1 versus 2 in order to control the computational costs of this step.

I have found that without this step the algorithm is dramatically less good.

Adaptive Elements

The mutation rate is adaptive. I keep statistics on whether there are any repetitions in the chromosomes I generated and if there are, I increase the mutation rate until they disappear. Thus the mutation rate is just high enough to make sure a maximum number of novel solutions are being explored. If I have increased the rate twice in a row then I double the increment size and if I decrease the rate twice in the row then I half the increment size. (This allows quick changes in the rate if necessary.)

I also keep statistics on the probability that crossover and the probability that mutaton improve the score. I randomly choose one or the other in proportion to their effectiveness in the last generation.

Cataloging solutions

I set a criteria for when I think the genetic algorithm is stuck (200 generations with no change in the best performer). If there is no improvement then I restart the algorithm and I store the best solution.

On crossover

Thanks for the suggestion. This is only my second genetic algorithm project so I appreciate the input. I tried it without crossover and crossover does seem to help. In the beginning, I tried crossover on the chomosomes with regular crossover points at the one third and two thirds mark. That did seem to be disasterous, leading to very early convergence.

Final comments

For n less than 8, this works very quickly. For n=5, a quick look at a few examples shows 150 is attained within 40 generations. This gets faster after the program has attained the solution once because a better mutation rate than my default guess is found.