Introduction to Evolutionary Algorithms

12. The Population

The TPopulation class is the last and most important piece of the puzzle. It is responsible for bringing together the functionality provided by the classes detailed in the last seven sections to implement the evolutionary algorithm.

Those familiar with design patterns will notice the heavy use that I have made of the Strategy (or Policy) pattern in the design of the TPopulation. This is done, essentially, to decouple any problem-specific behaviour from the Population component. The TPopulation has no knowledge of the travelling salesman problem, or any other problem. It simply implements the evolutionary algorithm shown in figure 4.

In order to apply the evolutionary algorithm to a problem, such as the TSP, descendants of the base strategy components must be created to implement the required functionality. The population then applies the evolutionary algorithm using the strategy components. Figure 7 illustrates this.

fig. 7: The EA implemented using the strategy pattern

The algorithm shown in figure 7 is implemented in the "Initialise" and "Generation" methods. These are shown in listing 16.

procedure TPopulation.Initialise(Size: Integer);
var
  i   : Integer;
  New : TIndividual;
begin
  // Clear out the old stuff
  Clear;

  // Set the capacity first to save about 12 nanoseconds ;o)
  FPop.Capacity := Size;

  // Create the appropriate number of individuals
  for i := 1 to Size do
  begin
    // Create the individual
    New := FCreator.CreateIndividual;

    // Get the fitness of the new individual
    New.Fitness := FExaminer.GetFitness(New);

    // Add to the population
    Add(New);
  end;

  SortPopulation;

  Change;
end;


procedure TPopulation.Generation;
var
  Replace, i : Integer;
  New        : TIndividual;
begin
  // Kill some of the population
  Replace := FKiller.Kill(Self);

  for i := 1 to Replace do
  begin
    // Breed a new individual
    New := FBreeder.BreedOffspring(FParentSelector, Self);

    // Perform some mutation on the individual
    FMutator.Mutate(New);

    // Get the fitness of the new individual
    New.Fitness := FExaminer.GetFitness(New);

    // Add it to the population
    Add(New);
  end;

  // Sort the population into fitness order where first <==> best
  SortPopulation;

  Change;
end;

listing 16: The "Initialise" and "Generation" methods, used to implement the EA

Note how the use of the strategy pattern allows us to delegate all problem specific functionality to our strategy classes and keep the code for the EA clean and simple.

Listing 17 shows the class declaration for the population component. Note the properties which allow the strategy components to be assigned at design time. Figure 8 shows this taking place.

  TPopulation = class(TComponent)
  private
    // The population
    FPop : TObjectList;
    // Worker for breeding
    FBreeder: TBreeder;
    // Worker for killing
    FKiller: TKiller;
    // Worker for parent selection
    FParentSelector: TParentSelector;
    // Worker for mutation
    FMutator: TMutator;
    // Worker for initial creation
    FCreator: TCreator;
    // Worker for fitness calculation
    FExaminer: TExaminer;
    // On Change event
    FOnChange: TNotifyEvent;
    procedure Change;
    // Getters...
    function GetIndividual(I: Integer): TIndividual;
    function GetCount: Integer;
  protected
    // Comparison function for Sort()
    function CompareIndividuals(I1 : Pointer; I2 : Pointer) : Integer;
    // Sort the population
    procedure SortPopulation;
  public
    // The constructor
    constructor Create(Owner : TComponent); override;
    // The destructor
    destructor Destroy; override;
    // Adds an individual to the population
    procedure Add(New : TIndividual);
    // Deletes an individual from the population
    procedure Delete(I : Integer);
    // Runs a single generation
    procedure Generation;
    // Initialise the population
    procedure Initialise(Size : Integer);
    // Clear ourselves out
    procedure Clear;
    // Get the fitness of an individual
    function FitnessOf(I : Integer) : Double;
    // Access to the population members
    property Pop[I : Integer] : TIndividual read GetIndividual; default;
    // The size of the population
    property Count : Integer read GetCount;
  published
    // Allow these to be assigned in the IDE...
    property ParentSelector : TParentSelector read FParentSelector
                           write FParentSelector;
    property Breeder : TBreeder read FBreeder write FBreeder;
    property Killer : TKiller read FKiller write FKiller;
    property Mutator : TMutator read FMutator write FMutator;
    property Creator : TCreator read FCreator write FCreator;
    property Examiner : TExaminer read FExaminer write FExaminer;
    // An event
    property OnChange : TNotifyEvent read FOnChange write FOnChange;
  end;

listing 17: Class declaration for the TPopulation component

fig. 8: Setting up the EA to solve the TSP at design time

The Observer pattern is also implemented (somewhat crudely) using the "OnChange" event. This can be assigned at design time to allow the user interface to monitor the population. Thus, displays and suchlike can be updated as the EA progresses. This is not the true observer pattern, because we are not maintaining lists of observer classes in our observed component, but it provides much of the functionality with a fraction of the overhead.


	Back
	Contents
	Next