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

TSP if a very famous combinatorial optimization problem with dozens of solu-
tion approaches. The exact solution of bigger TSP instances is impractical since
the problem is NP-complete [45]. With dynamic programming a solution can be
computed in time O ( n 2 2 n ), which is still impractical. Other exact methods to

solve the TSP are branch-and-bound and linear programming approaches. Var-
ious heuristics exist to solve the TSP reaching from nearest-neighbor strategies
to the 2-opt heuristic. 2-opt is a famous heuristic replacing two longer random
edges by two shorter ones [26]. The concept is based on the idea of inversion mu-
tation: we select a subtour, reverse it and accept an improvement. An approach
similar to simulated annealing accepts improvements with a certain probability,
e.g. recently theoretically analyzed by Meer [89]. He constructs a TSP instance
for which simulated annealing outperforms a metropolis algorithm with a fixed
temperature using the 2-opt heuristic.

·

5.1.2 Evolutionary Combinatorial Optimization

Combinatorial optimization problems are believed not to be eciently solvable,
most problems are NP-hard 1 . Examples for combinatorial problems are the knap-
sack problem or the TSP. For the latter the solution of trying all permutations
is impractical as the number of possible solutions is n !. In the traditional rep-
resentation the queue of integers represents the order of the tour in which the
cities have to be visited. To avoid multiple nodes, which would happen after the
application of n-point crossover, partially mapped crossover (PMX) is used, see
chapter 6. The random keys approach avoids infeasible solutions [10], [146]: Each
city is assigned with a random number x [0 , 1). The chromosome is produced

by visiting the nodes in ascending order. As this order is always well-defined as
long as no equal numbers exist, crossover operators like N-point crossover can be
applied. Other evolutionary approaches are successful like memetic algorithms,
which combine EAs with local optimization methods, e.g. 2-opt.

∈

5.1.3 Self-Adaptation for Discrete Strategy Variables

Not many EAs with discrete strategy variables exist. In chapter 6 we introduce
self-adaptive crossover. Self-adaptive crossover controls the position of crossover
points which are represented by integers [74]. Punctuated crossover by Schaffer
and Morishima [128] makes use of a bit string of discrete strategy variables which
represent location and number of crossover points. In section 4.6 we examined
the self-adaptive selection of mutation operators for ES. Spears [147] introduced
a similar approach for the selection of crossover operators. Back [7], Smith [142],
Fogarty [144] and Stone [148] introduced self-adaptive approaches for mutation
rates.

1 NP-hard (nondeterministic polynomial-time hard): a problem H is NP-hard iff there
is an NP-complete problem L that is polynomial time Turing-reducible to H, i.e.
L ≤ T H.