Information Technology Reference
In-Depth Information
Procedure DE GT SP
Set CR
,
F
,
NP
,
TerCriterion
X
=
x
1
,
x
2
,..,
x
NP
f
π
i
←
x
i
i
:=1
,
2
,..,
NP
←
x
i
= 2
opt
π
i
←
x
i
i
=1
,
2
,..,
NP
i
π
=
LS
π
i
←
x
i
i
=1
,
2
,..,
NP
0
i
←
x
i
0
π
←
x
i
= arg min
f
π
i
←
x
i
i
=1
,
2
,..,
NP
g
π
g
←
x
i
π
B
:= π
k
:= 1
while
Not TerCriterion
do
v
ij
:=
x
ia
+
F
x
ib
+
x
ic
i
:=1
,
2
,..,
NP
,
j
=1
,
2
,..,
m
u
ij
=
v
ij
if r
ij
<
CR or j
=
D
j
x
k
−
1
ij
ot herwise
i
=1
,
2
,..,
NP
,
j
=1
,
2
,..,
m
f
π
i
←
u
i
i
:=1
,
2
,..,
NP
= 2
opt
π
i
←
u
i
i
=1
,
2
,..,
NP
i
←
u
i
π
=
LS
π
i
←
u
i
i
=1
,
2
,..,
NP
k
i
←
u
i
k
π
x
i
=
u
i
if f
π
←
u
i
<
f
i
k
−
1
i
←
x
k
−
1
i
π
x
k
−
1
i
ot herwise
i
=1
,
2
,..,
NP
g
←
x
g
= arg min
f
π
←
x
i
,
f
π
i
k
−
1
←
x
k
−
1
g
π
g
i
:=1
,
2
,..,
NP
π
B
= arg min
f
(π
B
)
,
f
π
g
←
x
g
k
:=
k
+ 1
endwhile
ret urn
π
B
Fig. 5.4.
The DE Algorithm with Local Search Heuristics
instances from the TSPLIB library [23]. The benchmark set with optimal objective
function values for each of the problems is obtained through a personal communication
with Dr. Lawrence V. Snyder. The benchmark set contains between 51 (11) and 442
(89) nodes (clusters) with Euclidean distances and the optimal objective function value
for each of the problems is available. The DE algorithm was coded in Visual C++ and
run on an Intel Centrino Duo 1.83 GHz Laptop with 512MB memory.
We consider the RKGA by Snyder & Daskin [26] for comparison in this paper due to
the similarity in solution representation. The population size is taken as 100. Cross-over
and mutation probability are taken as 0.9 and 0.2, respectively. To be consistent with
Snyder & Daskin [26], the algorithm is terminated when 100 generations have been
carried out or when 10 consecutive generations have failed to improve the best-known
Search WWH ::
Custom Search