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

Table 3.44. EDE ATSP comparison

Instant Optimal ACS 3-OPT ACS 3-OPT EDE

best average

p43 5620 5620 5620 5639

ry48p 14422 14422 14422 15074

ft70 38673 38673 38679.8 40285

kro124p 36230 36230 36230 41180

ftv170 2755 2755 2755 6902

City Set 1 History

6.02

6.00

5.98

5.96

5.94

5.92

5.90

5.88

0 20 40 60 80 100

Number of Generations

Fig. 3.22. Sample output of the City set 1 problem

ACS heuristic performs very well, obtaining the optimal value, whereas EDE has an
average performance. The difference is that ACS employs 3 − Opt local search on each

generation of its best solution, where as EDE has a 2 − Opt routine valid only in local

optima stagnation.
A sample generation for City set 1 problem is given in Fig 3.22.

3.9 Analysis and Conclusion

One the few ways in which the validation of a permutative approach for a real domain
based heuristic can be done is empirically; through expensive experimentation's across
different problem classes, as attempted here. Through the results obtained, it can be
stated that EDE is a valid approach for permutative problems. One of the differing evi-
dent features, is that the operating parameters for each class of problems is unique. No