Information Technology Reference
In-Depth Information
•
Step 1: Initialization
-S t
t
=0,
NP
=100
-
Generate
NP
individuals randomly as in Table 5.1,
X
i
,
i
= 1
,
2
,...,
NP
where
X
i
=
x
i
1
,
x
i
2
,...,
x
in
.
i
=
π
in
of individual
X
i
0
0
i
1
,
0
i
2
,...,
0
-
Apply the SPV rule to find the tour
π
π
π
for
i
= 1
,
2
,...,
NP
.
Evaluate each individual
i
in the population using the objective function
f
i
-
π
X
i
for
i
= 1
,
2
,...,
NP
.
o
i
←
•
Step 2: Update generation counter
-
t
=
t
+ 1
•
Step 3: Generate mutant population
-
For each target individual,
X
i
,
i
= 1
,
2
,...,
NP
, at generation
t
, a mutant individ-
ual,
V
i
=
v
i
1
,
v
i
2
,...,
v
in
, is determined such that:
V
i
=
X
t
−
1
+
F
X
t
−
1
b
i
X
t
−
1
c
i
−
(5.2)
a
i
where
a
i
,
b
i
and
c
i
are three randomly chosen individuals from the population
such that (
a
i
=
b
i
=
c
i
).
•
Step 4: Generate trial population
-
Following the mutation phase, the crossover (re-combination) operator is applied
to obtain the trial population. For each mutant individual,
V
i
=
v
i
1
,
v
i
2
,...,
v
in
,
an integer random number between 1 and
n
,i.e.,
D
i
∈
(1
,
2
,...,
n
), is chosen, and
a trial individual,
U
i
=
u
i
1
,
u
i
2
,...,
u
in
is generated such that:
u
t
ij
=
v
t
ij
,
if r
t
ij
≤
CR or j
=
D
i
(5.3)
x
t
−
1
ij
,
Ot herwise
where the index
D
refers to a randomly chosen dimension (
j
= 1
,
2
,...,
n
), which
is used to ensure that at least one parameter of each trial individual
U
i
differs
from its counterpart in the previous generation
U
t
−
i
,
CR
is a user-defined cross-
over constant in the range (0, 1), and
r
t
ij
is a uniform random number between
0 and 1. In other words, the trial individual is made up with some parameters
of mutant individual, or at least one of the parameters randomly selected, and
some other parameters of target individual.
•
Step 5: Find tour
-
i
=
π
in
for
i
= 1
,
2
,...,
NP
.
t
t
t
t
Apply the SPV rule to find the tour
π
i
1
,
π
i
2
,...,
π
•
Step 6: Evaluate trial population
-
Evaluate the trial population using the objective function
f
i
(
t
U
i
) for
i
=
π
i
←
1
,
2
,...,
NP
.
•
Step 7: Selection
-
To decide whether or not the trial individual
U
i
should be a member of the
target population for the next generation, it is compared to its counterpart target
individual
X
t
−
i
at the previous generation. The selection is based on the survival
of fitness among the trial population and target population such that:
X
i
=
U
i
,
f
π
t
i
U
i
)
t
−
1
X
t
−
1
i
if f
(
π
←
≤
←
i
(5.4)
X
t
−
1
i
,
ot herwise
Search WWH ::
Custom Search