 |
    |
A Game-Theoretic Memory Mechanism for Coevolution
Sevan G. Ficici and Jordan B. Pollack
Department of Computer Science
Brandeis University
Waltham Massachusetts 02454 USA
http://www.demo.cs.brandeis.edu
Abstract. One problem associated with coevolutionary algorithms is that of forgetting, where one or more previously acquired traits are lost only to be needed later. We introduce a new coevolutionary memory mechanism to help prevent forgetting that is built upon game-theoretic principles, specifically Nash equilibrium. This "Nash memory" mechanism has the following properties: 1) It accumulates a collection of salient traits discovered by search, and represents this collection as a mixed strategy. 2) This mixed strategy monotonically approaches the quality of a Nash equilibrium strategy as search progresses, thus acting as a "ratchet" mechanism. 3) The memory naturally embodies the result (solution) obtained by the coevolutionary process. 4) The memory appropriately handles intransitive cycles (subject to resource limitations). We demonstrate our Nash memory using Watson and Pollack's intransitive numbers game, and compare its performance to the conventional "Hall of Fame" memory and the more recently proposed Dominance Tournament.
LNCS 2723, p. 286 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003