Genetic.tex

\section{Genetic algorithms}\label{genetic-alg}

Genetic algorithms can be used to find solutions to a wide variety of combinatorial problems. In most cases, many of the specifics of the implemenation are not essential. In this account, we seek to provide some of the more salient details of at least one way in which the Hales-Jewett problem can be approached using genetic algorithms.

The representation of genetic algorithms is a nontrivial problem.\cite{Rothlauf} Each solution in $[3]^n$ was represented as an array of $3^n$ elements where each element was a 0,1 or 2. This was generalized to higher dimensional versions of the problem. We depart from the traditonal genetic algorithm, in that, the genetic algorithm implemented is a mixture of both a greedy algorithm and a genetic algorithm. This combination of greedy and genetic algorithms, which has some precedent\cite{Krisha}, was observed to increase the effectiveness of the genetic algorithm solution of the Hales-Jewett problem significantly.

A lookup table was constructed where for each string, the other strings needed to make a line were listed. In order to check whether a particular line was present, it was sufficient to check whether all these strings were present. This particular implementation was chosen to increase the speed for checking whether lines were present.

While it may be possible to use invalid strings as members of the population in the genetic algorith, no invalid strings are used as solution candidates. Any candidate solutions which contain lines are corrected. If a group of elements creates a line, one of these elements is removed at random to elimiate the line. New solutions by three methods. They are created from old solutions by randomly including or removing a string from the list of strings in a candidate solution; they are created by taking part of one list of strings and merging it with part of another list; or they are created by adding any elements that can be added without adding a line.

There are small differences which speed up the basic function of the algorithm but probably do not contribute to the types of solutions ultimately found. For instance, the rate of mutation. Ways of generating a new solution were used in proprotion to their historical rate of success in producing new solutions. The population size was typically held between 60-80. The algorithm was periodically restarted if between solutions were not found after a reasonably long delay.