Information Technology Reference
In-Depth Information
from its counterpart in the previous generation
U
k
−
i
,
CR
is a user-defined cross-
over constant in the range (0, 1), and
r
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: Evaluate trial population
-
Evaluate the trial population using the objective function
f
i
U
i
for
i
=
k
i
←
π
1
,
2
,...,
NP
.
•
Step 6: 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
k
−
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
,
if f
π
U
i
≤
f
π
k
i
k
−
1
i
X
k
−
1
i
←
←
(6.7)
X
t
−
1
i
,
ot herwise
•
Step 7: Stopping criterion
-
If the number of generations exceeds the maximum number of generations, or
some other termination criterion, then stop; otherwise go to step 2
6.2.3
NEH Heuristic
Due to the availability of the insertion methods from the TSP literature, which are mod-
ified in this chapter, it is possible to apply the NEH heuristic of Nawaz et al. [17] to the
GTSP. Without considering cluster information for simplicity, the NEH heuristic for the
GTSP can be summarized as follows:
1. Determine an initial tour of nodes. Let this tour be
π
.
2. The first two nodes (that is,
π
2
) are chosen and two possible partial tours of
these two nodes are evaluated. Note that since a tour must be a Hamiltonian cycle,
partial tours will be evaluated with the first node being the last node as well. As an
example, partial tours, (
π
1
and
π
2
) are evaluated first.
3. Repeat the following steps until all nodes are inserted. In the
k
th
π
1
,
π
2
,
π
1
) and (
π
2
,
π
1
,
π
k
at
position
k
is taken and tentatively inserted into all the possible
k
positions of the
partial tour that are already partially completed. Select of these
k
tentative partial
tours the one that results in the minimum objective function value or a cost function
suitably predefined.
To picture out how the NEH heuristic can be adopted for the GTSP, consider a solu-
tion with five nodes as
step, node
. Following example illustrates the implemen-
tation of the NEH heuristic for the GTSP:
π =
{
3
,
1
,
4
,
2
,
5
}
1. Current solution is
}
2. Evaluate the first two nodes as follows:
π
=
{
3
,
1
,
4
,
2
,
5
. Assume that the first
partial tour has a better objective function value than the second one. So the current
partial tour will be
{
3
,
1
,
3
}
and
{
1
,
3
,
1
}
{
3
,
1
}
.
Search WWH ::
Custom Search