Introduction to Evolutionary Algorithms

9. The Breeder

The TBreeder class defines an interface for breeding parents to make new population members. The Breeder makes use of a Parent Selector to choose the parent individuals, then combines them to make the offspring. Listing 10 shows the TBreeder class declaration and listing 11 shows the TTSPBreeder class, which is used to create offspring solutions to the travelling salesman problem.

Listing 11 also shows the TTSPBreederCrossover class. This implements a crossover combination scheme. The following steps are carried out to create the offspring...

use the parent selector to select two parents from the population
for each step along the route...

choose a preffered parent at random from the two selected parents
if it hasn't been used already copy the city for this step from the preffered parent
otherwise, if it hasn't been used already, copy the city from the other parent
otherwise, if the cities from both parents have been used, choose an unused city at random

move to the next step along the route and repeat until a full route has been constructed

  TBreeder = class(TComponent)
    // This function should return a new population member based on parents
    // selected using the ParentSelector object
    function BreedOffspring(PSelector : TParentSelector; Pop : TPopulation) : TIndividual; virtual; abstract;
  end;

listing 10: TBreeder - base class for breeding parents to create offspring

Generated with HyperDelphi

interface

type
  TTSPBreeder = class(TBreeder);

  TTSPBreederCrossover = class(TTSPBreeder)
  public
    function BreedOffspring(PSelector : TParentSelector; Pop : TPopulation) : TIndividual; override;
  end;


procedure Register;

implementation

function TTSPBreederCrossover.BreedOffspring(
  PSelector: TParentSelector; Pop: TPopulation): TIndividual;
var
  Child, Mum, Dad, Parent1, Parent2 : TTSPIndividual;
  i, j, p : Integer;

  function AlreadyAssigned(City, X : Integer) : Boolean;
  var
    y : Integer;
    Found : Boolean;
  begin
    Found := False;

    for y := 0 to x - 1 do
    begin
      if Child.Route[y] = City then
      begin
        Found := True;
        Break;
      end;
    end;

    Result := Found;
  end;

begin
  // Select a some parents...
  Mum := TTSPIndividual(PSelector.SelectParent(Pop));
  Dad := TTSPIndividual(PSelector.SelectParent(Pop));

  // Create a child
  Child := TTSPIndividual.Create(Mum.Steps);

  // Copy the route from parents to child
  for i := 0 to Child.Steps - 1 do
  begin
    // Choose a parent at random
    p := Random(2);

    if p = 0 then
    begin
      Parent1 := Mum;
      Parent2 := Dad;
    end
    else
    begin
      Parent1 := Dad;
      Parent2 := Mum;
    end;

    if not AlreadyAssigned(Parent1.Route[i], i) then
    begin
      // Use city from Parent 1 unless used already
      Child.Route[i] := Parent1.Route[i];
    end
    else if not AlreadyAssigned(Parent2.Route[i], i) then
    begin
      // Otherwise use city from Parent 2 unless used already
      Child.Route[i] := Parent2.Route[i];
    end
    else
    begin
      // If both assigned already then use a random city
      repeat
        j := Random(Child.Steps);
      until not AlreadyAssigned(j, i);

      Child.Route[i] := j;
    end;
  end;

  // Return the child
  Result := Child;
end;

listing 11: TTSPBreederCrossover - breeds offspring to solve the TSP


	Back
	Contents
	Next