Information Technology Reference
In-Depth Information
CostFunction
Compile
Solution,
Integer, 1
,
Distance,
Real, 2
,
Size,
Integer
,
Module
Time
0.0
,
Time
Distance
Solution
1
, Solution
&
Range
Size
1
;
Time
Distance
Solution
1
, Solution
Size
; Return
Time
Fig. 7.36.
Traveling Salesman routine
Once all the related city distances have been added, the distance from the
last
city to
the
first
city is added to complete the
tour
, given as:
Time+=(Distance[[Solution[[1]]
,
Solution[[Size]]]])
7.5
DE Example
The simplest approach of explaining the application of discrete set handling is to im-
plement a worked example. In that respect, a TSP problem is proposed with only five
cities, in order to make it more viable.
Assume a symmetric TSP problem given as in Table 7.2. Symmetric implies that the
distances between the two cities are equal both ways of travelling.
Ta b l e 7 . 2 .
Symmetric TSP problem
Cities
A
B
C
D
E
A0
5
10
14
24
B
5
0
5
9
19
C
10
5
0
10
14
D14
9
10
0
10
E
24
19
14
10
0
Ta b l e 7 . 3 .
Decomposed symmetric TSP problem
Cities A
B
C
D
E
A
0
B
5
0
C
10
5
0
D
14
9
10
0
E
24
19
14
10
0
Since this is a symmetric TSP problem, the
Distance Matrix
can be decomposed to
the leading triangle as given in Table 7.3.
In order to use DE, some operational parameters are required, in this case the tuning
parameters of
CR
and
F
, and well as the size of the population
NP
and the number
of generations
Gen
. For the purpose of this example, the population is specified as 10
individuals.
Search WWH ::
Custom Search