Information Technology Reference
In-Depth Information
Ta b l e 1 . 2 .
DE Strategies
Strategy
Formulation
x
(
G
)
r
2
r
3
x
(
G
)
best
x
(
G
)
Strategy 1: DE/best/1/exp:
v
=
+
F
•
−
x
(
G
)
r
2
r
3
x
(
G
)
r
1
x
(
G
)
Strategy 2: DE/rand/1/exp:
v
=
+
F
•
−
x
(
G
)
best
x
(
G
)
r
1
r
2
x
(
G
)
i
x
(
G
)
i
x
(
G
)
Strategy 3: DE/rand-to-best/1/exp
v
=
+
λ
•
−
+
F
•
−
x
(
G
)
r
1
r
4
x
(
G
)
best
x
(
G
)
r
2
x
(
G
)
r
3
x
(
G
)
Strategy 4: DE/best/2/exp:
v
=
+
F
•
+
−
−
x
(
G
)
r
1
r
4
x
(
G
)
r
5
x
(
G
)
r
2
x
(
G
)
r
3
x
(
G
)
Strategy 5: DE/rand/2/exp:
v
=
+
F
•
+
−
−
x
(
G
)
r
2
r
3
x
(
G
)
best
x
(
G
)
Strategy 6: DE/best/1/bin:
v
=
+
F
•
−
x
(
G
)
r
2
r
3
x
(
G
)
r
1
x
(
G
)
Strategy 7: DE/rand/1/bin:
v
=
+
F
•
−
x
(
G
)
best
x
(
G
)
r
1
r
2
x
(
G
)
i
x
(
G
)
i
x
(
G
)
Strategy 8: DE/rand-to-best/1/bin:
v
=
+
λ
•
−
+
F
•
−
x
(
G
)
r
1
r
4
x
(
G
)
best
x
(
G
)
r
2
x
(
G
)
r
3
x
(
G
)
Strategy 9: DE/best/2/bin
v
=
+
F
•
+
−
−
x
(
G
)
r
1
r
4
x
(
G
)
r
5
x
(
G
)
r
2
x
(
G
)
r
3
x
(
G
)
Strategy 10: DE/rand/2/bin:
v
=
+
F
•
+
−
−
is added to the third one. Similarly for perturbation with two vector differences, five
distinct vectors other than the target vector are chosen randomly from the current pop-
ulation. Out of these, the weighted vector difference of each pair of any four vectors is
added to the fifth one for perturbation.
In exponential crossover, the crossover is performed on the
D
(the dimension or
number of variables to be optimized) variables in one loop until it is within the
CR
bound. For discrete optimization problems, the first time a randomly picked number
between
0
and
1
goes beyond the
CR
value, no crossover is performed and the remaining
D
variables are left intact. In binomial crossover, the crossover is performed on each
the D variables whenever a randomly picked number between
0
and
1
is within the
CR
value. Hence, the exponential and binomial crossovers yield similar results.
1.3
Differential Evolution for Permutative
−
Based Combinatorial
Optimization Problems
The canonical DE cannot be applied to discrete or permutative problems without modi-
fication. The internal crossover and mutation mechanism invariably change any applied
value to a real number. This in itself will lead to infeasible solutions. The objective
then becomes one of transformation, either that of the population or that of the internal
crossover/mutation mechanism of DE. A number of researchers have decided not to
modify in any way the operation of DE strategies, but to manipulate the population in
such a way as to enable DE to operate unhindered. Since the solution for a population
is permutative, suitable conversion routines are required in order to change the solution
from integer to real and then back to integer after crossover.
Application areas where DE for permutative-based combinatorial optimization prob-
lems can be applied include but not limited to the following:
Search WWH ::
Custom Search