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

Table 7.31. General ATSP comparison results

Instance Optimal AC S 3 opt DE DSH

ft70 38673 0.001 0.96

ftv170 2755 0.002 2.32

kro124p 36230 0 1.57

p43 5620 0 0.24

ry48p 14422 0 0.47

Average 1.112

7.7 Conclusion

Differential Evolution is an effective heuristic for optimization. This approach was an
attempt to show it effectiveness in permutative problems. The key approach was to
keep the conversion of the operational domain as simple as possible, as shown in this
variant of discrete set handling. Simplicity removes excess computation overhead to
this heuristic while at the same time delivering comparative results.
Two different problem scopes of Flow Shop scheduling and Traveling Salesman
problems were attempted. This was done in order to show that this generic version
of DE is able to work in different classes of problems, and not simply tailor made for
a special class. The core research focused on Flow Shop with Traveling Salesman pro-
viding a secondary comparison.
A principle direction as seen in this research has been the tuning of the heuristic.
Researchers, who generally take the default values, often overlook this process, however
it is imperative to check for the best values. As shown from the obtained results, the
operating values obtained for the two different problems were unique in all aspects.
The results obtained can be visualized as competitive for their own classes. The
most promising is the results obtained for Flow Shop, and the worst performing is the
Asymmetric Traveling Salesman. It is believed that a better local search heuristic, like
Lin

Kernighan or a 3 Opt heuristic will further improve the quality of the solutions.
Further directions for this approach will involve further testing with other problem
classes like Vehicle Routing and Quadratic Assignment, which are also realised in real
systems.

−

Acknowledgement

This work was supported by grant No. MSM 7088352101 of the Ministry of Education
of the Czech Republic and by grants of the Grant Agency of the Czech Republic GACR
102/06/1132.

References

1. Bland, G., Shallcross, D.: Large traveling salesman problems arising fromexperiments in X-
ray crystallography: A preliminary report on computation. OpersRes. Lett. 8, 125-128 (1989)
2. Croes, G.: A method for solving traveling salesman problems. Oper. Res. 6, 791-812 (1958)