Discrete Set Handling - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 201

Table 7.29. STSP comparison results

Instance Optimal AC S 3 opt SA 3 opt SOM FI 3 opt DE DSH

City 1 5.84 0 0 0 0.002 0.002

City 2 5.99 0.002 0 0.002 0 0.03

City 3 5.57 0 0 0.002 0 0.059

City 4 5.06 0.12 0.12 0 0.13 0.16

City 5 6.17 0 0 0.003 0.03 0.01

Table 7.30. General STSP comparison results

Instance Optimal AC S 3 opt DE DSH

att532 27,686 0 0.17

d198 15,780 0.006 0.54

eil51 426 - 0.08

eil76 538 - 0.1

fl1577 8,806 0.03 1.23

kroA100 21,282 0 0.56

pcb442 50,779 0.01 0.32

rat783 8,806 - 0.92

Average 0.49

The results are presented in Table 7.29 as percentage increase upon the reported
optimal as given in Equation 7.15.
In this instance, DE DSH , was competitive to the other performing heuristics. As
shown, no one heuristic was able to find all optimal values, and some heuristic per-
formed better than other for specific instances.
The second set of experiment was conducted on some selective TSP instances [23].
The results are presented in Table 7.30.
The comparison is done with AC S 3 opt of [4]. ACS performs very well, almost achiev-
ing the optimal solution. DE DSH performs well, obtaining on average 0.49% to the op-
timal results for the entire set. The set contains instance s ranging from sizes of 51 to
1577 cities.

7.6.4.2 Asymmetric Traveling Salesman

The second set of problems is that, which involves the asymmetric TSP. Asymmetric
TSP is one where the distances between two cities are not equal, to and from. This
implies that going from one city to another has a different distance than coming back
from that city to the original one. The results are presented in Table 7.31.
The results for ATSP are on average 1.112% over the optimal value. However, it
should be noted that the experimentation values was kept stagnant to fixed values, even
as the problem size was increased, hence the trend of worsening solutions as problem
size increases.