Getting Started - Genetic Algorithms

The basic steps for adding genetic algorithms to your applications are:

Setting up the genes of your population is one of the most important steps in making a useful genetic algorithm.  In this step, you define the parameters of your problem, e.g., what properties or parameters define the solution.  For example, in a shooter game if you were creating the "best" AI bot, these may be a 3-bit enumeration of which weapon to choose, 2-bit enumeration specifying aggression, 8-bit integer specifying the maximum range to shoot at an enemy, etc.

For this example, we are going to go through the steps of defining and solving the 8-Queens problem (this is also a demo application).  The 8-Queens problem is a chess problem, which asks how do you place 8 queens on a chessboard, each in a unique column, so that no queen can attack the other?  Here is an example solution of the problem:

.  .  .  .  Q  .  .  .

.  .  .  .  .  .  Q  .

.  Q  .  .  .  .  .  .

.  .  .  .  .  Q  .  .

.  .  Q  .  .  .  .  .

Q  .  .  .  .  .  .  .

.  .  .  .  .  .  .  Q

.  .  .  Q  .  .  .  .

The chromosome for this problem would specify a solution for the 8-Queens problem.  We need to find the place, in each of 8 columns, where we can place a queen and not be able to attack any other queen.  So for this problem, there are 8 genes, one for each column.  Each gene is a 3 bit integer representing the place of the queen for that column (there are 8 places per column).  This means there are 24 bits (8*3) in the chromosome for each individual solution.

To set the chromosome size directly, use the GeneSize property:

RSGeneticAlgorithm1.GeneSize := 24;

Alternatively, you can build the genetic mapping for your solution using the Genes property.  Using this property, the GeneSize property is simply the sum of all genes you define.  The Genes property is especially helpful because it allows you to easily access the values of each gene in an individual.  The Genes property allows you to define each gene of your problem separately, whether it is integers, floats, or enumerations.  For this problem, you define the same gene 8 times:

var

   i: Integer;

begin

     // create the N-Queens genes

     with RSGeneticAlgorithm1 do

     begin

          Genes.Clear;

          for i := 0 to NUM_QUEENS - 1 do

              with Genes.Add do

              begin

                   GeneType := gtInteger;

                   Name := 'Col '+IntToStr(i);

                   Size := BitsRequired( NUM_QUEENS-1 );

                   MaxValue := NUM_QUEENS - 1;

              end;

     end;

end;

Set InitialPopulation to a positive integer value.  For the 8-queens problem, a good initial population is at least 4 times the number of queens in the problem, e.g., 32 individuals (to converge a solution faster, use a higher value):

RSGeneticAlgorithm1.InitialPopulation := 32;

Defining your fitness function is another highly important part of defining a genetic algorithm.  The fitness function returns a floating point value that specifies the correctness of the individual solution (chromosome).  The fitness function needs to be able to allow the genetic algorithm component to decide which solution is better than another.  The genetic algorithm component will seek to either maximize the solution (e.g., keep evolving for individuals whose fitness are greater than other individuals in the population) or to minimize the solution (e.g., find the individuals whose fitness are less than other individuals).  Note you can specify which direction to evolve towards with the FitnessMethod property.

For the 8-queens problem, we are going to choose a fitness function that calculates the number of non-attacking pairs of queens.  A completely solved solution would be 28 non-attacking pairs of queens.  

To define your fitness function, you need to define an OnEvaluateFitness event handler:

procedure TForm1.RSGeneticAlgorithm1EvaluateFitness(Sender: TObject;

  const Item: TRSGAIndividual; var Fitness: TGAFitness);

var

   i: Integer;

   j: Integer;

   Queen: Integer;

   newQueen: Integer;

   d1, d2: Integer;

begin

     // fitness function for 8 queens problem is the number of non-attacking

     // pairs of queens (perfect is 28)

     Fitness := 0;

     with Sender as TRSGeneticAlgorithm do

     for i := 0 to Genes.Count - 2 do

     begin

          Queen := Genes[i].AsInteger[Item.Index];

          if Queen >= NUM_QUEENS then Fitness := Fitness - 1;

          d1 := Queen + 1;

          d2 := Queen - 1;

          for j := i + 1 to Genes.Count - 1 do

          begin

               NewQueen := Genes[j].AsInteger[Item.Index];

               if NewQueen >= NUM_QUEENS then Fitness := Fitness - 1;

               if (NewQueen <> Queen) and (NewQueen <> d1) and (NewQueen <> d2) then

                  Fitness := Fitness + 1;

               Inc(d1);

               Dec(d2);

          end;

     end;

end;

Notice how the fitness function uses the Genes property to access each portion of the individual's (Item) chromosome simply:

RSGeneticAlgorithm1.Genes[i].AsInteger[Item.Index]

Finally, we are almost ready to start evolving the population towards a solution!

First, you need to specify the Operations performed while evolving.  By default, the TRSGeneticAlgorithm component provides crossover, mutation, and inversion operations.  You can also specify the chances of each operation occurring every generation using the CrossoverProbability, MutationProbability, and InversionProbability properties.

Next, you need to specify how the TRSGeneticAlgorithm component selects individuals from the current generation to be used as parents of the next generation.  The SelectionMethod property (or OnSelection event) controls this selection:

Finally, it's time to start evolving towards a solution.  Call the Evolve method.  The Evolve method starts "breeding" an answer to your goal.  Each generation, the Evolve method selects parents and then Reproduces children for the new generation by using the genetic operations: first crossover, then mutation, and finally inversion.  You can specify the number of generations to evolve or use the FitnessCutoff, GenerationLimit, and DiversityLimit properties to automatically stop the genetic process.  Successive calls to the Evolve method continues the evolutionary process from where the Evolve method stopped (use Initialize to reset the process).

An important thing to remember about genetic components: you are trying to breed a solution that is "good enough", not perfect.  It is a difficult thing to wrap your mind around, but it is often impossible to find a perfect solution.  Rather, you should be looking for a solution that meets your requirements.  The demo programs can be misleading as we know the perfect solution for the problems but are using these problems to show you how to use the components.  Do not fall into the trap of trying to find a perfect solution.

The FitnessCutoff property aborts the evolutionary process when any child meets or exceeds (if FitnessMethod is fmMaximize) or is less than (if FitnessMethod is fmMinimize) the cutoff value.  The UseFitnessCutoff property must be true to use the fitness cutoff.

The DiversityLimit property aborts the evolutionary process when the diversity of the children falls below the DiversityLimit, e.g., all the children are too alike to go any further.  The UseDiversityLimit property must be true to use the diversity limit.

The GenerationLimit property aborts the evolutionary process after the number of generations have been evolved.  The UseGenerationLimit property must be true to use the generation limit.

For the 8-Queens problem, you can use a fitness cutoff:

begin

  RSGeneticAlgorithm1.UseFitnessCutoff := True;

  RSGeneticAlgorithm1.FitnessCutoff := 28;

  RSGeneticAlgorithm1.SelectionMethod := smStochasticTournament;

  while RSGeneticAlgorithm1.MaxFitness < 28 do

    RSGeneticAlgorithm1.Evolve(10);

end;