Information Technology Reference
In-Depth Information
Table 6.18. Selection For Next Generation
j
1
2
3
4
5
X i
n j
3
5
2
1
4
π j
12
23
8
4
19
U i
n j
2
1
3
5
4
π j
8
4
15
25
17
Assume that f ( U i ) f ( X i ) X i = U i
U i
n j
2
1
3
5
4
π j
8
4
15
25
17
and insert mutation operators are employed. Given the individual and the global best
(best so far solution for DDE) solution, the global best solution is first mutated by using
equation 6.1. For example, in Table 6.15, the dimensions u =3 is chosen randomly with
its corresponding cluster and node. Node
3 = 24 from
the same cluster n u = n 3 = 5, thus resulting in the mutant individual V i . Then the mutant
individual V i is recombined with its corresponding individual X i in the target population
to generate the trial individual U i by using equation 6.2. Finally, the target individual X i
is compared to the trial individual U i to determine which one would survive for the next
generation based on the survival of the fittest by using equation 6.3.
π
u =
π
3 = 25 is replaced by
π
u =
π
6.3
Hybridization with Local Search
The hybridization of DE algorithm with local search heuristics is achieved by per-
forming a local search phase on every trial individual generated. The SWAP proce-
dure [30], denoted as LocalSearchSD in this chapter, and the 2-opt heuristic [16] were
separately applied to each trial individual. The 2-opt heuristic finds two edges of a
tour that can be removed and two edges that can be inserted in order to generate a new
tour with a lower cost. More specifically, in the 2-opt heuristic, the neighborhood of a
tour is obtained as the set of all tours that can be replaced by changing two nonadjacent
edges in that tour. Note that the 2-opt heuristic is employed with the first improvement
strategy in this study. The pseudo code of the local search ( LS ) procedures is given in
Fig 6.2.
As to the LocalSearchSD procedure, it is based on the SWAP procedure and is
basically concerned with removing a node from a cluster and inserting a different node
from that cluster into the tour. The insertion is conducted using a modified nearest-
neighbour criterion, so that the new node may be inserted on the tour in a spot different.
Each node in the cluster is inserted into all possible spots in the current solution and
the best insertion is replaced with the current solution. The SWAP procedure of Snyder
& Daskin [30] is outlined in Fig 6.3, whereas the proposed DDE algorithm is given in
Fig 6.4. Note that in SWAP procedure, the followings are given such that tour T ;set V j ;
node j
V j , j
T ; distances d uv between each u , v
V .
Search WWH ::




Custom Search