Motivation for Differential Evolution for Permutative-Based Combinatorial Problems - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 4

−
based combinatorial optimization and they have found that DE is quite appropriate
for combinatorial optimization and that it is effective and competitive with other ap-
proaches in this domain. Some of the DE permutative

Over the years, some researchers have been working in the area of DE permutative

− based combinatorial optimiza-

tion approaches that have proved effective include:

1. Forward/Backward Transformation Approach;
2. Relative Position Indexing Approach;
3. Smallest Position Value Approach;
4. Discrete/Binary Approach; and
5. Discrete Set Handling Approach.

These approaches have been applied to combinatorial optimization problems with
competitive results when compared to other optimization approaches, and they form
the basis for writing this topic. The remainder of this topic explores available DE ap-
proaches for solving permutative-based combinatorial problems. Although there have
been discussions regarding DE approaches that rely to varying degrees on repair mecha-
nisms, it is now generally agreed that in order to solve permutative-based combinatorial
problems, it is necessary to employ some heuristics as some other evolutionary com-
putation approaches do, rather than insisting on approaches that generate only feasible
solutions. Each method proposes an analog of DE s differential mutation operator to
solve permutative-based combinatorial problems.

1.2 Canonical Differential Evolution for Continuous Optimization

Problems

The parameters used in DE are = cost or the value of the objective function, D =

problem dimension, NP = population size, P = population of X

ℑ

vectors, G = generation
number, Gmax = maximum generation number, X = vector composed of D parameters,
V = trial vector composed of D parameters, CR = crossover factor. Others are F =
scaling factor (0 < F

−

≤ 1 . 2), (U) = upper bound, (L) = lower bound, u ,and v =trial

vectors, x ( G )

best = vector with minimum cost in generation G , x ( G )

= ith vector in generation

i

G, b ( G )
i

= ith buffer vector in generation G , x ( G )

r 1 , x ( G )

= randomly selected vector, L

r 2

= random integer (0 < L < D − 1). In the formulation, N = number of cities. Some

integers used are i, j .
Differential Evolution (DE) is a novel parallel direct search method, which utilizes
NP parameter vectors

x ( G )
i

, i = 0 , 1 , 2 ,..., NP − 1 (1.4)

as a population for each generation, G . The population size, NP does not change dur-
ing the minimization process. The initial population is generated randomly assuming a
uniform probability distribution for all random decisions if there is no initial intelligent
information for the system. The crucial idea behind DE is a new scheme for generating
trial parameter vectors. DE generates new parameter vectors by adding the weighted
difference vector between two population members to a third member. If the resulting