The TMutator class defines the basic interface for a mutator (see listing 12). The job of the mutator is to perform a slight mutation on an individual after it has been created by the Breeder and before it is inserted into the population. The mutation simulates the small copying errors which occur when replicating DNA in natural organisms.
TMutator = class(TComponent)
// This function performs mutation(s) on the individual passed
procedure Mutate(Individual : TIndividual); virtual; abstract;
end;
|
listing 12: TMutator - base class for mutating individuals
The basic mutation methods, introduced in Figure 3 (back in section 2), can not all be applied to the TSP. The problem we have is that the problem constrains us such that each symbol (city) must appear exactly once in the route. Single Point Mutation and Deletion can, therefore, not be applied to our TSP individuals because they would cause cities to be omitted and/or duplicated. Translocation can not be applied either because it would change the length of the route. The TTSPMutator implements the remaining mutation type: Inversion (where a sub-route is reversed), and also implements another simple mutation: Transposition (where two randomly chosen cities are swapped).
Properties are used to allow the user to control the probabilities of these mutations being carried out
interface
type
TTSPMutator = class(TMutator)
private
FTrans: Double;
FInv: Double;
procedure SetInv(const Value: Double);
procedure SetTrans(const Value: Double);
public
procedure Mutate(Individual : TIndividual); override;
published
// Probability of doing a transposition
property Transposition : Double read FTrans write SetTrans;
// Probability of doing an inversion
property Inversion : Double read FInv write SetInv;
end;
implementation
procedure TTSPMutator.Mutate(Individual: TIndividual);
var
P : Double;
i, j, t : Integer;
Start, Finish : Integer;
begin
with TTSPIndividual(Individual) do
begin
// Should we do an inversion?
P := Random * 100;
if P < FTrans then
begin
// Do an inversion (i.e. swap two cities at random)
// Choose first city
i := Random(Steps);
// Choose a second city
repeat
j := Random(Steps);
until i <> j;
// Swap them over
t := Route[i];
Route[i] := Route[j];
Route[j] := t;
end;
// Should we do a transposition?
P := Random * 100;
if P < FInv then
begin
// Do a transposition (i.e. reverse a sub-route)
// Choose random start and finish points
Start := Random(Steps - 1);
Finish := Start + Random(Steps - Start);
// Reverse the sub-route
for i := 0 to Floor((Finish - Start) / 2) do
begin
t := Route[Start + i];
Route[Start + i] := Route[Finish - i];
Route[Finish - i] := t;
end;
end;
end;
end;
|
listing 13: TTSPMutator - performs inversion and/or transposition on travelling salesman routes based on probabilities
| Back |
|
|
| Contents | ||
| Next | ||