Top

Published in:

2016 | OriginalPaper | Chapter

The Uncertainty Quandary: A Study in the Context of the Evolutionary Optimization in Games and Other Uncertain Environments

Authors : Juan J. Merelo, Federico Liberatore, Antonio Fernández Ares, Rubén García, Zeineb Chelly, Carlos Cotta, Nuria Rico, Antonio M. Mora, Pablo García-Sánchez, Alberto Tonda, Paloma de las Cuevas, Pedro A. Castillo

Published in: Transactions on Computational Collective Intelligence XXIV

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Evaluative Study of PSO/Snake Hybrid Algorithm and Gradient Path Labeling for Calculating Solar Differential Rotation

next chapter Hybrid Single Node Genetic Programming for Symbolic Regression

Aizawa, A.N., Wah, B.W.: Scheduling of genetic algorithms in a noisy environment. Evol. Comput. 2(2), 97–122 (1994)CrossRef

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 CrossRef

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 CrossRefMATH

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 CrossRefMATH

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 CrossRef

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

10.

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)

11.

Deb, K.: Multi-objective Optimization Using Evolutionary Algorithms, vol. 16. John Wiley & Sons, New York (2001)MATH

12.

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

13.

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)

14.

Fahlman, S.: Faster-learning variations on back-propagation: an empirical study. In: Proceedings of the 1988 Connectionist Models Summer School. Morgan Kaufmann (1988)

15.

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

16.

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)

17.

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 CrossRef

18.

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)

19.

Fogel, L.J., Owens, A.J., Walsh, M.J.: Artificial Intelligence Through Simulated Evolution. John Wiley, New York (1966)MATH

20.

Friedrich, T., Kötzing, T., Krejca, M., Sutton, A.M.: The Benefit of Sex in Noisy Evolutionary Search. ArXiv e-prints, February 2015

21.

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)

22.

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)

23.

Goh, C.K., Tan, K.C.: An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 11(3), 354–381 (2007)CrossRef

24.

Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Reading (1989)MATH

25.

Groeneveld, R.A., Meeden, G.: Measuring skewness and kurtosis. The Statistician, 391–399 (1984)

26.

Hansen, N., Finck, S., Ros, R., Auger, A.: Real-parameter black-box optimization benchmarking 2009: noisy functions definitions (2009)

27.

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)CrossRef

28.

Haykin, S.: Neural Networks: A Comprehensive Foundation, 2nd edn. Prentice Hall PTR, Upper Saddle River (1998)MATH

29.

Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments - a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005). Cited by (since 1996) 576CrossRef

30.

Jin, Y.: Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm Evol. Comput. 1(2), 61–70 (2011)CrossRef

31.

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 CrossRef

32.

Koza, J.R.: Genetic Programming - on the Programming of Computers by Means of Natural Selection. Complex Adaptive Systems. MIT Press, Cambridge (1993)MATH

33.

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 CrossRef

34.

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)

35.

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

36.

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

37.

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

38.

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)

39.

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 CrossRef

40.

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

41.

Miller, B.L., Goldberg, D.E.: Genetic algorithms, selection schemes, and the varying effects of noise. Evol. Comput. 4(2), 113–131 (1996)CrossRef

42.

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)MathSciNetCrossRef

43.

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 CrossRef

44.

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)

45.

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)CrossRef

46.

Paredis, J.: Coevolutionary computation. Artif. Life 2(4), 355–375 (1995)CrossRef

47.

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 CrossRef

48.

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 CrossRef

49.

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

50.

Qian, C., Yu, Y., Zhou, Z.H.: Analyzing evolutionary optimization in noisy environments. CoRR abs/1311.4987 (2013)

51.

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 CrossRef

52.

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

53.

Rattray, M., Shapiro, J.: Noisy fitness evaluation in genetic algorithms and the dynamics of learning, pp. 117–139 (1998)

54.

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)

55.

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 CrossRef

56.

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)CrossRef

57.

Wilcoxon, F.: Individual comparisons by ranking methods. Biometrics Bull. 1(6), 80–83 (1945)CrossRef

Title: The Uncertainty Quandary: A Study in the Context of the Evolutionary Optimization in Games and Other Uncertain Environments
Authors: Juan J. Merelo
Federico Liberatore
Antonio Fernández Ares
Rubén García
Zeineb Chelly
Carlos Cotta
Nuria Rico
Antonio M. Mora
Pablo García-Sánchez
Alberto Tonda
Paloma de las Cuevas
Pedro A. Castillo
Publisher: Springer Berlin Heidelberg
Book: Transactions on Computational Collective Intelligence XXIV
Print ISBN: 978-3-662-53524-0

Electronic ISBN: 978-3-662-53525-7

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-662-53525-7_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner