New Evaluations of Ant Colony Optimization Start Nodes

• Autorzy: Stefka Fidanova , Pencho Marinov , Krassimir Atanassov
• Języki publikacji: EN

Abstrakty

EN

Ant Colony Optimization (ACO) is a stochastic search method that mimics the social behavior of real ant colonies, managing to establish the shortest route to the feeding sources and back. Such algorithms have been developed to arrive at near-optimal solutions to large-scale optimization problems, for which traditional mathematical techniques may fail. In this paper, the semi-random start procedure is applied. A new kind of evaluation of start nodes of the ants is developed and several starting strategies are prepared and combined. The idea of semi-random start is related to a better management of the ants. This new technique is tested on the Multiple Knapsack Problem (MKP). A Comparison among the strategies applied is presented in terms of quality of the results. A comparison is also carried out between the new evaluation and the existing one. Based on this comparative analysis, the performance of the algorithm is discussed. The study presents the idea that should be beneficial to both practitioners and researchers involved in solving optimization problems. (original abstract)

Słowa kluczowe

EN

Combinatorial analysis; Stochastic models; Optimization theory

PL

Kombinatoryka; Modele stochastyczne; Teoria optymalizacji

• Czasopismo: Control and Cybernetics
• Rocznik: 2014
• Tom: 43
• Numer: nr 3
• Strony: 471--485

Twórcy

autor

Stefka Fidanova

• Bulgarian Academy of Science

autor

Pencho Marinov

• Bulgarian Academy of Science

autor

Krassimir Atanassov

• Bulgarian Academy of Science

Bibliografia

• BONABEAU E., DORIGO M. and THERAULAZ G. (1999) Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York.
• DIFFIE W. and HELLMAN M.E. (1976) New directions in cryptography. IEEE Trans Inf. Theory, 22 (6), 644 654.
• DORIGO M. and GAMBARDELLA L.M. (1997) Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation 1, 53-66.
• DORIGO M. and STUTZLE T. (2004) Ant Colony Optimization. MIT Press.
• FIDANOVA S. (2002) Evolutionary Algorithm for Multiple Knapsack Problem. Int. Conference Parallel Problems Solving from Nature, Real World Optimization Using Evolutionary Computing, Granada, Spain, University of Granada.
• FIDANOVA S. (2006) Ant colony optimization and multiple knapsack problem. In: J. Ph. Renard, ed., Handbook of Research on Nature Inspired Computing for Economics ad Management. Idea Group Inc., 498 509.
• FIDANOVA S. (2008) Probabilistic Model of Ant Colony Optimization for Multiple Knapsack Problem. Large Scale Scientific Computing. Lecture Notes in Computer Science, 4818, 545-552.
• FIDANOVA S., ATANASSOV K., MARINOV P. and PARVATHI R. (2009) Ant Colony Optimization for Multiple Knapsack Problem with Controlled Start. Int. Journal on BIOautomation, 13(4), 271-280.
• KONG M., TIAN P. and KAO Y. (2008) A New Ant Colony Optimization Algorithm for the Multidimensional Knapsack Problem. J. Computers and Operational Research, 35(8), 2672-2683.
• LEGUIZAMON G. and MICHALEWICZ Z. (1999) A New Version of Ant System for Subset Problems. In: Proceedings of Congress on Evolutionary Computation. IEEE Press, 1459-1464.
• MARTELLO S. and TOTH P. (1984) A mixture of dynamic programming and branch-and-bound for the subset sum problem. Management Science 30, 756-771.
• REIMAN M. and LAUMANNS M. (2004) A Hybrid ACO algorithm for the Capacitate Minimum Spanning Tree Problem. In: Ch. Blum, A. Roli and M. Sampels, eds., Proceedings of First International Workshop on Hybrid Metaheuristics, Valencia, Spain, ISBN 3-00-015331-4, 1-10.
• SINHA A. and ZOLTNER A.A. (1979) The multiple-choice knapsack problem. J. Operational Research 27, 503-515.
• STUTZLE T. and DORIGO M. (1999) ACO Algorithm for the Traveling Salesman Problem. In: K. Miettinen, M. Makela, P. Neittaanm¨aki, J. Periaux, eds., Evolutionary Algorithms in Engineering and Computer Science. Wiley, 163-183.
• STUTZLE T. and HOOS H.H. (2000) MAX-MIN Ant System. In: M. Dorigo, T. Stutzle and G. Di Caro, eds., Future Generation Computer Systems, 16. Elsevier, 889-914.
• ZHANG T., WANG S., TIAN W. and ZHANG Y. (2006) ACO-VRPTWRV: A New Algorithm for the Vehicle Routing Problems with TimeWindows and Re-used Vehicles based on Ant Colony Optimization. In: Proc. Of Sixth International Conference on Intelligent Systems Design and Applications, IEEE Press, 390-395.