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

Table 5.2. Experimental analysis of SA-INV on TSP instance bier127 with 127 cities
after 25 generations. All self-adaptive variants are faster than standard INV with
fixed k .

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

best 353797.61 365157.31 372974.76 394652.11 403258.10

median 393111.29 393376.07 391979.44 414801.92 424457.13

worst 410781.74 478352.23 427454.29 442159.83 438986.51

mean 387801.57 397354.46 392307.67 416232.81 424336.54

dev 15583.604 23499.15 14342.49 13123.65 8876.50

25 generations. All variants of the SA-INV are better than the standard INV
operator concerning the mean and the best results. SA-INV 5 − 1 is the fastest
variant, see also figure 5.4. Between generations 70 to 80, INV 1 reaches the same
approximation quality, again we hold the strategy bound problem , see section 5.5,
responsible for this. The median of the self-adaptive variants is approximately
the same. The results of standard INV with ν = 10 are poor. The number of
ten edge exchanges seems to be too high in order to save the structure of the
solutions, i.e. not to destroy them. This behavior is the basis for the success of
SA-INV, which is able to reduce the mutation strength appropriately.
Figure 5.4 shows the development of the strategy parameter k during the first
100 generations and the fitness development in the same time slot. For all SA-
INV variants k increases within the first generations, very demonstrative in the
case of SA-INV 5 − 1 . This shows that the self-adaptation process is working prop-
erly: an increase of the mutation strength ( k> 5) is desirable at the beginning
of the search. Later the mutation strength developments of all SA-INV variants
show similar properties. SA-INV 20 − 5 decreases its k faster between generation
t

30. We hold the higher strategy mutation parameter γ responsi-
ble for that. Similar to instance berlin52 ,INV 10 suffers from fitness stagnation,
here around t

≈

10 and t

≈

≈ 20. SA-INV 5 − 1 is better than INV 1 until generation t ≈ 80.

5.4.3 TSP Instance Gr666

Problem gr666 , also from TSPlib, is the largest TSP instance considered in this
work. It is a geographical distance problem of 666 cities spread over the world.
The experimental results after 70 generations can be found in table 5.3.
Also here, the picture drawn from the previous experiments is confirmed. The
self-adaptive variants perform better than the standard ones, concerning the best ,
the median ,the worst and the average results. We do not observe any significant
differences between the three tested variants. INV 10 produces the worst results
as the big mutation strength destroys solutions in later phases of the search.
In figure 5.5 the average development of strategy parameter k and the fitness
development over 25 runs and 100 generations of SA-INV and INV are shown.
The smoothness of the development of k over successive generations is worse
than the smoothness on the previous problems. The reason is probably the size