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

experimental results of SA-1-point on the problems onemax, sphere 1 ,ackleyand
3-SAT. The table shows the number of generations until the optimum is found.
Although in all experiments the mean of SA-1-point lies under the mean of
1-point crossover, the standard deviation is too high to assert statistical signifi-
cance. SA-1-point was able to find the optimum of 3-SAT in only 7 generations,
which is very fast. But it also needs the longest time with its worst result. We
observe no significant improvement of the self-adaptive variants in comparison
to the standard operators.

6.2.2 SA-n-Point

For n-point crossover the representation is broken into more than two segments
and assembled alternately from both parents. For the self-adaptive extension
(SA-n-point) the n crossover points are saved in the genome as strategy variables
Σ =( Λ 1 ,...,Λ n ), sorted by size Λ 1 <Λ 2 < ... < Λ n . Given two parents p 1 =
( p 1 ,...,p l ,Λ 1 ,...,Λ n )and p 2 =( p 1 ,...,p l ,Λ 1 ,...,Λ n ), SA-n-point crossover

selects a crossover point set Σ ζ to create the new offspring o 1 and o 2 with

o i = p i ,

Λ ζ m <i≤ Λ ζ m +1 m even

(6.9)

Λ ζ m +1

p i , Λ ζ m <i ≤ m odd

and

o i = p i ,

Λ ζ m +1 Λ ζ m <i ≤ m odd

(6.10)

Λ ζ m +1

p i , Λ ζ m <i

≤ m even

with Λ 0 =0and Λ n +1 = l The strategy part Σ ζ has to be mutated, sorted and
included into each offspring genome afterwards. In order to evaluate the success
of SA-n-point crossover, we take the test problems of the previous section and
test SA-5-point with five crossover points. Table 6.2 shows the results, using the
settings of the previous experiments. Similar to the previous series of experiments
we cannot observe a significant improvement of self-adaptive crossover. Neither
on the unimodal functions (onemax and sphere) nor on the highly multimodal
SAT-problem the self-adaptation of crossover points seems to be effective. Hence,
these experiments call the possibility that building blocks can be identified au-
tomatically with self-adaptation into question. But if we compare the results
to 1-point crossover, we observe that the increase of crossover points achieves
improvements. This observation mainly concerns the mean and the standard
deviation.

6.2.3 Self-Adaptive Uniform and Multi Parent Crossover

For the sake of completeness we now equip uniform crossover and multi parent
genetic algorithms (MPGAs) with self-adaptation, but without presenting an

1 in binary representation