%0 Thesis %1 ficici:thesis %A Ficici, Sevan Gregory %C USA %D 2004 %K Algorithms Coevolutionary Evolutionary Game Learning Machine Theory ToReview algorithms genetic %T Solution Concepts in Coevolutionary Algorithms %U http://www.demo.cs.brandeis.edu/papers/long.html#ficici_thesis_04 %X Inspired by the principle of natural selection, coevolutionary algorithms are search methods in which processes of mutual adaptation occur amongst agents that interact strategically. The outcomes of interaction reveal a reward structure that guides evolution towards the discovery of increasingly adaptive behaviors. Thus, coevolutionary algorithms are often used to search for optimal agent behaviors in domains of strategic interaction. Coevolutionary algorithms require little a priori knowledge about the domain. We assume the learning task necessitates the algorithm to 1) discover agent behaviors, 2) learn the domain's reward structure, and 3) approximate an optimal solution. Despite the many successes of coevolutionary optimization, the practitioner frequently observes a gap between the properties that actually confer agent adaptivity and those expected (or desired) to yield adaptivity, or optimality. This gap is manifested by a variety of well-known pathologies, such as cyclic dynamics, loss of fitness gradient, and evolutionary forgetting. This dissertation examines the divergence between expectation and actuality in coevolutionary algorithms---why selection pressures fail to conform to our beliefs about adaptiveness, or why our beliefs are evidently erroneous. When we confront the pathologies of coevolutionary algorithms as a collection, we find that they are essentially epiphenomena of a single fundamental problem, namely a lack of rigor in our solution concepts. A solution concept is a formalism with which to describe and understand the incentive structures of agents that interact strategically. All coevolutionary algorithms implement some solution concept, whether by design or by accident, and optimize according to it. Failures to obtain the desiderata of "complexity" or öptimality" often indicate a dissonance between the implemented solution concept and that required by our envisaged goal. We make the following contributions: 1) We show that solution concepts are the critical link between our expectations of coevolution and the outcomes actually delivered by algorithm operation, and are therefore crucial to explicating the divergence between the two, 2) We provide analytic results that show how solution concepts bring our expectations in line with algorithmic reality, and 3) We show how solution concepts empower us to construct algorithms that operate more in line with our goals.

@phdthesis{ficici:thesis, abstract = {Inspired by the principle of natural selection, coevolutionary algorithms are search methods in which processes of mutual adaptation occur amongst agents that interact strategically. The outcomes of interaction reveal a reward structure that guides evolution towards the discovery of increasingly adaptive behaviors. Thus, coevolutionary algorithms are often used to search for optimal agent behaviors in domains of strategic interaction. Coevolutionary algorithms require little a priori knowledge about the domain. We assume the learning task necessitates the algorithm to 1) discover agent behaviors, 2) learn the domain's reward structure, and 3) approximate an optimal solution. Despite the many successes of coevolutionary optimization, the practitioner frequently observes a gap between the properties that actually confer agent adaptivity and those expected (or desired) to yield adaptivity, or optimality. This gap is manifested by a variety of well-known pathologies, such as cyclic dynamics, loss of fitness gradient, and evolutionary forgetting. This dissertation examines the divergence between expectation and actuality in coevolutionary algorithms---why selection pressures fail to conform to our beliefs about adaptiveness, or why our beliefs are evidently erroneous. When we confront the pathologies of coevolutionary algorithms as a collection, we find that they are essentially epiphenomena of a single fundamental problem, namely a lack of rigor in our solution concepts. A solution concept is a formalism with which to describe and understand the incentive structures of agents that interact strategically. All coevolutionary algorithms implement some solution concept, whether by design or by accident, and optimize according to it. Failures to obtain the desiderata of {"}complexity{"} or {"}optimality{"} often indicate a dissonance between the implemented solution concept and that required by our envisaged goal. We make the following contributions: 1) We show that solution concepts are the critical link between our expectations of coevolution and the outcomes actually delivered by algorithm operation, and are therefore crucial to explicating the divergence between the two, 2) We provide analytic results that show how solution concepts bring our expectations in line with algorithmic reality, and 3) We show how solution concepts empower us to construct algorithms that operate more in line with our goals.}, added-at = {2012-05-04T00:00:32.000+0200}, address = {USA}, author = {Ficici, Sevan Gregory}, biburl = {https://www.bibsonomy.org/bibtex/28f80f6dedb647ecb041a16c147e44f11/kmukhar}, interhash = {414be632865d9884908ef55895ddda2b}, intrahash = {8f80f6dedb647ecb041a16c147e44f11}, keywords = {Algorithms Coevolutionary Evolutionary Game Learning Machine Theory ToReview algorithms genetic}, month = may, notes = {Available as Computer Science Department Technical Report CS-03-243 Download this paper as: Postscript (ficici_thesis_04.ps) Gzipped Postscript (ficici_thesis_04.ps.gz) PDF (ficici_thesis_04.pdf)}, school = {Computer Science Department, Brandeis University}, size = {299 pages}, timestamp = {2012-05-04T00:01:04.000+0200}, title = {Solution Concepts in Coevolutionary Algorithms}, url = {http://www.demo.cs.brandeis.edu/papers/long.html#ficici_thesis_04}, year = 2004 }