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

Table 5.4. Experimental comparison of SA-INV-c, SA-INV and INV on problem
bier127 after 100 generations. SA-INV-c achieves the best results for best , median
and mean .

SA-INV-c 5 − 1 SA-INV 5 − 1 INV 1 INV 10

best 190912.96 191115.51 194403.16 402244.68

median 200495.52 214640.67 205783.69 419211.84

worst 235531.40 234179.99 221001.62 447189.49

mean 202989.63 212523.76 206272.24 421587.75

dev 10327.06 9954.37 6339.65 12164.78

vote for the setting k = 1, we approve this choice for all parameters. We tested
the SA-INV-c 5 − 1 algorithm experimentally on instance bier127 and present the
results in figure 5.6. The upper part shows the development of mutation strength
k . As expected once reached the region of one it is constantly set to k =1to
avoid solution destroying mutations. The lower part of the figure illustrates the
superiority of SA-INV-c 5 − 1 in comparison to SA-INV 5 − 1 . SA-INV-c 5 − 1 is faster,
in particular in later phases of the search.
Table 5.4 confirms the results. It shows the fitness after 100 generations on
problem bier127 . SA-INV-c 5 − 1 achieves the best results for best , median and
mean . The Wilcoxon rank-sum test reveals that SA-INV-c 5 − 1 is significantly
better than SA-INV 5 − 1 ( p w ≤ 0 . 0001043), also better than INV 1 ( p w ≤ 0 . 04781),

and definitely better than INV 10 ( p w ≤ 9). SA-INV 5 − 1 and INV 1 do not

produce significantly different solutions. Hence, the experiments show that self-
adaptive inversion mutation with the heuristic extension (SA-INV-c) is able to
beat standard inversion mutation.

1 . 4 E −

5.6 Summary

1. Despite the fact that only very few examples exist, where the self-adaptation
of discrete variables for EAs work properly, in this chapter we presented the
SA-INV, a successful example for discrete mutation strength self-adaptation.
2. Inversion mutation is a common mutation operator for GAs on the TSP.
SA-INV is its self-adaptive variant. The strategy parameter k determines
the number of successive applications of inversion mutation, i.e. swaps of
edges.
3. Our convergence analysis revealed that an EA with INV or SA-INV con-
verges with probability one to the global optimum after a finite number of
iterations. 5
4. Experiments showed that self-adaptation is able to speed up the optimiza-
tion, in particular at the beginning of the search. The results have been
validated with the Wilcoxon rank-sum test.

5 This statement holds as long as the other genetic operators fulfill the necessary
conditions.