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

{

1 , 0 , 1 , 0 , 0 , 1

}

spfun2[ spfun2[ spfun2[ { { 1 , 0 , 1 , 0 , 0 , 1 1 , 0 , 1 , 0 , 0 , 1 } } ] ] ]

0 . 468741

With this knowledge it is now reasonably straightforward to write the code that will
perform our optimization. We create a set of variables, one for each element in the set.
We constrain the variables to take on values that are either 0 or 1, and such that the sum
is exactly half the cardinality of the set (that is, 100/2, or 50, in the example of interest to
us). Since we force variables to be integer valued, NMinimize will automatically use
DifferentialEvolution for its method. Again, we might still wish to explicitly
request it so that we can set option to nondefault values.

Outline of getHalfSet2 getHalfSet2

1. Input: An even integer n , and options to pass along to NMinimize .
2. Create a list of variables, vars, of length n .
3. Set up constraints.
All variables lie between 0 and 1.
All variables are integers.
Their total is 2 .
4. Call NMinimize , passing it spfun2[vars] as objective function, along
with the constraints and the option settings that were input.
5. Return the minimum value found, and the two complementary subsets of the
original integer set

{ 1 ,..., n } that give rise to this value.

getHalfSet2[n , opts ]:=Module[

getHalfSet2[n , opts getHalfSet2[n , opts ]:=Module[ ]:=Module[

{ vars , x , nmin , vals , ranges , s1 } ,

{ { vars , x , nmin , vals , ranges , s1 vars , x , nmin , vals , ranges , s1 } } , ,

vars = Array[ x , n ]; vars = Array[ x , n ];

ranges = Map[(0 ranges = Map[(0 ranges = Map[(0 ≤ ≤ ≤ # # # ≤ ≤ ≤ 1)& , vars]; 1)& , vars]; 1)& , vars];

{ { { nmin , vals =

NMinimize[

nmin , vals nmin , vals } } } = =

NMinimize[ NMinimize[ { { { spfun2[vars] , spfun2[vars] , spfun2[vars] ,

Join[ranges , Join[ranges , Join[ranges , { { { Element[vars , Integers] , To tal[vars]== n / 2 Element[vars , Integers] , To tal[vars]== n / 2 Element[vars , Integers] , To tal[vars]== n / 2 } } } ] ] ] } } } , vars , opts]; , vars , opts]; , vars , opts];

s1 = Select[Inner[Times , Range[ n ] , (vars/.vals) , List] , # s1 = Select[Inner[Times , Range[ n ] , (vars/.vals) , List] , # s1 = Select[Inner[Times , Range[ n ] , (vars/.vals) , List] , # = 0&]; = 0&]; = 0&];

{ { { nmin , nmin , nmin , { { { s1 , Complement[Range[ n ] , s1] s1 , Complement[Range[ n ] , s1] s1 , Complement[Range[ n ] , s1] }} }} }} ] ] ]

Timing[ Timing[

{ { { min , min , min , { { { s1 , s2 s1 , s2 s1 , s2 }} }} }} = getHalfSet2[100 , MaxIterations = getHalfSet2[100 , MaxIterations = getHalfSet2[100 , MaxIterations → → → 1000 , Method 1000 , Method 1000 , Method → → →

{ { { DifferentialEvolution , CrossProbability DifferentialEvolution , CrossProbability DifferentialEvolution , CrossProbability → → → . 8 , SearchPoints . 8 , SearchPoints . 8 , SearchPoints → → → 100 100 100 } } } ]] ]] ]]

{ 1732 . 97 , { 0 . 000251303 ,

{ 1 , 4 , 5 , 7 , 12 , 13 , 14 , 15 , 16 , 19 , 20 , 22 , 23 , 31 , 32 , 36 , 37 , 38 , 41 , 42 ,

43 , 44 , 45 , 46 , 47 , 49 , 50 , 51 , 52 , 55 , 59 , 60 , 62 , 65 , 66 , 71 , 73 , 78 ,
79 , 83 , 84 , 87 , 88 , 89 , 90 , 91 , 94 , 97 , 99 , 100 } ,