Information Technology Reference
In-Depth Information
The aim of the research was to ascertain the feasibility of DE to solve a unique class
of problems; Permutative Problems. Permutative problems belong to the Nondetermin-
istic Polynomial
Time hard (NP hard) problems. A problem is assigned to such a class
if it is solvable in polynomial time by a nondeterministic Turing Machine.
Two different versions of permutative DE are presented. The first is the Discrete
Differential Evolution [23, 26, 6] and its superset Enhanced Differential Evolution
Algorithm [8, 9].
−
3.2
Differential Evolution
In order to describe DE, a schematic is given in Fig 3.1.
There are essentially five sections to the code. Section 1 describes the input to the
heuristic.
D
is the size of the problem,
G
max
is the maximum number of generations,
NP
is the total number of solutions,
F
is the scaling factor of the solution and
CR
is
the factor for crossover.
F
and
CR
together make the internal tuning parameters for the
heuristic.
Section 2 outlines the initialisation of the heuristic. Each solution
x
i
,
j
,
G
=0
is created
randomly between the two bounds
x
(
lo
)
and
x
(
hi
)
. The parameter
j
represents the in-
dex to the values within the solution and
i
indexes the solutions within the population.
So, to illustrate,
x
4
,
2
,
0
represents the second value of the fourth solution at the initial
generation.
After initialisation, the population is subjected to repeated iterations in section 3.
Section 4 describes the conversion routines of DE. Initially, three random numbers
r
1
,
r
2
,
r
3
are selected, unique to each other and to the current indexed solution
i
in the
population in 4.1. Henceforth, a new index
j
rand
is selected in the solution.
j
rand
points
to the value being modified in the solution as given in 4.2. In 4.3, two solutions,
x
j
,
r
1
,
G
and
x
j
,
r
2
,
G
are selected through the index
r
1
and
r
2
and their values subtracted. This
1
.
Input :
D
,
G
max
,
NP
≥
4
,
F
∈
(0
,
1+)
,
CR
∈
[0
,
1]
,
and initial bounds :
x
(
lo
)
,
x
(
hi
)
.
2
.
Initialize :
x
(
hi
)
j
∀
i
≤
NP
∧∀
j
≤
D
:
x
i
,
j
,
G
=0
=
x
(
lo
)
−
x
(
lo
)
j
+
rand
j
[0
,
1]
•
j
i
=
{
1
,
2
,...,
NP
},
j
=
{
1
,
2
,...,
D
},
G
= 0
,
rand
j
[0
,
1]
∈
[0
,
1]
⎨
⎩
3
.
While
G
<
G
max
⎨
⎩
4
.
Mutate and recombine :
4
.
1
r
1
,
r
2
,
r
3
∈{
1
,
2
,....,
NP
},
randomly selected
,
except :
r
1
=
r
2
=
r
3
=
i
4
.
2
j
rand
∈{
1
,
2
,...,
D
},
randomly selected once each
i
⎨
⎩
x
j
,
r
3
,
G
+
F
·
(
x
j
,
r
1
,
G
−
x
j
,
r
2
,
G
)
if (
rand
j
[0
,
1]
<
CR
∨
j
=
j
rand
)
x
j
,
i
,
G
∀
i
≤
NP
4
.
3
∀
j
≤
D
,
u
j
,
i
,
G
+1
=
otherwise
5
.
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.1.
Canonical Differential Evolution Algorithm
Search WWH ::
Custom Search