Information Technology Reference
In-Depth Information
Deviation comparison of different heuristics with local search
1.4
DE
DSHX
DE
DSHX
1.2
DE
DSHX
DE
DSHX
1.0
DE
SPVX
DE
SPVX
DE
SPVX
0.8
DE
SPVX
DE
SPVX
0.6
DE
SPVX
DE
SPVX
DE
DSHX
DE
DSHX
DE
DSHX
DE
DSHX
0.4
DE
SPVX
DE
SPVX
DE
DSHX
DE
DSHX
DE
SPVX
0.2
0.0
20 x5
20 x10
20 x20
50 x5
50 x10
50 x20
100 x5
100 x10 100 x20 200 x10
Data Sets Taillard
Fig. 7.49.
Deviation display of different heuristics with local search
7.6.4
Traveling Salesman Problem Results
7.6.4.1
Symmetric Traveling Salesman
The second set of problem set to be considered is the Traveling Salesman Problem
(TSP). TSP is a widely realized problem with many applications in real life problems.
However, to compensate for its myriad usage, a number of targeted heuristics have
evolved to solve it; often to optimal as is the case for all for all known problem instance
in the TSPLIB. For evolutionary heuristics to operate in TSP, it has become a norm for
them to employ local search, usually 3 opt [4]. Utilizing local search heuristics always
improve the quality of the results of the solutions, since triangle inequality rule and
Lin
Kernigham are very robust
deterministic
search heuristics.
The operating parameters for the TSP is given in Table 7.28.
A sample of TSP problem is given in Table 7.28. Comparison is done with the Ant
Colony (AC), Simulated Annealing (SA), Self Organising Map (SOM) and Furthest
Insertion(FI)of[4].
−
avg
=
H
−
U
Δ
(7.15)
U
Table 7.28.
DE
DSH
TSP operating parameters
Parameters
CR
F
NP
Gen
Value
0.4
0.1
500
700
Search WWH ::
Custom Search