Forward Backward Transformation - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 75

The total cost for this tour is 11.
The objective of TSP optimisation is to find a tour with the minimal value. Assume
now another tour A → D → C → E → B → A . The graphical representation is given in

Fig 3.21.
The cost for this new tour is 8, which is a decrease from the previous tour of 11. This
is now an improved tour. Likewise many other tours can be found which have better
values.

3.8.2 Experimentation on Symmetric TSP

Symmetric TSP problem is one, where the distance between two cities is the same to
and fro . This is considered the easiest branch of TSP problem.
The operational parameters for TSP is given in Table 3.42.
Experimentation was conducted on the City problem instances. These instances are
of 50 cities and the results are presented in Table 3.43. Comparison was done with Ant
Colony (ACS) [11], Simulated Annealing (SA) [21], Elastic Net (EN) [12], and Self
Organising Map (SOM) [17]. The time values are presented alongside.
In comparison, ACS is the best performing heuristic for TSP. EDE performs well,
with tolerance of 0.1 from the best performing heuristics on average.

3.8.3 Experimentation on Asymmetric TSP

Asymmetric TSP is the problem where the distance between the different cities is dif-
ferent, depending on the direction of travel. Five different instances were evaluated and
compared with Ant Colony (ACS) with local search [11]. The experimetational results
are given in Table 3.44.

Table 3.42. EDE TSP operational values

Parameter Value

Strategy 9

CR 0.9

F 0.1

Table 3.43. EDE STSP comparison

Instant ACS SA EN SOM EDE

(average) (average) (average) (average) (average)

City set 1 5.88 5.88 5.98 6.06 5.98

City set 2 6.05 6.01 6.03 6.25 6.04

City set 3 5.58 5.65 5.7 5.83 5.69

City set 4 5.74 5.81 5.86 5.87 5.81

City set 5 6.18 6.33 6.49 6.7 6.48