1. bookVolume 26 (2016): Issue 1 (March 2016)
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 31 Mar 2016
Volume & Issue: Volume 26 (2016) - Issue 1 (March 2016)
Page range: 215 - 229
Received: 13 Feb 2015
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
Abstract

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.

Keywords

Ashlock, D. and Lee, C. (2013). Agent-case embeddings for the analysis of evolved systems, IEEE Transactions on Evolutionary Computation17(2): 227–240.10.1109/TEVC.2012.2234464Search in Google Scholar

Axelrod, R. (1984). The Evolution of Cooperation, Basic Books, New York, NY.Search in Google Scholar

Beyer, H.-G. and Schwefel, H.-P. (2002). Evolution strategies—a comprehensive introduction, Natural Computing1(1): 3–52.10.1023/A:1015059928466Search in Google Scholar

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.10.1007/978-3-540-24854-5_53Search in Google Scholar

Chong, S.Y., Tiño, P., Ku, D.C. and Xin, Y. (2012). Improving generalization performance in co-evolutionary learning, IEEE Transactions on Evolutionary Computation16(1): 70–85.10.1109/TEVC.2010.2051673Search in Google Scholar

Chong, S.Y., Tiño, P. and Yao, X. (2008). Measuring generalization performance in coevolutionary learning, IEEE Transactions on Evolutionary Computation12(4): 479–505.10.1109/TEVC.2007.907593Search in Google Scholar

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 Games1(3): 214–232.10.1109/TCIAIG.2009.2034269Search in Google Scholar

Chong, S.Y. and Yao, X. (2005). Behavioral diversity, choices and noise in the iterated prisoner’s dilemma, IEEE Transactions on Evolutionary Computation9(6): 540–551.10.1109/TEVC.2005.856200Search in Google Scholar

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.Search in Google Scholar

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 Systems4(3): 191–200.Search in Google Scholar

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.10.1007/978-3-540-24854-5_55Search in Google Scholar

Ficici, S.G. (2004). Solution Concepts in Coevolutionary Algorithms, Ph.D. thesis, Brandeis University, Waltham, MA.Search in Google Scholar

Fogel, D.B. (1991). The evolution of intelligent decision making in gaming, Cybernetics and Systems22(2): 223–236.10.1080/01969729108902281Search in Google Scholar

Fogel, D.B. (2001). Blondie24: Playing at the Edge of AI, Morgan Kaufmann Publishers, San Francisco, CA.10.1016/B978-155860783-5/50016-7Search in Google Scholar

Frean, M. (1996). The evolution of degrees of cooperation, Journal of Theoretical Biology182(4): 549–59.10.1006/jtbi.1996.0194Search in Google Scholar

Hart, S. and Mas-Colell, A. (2000). A simple adaptive procedure leading to correlated equilibrium, Econometrica68(5): 1127–1150.10.1111/1468-0262.00153Search in Google Scholar

Hillis, W.D. (1990). Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D42(1–3): 228–234.10.1016/0167-2789(90)90076-2Search in Google Scholar

Jaśkowski, W. (2011). Algorithms for Test-Based Problems, Ph.D. thesis, Poznań University of Technology, Poznań.Search in Google Scholar

Jaśkowski, W. (2014). Systematic n-tuple networks for Othello position evaluation, ICGA Journal37(2): 85–96.10.3233/ICG-2014-37203Search in Google Scholar

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.Search in Google Scholar

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 Machines9(4): 281–294.10.1007/s10710-008-9062-1Search in Google Scholar

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.10.1145/2463372.2463512Search in Google Scholar

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.10.1007/978-3-662-45523-4_25Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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 Science21(4): 717–731, DOI: 10.2478/v10006-011-0057-3.10.2478/v10006-011-0057-3Search in Google Scholar

Lucas, S.M. (2007). Learning to play Othello with n-tuple systems, Australian Journal of Intelligent Information Processing Systems9(4): 1–20.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Manning, E.P. (2010). Using resource-limited Nash memory to improve an Othello evaluation function, IEEE Transactions on Computational Intelligence and AI in Games2(1): 40–53.10.1109/TCIAIG.2010.2042598Search in Google Scholar

Nolfi, S. and Floreano, D. (1998). Coevolving predator and prey robots: Do “Arms races” arise in artificial evolution?, Artificial Life4(4): 311–335.10.1162/10645469856862010352236Search in Google Scholar

Pollack, J.B. and Blair, A.D. (1998). Co-evolution in the successful learning of backgammon strategy, Machine Learning32(3): 225–240.10.1023/A:1007417214905Search in Google Scholar

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.Search in Google Scholar

Popovici, E. and De Jong, K. (2009). Monotonicity versus performance in co-optimization, FOGA’09: Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, Orlando, FL, USA, pp. 151–170.Search in Google Scholar

Poundstone, W. (1992). Prisoner’s Dilemma: John von Neuman, Game Theory, and the Puzzle of the Bomb, Doubleday, NY.10.1063/1.2809809Search in Google Scholar

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.Search in Google Scholar

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 Games6(3): 300–313.10.1109/TCIAIG.2014.2307272Search in Google Scholar

Samothrakis, S., Lucas, S., Runarsson, T. and Robles, D. (2012). Coevolving game-playing agents: Measuring performance and intransitivities, IEEE Transactions on Evolutionary Computation17(2): 1–15.10.1109/TEVC.2012.2208755Search in Google Scholar

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.Search in Google Scholar

Szubert, M., Jaśkowski, W. and Krawiec, K. (2011). Learning board evaluation function for Othello by hybridizing coevolution with temporal difference learning, Control and Cybernetics40(3): 805–831.Search in Google Scholar

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 Games5(3): 214–226.10.1109/TCIAIG.2013.2258919Search in Google Scholar

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.10.1145/2463372.2463513Search in Google Scholar

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.10.1007/978-3-319-16549-3_32Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo