Self-Adaptive Crossover - Self-Adaptive Heuristics for Evolutionary Computation - page 98

Λ 1 <Λ 2 < ...<Λ n− 1 , which are saved in the strategy part Σ ζ , the offspring is
produced in the following way:

o i = p j− 1 modulo n

for Λ j <i

Λ j +1 ≤

(6.13)

i

with Λ 0 =1and Λ n +1 = l . U-Scan is the multi-parent variant of uniform
crossover. The idea is to assign each of the offspring's gene position randomly
with one of the parent's genes at the same position. Self-adaptive U-Scan (SA-U-
Scan) saves the parent j , from which to take the gene for every position i . Hence,
Σ ζ

=( Λ 1 ,...Λ ζ N )with1

is a N-dimensional vector of integers Σ ζ Λ ζ

≤ ≤ ρ .

SA-U-Scan produces new solutions as follows:

o i = p Λ i
i

(6.14)

OB-scan performs a majority decision, the most frequent gene of all parents at
a position determines the gene of the offspring at the same position. Thus, this
operator cannot be equipped with self-adaptation.

6.3 Self-Adaptive Partially Mapped Crossover

Partially mapped crossover (PMX) was designed for TSP by Goldberg and Lingle
[48] and enhanced by Whitley [159]. The PMX works as follows:

Choose two parents p 1 and p 2 , •

• choose two crossover points Λ 1 and Λ 2 ,

copy the segment between Λ 1 and Λ 2 from p 1 to offspring o 1 ,

•

put all genes of p 2 in this segment which have not been copied into set

• L ,

look for the corresponding locus in parent p 1 and
copy l to this position if free. If this position is not free, recursively repeat
the process until a free position can be found,

• for each element l of L

fill the empty loci with genes from corresponding loci of p 2 .

•

We extend the PMX to self-adaptive partially mapped crossover (SA-PMX). SA-
PMX keeps the crossover points Λ 1 and Λ 2 in the strategy part Σ and evolves
them during the optimization process [74]. We use the best inheritance heuristic
to determine the strategy set Σ ζ , i.e. ζ = argmax j, 1 ≤j≤ρ f ( p j ). Self-adaptation
is only possible if the strategy variables are modified with the genetic operators.
We propose to use meta-EP mutation for the crossover points.

Experimental settings
Population model steady state, (100,200)

Mutation type inversion mutation, σ =3 , 5 , 25

Crossover type SA-PMX

Selection type fitness proportional

Initialization random

Termination 500,2000,3000 generations

Runs 25