The performance profile: A multi-criteria performance evaluation method for test-based problems

• Autorzy: Jaśkowski W. , Liskowski P. , Szubert M. , Krawiec K.

Identyfikatory

DOI

10.1515/amcs-2016-0015

• Języki publikacji: EN

Abstrakty

EN

In test-based problems, solutions produced by search algorithms are typically assessed using average outcomes of interactions with multiple tests. This aggregation leads to information loss, which can render different solutions apparently indifferent and hinder comparison of search algorithms. In this paper we introduce the performance profile, a generic, domain-independent, multi-criteria performance evaluation method that mitigates this problem by characterizing the performance of a solution by a vector of outcomes of interactions with tests of various difficulty. To demonstrate the usefulness of this gauge, we employ it to analyze the behavior of Othello and Iterated Prisoner’s Dilemma players produced by five (co)evolutionary algorithms as well as players known from previous publications. Performance profiles reveal interesting differences between the players, which escape the attention of the scalar performance measure of the expected utility. In particular, they allow us to observe that evolution with random sampling produces players coping well against the mediocre opponents, while the coevolutionary and temporal difference learning strategies play better against the high-grade opponents. We postulate that performance profiles improve our understanding of characteristics of search algorithms applied to arbitrary test-based problems, and can prospectively help design better methods for interactive domains.

Słowa kluczowe

EN

coevolutionary algorithms; evolution strategies; Othello; Reversi; games; multiobjective analysis

PL

algorytm koewolucyjny; strategie ewolucyjne; gra Othello; analiza wielokryterialna

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 1
• Strony: 215--229
• Opis fizyczny: Bibliogr. 45 poz., rys., tab., wykr.

Twórcy

autor

Jaśkowski W.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

autor

Liskowski P.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

autor

Szubert M.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

autor

Krawiec K.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

Bibliografia

