Information Technology Reference
In-Depth Information
bounds :
x
(
lo
)
,
x
(
hi
)
.
Input :
D
,
G
max
,
NP
≥
4
,
F
∈
(
0
,
1
+)
,
CR
∈
[
0
,
1
]
,
⎧
⎨
⎩
D
x
i
,
j
,
G
=
0
x
(
hi
)
j
x
(
lo
j
x
(
lo
)
j
=
+
rand
j
[
0
,
1
]
•
−
∀
i
≤
NP
∧∀
j
≤
∈
x
0
,
i
x
j
−
1
,
i
Initialize :
ifx
j
,
i
,
x
1
,
i
, ...,
i
=
{
1
,
2
, ...,
NP
},
j
=
{
1
,
2
, ...,
D
},
G
=
0
,
rand
j
[
0
,
1
]
∈
[
0
,
1
]
Cost :
∀
i
≤
NP
:
f
(
x
i
,
G
=
0
)
⎨
⎩
While
G
<
G
max
⎧
⎨
⎩
Mutate and recombine :
r
1
,
r
2
,
r
3
∈{
1
,
2
, ....,
NP
},
randomly selected
,
except :
r
1
=
r
2
=
r
3
=
i
j
rand
∈{
1
,
2
, ...,
D
},
randomly selected once each
i
γ
G
←
x
j
,
r
3
,
G
:
γ
G
←
x
j
,
r
1
,
G
:
γ
G
←
x
j
,
r
2
,
G
⎧
⎨
⎩
j
,
r
3
,
j
,
r
1
,
j
,
r
2
,
Forward Transformation
∀
≤
,
=
γ
+
F
·
(
γ
−γ
)
j
D
u
j
,
i
,
G
+
1
j
,
r
3
,
G
j
,
r
1
,
G
j
,
r
2
,
G
if
(
rand
j
[
0
,
1
]
<
CR
∨
j
=
j
rand
)
γ
G
←
x
j
,
i
,
G
otherwise
u
i
,
G
+
1
j
,
i
,
=
ρ
1
←
ϕ
1
Backward Transformation
∀
i
≤
NP
j
,
i
,
G
+
j
,
i
,
G
+
Recursive Mutation :
⎨
⎩
u
i
,
G
+
1
if
u
j
,
i
,
G
+
1
=
u
1
,
i
,
G
+
1
u
j
−
1
,
i
,
G
+
1
, ..,
u
i
,
G
+
1
=
x
(
lo
)
≤
x
(
hi
)
u
j
,
i
,
G
+
1
≤
x
i
,
G
otherwise
Select :
x
i
,
G
+
1
u
i
,
G
+
1
if
f
(
u
i
,
G
+
1
)
≤
f
(
x
i
,
G
)
=
x
i
,
G
otherwise
G
=
G
+
1
Fig. 3.2.
DDE schematic
Recursive mutation refers to the fact that if a solution is deemed in-feasible, it is
discarded and the parent solution is retained in the population as given in Equation 3.6.
The general schematic is given in Figure 3.2.
A number of experiments were conducted by DDE on Flowshop Scheduling prob-
lems. These are collectively given in the results section of this chapter.
3.4
Enhanced Differential Evolution
Enhanced Differential Evolution (EDE) [7, 8, 9], heuristic is an extension of the DDE
variant of DE. One of the major drawbacks of the DDE algorithm was the high fre-
quency of in-feasible solutions, which were created after evaluation. However, since
DDE showed much promise, the next logical step was to devise a method, which would
repair the in-feasible solutions and hence add viability to the heuristic.
To this effect, three different repairment strategies were developed, each of which
used a different index to repair the solution. After repairment, three different enhance-
ment features were added. This was done to add more depth to the code in order to solve
permutative problems. The enhancement routines were standard mutation, insertion and
local search. The basic outline is given below.
1.
Initial Phase
a)
Population Generation
: An initial number of discrete trial solutions are gener-
ated for the initial population.
Search WWH ::
Custom Search