Cognitive Ant Colony Optimization : a new framework in swarm intelligence

Riadi, ICJ

Abstract

Ant Colony Optimization (ACO) algorithms which belong to metaheuristic algorithms and swarm intelligence algorithms have been the focus of much attention in the quest to solve optimization problems. These algorithms are inspired by colonies of ants foraging for food from their nest and have been considered state-of-art methods for solving both discrete and continuous optimization problems. One of the most important phases of ACO algorithms is the construction phase during which an ant builds a partial solution and develops a state transition strategy. There have been a number of studies on the state transition strategy. However, most of the research studies look at how to improve pheromone updates rather than at how the ant itself makes a decision to move from a current position to the next position.
The aim of this research is to develop a novel state transition strategy for Ant Colony Optimization algorithms that can improve the overall performance of the algorithms. The research has shown that the state transition strategy in ACO can be improved by introducing non-rational decision-making.
The new proposed algorithm is called Cognitive Ant Colony Optimization and uses a new concept of decision-making taken from cognitive behaviour theory. In this proposed algorithm, the ACO has been endowed with non-rational behaviour in order to improve the overall optimization behaviour of ants during the process. This new behaviour will use a non-rational model named prospect theory (Kahneman & Tversky, 1979) to select the transition movements of the ants in the colony in order to improve the overall search capability and the convergence of the algorithm. The new Cognitive Ant Colony Optimization framework has been tested on the Travelling Salesman Problem (TSP), Water Distribution System and Continuous optimization problems. The results obtained show that our algorithm improved the performance of previous ACO techniques considerably.

Citation

Riadi, I. Cognitive Ant Colony Optimization : a new framework in swarm intelligence. (Thesis). University of Salford

