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

now do larger runs to get a better idea of what are the relative merits of these various
cross probability parameter settings.
Quiet[Tab le[ Quiet[Tab le[ Quiet[Tab le[ { { { j , First[QAP2[mat1 , mat2 , j / 100 , 80 , 20]] j , First[QAP2[mat1 , mat2 , j / 100 , 80 , 20]] j , First[QAP2[mat1 , mat2 , j / 100 , 80 , 20]] } } } , , , { { { j , 87 , 98 , 1 j , 87 , 98 , 1 j , 87 , 98 , 1 } } } ]] ]] ]]

{{ 87 , 4298 . } , { 88 , 4418 . } , { 89 , 4346 . } , { 90 , 4314 . } , { 91 , 4396 . } , { 92 , 4416 . } ,

{ 93 , 4300 . } , { 94 , 4308 . } , { 95 , 4274 . } , { 96 , 4322 . } , { 97 , 4282 . } , { 98 , 4298 . }}

We will finally try a longer run with cross probability set to 0.975.

Quiet[Timing[ Quiet[Timing[ Quiet[Timing[ { { { min , perm min , perm min , perm } } } = QAP2[mat1 , mat2 ,. 975 , 10000 , 100]]] = QAP2[mat1 , mat2 ,. 975 , 10000 , 100]]] = QAP2[mat1 , mat2 ,. 975 , 10000 , 100]]]

{ 2590 . 27 , { 3814 .,

{ 5 , 2 , 11 , 22 , 15 , 18 , 25 , 16 , 9 , 1 , 17 , 3 , 6 , 8 ,

19 , 12 , 14 , 7 , 23 , 20 , 24 , 4 , 21 , 10 , 13 }}}

This gets us reasonably close to the global minimum with a scant 15 lines of code. While
it is mildly more complicated than the 10 line relative position indexing method, it has
the advantage that it is slightly less dependent on fine tuning of the cross probability
parameter.

4.6.3 Another Shuffle Method

There are other plausible ways to set up permutations, such that they behave in a rea-
sonable manner with6 respect to mutation and mating operations. Here is one such.
We have for our vector a set of integers from 1 to n , the length of the set in ques-
tion (again we will actually work with reals, and round off to get integers). The range
restriction is the only stipulation and in particular it may contain repeats. We associate
to it a unique permutation as follows. We initialize a list to contain n zeros. The first
element in our list is then set to the first element in the vector. We also have a marker
set telling us that that first element is now used. We iterate over subsequent elements
in our list, setting them to the corresponding values in vector provided those values
are not yet used. Once done with this iteration we go through the elements that have
no values, assigning them in sequence the values that have not yet been assigned. This
method, which is used in [7], is similar to that of GeneRepair [8]. It is also related to
a method of [12], although they explicitly alter the recombination (that is, the genotype)
rather than the resulting phenotype.

Outline of getPerm2 getPerm2

1. Input: a shuffle S encoded as n integers in the range .

2. Create vectors P 1 and P 2 of length n . The first will be for the permutation we
create, and the second will mark as “used” those elements we have encoun-
tered. Initialize elements of each to be 0.

{ 1 ,..., n }