Adaptive Ant Colony Optimization Algorithm Based on Information Entropy: Foundation and Application

• Autorzy: Li Y. , Li W.
• Języki publikacji: EN

Abstrakty

EN

In order to solve the premature convergence problem of the basic Ant Colony Optimization algorithm, a promising modification based on the information entropy is proposed. The main idea is to evaluate stability of the current space of represented solutions using information entropy, which is then applied to turning of the algorithm's parameters. The path selection and evolutional strategy are controlled by the information entropy self-adaptively. Simulation study and performance comparison with other Ant Colony Optimization algorithms and other meta-heuristics on Traveling Salesman Problem show that the improved algorithm, with high efficiency and robustness, appears self -adaptive and can converge at the global optimum with a high probability. The work proposes a more general approach to evolutionary-adaptive algorithms related to the population's entropy and has significance in theory and practice for solving the combinatorial optimization problems.

Słowa kluczowe

EN

ant colony optimization; modification; information entropy; self-adaptive; traveling salesman problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 77, nr 3
• Strony: 229--242
• Opis fizyczny: bibliogr. 29 poz., wykr.

Twórcy

autor

Li Y.

autor

Li W.

• College of Civil Engineering, Tianjin University, Tianjin, 300072, China,

Bibliografia

• [1] DorigoM.,Maniezzo V., Colorni A.: The Ant System: An autocatalytic optimizing process.Technical Report 91-106 revised, Department of Electronic, Politecnico of Milano, Milan, Italy,1991.
• [2] Colorni A., Dorigo M. and Maniezzo V.: Distributed Optimization by Ant Colonies. Proceedings of the First European Conference on Artificial Life, Elsevier Publishing, Paris, France, 134-142,1991.
• [3] Hölldobler B., Wilson E.O.: The Ants. Springer-Verlag, Berlin, Germany, 1990.
• [4] DorigoM.Gambardella LM.: Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEC Trans on Evolutionary Computing, 1 (1), 1997, 53-56.
• [5] Colorni ADorigo M and Maniezzo V.: Ant colony system for job-shop scheduling, Belgian Journal of Operations Research Statistics and Computer Science, 34(1) (1994), 39-53.
• [6] Maniezzo V, DorigoMand Colorni A: The ant system applied to Quadratic Assignment Problem, Technical Report IRIDIA 94-28, University de Bruxelles, Belgium,1994.
• [7] Gambardella L MDorigo M.: HAS-SOP: Hybrid ant system for the sequential problem, Technical Report, IDSIA, 1997.
• [8] Chen L., Shen J., Qin L.: A method for solving optimization problem in continuous space using ant colony algorithm, Systems Engineering-Theory and Practice, 3, 2003, 48-53.
• [9] Wang Y., Xie J.Y. An ant system algorithm for multicast routing, Systems Engineering and Electronics, 23 (8), 2001, 98-101.
• [10] Dorigo M. Caro D.: The Ant Colony Optimization m Meta-heuristic: New ideas in Optimization. McGraw-Hill, New York, 1999.
• [11] Dorigo M., Stutzle T.: Ant Colony Optimization. Cambridge, MIT Press, MA, July, 2004.
• [12] Dorigo M., Maniezzo V. and Colorni A.: Ant system: optimization by a colony of cooperating agents, IEEE Trans on SMC26 (1), 1996, 28-41.
• [13] Bullnheimer B., Hartl R. F. and Stauss C.: a new rank-based version of the ant system: A computational study, European Journal for Operations Research and Economics, 7(1), 1999, 25-38.
• [14] Stutzle THoos H.: MAX-MIN ant system, Future Generation Computer systems, 16, 2000, 889-914.
• [15] Cordon O., Fernodezde V.I. and Moreno L.: A new ACO model integrating evolutionary concepts: the bestworst ant system, From ant colonies to artificial ants A series of inter workshop on ant Algorithm, 2000: Proc. of ANTS Brussels, 22-29.
• [16] Wanhua Q.: Management decision making and the applied entropy, 2002, China Mechanical Press, Beijing, China.
• [17] Gutjahr W. J. A.: graph-based ant system and its convergence, Future General Computer System. 16(8), 2001, 873-888.
• [18] Randall M., Montgomery J.: Candidate set strategies for Ant Colony Optimization, Technical Report TR02-04, School of Information Technology, Bond University.
• [19] Reimann M., Shtovba S. and nepomuceno E.: A hybrid Ant Colony Optimization and Genetic Algorithm approach for vehick routing problems solving, Student Papers of Complex System Summer School, Budapest,2001,134-141.
• [20] Dorigo M.Luca M.: A study of Ant-Q, 1996: Proceedings of 4th International Conference on Parallel Problem from Nature, Berlin: Springer Verlag, 656-665.
• [21] Blum.C., Roli.A and Dorigo.M.: HC-ACO: The hyper-cube framework for Ant Colony Optimization. Proceedings of MIC 2001-meta-heuristics International Conference, Porto, Portugal, 2,399-403.
• [22] Wu Q.H., ZHang J.H. and XU X.H.: An ant colony algorithm with mutation features, Journal of computer Research and Development, 36(10), 1999, 1240-1245.
• [23] Asmar D. and ElshamliA.and Areibi S.: A comparative assessment of ACO Algorithms within a TSP environment, Dynamics of Continuous Discrete and Impulsive systems-series B-Application and Algorithm, SP.ISS. SI, 1, 2005, 462-467.
• [24] JS Chun, MK Kim, HK Jung, SK Hong: Shape optimization of electromagnetic devices using immune algorithm, IEEE Trans on Magnetics, 33(2), 1997, 1876-1879.
• [25] Durbin, R., Willshaw, D.: An analogue approach to the traveling salesman problem using an elastic net method, Nature, 326, 1987, 689-691.
• [26] Potvin, J.Y.: The traveling salesman problem: A neural network Perpective, ORSA Journal of Computing, 5 (4), 1993, 328-347.
• [27] Fogel, D.: Applying evolutionary programming to selected traveling salesman problems, Cybernetics and Systems: An International Journal, 24, 1993, 27-36.
• [28] DorigoM., L.M. Gambardella.: Ant Colonies for the Traveling Salesman Problem, BioSystems, 43,1997:73-81. Also Tecnical Report TR/IRIDIA/1996-3, IRIDIA, Universit Libre de Bruxelles.
• [29] Lin, S., Kernighan, B.W.: An effective Heuristic Algorithm for the TSP, Operations Research, 21, 1973, 498-516.