A game-theoretic investigation of selection methods used in evolutionary algorithms Export

@proceedings{citeulike:2012205, abstract = {The replicator equation used in evolutionary game theory (EGT) assumes that strategies reproduce in direct proportion to their payoffs; this is akin to the use of fitness-proportionate selection in an evolutionary algorithm (EA). In this paper, we investigate how various other selection methods commonly used in EAs can affect the discrete-time dynamics of EGT. In particular, we show that the existence of evolutionary stable strategies (ESS) is sensitive to the selection method used. Rather than maintain the dynamics and equilibria of EGT, the selection methods we test either impose a fixed-point dynamic virtually unrelated to the payoffs of the game matrix, or they give limit cycles or induce chaos. These results are significant to the field of evolutionary computation because EGT can be understood as a coevolutionary algorithm operating under ideal conditions: an infinite population, noiseless payoffs and complete knowledge of the phenotype space. Thus, certain selection methods, which may operate effectively in simple evolution, are pathological in an ideal-world coevolutionary algorithm, and therefore dubious under real-world conditions}, author = {Ficici, S. G. and Melnik, O. and Pollack, J. B.}, booktitle = {Evolutionary Computation, 2000. Proceedings of the 2000 Congress on}, citeulike-article-id = {2012205}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=870732}, journal = {Evolutionary Computation, 2000. Proceedings of the 2000 Congress on}, keywords = {coevolution, fitness}, pages = {880--887 vol.2}, posted-at = {2007-11-29 09:24:38}, priority = {0}, title = {A game-theoretic investigation of selection methods used in evolutionary algorithms}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=870732}, volume = {2}, year = {2000} }

TY - CONF ID - citeulike:2012205 L3 - citeulike-article-id:2012205 N2 - The replicator equation used in evolutionary game theory (EGT) assumes that strategies reproduce in direct proportion to their payoffs; this is akin to the use of fitness-proportionate selection in an evolutionary algorithm (EA). In this paper, we investigate how various other selection methods commonly used in EAs can affect the discrete-time dynamics of EGT. In particular, we show that the existence of evolutionary stable strategies (ESS) is sensitive to the selection method used. Rather than maintain the dynamics and equilibria of EGT, the selection methods we test either impose a fixed-point dynamic virtually unrelated to the payoffs of the game matrix, or they give limit cycles or induce chaos. These results are significant to the field of evolutionary computation because EGT can be understood as a coevolutionary algorithm operating under ideal conditions: an infinite population, noiseless payoffs and complete knowledge of the phenotype space. Thus, certain selection methods, which may operate effectively in simple evolution, are pathological in an ideal-world coevolutionary algorithm, and therefore dubious under real-world conditions JF - Evolutionary Computation, 2000. Proceedings of the 2000 Congress on EP - 887 vol.2 TI - A game-theoretic investigation of selection methods used in evolutionary algorithms VL - 2 T2 - Evolutionary Computation, 2000. Proceedings of the 2000 Congress on SP - 880 KW - coevolution KW - fitness AU - Ficici, SG AU - Melnik, O AU - Pollack, JB PY - 2000/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=870732 ER -