Self-Adaptive Inversion Mutation - Self-Adaptive Heuristics for Evolutionary Computation - page 86

5.4.4 Small TSP Instances

On smaller instances like ulysses16 we observed principally a similar develop-
ment of k . Within the first generations k is bigger than one. After 10 to 20
generations k almost constantly decreases to 1. Due to comparatively small im-
provements at the beginning of the search, we skip the presentation of these
results. They are comparable to the results on the other TSP instances.

5.4.5 Statistical Test

We apply the non-parametric Wilcoxon rank-sum test on the results of the pre-
vious sections, in order to prove statistically that the SA-INV variants are sig-
nificantly better than the best INV variants.

Wilcoxon Rank-Sum Test

berlin52 bier127 gr666
SA-INV 5 − 1 vs. INV 10 SA-INV 5 − 1 vs. INV 1 SA-INV 10 − 2 vs. INV 1
p w 0.0001129 1.312E-07 5.561E-08

To this end we compare the results of SA-INV 5 − 1 to the results of INV 10 on
instance berlin52 . 4 The small p w -value of 0 . 0001129 << 0 . 05 leads to a rejec-
tion of the hypothesis that both heuristics produce an identical distribution.
The median and mean of SA-INV 5 − 1 is smaller, hence its results are signifi-
cantly better. The comparisons between SA-INV 5 − 1 and INV 1 on bier127 and
SA-INV 10 − 2 and INV 1 on gr666 with the small p w -values lead to the same con-
clusion: the self-adaptive variants produce significantly better results than the
standard inversion operator.

5.5 The Strategy Bound Problem and SA-INV-c

The self-adaptation of k speeds up the starting phase of the search. At the be-
ginning, more than one inversion mutation in each step leads to considerable
improvements. Parameter k decreases constantly, as less and less edge swaps are
necessary to improve the solution and not to destroy it. After a certain number
of generations g , the strategy parameter k is almost constantly one. From now on
more than one change of edges leads to a fitness deterioration. But the mutation
of strategy variables in the context of the self-adaptive process still produces so-
lutions with k> 1 and consequently offspring with potentially worse fitness. The
progress of SA-INV slows down and soon INV 1 overtakes SA-INV concerning
the approximation. We call this problem strategy bound problem : Whenever the
strategy variables reach a bound b , the self-adaptive process experiments with

4 The mean of INV 10 is better than the mean of INV 1 , the median is worse. A test of
INV 1 and SA-INV 5 − 1 produces p w ≤ 0 . 01166, which is still significant.