Abstract
In many optimization processes, the fitness or the considered measure of goodness for the candidate solutions presents uncertainty, that is, it yields different values when repeatedly measured, due to the nature of the evaluation process or the solution itself. This happens quite often in the context of computational intelligence in games, when either bots behave stochastically, or the target game possesses intrinsic random elements, but it shows up also in other problems as long as there is some random component. Thus, it is important to examine the statistical behavior of repeated measurements of performance and, more specifically, the statistical distribution that better fits them. This work analyzes four different problems related to computational intelligence in videogames, where Evolutionary Computation methods have been applied, and the evaluation of each individual is performed by playing the game, and compare them to other problem, neural network optimization, where performance is also a statistical variable. In order to find possible patterns in the statistical behavior of the variables, we track the main features of its distributions, skewness and kurtosis. Contrary to the usual assumption in this kind of problems, we prove that, in general, the values of two features imply that fitness values do not follow a normal distribution; they do present a certain common behavior that changes as evolution proceeds, getting in some cases closer to the standard distribution and in others drifting apart from it. A clear behavior in this case cannot be concluded, other than the fact that the statistical distribution that fitness variables follow is affected by selection in different directions, that parameters vary in a single generation across them, and that, in general, this kind of behavior will have to be taken into account to adequately address uncertainty in fitness in evolutionary algorithms.
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
Similar content being viewed by others
References
Aizawa, A.N., Wah, B.W.: Scheduling of genetic algorithms in a noisy environment. Evol. Comput. 2(2), 97–122 (1994)
Arnold, D.: Evolution strategies in noisy environments-a survey of existing work. In: Kallel, L., Naudts, B., Rogers, A. (eds.) Theoretical Aspects of Evolutionary Computing. Natural Computing Series, pp. 239–250. Springer, Heidelberg (2001). doi:10.1007/978-3-662-04448-3_11
Bhattacharya, M., Islam, R., Mahmood, A.: Uncertainty and evolutionary optimization: a novel approach. In: 2014 IEEE 9th Conference on Industrial Electronics and Applications (ICIEA), pp. 988–993, June 2014
Castillo, P.A., González, J., Merelo-Guervós, J.J., Prieto, A., Rivas, V., Romero, G.: G-Prop-III: global optimization of multilayer perceptrons using an evolutionary algorithm. In: GECCO 1999: Proceedings of the Genetic and Evolutionary Computation Conference, p. 942 (1999)
Castillo, P.A., Merelo-Guervós, J.J., Prieto, A., Rivas, V., Romero, G.: G-Prop: global optimization of multilayer perceptrons using GAs. Neurocomputing 35, 149–163 (2000). http://dx.doi.org/10.1016/S0925-2312(00)00302–7, available from http://geneura.ugr.es/pub/papers/castilloNC.ps.gz
Castillo, P., Carpio, J., Merelo-Guervós, J.J., Rivas, V., Romero, G., Prieto, A.: Evolving multilayer perceptrons. Neural Process. Lett. 12, 115–127 (2000). http://dx.doi.org/10.1023/A:1009684907680
Castillo, P., Merelo-Guervós, J.J., Prieto, A., Rojas, I., Romero, G.: Statistical analysis of the parameters of a neuro-genetic algorithm. IEEE Trans. Neural Netw. 13(6), 1374–1394 (2002). http://ieeexplore.ieee.org/iel5/72/22620/01058074.pdf
Cauwet, M.L., Liu, J., Teytaud, O., et al.: Algorithm portfolios for noisy optimization: compare solvers early. In: Learning and Intelligent Optimization Conference (2014)
Chiaberge, M., Merelo, J.J., Reyneri, L.M., Prieto, A., Zocca, L.: A comparison of neural networks, linear controllers, genetic algorithms and simulated annealing for real time control. In: De Facto, B. (ed.)Proceedings of the European Symposium on Artificial Neural Networks, pp. 205–210 (1994). Index available from http://www.dice.ucl.ac.be/esann/proceedings/esann1994/content.htm, available from http://polimage.polito.it/~marcello/articoli/esann.94.jj.pdf, and a scanned version from http://www.dice.ucl.ac.be/Proceedings/esann/esannpdf/es1994-533-S.pdf
Costa, A., Vargas, P., Tinós, R.: Using explicit averaging fitness for studying the behaviour of rats in a maze. In: Advances in Artificial Life, ECAL, vol. 12, pp. 940–946 (2013)
Deb, K.: Multi-objective Optimization Using Evolutionary Algorithms, vol. 16. John Wiley & Sons, New York (2001)
Di Mario, E., Navarro, I., Martinoli, A.: A distributed noise-resistant particle swarm optimization algorithm for high-dimensional multi-robot learning. In: Robotics and Automation (ICRA), pp. 5970–5976, May 2015
Esteban-Diaz, J., Handl, J.: Implicit and explicit averaging strategies for simulation-based optimization of a real-world production planning problem. Informatica (03505596) 39(2) (2015)
Fahlman, S.: Faster-learning variations on back-propagation: an empirical study. In: Proceedings of the 1988 Connectionist Models Summer School. Morgan Kaufmann (1988)
Fernández-Ares, A., Mora, A.M., García-Arenas, M., Guervós, J.J.M., García-Sánchez, P., Castillo, P.A.: Co-evolutionary optimization of autonomous agents in a real-time strategy game. In: Esparcia-Alcázar, A.I., Mora, A.M. (eds.) EvoApplications 2014. LNCS, vol. 8602, pp. 374–385. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45523-4_31
Fernández-Ares, A., Mora, A.M., Guervós, J.J.M., García-Sánchez, P., Fernandes, C.: Optimizing player behavior in a real-time strategy game using evolutionary algorithms. In: IEEE Congress on Evolutionary Computation, pp. 2017–2024. IEEE (2011)
Fernández-Ares, A., Mora, A.M., Merelo, J.J., García-Sánchez, P., Fernandes, C.M.: Optimizing strategy parameters in a game bot. In: Cabestany, J., Rojas, I., Joya, G. (eds.) IWANN 2011. LNCS, vol. 6692, pp. 325–332. Springer, Heidelberg (2011). doi:10.1007/978-3-642-21498-1_41
Flores, D.: Rank based evolution of real parameters on noisy fitness functions: evolving a robot neurocontroller. In: 10th Mexican International Conference on Artificial Intelligence (MICAI), pp. 72–76. IEEE (2011)
Fogel, L.J., Owens, A.J., Walsh, M.J.: Artificial Intelligence Through Simulated Evolution. John Wiley, New York (1966)
Friedrich, T., Kötzing, T., Krejca, M., Sutton, A.M.: The Benefit of Sex in Noisy Evolutionary Search. ArXiv e-prints, February 2015
García-Ortega, R.H., García-Sánchez, P., Mora, A.M., Merelo, J.: My life as a sim: evolving unique and engaging life stories using virtual worlds. In: ALIFE 2014: The Fourteenth Conference on the Synthesis and Simulation of Living Systems, vol. 14, pp. 580–587 (2014)
García-Sánchez, P., Tonda, A.P., Mora, A.M., Squillero, G., Guervós, J.J.M.: Towards automatic starcraft strategy generation using genetic programming. In: 2015 IEEE Conference on Computational Intelligence and Games, CIG 2015, Tainan, Taiwan, 31 August – 2 September 2015, pp. 284–291. IEEE (2015)
Goh, C.K., Tan, K.C.: An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 11(3), 354–381 (2007)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Reading (1989)
Groeneveld, R.A., Meeden, G.: Measuring skewness and kurtosis. The Statistician, 391–399 (1984)
Hansen, N., Finck, S., Ros, R., Auger, A.: Real-parameter black-box optimization benchmarking 2009: noisy functions definitions (2009)
Hansen, N., Niederberger, A.S., Guzzella, L., Koumoutsakos, P.: A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion. IEEE Trans. Evol. Comput. 13(1), 180–197 (2009)
Haykin, S.: Neural Networks: A Comprehensive Foundation, 2nd edn. Prentice Hall PTR, Upper Saddle River (1998)
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments - a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005). Cited by (since 1996) 576
Jin, Y.: Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm Evol. Comput. 1(2), 61–70 (2011)
Jun-hua, L., Ming, L.: An analysis on convergence and convergence rate estimateof elitist genetic algorithms in noisy environments. Optik Int. J. Light Electron Opt. 124(24), 6780–6785 (2013). http://www.sciencedirect.com/science/article/pii/S0030402613007730
Koza, J.R.: Genetic Programming - on the Programming of Computers by Means of Natural Selection. Complex Adaptive Systems. MIT Press, Cambridge (1993)
Jiménez Laredo, J.L., Dorronsoro, B., Fernandes, C., Merelo, J.J., Bouvry, P.: Oversized populations and cooperative selection: dealing with massive resources in parallel infrastructures. In: Nicosia, G., Pardalos, P. (eds.) LION 2013. LNCS, vol. 7997, pp. 444–449. Springer, Heidelberg (2013). doi:10.1007/978-3-642-44973-4_47
Liberatore, F., Mora, A., Castillo, P., Merelo, J.: Comparing heterogeneous and homogeneous flocking strategies for the ghost team in the game of Ms. Pac-Man. IEEE Trans. Comput. Intell. AI Games PP(99), 1 (2015)
Liu, J., St-Pierre, D.L., Teytaud, O.: A mathematically derived number ofresamplings for noisy optimization. In: Proceedings of the 2014 Conference Companion on Genetic and Evolutionary Computation Companion, GECCO Comp 2014, pp. 61–62. ACM, New York (2014). http://doi.acm.org/10.1145/2598394.2598458
Lucas, S.M.: Ms Pac-Man versus ghost-team competition. In: 2009 IEEE Symposium on Computational Intelligence and Games, CIG 2009, p. 1, September 2009
Luke, S., Panait, L., Balan, G., Paus, S., Skolicki, Z., Bassett, J., Hubley, R., Chircop, A.: ECJ: a java-based evolutionary computation research system (2006). Downloadable versions and documentation can be found at the following url: http://cs.gmu.edu/eclab/projects/ecj
Merelo, J.J., Castillo, P.A., Mora, A., Fernández-Ares, A., Esparcia-Alcázar, A.I., Cotta, C., Rico, N.: Studying and tackling noisy fitness in evolutionary design of game characters. In: Rosa, A., Merelo, J.J., Filipe, J. (eds.) ECTA 2014 - Proceedings of the International Conference on Evolutionary Computation Theory and Applications, pp. 76–85 (2014)
Merelo, J.J., Chelly, Z., Mora, A., Fernández-Ares, A., Esparcia-Alcázar, A.I., Cotta, C., Cuevas, P., Rico, N.: A statistical approach to dealing with noisy fitness in evolutionary algorithms. In: Merelo, J.J., Rosa, A., Cadenas, J.M., Dourado, A., Madani, K., Filipe, J. (eds.) Computational Intelligence. SCI, vol. 620, pp. 79–95. Springer, Heidelberg (2016). doi:10.1007/978-3-319-26393-9_6
Merelo-Guervós, J.J., Prieto, A., Morán, F.: Optimization of classifiers using genetic algorithms, pp. 91–108. MIT Press (2001). Chap. 4, iSBN:0262162016, draft available from http://geneura.ugr.es/pub/papers/g-lvq-book.ps.gz
Miller, B.L., Goldberg, D.E.: Genetic algorithms, selection schemes, and the varying effects of noise. Evol. Comput. 4(2), 113–131 (1996)
Mora, A.M., Fernández-Ares, A., Merelo-Guervós, J.J., García-Sánchez, P., Fernandes, C.M.: Effect of noisy fitness in real-time strategy games player behaviour optimisation using evolutionary algorithms. J. Comput. Sci. Technol. 27(5), 1007–1023 (2012)
Mora, A.M., Montoya, R., Merelo, J.J., Sánchez, P.G., Castillo, P.Á., Laredo, J.L.J., Martínez, A.I., Espacia, A.: Evolving bot AI in unreal\(^{\rm TM}\). In: Chio, C., Cagnoni, S., Cotta, C., Ebner, M., Ekárt, A., Esparcia-Alcazar, A.I., Goh, C.-K., Merelo, J.J., Neri, F., Preuß, M., Togelius, J., Yannakakis, G.N. (eds.) EvoApplications 2010. LNCS, vol. 6024, pp. 171–180. Springer, Heidelberg (2010). doi:10.1007/978-3-642-12239-2_18
Ong, Y.S., Zhou, Z., Lim, D.: Curse and blessing of uncertainty in evolutionary algorithm using approximation. In: 2006 IEEE Congress on Evolutionary Computation, CEC 2006, pp. 2928–2935. IEEE (2006)
Ontañón, S., Synnaeve, G., Uriarte, A., Richoux, F., Churchill, D., Preuss, M.: A survey of real-time strategy game AI research and competition in starcraft. IEEE Trans. Comput. Intellig. AI Games 5(4), 293–311 (2013)
Paredis, J.: Coevolutionary computation. Artif. Life 2(4), 355–375 (1995)
Parras-Gutierrez, E., Arenas, M.G., Rivas, V.M., del Jesus, M.J.: Coevolutionof lags and RBFNs for time series forecasting: L-Co-R algorithm. Soft Comput. 16(6), 919–942 (2012). http://dx.doi.org/10.1007/s00500-011-0784-2
Peñalver, J.G., Merelo, J.J.: Optimizing web page layout using an annealed genetic algorithm as client-side script. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 1018–1027. Springer, Heidelberg (1998). doi:10.1007/BFb0056943. http://www.springerlink.com/link.asp?id=2gqqar9cv3et5nlg
Qian, C., Yu, Y., Jin, Y., Zhou, Z.-H.: On the effectiveness of sampling for evolutionary optimization in noisy environments. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 302–311. Springer, Heidelberg (2014). doi:10.1007/978-3-319-10762-2_30
Qian, C., Yu, Y., Zhou, Z.H.: Analyzing evolutionary optimization in noisy environments. CoRR abs/1311.4987 (2013)
Rada-Vilela, J., Johnston, M., Zhang, M.: Population statistics for particle swarm optimization: resampling methods in noisy optimization problems. Swarm Evol. Comput. 17, 37–59 (2014). http://www.sciencedirect.com/science/article/pii/S2210650214000261
Rakshit, P., Konar, A., Nagar, A.: Artificial bee colony induced multi-objective optimization in presence of noise. In: 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 3176–3183, July 2014
Rattray, M., Shapiro, J.: Noisy fitness evaluation in genetic algorithms and the dynamics of learning, pp. 117–139 (1998)
Rudolph, G.: A partial order approach to noisy fitness functions. In: Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, vol. 1, pp. 318–325 (2001)
Squillero, G.: MicroGP-an evolutionary assembly program generator. Genet. Program Evolvable Mach. 6(3), 247–263 (2005). http://dx.doi.org/10.1007/s10710-005-2985-x
Stroud, P.D.: Kalman-extended genetic algorithm for search in nonstationary environments with noisy fitness evaluations. IEEE Trans. Evol. Comput. 5(1), 66–77 (2001)
Wilcoxon, F.: Individual comparisons by ranking methods. Biometrics Bull. 1(6), 80–83 (1945)
Acknowledgements
This work has been supported in part by projects TIN2014-56494-C4-3-P (Spanish Ministry of Economy and Competitiveness), SPIP2014-01437 (Dirección General de Tráfico), PRY142/14 (Fundación Pública Andaluza Centro de Estudios Andaluces en la IX Convocatoria de Proyectos de Investigación), PROY-PP2015-06 (Plan Propio 2015 UGR), and project CEI2015-MP-V17 of the Microprojects program 2015 from CEI BioTIC Granada. We would like also to thank the anonymous reviewers for this paper, for suggesting new readings and avenues of research.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Merelo, J.J. et al. (2016). The Uncertainty Quandary: A Study in the Context of the Evolutionary Optimization in Games and Other Uncertain Environments. In: Nguyen, N., Kowalczyk, R., Filipe, J. (eds) Transactions on Computational Collective Intelligence XXIV. Lecture Notes in Computer Science(), vol 9770. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53525-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-662-53525-7_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53524-0
Online ISBN: 978-3-662-53525-7
eBook Packages: Computer ScienceComputer Science (R0)