Quantifying Ordinal Performance of Ant Colony Optimization

Abstract:

In contrast to many successful applications of ant colony optimization, the theoretical foundation is rather weak. It greatly limits the application in practical problems. One problem, called solution quality evaluation, is how to quantify the performance of the algorithm. It is hardly solved by theoretical methods. Experimental analysis method based on the analysis of search space and characteristic of algorithm itself is proposed in this paper. As algorithm runs, it would produce a large number of feasible solutions. After preprocessing, they were clustered according to distance. Then, good enough set was partitioned by the results of clustering. Last, evaluation result of ordinal performance was got by using relative knowledge of statistics. As the method only uses feasible solution produced by optimization algorithm, it is independent to specific algorithm. Therefore, the proposed method can be adopted by other intelligent optimization algorithms. The method is demonstrated through traveling salesman problem.

• Periodical: Applied Mechanics and Materials (Volume 378)
• Pages: 387-393
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.378.387
• Online since: August 2013
• Authors: Zhao Jun Zhang, Zu Ren Feng
• Keywords: Ant Colony Optimization (ACO), Experimental Analysis, Good Enough Set

References

[1] M. Dorigo, V. Maniezzo, and A. Colorni: The ant system: optimization by a colony of cooperating agents, IEEE Trans. on Systems, Man, and Cybernetics–Part B, 26(1996), p.29–41.

DOI: 10.1109/3477.484436

[2] M. Dorigo, and L. M. Gambardella: Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Trans. on Evolutionary Computation, 1(1997), p.53–66.

DOI: 10.1109/4235.585892

[3] T. Stützle, and H. H. Hoos: Max-Min ant system, Future Generation Computer Systems, 16(2000), p.889–914.

DOI: 10.1016/s0167-739x(00)00043-1

[4] M. Dorigo and T. Stützle: Ant Colony Optimization, 1st ed. Cambridge, MA: MIT Press, (2004).

[5] W. J. Gutjahr: A graph-based ant system and its convergence, Future Generation Computer Systems, 16(2000), p.873–888.

DOI: 10.1016/s0167-739x(00)00044-3

[6] T. Stützle and M. Dorigo: A short convergence proof for a class of ACO algorithms, IEEE Trans. on Evolutionary Computation, 16(2002), p.358–365.

DOI: 10.1109/tevc.2002.802444

[7] F. Neumann and C. Witt: Runtime analysis of a simple ant colony optimization algorithm, in Proceedings of. 17th international symposium on High performance distributed computing, (2006), p.618–627.

DOI: 10.1007/11940128_62

[8] W. J. Gutjahr: First steps to the runtime complexity analysis of ant colony optimization, Computers & Operations Research, 35(2008), p.2711–2727.

DOI: 10.1016/j.cor.2006.12.017

[9] Y. R. Zhou: Runtime analysis of an ant colony optimization algorithm for TSP instances, IEEE Trans. on Evolutionary Computation, 13(2009), p.1083–1092.

DOI: 10.1109/tevc.2009.2016570

[10] Y. C. Ho, R. S. Sreenivas, and P. Vakili: Ordinal optimizaiton of discrete event dynamic systems, Journal of Optimization Theory and Applications, 2(1992), pp.61-88.

DOI: 10.1007/bf01797280

[11] Y. C. Ho, Q. C. Zhao, and Q. S. Jia: Ordinal Optimization: Soft Coputation for Hard Problems. Springer Verlag, (2007).

[12] S. Ben-David, and A. Borodin: A new measure for the study of on-line algorithms, Algorithmica, 11(1994), pp.73-91.

DOI: 10.1007/bf01294264

[13] J. Aspnes, and O. Waarts: Compositional competitiveness for distributed algorithms, Journal of Algorithms, 54(2005), pp.127-151.

DOI: 10.1016/j.jalgor.2004.06.004

[14] J. Hüsler, P. Cruz, and A. Hall: On optimizaiton and extreme value theory, Methodology and Computing in Applied Probability, 5(2003), pp.183-195.

[15] D. P. Bertsekas: Nonlinear Programming, 2nd ed. Belmont, MA, USA: Athena Scientific, (1999).

[16] Z. Shen, Y. C. Ho, and Q. C. Zhao: Ordinal optimization and quantification of heuristic designs, Discrete Event Dynamic Systems Theory and Applications, 19(2009), pp.317-345.

DOI: 10.1007/s10626-009-0067-6

[17] Z. Shen, Q. C. Zhao, and Q. S. Jia: Quantifying heuristics in the ordinal optimization framework, Discrete Event Dynamic Systems, 20(2010), pp.441-471.

DOI: 10.1007/s10626-009-0087-2