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

TSP instances of the TSPlib of Reinelt [117], berlin52 , bier127 and gr666 .Fur-
thermore, we analyze the development of the strategy parameter k . For our
experiments we make use of the following settings.

Experimental settings
Population model

(15,100)

Mutation type SA-INV, INV, γ =1 , 2 , 5

Crossover type no crossover

Selection type comma

Initialization random, ν =5 , 10 , 20

Termination 1 000 generations

Runs 25

In order to avoid side effects we do not apply crossover. We use the following
notation: SA-INV ν−γ is the self-adaptive inversion mutation with the initial
setting k (0) = ν and the strategy mutation strength γ and INV ν is the common
inversion mutation with constant k = ν edge swaps.

5.4.1 TSP Instance Berlin52

At first, we analyze SA-INV on the 2-dimensional Euclidean distance problem
berlin52 . Table 5.1 shows the results after 10 generations in order to show the
behavior at the beginning of the search. The table clearly shows that SA-INV 5 − 1
achieves the best results after 10 generations. Within this time horizon INV 1 is
slower with only one edge swap for a solution each generation. INV 10 is as
faster than INV 1 , because 10 swaps each generation produce better results, at
least within this small timespan. The situation will change rapidly a couple of
generations later, see figure 5.3. The lower part of the figure shows the fitness
development of the SA-INV and INV variants. SA-INV 5 − 1 is the fastest variant
at the beginning until INV 1 overtakes its approximation. We call the reason for
that strategy bound problem and explain it in section 5.5.
While INV 10 is comparatively fast at the beginning, the 10 swaps destroy the
solutions in later generations and hinder any further approximation of the opti-
mum. This situation is similar to the comparison between an ES with constant

Table 5.1. Experimental analysis of SA-INV on TSP instance berlin52 with 52 cities .
SA-INV 5 − 1 is faster than INV 1 after 10 generations. The other SA-INV variants began
with a too high number of edge swaps.

SA-INV 5 − 1 SA-INV 10 − 2 SA-INV 20 − 5 INV 1 INV 10

best 17027.32 17677.79 17493.31 16870.67 18136.78

median 18819.53 19123.82 19760.08 19526.80 19962.73

worst 20581.50 22221.77 25793.67 25586.68 21249.91

mean 18751.74 19365.57 20429.49 20111.88 19809.41

dev 826.00 1365.08 2557.71 2014.32 807.20