Relative Position Indexing Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 111

Timing[Quiet[QAP3[mat1 , mat2 ,. 93 , 8000 , 100]]]

{ 2380 . 2 , { 3888 .,

{ 7 , 20 , 11 , 8 , 13 , 4 , 25 , 10 , 19 , 18 , 17 , 22 , 6 , 3 , 5 , 15 , 24 ,

14 , 23 , 21 , 1 , 16 , 2 , 12 , 9 , 26

}}}

4.7 Hybridizing Differential Evolution for the Assignment

Problem

Thus far we have seen methods that, for a standard benchmark problem from the
quadratic assignment literature, take us to within shouting distance of the optimal value.
These methods used simple tactics to formulate permutations from a vector chromo-
some, and hence could be applied within the framework of Differential Evolution. We
now show a method that hybridizes Differential Evolution with another approach.
A common approach to combinatorial permutation problems is to swap pairs (this
is often called 2-opt ), or reorder triples, of elements (also reversal of segments is
common). With Differential Evolution one might do these by modifying the objective
function to try them, and then recording the new vector (if we choose to use it) in the
internals of the algorithm. This can be done in NMinimize , albeit via alteration of an
entirely undocumented internal variable. We show this below, using a simple set of pair
swaps. When we obtain improvement in this fashion, we have gained something akin
to a local hill climbing method. I remark that such hybridization, of an evolutionary
method with a local improvement scheme, is often referred to as a memetic algorithm.
Nice expositions of such approaches can be found in [9] and [6].
The code creates a random value to decide when to use a swap even if it resulted in
no improvement. This can be a useful way to maintain variation in the chromosome set.
We also use a print flag: if set to True , whenever we get an improvement on the current
best permutation, we learn what is the new value and how much time elapsed since the
last such improvement. We also learn when we get such an improvement arising from
a local change (that is, a swap).
As an aside, the use of a swap even when it gives a worse result has long standing
justification. The idea is that we allow a decrease in quality in the hope that it will
later help in finding an improvement. This is quite similar to the method of simulated
annealing , except we do not decrease the probability, over the course of generations, of
accepting a decrease in quality.

QAP4

Outline of QAP4

1. Input: square matrices M 1 and M 2 each of dimension n , along with parameter
settings to pass to NMinimize , and a probability level p between 0 and 1
to determine when to retain an altered chromosome that gives a decrease in
quality.
2. Form a vector of variables of length n .