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

5 Self-Adaptive Inversion Mutation

Inversion mutation is a mutation operator for combinatorial search domains. It
is based on the random change of edges. A famous example for a combinatorial
problem is the traveling salesman problem (TSP). Inversion mutation is a typical
genetic operator for combinatorial problems like the TSP. It reverses the tour
between two randomly chosen cities. Here, we propose a self-adaptive variant
of inversion mutation. Self-adaptation is a successful control technique for the
mutation strength, see chapter 3. Up to now, the concept of self-adaptation has
not been applied to inversion mutation. As the number of successive inversion
mutation operator applications can be seen as the mutation strength, we propose
to control this parameter self-adaptively. In this chapter we introduce a self-
adaptive variant of inversion mutation (SA-INV). We prove the convergence of
inversion mutation and its self-adaptive variant and show experimentally that
SA-INV speeds up the evolutionary process, in particular at the beginning of the
search. Later we encounter the strategy bound problem and introduce a heuristic
to overcome it.

5.1 Introduction

At first, we introduce the TSP and give an overview of evolutionary combinato-
rial optimization and self-adaptation for discrete strategy variables.

5.1.1 The Traveling Salesman Problem
The TSP is the problem to minimize the length of a salesman's tour visiting
every city of a given set only once and then returning back to the point where
he started. It is defined as follows.

Definition 5.1 (Traveling Salesman Problem)
Let C be a set of N cities with distances d ( c i ,c j ) ∈ IR for each pair of cities

C. An optimal solution of the TSP is the shortest tour π ∗ c i ,c j ∈ of C, i.e.

[1 ,...,N ] with minimum length l = N− 1
i =1

a permutation π :[1 ,...,N ] −→

d c π ( i ) ,c π ( i +1) + d c π ( N ) ,c π (1) .