Discrete/Binary Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 159

terms of CPU times, the paired t -test on the CPU times confirms that the differences
between DDE and mrOXGA were significant since the p -values was 0.020, whereas
it was failed to reject the null hypothesis of being equal difference between DDE and
RKGA due to the p -value of 0.129. Briefly, the paired t -test indicates that DDE was
able to generate lower objective function values with less CPU times than mrOXGA.
On the other hand, DDE yielded much better objective function values with identical
CPU times than RKGA.

6.5 Conclusions

A DDE algorithm is presented to solve the GTSP on a set of benchmark instances rang-
ing from 51 (11) to 1084 (217) nodes (clusters). The contributions of this paper can
be summarized as follows. A unique solution representation including both cluster and
tour information is presented, which handles the GTSP properly when carrying out the
DDE operations. To the best of our knowledge, this is the first reported application of
the DDE algorithm applied to the GTSP. The perturbation scheme is presented in the
destruction procedure. Furthermore, the DDE algorithm is donated with very effective
local search methods, 2-opt and SWAP procedure, in order to further improve the so-
lution quality. Ultimately, the DDE algorithm was able to find optimal solutions for a
large percentage of problem instances from a set of test problems from the literature.
It was also able to further improve 8 out of 9 larger instances from the literature. Both
solution quality and computation times are competitive to or even better than the best
performing algorithms from the literature. In particular, its performance on the larger
instances is noteworthy.

Acknowledgement

P. Suganthan acknowledges the financial support offered by the A ∗ Star (Agency for
Science, Technology and Research) under the grant # 052 101 0020.

References

1. Babu, B., Onwubolu, G.: New Optimization Techniques in Engineering. Springer, Germany
(2004)
2. Bean, J.: Genetic algorithms and random keys for sequencing and optimization. ORSA, Jour-
nal on Computing 6, 154-160 (1994)
3. Ben-Arieh, D., Gutin, G., Penn, M., Yeo, A., Zverovitch, A.: Process planning for rotational
parts using the generalized traveling salesman problem. Int. J. Prod. Res. 41(11), 2581-2596
(2003)
4. Chentsov, A., Korotayeva, L.: The dynamic programming method in the generalized travel-
ing salesman problem. Math. Comput. Model. 25(1), 93-105 (1997)
5. Corne, D., Dorigo, M., Glover, F.: Differential Evolution, Part Two. In: New Ideas in Opti-
mization, pp. 77-158. McGraw-Hill, New York (1999)
6. Dimitrijevic, V., Saric, Z.: Efficient Transformation of the Generalized Traveling Salesman
Problem into the Traveling Salesman Problem on Digraphs. Information Science 102, 65-
110 (1997)