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

Table 6.3. Analysis of standard PMX and SA-PMX on three TSP instances. The
figures show the tour length after the maximum number of generations. Although SA-
PMX achieves slightly better results, the standard deviation is too high to speak of
significant superiority. But the results of SA-PMX are better than the results of PMX c
with constant crossover points.

best mean dev worst optimum

ulsysses16
PMX

6859.0 6866.8 10.6 6950.0 6859.0

PMX c 6859.0 6869.6 15.0 6950.0

SA-PMX 6859.0 6864.3 6.3 6875.0

berlin52
PMX 7642.1 8366.4 270.9 9297.6 7542.0

PMX c 7887.3 8539.6 269.0 9335.7

SA-PMX 7777.3 8304.2 249.5 8921.0

bier127
PMX 123765.0 133600.4 3399.7 141157.7 118282

PMX c 131124.4 137679.4 3592.6 143680.4

SA-PMX 125620.9 133594.2 3426.5 140236.1

We tested SA-PMX on three TSP instances [74] from the TSPlib of Reinelt [117].
For the experiments we use inversion mutation 2 with p m =0 . 1, crossover prob-
ability of p c =1 . 0, population size 100 and fitness proportional parent selection.
Besides PMX we also tested a variant with fixed crossover points at Λ 1 ≈

N
3

and

2 N

Λ 2 ≈

3 .OnTSPinstance ulysses16 [ σ = 3, termination after 500 generations]
all variants reached the optimum in the best run, but SA-PMX achieved the
best average and worst result with the lowest standard deviation. On problem
berlin52 [ σ = 5, termination after 2000 generations] PMX achieved the shortest
but not optimal tour length of all runs. SA-PMX succeeded considering the aver-
age and the worst tour. On bier127 [ σ = 25, termination after 3000 generations]
the PMX attained the best overall tour length, while SA-PMX achieved the best
average and worst as well as the lowest standard deviation. But due to the stan-
dard deviation we have to point out that we cannot speak of significant results:
The behavior of the algorithm with regard to the problem is not changed by the
introduced self-adaptation. In every case the variant PMX c with fixed crossover
points achieved the worst results. Obviously, the randomness is essential for the
success of crossover.
To summarize the experimental results, a slight but not statistically significant
improvement can be reported with self-adaptation of crossover points. No con-
sistent picture concerning the superiority of SA-PMX can be drawn. Figure 6.1
shows a comparison of both crossover points of PMX (left part) and both of
SA-PMX (right part) averaged in each generation on problem bier127 during
3000 generations. The crossover points of PMX are stable, oscillating around the

2 Here, we do not use the self-adaptive variant SA-INV introduced in chapter 5.