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

Wojciech Jaśkowski; Paweł Liskowski; Marcin Szubert; Krzysztof Krawiec

International Journal of Applied Mathematics and Computer Science (2016)

  • Volume: 26, Issue: 1, page 215-229
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Wojciech Jaśkowski, et al. "The performance profile: A multi-criteria performance evaluation method for test-based problems." International Journal of Applied Mathematics and Computer Science 26.1 (2016): 215-229. <http://eudml.org/doc/276693>.

@article{WojciechJaśkowski2016,
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.},
author = {Wojciech Jaśkowski, Paweł Liskowski, Marcin Szubert, Krzysztof Krawiec},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {coevolutionary algorithms; evolution strategies; Othello; Reversi; games; multi-objective analysis},
language = {eng},
number = {1},
pages = {215-229},
title = {The performance profile: A multi-criteria performance evaluation method for test-based problems},
url = {http://eudml.org/doc/276693},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Wojciech Jaśkowski
AU - Paweł Liskowski
AU - Marcin Szubert
AU - Krzysztof Krawiec
TI - The performance profile: A multi-criteria performance evaluation method for test-based problems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 1
SP - 215
EP - 229
AB - 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.
LA - eng
KW - coevolutionary algorithms; evolution strategies; Othello; Reversi; games; multi-objective analysis
UR - http://eudml.org/doc/276693
ER -

References

top
  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. Zbl1014.68134
  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. Zbl1121.91312
  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. Zbl1020.91003
  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. Zbl1286.91034
  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. Zbl0913.90289
  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 ACM SIGEVO Workshop 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. Zbl1318.68167
  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. Zbl1318.68167
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.