Abstract
Ant Colony Optimization (ACO) has been successfully applied to a wide number of complex and real domains. From classical optimization problems to video games, these kind of swarm-based approaches have been adapted, to be later used, to search for new meta-heuristic based solutions. This paper presents a simple ACO algorithm that uses a specifically designed heuristic, called common-sense, which has been applied in the classical video game Lemmings. In this game a set of lemmings must reach the exit point of each level, using a subset of finite number of skills, taking into account the contextual information given from the level. The paper describes both the graph model and the context-based heuristic, designed to implement our ACO approach. Afterwards, two different kind of simulations have been carried out to analyse the behaviour of the ACO algorithm. On the one hand, a micro simulation, where each ant is used to model a lemming, and a macro simulation where a swarm of lemmings is represented using only one ant. Using both kind of simulations, a complete experimental comparison based on the number and quality of solutions found and the levels solved, is carried out to study the behaviour of the algorithm under different game configurations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Abraham, A., Ramos, V.: Web usage mining using artificial ant colony clustering and linear genetic programming. In: The 2003 Congress on Evolutionary Computation, CEC 2003, vol. 2, pp. 1384–1391 (December 2003)
Berghman, L., Goossens, D., Leus, R.: Solving mastermind using genetic algorithms. Computers & Operations Research 36, 1880–1885 (2009)
Blickle, T., Thiele, L.: A comparison of selection schemes used in evolutionary algorithms. Evolutionary Computation 4(4), 361–394 (1996)
Blum, C., Merkle, D.: Swarm Intelligence: Introduction and Applications, 1st edn. Springer Publishing Company (2008) (incorporated)
Chen, X., Wang, H., Wang, W., Shi, Y., Gao, Y.: Apply ant colony optimization to tetris. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO), pp. 1:1741–1:1742 (2009)
Coldridge, J., Amos, M.: Genetic algorithms and the art of zen. Technical report, Manchester Metropolitan University (2010)
Colorni, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies. In: European Conference on Artificial Life, pp. 134–142 (1991)
Cormode, G.: The hardness of the lemmings game, or oh no, more np-completeness proofs. In: Proceedings of Third International Conference on Fun with Algorithms, pp. 65–76 (2004)
Das, S., Biswas, A., Dasgupta, S., Abraham, A.: Bacterial foraging optimization algorithm: theoretical foundations, analysis, and applications. Foundations of Computational Intelligence 203, 2355 (2009)
Das, T.K.: Bio-inspired algorithms for the design of multiple optimal power system stabilizers: Sppso and bfa. IEEE Transactions on Industry Applications 44(5) (September/October 2008)
Dorigo, M.: Ant colony optimization: A new meta-heuristic. In: Proceedings of the Congress on Evolutionary Computation, pp. 1470–1477. IEEE Press (1999)
Engelbrecht, A.P.: Computational Intelligence: An Introduction, 2nd edn. Wiley Publishing (2007)
Akan, O.B., Dressler, F.: Bio-inspired networking: From theory to practice. IEEE Communications Magazine, 177–183 (November 2010)
Farooq, M.: Bee-Inspired Protocol Engineering: From Nature to Networks. Springer (2008) (incorporated)
Gonzalez-Pardo, A., Camacho, D.: A new csp graph-based representation for ant colony optimization. In: 2013 IEEE Conference on Evolutionary Computation, June 20–23, vol. 1, pp. 689–696 (2013)
Gonzalez-Pardo, A., Camacho, D.: Environmental influence in bio-inspired game level solver algorithms. In: Zavoral, F., Jung, J.J., Badica, C. (eds.) IDC 2013. SCI, vol. 511, pp. 157–162. Springer, Heidelberg (2013)
Karaboga, D.: An idea based on honey bee swarm for numerical optimization. Techn. Rep. TR06 Erciyes Univ. Press Erciyes, 129(2) p. 2865 (2005)
Karaboga, D., Basturk, B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (abc) algorithm. J. of Global Optimization 39, 459–471 (2007)
Kendall G., Spoerer, K.: Scripting the game of lemmings with a genetic algorithm. In: Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 117–124 (2004)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of the Congress on Evolutionary Computation, vol. 4, pp. 1942–1948 (1995)
Martin, E., Martinez, M., Recio, G., Saez, Y.: Pac-mant: Optimization based on ant colonies applied to developing an agent for ms. pac-man. In: Proceedings of the Symposium on Computational Intelligence and Games (CIG), pp. 1:458–1:464 (2010)
Miikkulainen, R., Bryant, B.D., Cornelius, R., Karpov, I.V., Stanley, K.O., Yong, C.H.: Computational intelligence in games. In: Computational Intelligence: Principles and Practice (2006)
Reynolds, C.W.: Flocks, herds and schools: A distributed behavioral model. SIGGRAPH Comput. Graph. 21, 25–34 (1987)
Shaker, N., Togelius, J., Yannakakis, G.N., Weber, B.G., Shimizu, T., Hashiyama, T., Sorenson, N., Pasquier, P., Mawhorter, P.A., Takahashi, G., Smith, G., Baumgarten, r: The 2010 mario ai championship: Level generation track. IEEE Trans. Comput. Intellig. and AI in Games 3(4), 332–347 (2011)
Togelius, J.: Mario ai competition. In: Lanzi, P.L. (ed.) CIG. IEEE (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
González-Pardo, A., Palero, F., Camacho, D. (2014). Micro and Macro Lemmings Simulations Based on Ants Colonies. In: Esparcia-Alcázar, A., Mora, A. (eds) Applications of Evolutionary Computation. EvoApplications 2014. Lecture Notes in Computer Science(), vol 8602. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45523-4_28
Download citation
DOI: https://doi.org/10.1007/978-3-662-45523-4_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45522-7
Online ISBN: 978-3-662-45523-4
eBook Packages: Computer ScienceComputer Science (R0)