• [1] Ashlock, D. and Lee, C. (2013). Agent-case embeddings for the analysis of evolved systems, IEEE Transactions on Evolutionary Computation 17(2): 227–240.
• [2] Axelrod, R. (1984). The Evolution of Cooperation, Basic Books, New York, NY.
• [3] Beyer, H.-G. and Schwefel, H.-P. (2002). Evolution strategies—a comprehensive introduction, Natural Computing 1(1): 3–52.
• [4] Bucci, A., Pollack, J.B. and de Jong, E. (2004). Automated extraction of problem structure, in K. Deb et al. (Eds.), Genetic and Evolutionary Computation—GECCO-2004, Part I, Lecture Notes in Computer Science, Vol. 3102, Springer-Verlag, Berlin/Heidelberg, pp. 501–512.
• [5] Chong, S.Y., Tiño, P., Ku, D.C. and Xin, Y. (2012). Improving generalization performance in co-evolutionary learning, IEEE Transactions on Evolutionary Computation 16(1): 70–85.
• [6] Chong, S.Y., Tiño, P. and Yao, X. (2008). Measuring generalization performance in coevolutionary learning, IEEE Transactions on Evolutionary Computation 12(4): 479–505.
• [7] Chong, S.Y., Tiño, P. and Yao, X. (2009). Relationship between generalization and diversity in coevolutionary learning, IEEE Transactions on Computational Intelligence and AI in Games 1(3): 214–232.
• [8] Chong, S.Y. and Yao, X. (2005). Behavioral diversity, choices and noise in the iterated prisoner’s dilemma, IEEE Transactions on Evolutionary Computation 9(6): 540–551.
• [9] Darwen, P.J. and Yao, X. (2001). Why more choices cause less cooperation in iterated prisoner’s dilemma, Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, South Korea, Vol. 2, pp. 987–994.
• [10] Darwen, P. and Yao, X. (2000). Does extra genetic diversity maintain escalation in a co-evolutionary arms race, International Journal of Knowledge-Based Intelligent Engineering Systems 4(3): 191–200.
• [11] de Jong, E.D. (2004). The incremental Pareto-coevolution archive, in K. Deb et al. (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference, Lecture Notes in Computer Science, Vol. 3102, Springer-Verlag, Berlin/Heidelberg, pp. 525–536.
• [12] Ficici, S.G. (2004). Solution Concepts in Coevolutionary Algorithms, Ph.D. thesis, Brandeis University, Waltham, MA.
• [13] Fogel, D.B. (1991). The evolution of intelligent decision making in gaming, Cybernetics and Systems 22(2): 223–236.
• [14] Fogel, D.B. (2001). Blondie24: Playing at the Edge of AI, Morgan Kaufmann Publishers, San Francisco, CA.
• [15] Frean, M. (1996). The evolution of degrees of cooperation, Journal of Theoretical Biology 182(4): 549–59.
• [16] Hart, S. and Mas-Colell, A. (2000). A simple adaptive procedure leading to correlated equilibrium, Econometrica 68(5): 1127–1150.
• [17] Hillis, W.D. (1990). Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D 42(1–3): 228–234.
• [18] Jaśkowski, W. (2011). Algorithms for Test-Based Problems, Ph.D. thesis, Poznań University of Technology, Poznań.
• [19] Jaśkowski, W. (2014). Systematic n-tuple networks for Othello position evaluation, ICGA Journal 37(2): 85–96.
• [20] Jaśkowski, W. and Krawiec, K. (2011). How many dimensions in cooptimization?, in N. Krasnogor (Ed.), Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, ACM, New York, NY, pp. 829–830.
• [21] Jaśkowski, W., Krawiec, K. and Wieloch, B. (2008). Evolving strategy for a probabilistic game of imperfect information using genetic programming, Genetic Programming and Evolvable Machines 9(4): 281–294.
• [22] Jaśkowski, W., Liskowski, P., Szubert, M. and Krawiec, K. (2013). Improving coevolution by random sampling, in C. Blum (Ed.), GECCO’13: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, ACM, Amsterdam, pp. 1141–1148.
• [23] Jaśkowski, W., Szubert, M. and Liskowski, P. (2014). Multi-criteria comparison of coevolution and temporal difference learning on Othello, in A.I. Esparcia-Alcazar and A.M. Mora (Eds.), EvoApplications 2014, Lecture Notes in Computer Science, Vol. 8602, Springer, Berlin/Heidelberg, pp. 301–312.
• [24] Juillé, H. and Pollack, J.B. (1998). Coevolving the ideal trainer: Application to the discovery of cellular automata rules, Proceedings of the 3rd Annual Conference on Genetic Programming, Madison, WI, USA, pp. 519–527.
• [25] Knowles, J.D., Watson, R.A. and Corne, D. (2001). Reducing local optima in single-objective problems by multi-objectivization, EMO’01: Proceedings of the 1st International Conference on Evolutionary Multi-Criterion Optimization, Zurich, Switzerland, pp. 269–283.
• [26] Krawiec, K., Jaśkowski, W. and Szubert, M. (2011). Evolving small-board go players using coevolutionary temporal difference learning with archive, International Journal of Applied Mathematics and Computer Science 21(4): 717–731, DOI: 10.2478/v10006-011-0057-3.
• [27] Lucas, S.M. (2007). Learning to play Othello with n-tuple systems, Australian Journal of Intelligent Information Processing Systems 9(4): 1–20.
• [28] Lucas, S.M. and Runarsson, T.P. (2006). Temporal difference learning versus co-evolution for acquiring Othello position evaluation, IEEE Symposium on Computational Intelligence and Games, Reno, NV, USA, pp. 52–59.
• [29] Luke, S. and Wiegand, R.P. (2002). When coevolutionary algorithms exhibit evolutionary dynamics, in A.M. Barry (Ed.), GECCO 2002: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, AAAI, New York, NY, pp. 236–241.
• [30] Manning, E.P. (2010). Using resource-limited Nash memory to improve an Othello evaluation function, IEEE Transactions on Computational Intelligence and AI in Games 2(1): 40–53.
• [31] Nolfi, S. and Floreano, D. (1998). Coevolving predator and prey robots: Do “Arms races” arise in artificial evolution?, Artificial Life 4(4): 311–335.
• [32] Pollack, J.B. and Blair, A.D. (1998). Co-evolution in the successful learning of backgammon strategy, Machine Learning 32(3): 225–240.
• [33] Popovici, E., Bucci, A., Wiegand, R.P. and de Jong, E.D. (2011). Coevolutionary principles, in G. Rozenberg et al. (Eds.), Handbook of Natural Computing, Springer-Verlag, Berlin/Heidelberg, pp. 987–1033.
• [34] Popovici, E. and De Jong, K. (2009). Monotonicity versus performance in co-optimization, FOGA’09: Proceedings of the 10th ACMSIGEVOWorkshop on Foundations of Genetic Algorithms, Orlando, FL, USA, pp. 151–170.
• [35] Poundstone,W. (1992). Prisoner’s Dilemma: John von Neuman, Game Theory, and the Puzzle of the Bomb, Doubleday, NY.
• [36] Reynolds, C. (1994). Competition, coevolution and the game of tag, in R.A. Brooks and P. Maes (Eds.), Artificial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems,MIT Press, Cambridge, MA, pp. 59–69.
• [37] Runarsson, T. and Lucas, S. (2014). Preference learning for move prediction and evaluation function approximation in Othello, IEEE Transactions on Computational Intelligence and AI in Games 6(3): 300–313.
• [38] Samothrakis, S., Lucas, S., Runarsson, T. and Robles, D. (2012). Coevolving game-playing agents: Measuring performance and intransitivities, IEEE Transactions on Evolutionary Computation 17(2): 1–15.
• [39] Szubert, M., Jaśkowski, W. and Krawiec, K. (2009). Coevolutionary temporal difference learning for Othello, IEEE Symposium on Computational Intelligence and Games, Milan, Italy, pp. 104–111.
• [40] Szubert, M., Jaśkowski, W. and Krawiec, K. (2011). Learning board evaluation function for Othello by hybridizing coevolution with temporal difference learning, Control and Cybernetics 40(3): 805–831.
• [41] Szubert, M., Jaśkowski, W. and Krawiec, K. (2013a). On scalability, generalization, and hybridization of coevolutionary learning: A case study for Othello, IEEE Transactions on Computational Intelligence and AI in Games 5(3): 214–226.
• [42] Szubert, M., Liskowski, P., Jaśkowski, W. and Krawiec, K. (2013b). Shaping fitness function for evolutionary learning of game strategies, in C. Blum (Ed.), GECCO’13: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, ACM, Amsterdam, pp. 1149–1156.
• [43] Szubert, M., Jaśkowski, W., Liskowski, P. and Krawiec, K. (2015). The role of behavioral diversity and difficulty of opponents in coevolving game-playing agents, in M.A. Mora and G. Squilero (Eds.), EvoApplications 2015, Lecture Notes in Computer Science, Vol. 9028, Springer, pp. 394–405.
• [44] Watson, R.A. and Pollack, J.B. (2001). Coevolutionary dynamics in a minimal substrate, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, CA, USA, pp. 702–709.
• [45] Yoshioka, T., Ishii, S. and Ito, M. (1998). Strategy acquisition for the game ”Othello” based on reinforcement learning, in S. Usui and T. Omori (Eds.), Proceedings of the Fifth International Conference on Neural Information Processing, ICONIP98, IOA Press, Kitakyushu, pp. 841–844.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.