A Novel ACO with Average Entropy

Yancang LI

.

DOI: 10.4236/jsea.2009.25049                

Abstract

In order to solve the premature convergence problem of the basic Ant Colony Optimization algorithm, a promising modification with changing index was proposed. The main idea of the modification is to measure the uncertainty of the path selection and evolution by using the average information entropy self-adaptively. Simulation study and perform-ance comparison on Traveling Salesman Problem show that the improved algorithm can converge at the global opti-mum with a high probability. The work provides a new approach for solving the combinatorial optimization problems, especially the NP-hard combinatorial optimization problems.

Keywords

ACO, Modification, Average Entropy, TSP

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Dorigo, V. Maniezzo, and A. Colorni, “The ant sys-tem: An autocatalytic optimizing process,” Technical Report 91-106 revised, Department of Electronic, Politecnico of Milano, Milan, Italy, 1991.
[2]	Colorni, M. Dorigo, and V. Maniezzo, “Distributed Op-timization by Ant Colonies,” in Proceedings of the First European Conference on Artificial Life, Elsevier Pub-lishing, Paris, France, 1991.
[3]	M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEC Transon Evolutionary Computing, Vol. 1 No. 1, pp. 53–56, 1997.
[4]	Blum, A. Roli and M. Dorigo, “HC-ACO: The hy-per-cube framework for ant colony optimization,” in Pro-ceedings of MIC 2001-meta-heuristics International Con-ference, Porto, Portugal, Vol. 2, pp. 399–403, 2001.
[5]	A. Colorni, M. Dorigo, and V. Maniezzo, “Ant colony system for job-shop scheduling,” Belgian Journal of Op-erations Research Statistics and Computer Science, Vol. 34, No. 1 , pp. 39–53, 1994.
[6]	V. Maniezzo, M. Dorigo, and A. Colorni, “The ant sys-tem applied to quadratic assignment problem,” Technical Report IRIDIA94-28, University de Bruxelles, Belgium, 1994.
[7]	L. Gambardella and M. Dorigo, “HAS-SOP: Hybrid ant system for the sequential problem,” Technical Report, IDSIA, 1997.
[8]	L. Chen and Z. Pan, “Ant colony optimization approach for test scheduling of system on chip,” Journal of Chongqing University of Posts and Telecommunications, Vol. 21, No. 2, pp. 212–217, 2009.
[9]	M. L. Spangler, K. R. Robbins, J. K. Bertrand, and M. Macneil, et al., “Ant colony optimization as a method for strategic genotype sampling,” Animal genetics, Vol. 40, No. 3, pp. 308–314, 2009.
[10]	Q. Zhang, “Research on ant colony algorithm and its applications”, Computer Knowledge and Technology, Vol. 5, No. 9, pp. 2396–2398, 2009.
[11]	M. Dorigo and T. Stutzle, “Ant colony optimization,” Cambridge, MIT Press, MA, 2004.
[12]	Y. Li and W. Li, “Adaptive ant colony optimization algo-rithm based on information entropy: Foundation and ap-plication,” Fundamenta Informaticae, Vol. 77, No. 3, pp. 229–242, 2007.
[13]	T. Stutzle and H. Hoos, “MAX-MIN ant system,” Future Generation Computer systems, No. 16, pp. 889–914, 2000.
[14]	M. Dorigo and M. Luca, “A study of some properties of Ant-Q,” Proceedings of 4th International Conference on Parallel Problem from Nature, Berlin: Springer Verlag, pp. 656–665, 1996.
[15]	Wanhua Q., “Management decision making and the ap-plied entropy,” China Mechanical Press, Beijing, China, 2002.