• Thesis Type: Thesis
• Deposit Date: Mar 7, 2014
• Publicly Available Date: Mar 7, 2014
• Additional Information: References : Allais, M. (1979). The so-called Allais paradox and rational decisions under uncertainty. Springer Netherlands. Beni, G., & Wang, J. (1993). Swarm Intelligence in Cellular Robotic Systems. In Robots and Biological Systems: Towards a New Bionics? (pp. 703-712). Springer Berlin Heidelberg. Bilchev, G., & Parmee, I. (1995). The ant colony metaphor for searching continuous design spaces. In Evolutionary Computing (pp. 25-39). Springer Berlin Heidelberg. Blum, C. (2005). Ant colony optimization: Introduction and recent trends. Physics of Life reviews, 2(4), 353-373. Blum, C., & Dorigo, M. (2004). The hyper-cube framework for ant colony optimization. IEEE Trans Syst Man Cybernet Part B, 34(2), 1161-72. Brand, M., Masuda, M., Wehner, N., & Yu, X.-H. (2010). Ant colony optimization algorithm for robot path planning. Computer Design and Applications (ICCDA), 2010 International Conference on (pp. 436-440). IEEE. Bullnheimer, B., Hartl, R. F., & Strauß, C. (1999). A new rank based version of the Ant System: A computational study. Central European Journal Operations Research Economics, 7(1), 25-38. Camazine, S., Deneubourg, J. L., Franks, N. R., Sneyd, J., Theraulaz, G., & Bonabeau, E. (2003). Self-organization in biological systems. Princeton University Press. Camerer, C. F. (1989). An experimental test of several generalized utility theories. Journal of Risk and uncertainty, 2(1), 61-104. Christodoulou, S. E., & Ellinas, G. (2010). Pipe routing through ant colony optimization. Journal of Infrastructure Systems, 16(2), 149-159. Coello Coello, C. A. (2002). Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer methods in applied mechanics and engineering, 191(11), 1245-1287. Cunha, M. D., & Sousa, J. (1999). Water distribution network design optimization: simulated annealing approach. Journal of Water Resources Planning and Management, 125(4), 215-221. Deb, K., & Padhye, N. (2010). Development of efficient particle swarm optimizers by using concepts from evolutionary algorithms. Proceedings of the 12th annual conference on Genetic and evolutionary computation (pp. 55-62). ACM. Deneubourg, J.-L., Aron, S., Goss, S., & Pasteels, J. (1990). The self-organizing exploratory pattern of the argentine ant. Journal of insect behavior, 3(2), 159-168. Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. BioSystems, 43(2), 73--82. Dorigo, M., & Stützle, T. (2003). The ant colony optimization metaheuristic: Algorithms, applications, and advances. Handbook of metaheuristics, 250-285. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. Cambridge, MA: MIT Press. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 26(1), 29-41. Dréo, J., & Siarry, P. (2004). Heterarchy, Continuous interacting ant colony algorithm based on dense. Future Generation Computer Systems, 20(5), 841-856. Engelbrecht, A. P. (2005). Fundamentals of computational swarm intelligence (Vol. 1). Chichester: Wiley. Fishburn, P. C. (1970). Utility Theory For Decision Making. John Wiley & Sons, Inc. Fujiwara, O., & Khang, D. B. (1990). A two-phase decomposition method for optimal design of looped water distribution netwotks. Water resources research, 26(4), 539-549. García, O. C., Triguero, F. H., & Stützle, T. (2002). A review on the ant colony optimization metaheuristic: basis, models and new trends. Mathware & Soft Computing, 9(3), 141-175. Geetha, R., & Srikanth, G. U. (2012). Ant Colony Optimization in Diverse Engineering Applications: an Overview. International Journal of Computer Application, 19-25. Gomes, H. P., Bezerra, S. D., De Carvalho, P. S., & Salvino, M. M. (2009). Optimal dimensioning model of water distribution systems. Water Sa, 35(4). Guo, M., Liu, Y., & Malec, J. (2004). A new Q-learning algorithm based on the metropolis criterion. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics,, 34(5), 2140-2143. doi:10.1109/TSMCB.2004.832154 Hansson, S. O. (1994). Decision theory: A brief introduction. Department of Philosophy and the History of Technology. Royal Institute of Technology. Stockholm. Herrera, F., Lozano, M., & Molina, D. (2010). Test suite for the special issue of soft computing on scalability of evolutionary algorithms and other metaheuristics for large scale continuous optimization problems. Retrieved from http://sci2s.ugr.es/eamhco/ Hölldobler, B., & Wilson, E. O. (1990). The ants. Cambridge, MA: Harvard University Press. Kahneman, D. (2003). Maps of bounded rationality: Psychology for behavioral economics. The American economic review, 93(5), 1449-1475. Kahneman, D., & Tversky, A. (1979). Prospect theory: An analysis of decision under risk. Econometrica: Journal of the Econometric Society, 263-291. Kahneman, D., & Tversky, A. (2000). Choices, Values, and Frames. New York: Cambridge University Press. Kahneman, D., Slovic, P., & Tversky, A. (1982). Judgment under uncertainty: Heuristics and biases. Cambridge Univ Press. Khichane, M., Albert, P., & Solnon, C. (2008). Integration of ACO in a constraint programming language. Ant Colony Optimization and Swarm Intelligence, 84-95. Leguizamón, G., & Coello, C. (2010). An alternative ACOR algorithm for continuous optimization problems. Proc of ANTS, 6234, 48-59. Li, T., Chen, W., Zheng, X., & Zhang, Z. (2009). An improvement of the ant colony optimization algorithm for solving travelling sales problem (TSP). 5th International Conference on Wireless Communications Networking and Mobile Computing. Liao, T., de Oca, M., Aydn, D., Stützle, T., & Dorigo, M. (2011). An incremental ant colony algorithm with local search for continuous optimization. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011). New York. Liu, L., Dai, Y., & Tao, C. (2011). State Transition Strategy Analysis of Ant Colony Algorithm. Fourth International Joint Conference on Computational Sciences and Optimization (CSO), (pp. 969-973). doi:10.1109/CSO.2011.245 López-Ibáñez, M., Prasad, T. D., & Paechter, B. (2008). Ant colony optimization for optimal control of pumps in water distribution networks. Journal of water resources planning and management, 134(4), 337-346. Lozano, M., Herrera, F., & Molina, D. (2011). Special issue on scalability of evolutionary algorithms and other metaheuristics for large scale continuous optimization problems. Soft Comput. Maier, H., Simpson, A., Zecchin, A., Foong, W., Phang, K., Seah, H., & Tan, C. (2003). Ant colony optimization for design of water distribution systems. Journal of water resources planning and management, 129(3), 200-209. McDermott, R. (2001). Risk-taking in international politics: Prospect theory in American foreign policy. University of Michigan Press. Monmarché, N., Venturini, G., & Slimane, M. (2000). On how Pachycondyla apicalis ants suggest a new search algorithm. Future Generation Computer Systems, 16, 937-946. Nobahari, H., & Pourtakdoust, S. H. (2005, February). Optimization of fuzzy rule bases using continuous ant colony system. In Proceedings of the First International Conference on Modeling, Simulation and Applied Optimization. Rini, D. P., & Shamsuddin, S. M. (2011). Particle swarm optimization: technique, system and challenges. International Journal of Applied Information Systems, 1, 33-45. Runarsson, T. P., & Yao, X. (2000). Stochastic ranking for constrained evolutionary optimization. Evolutionary Computation, IEEE Transactions on, 4(3), 284-294. Serugendo, G. D., Gleizes, M. P., & Karageorgos, A. (2011). Self-organising Sofware: From Natural to Artificial Adaption. Heidelberg: Springer. Socha, K., & Dorigo, M. (2008). Ant colony optimization for continuous domains. European Journal of Operational Research, 185(3), 1155--1173. Stützle, T., & Hoos, H. (2000). MAX--MIN ant system. Future Generation Computer Systems, 16, 889-914. Trepel, C., Fox, C. R., & Poldrack, R. A. (2005). Prospect theory on the brain? Toward a cognitive neuroscience of decision under risk. Cognitive Brain Research, 23(1), 34-50. Tversky, A., & Kahneman, D. (1992). Advances in prospect theory: Cumulative representation of uncertainty. Journal of Risk and uncertainty, 5(4), 297-323. Wakker, P. P. (2010). Prospect theory: For risk and ambiguity. Cambridge: Cambridge University Press. Zecchin, A. a., Simpson, A., Leonard, M., & Nixon, J. (2007). Ant colony optimization applied to water distribution system design: comparative study of five algorithms. Journal of Water Resources Planning and Management, 133(1), 87-92. Zheng, S., Ge, M., Li, C., Wang, C., & Xue, A. (2010 July). New transition probability for Ant Colony Optimization: global random-proportional rule. In Proceeding of 8th World Congress on Intelligent Control and Automation (WCICA), 2010 (pp. 2698-2702). IEEE.; Funders : Directorate of Higher Education, Ministry of Education and Culture, Goverment of Indonesia