Bader-Natal, A.
(2008). The Teacher's Dilemma: A game-based approach for motivating appropriate challenge among peers.
PhD dissertation, Michtom School of Computer Science, Brandeis University.
Abstract
In classroom-based studies, peer tutoring has proved to be an effective learning strategy, both for the tutees and for their peer tutors. Today, the increasingly widespread availability of computers and internet access in the homes and after-school programs of students offers a new venue for peer learning. In seeking to translate the successes of peer-assisted learning from the classroom to the Internet, one major hurdle to overcome is that of motivation. When teachers are no longer supervising student activity and when participation itself becomes voluntary, peer tutoring protocols may stop being educationally productive. In order to successfully leverage these peer interactions, we must find a way to facilitate and motivate learning among a group of unsupervised peers. In this dissertation, we respond to this challenge by reconceptualizing the interactions among peers within the context of a different medium: that of games. In designing a peer tutoring experience as a two-player game, we gain a valuable set of tools and techniques for affecting student participation, engagement, goals, and strategies.
Our contributions: 1) We define a criteria for games -- the Teacher's Dilemma criteria -- that motivates players to challenge one another with problems of appropriate difficulty; 2) We show three games that satisfy the Teacher's Dilemma criteria when played by rational players under idealized conditions; 3) We demonstrate, using computer simulations of strategic dynamics, that game-play will converge towards meeting these criteria, through time, under more realistic conditions; 4) We design a suite of software that incorporates a Teacher's Dilemma game into several web-based activities for different learning domains; 5) We collect data from thousands of students using these activities, and examine how the games actually affected the game-play strategy and learning among these students.
The game-theoretic analysis establishes the possibility for a game-based mechanism for motivating appropriate challenges, the simulations support the plausibility of this approach given non-optimal players, the implemented software systems demonstrate the scalability of this model, and the data analysis supports the real-world applicability of this game-based approach to motivating appropriate challenges for learning among unsupervised peers.
.
De Jong, E.D. and
Bucci, A.
(2008). Objective Set Compression: Test-based Problems and Multi-objective Optimization.
Chapter in Multi-Objective Problem Solving from Nature: From Concepts to Applications. Joshua Knowles et al. (editors). Springer-Verlag.
Abstract
We consider a class of optimization problems wherein the quality of
candidate solutions is estimated by their performance on a number of tests.
Classifier induction, function regression, and certain types of
reinforcement learning, including problems often attacked with
coevolutionary algorithms, can all be seen as members of this class.
Traditional approaches to such test-based problems use a single
objective function that aggregates the scores obtained on the tests. Recent
work, by contrast, argues that useful finer-grained distinctions between
candidate solutions are obtained when each test is treated as a separate
objective, and that algorithms employing such multi-objective comparisons
show favorable behavior relative to those which do not. Unfortunately, the
number of tests can be very large. Since it is well-known that
high-dimensional multi-objective optimization problems are difficult to
handle in practice, the question arises whether the multi-objective
treatment of test-based problems is feasible. To begin addressing this
question, we examine a method for reducing the number of dimensions without
sacrificing the favorable properties of the multi-objective approach. Our
method, which is a form of dimension extraction, finds underlying
objectives implicit in test-based problems. Essentially, the method
proceeds by placing the tests along the minimal number of coordinate axes
that still preserve ordering information among the candidate solutions.
Application of the method to the strategy set for several instances of the
game of Nim suggest the technique has significant practical benefits: a type
of compression of the set of objectives is observed in all tested instances.
Surprisingly, we also find that the information contained in the arrangement
of tests on the coordinate axes reveals important information about the
structure of the underlying problem.
Download this paper as:
Postscript
(emo_coev.ps)
Gzipped Postscript
(emo_coev.ps.gz)
PDF
(emo_coev.pdf)
Bader-Natal, A. and
Pollack, J.B.
(2007). Assessing Learning in a Peer-Driven Tutoring System.
Proceedings of the 13th International Conference on Artificial Intelligence in Education, IOS Press, 2007.
Abstract
In many intelligent tutoring systems, a detailed model of the task domain is constructed and used to provide students with assistance and direction. Reciprocal tutoring systems, however, can be constructed without needing to codify a full-blown model for each new domain. This provides various advantages: these systems can be developed rapidly and can be applied to complex domains for which detailed models are not yet known. In systems built on the reciprocal tutoring model, detailed validation is needed to ensure that learning indeed occurs. Here, we provide such validation for SpellBEE, a reciprocal tutoring system for the complex task domain of American-English spelling. Using a granular definition of response accuracy, we present a statistical study designed to assess and characterize student learning from collected data. We find that students using this reciprocal tutoring system exhibit learning at the word, syllable, and grapheme levels of task granularity.
Download this paper as:
PDF
(badernatal2007aied.pdf)
Bader-Natal, A. and
Pollack, J.B.
(2007). Evaluating Problem Difficulty Rankings Using Sparse Student Response Data.
Supplementary Proceedings of the 13th International Conference on Artificial Intelligence in Education, IOS Press, 2007.
Abstract
Problem difficulty estimates play important roles in a wide variety of educational systems, including determining the sequence of problems presented to students and the interpretation of the resulting responses. The accuracy of these metrics are therefore important, as they can determine the relevance of an educational experience. For systems that record large quantities of raw data, these observations can be used to test the predictive accuracy of an existing difficulty metric. In this paper, we examine how well one rigorously developed -- but potentially outdated -- difficulty scale for American-English spelling fits the data collected from seventeen thousand students using our SpellBEE peer-tutoring system. We then attempt to construct alternate metrics that use collected data to achieve a better fit. The domain-independent techniques presented here are applicable when the matrix of available student-response data is sparsely populated or non-randomly sampled. We find that while the original metric fits the data relatively well, the data-driven metrics provide approximately 10% improvement in predictive accuracy. Using these techniques, a difficulty metric can be periodically or continuously re-calibrated to ensure the relevance of the educational experience for the student.
Download this paper as:
PDF
(badernatal2007edm_aied.pdf)
Bucci, A.
(2007). Emergent Geometric Organization and Informative Dimensions in Coevolutionary Algorithms.
PhD dissertation, Michtom School of Computer Science, Brandeis University.
Abstract
Coevolutionary algorithms vary entities which can play two or more distinct,
interacting roles, with the hope of producing raw material from which a
highly-capable composition can be constructed. Ranging in complexity from
autodidactic checkers-learning systems to the evolution of competing agents
in 3-d simulated physics, applications of these algorithms have proved both
motivating and perplexing. Successful applications inspire further
application, supporting the belief that a correctly implemented form of
evolution by natural selection can produce highly-capable entities with
minimal human input or intervention. However, the successes to date have
generated limited insight into how to transfer success to other domains. On
the other hand, failed applications leave behind a frustratingly opaque
trace of misbehavior. In either case, the question of what worked or what
went wrong is often left open.
One impediment to understanding the dynamics of coevolutionary algorithms is that the interactive domains explored by these algorithms typically lack an explicit objective function. Such a function is a clear guide for judging the progress or regress of an algorithm. However, in the absence of an explicit yardstick to judge the value of coevolving entities, how should they be measured?
To begin addressing this question, we start with the observation that in any interaction, an entity is not only performing a task, it is also informing about the capabilities of its interactants. In other words, an interaction can provide a measurement. Entities themselves can therefore be treated as measuring rods, here dubbed informative dimensions, against which other entities are incented to improve. It is argued that when entities are only incented to perform well, and adaptation of the function of measurement is neglected, algorithms tend not to keep informative dimensions and thus fail to produce high-performing entities.
It is demonstrated empirically that algorithms which are sensitized to these
yardsticks through an informativeness mechanism have better dynamic
behavior; in particular, known pathologies such as overspecialization,
cycling, or relative overgeneralization are mitigated. We argue that in
these cases an emergent geometric organization of the population implicitly
maintains informative dimensions, providing a direction to the evolving
population and so permitting continued improvement.
Download this paper as:
Postscript
(bucci_diss.ps)
Gzipped Postscript
(bucci_diss.ps.gz)
PDF
(bucci_diss.pdf)
Bucci, A. and
Pollack, J.B.
(2007). Thoughts on Solution Concepts.
Proceedings of the 2007 Genetic and Evolutionary Computation Conference.
Dirk Thierens et al. (editors). ACM Press, New York, NY.
Abstract
This paper explores connections between Ficici's notion of solution concept
and order theory. Ficici postulates that algorithms should ascend an order
called weak preference; thus, understanding this order is important
to questions of designing algorithms. We observe that the weak preference
order is closely related to the pullback of the so-called lower ordering on
subsets of an ordered set. The latter can, in turn, be represented as the
pullback of the subset ordering of a certain powerset. Taken together,
these two observations represent the weak preference ordering in a more
simple and concrete form as a subset ordering. We utilize this
representation to show that algorithms which ascend the weak preference
ordering are vulnerable to a kind of bloating problem. Since this kind of
bloat has been observed several times in practice, we hypothesize that
ascending weak preference may be the cause. Finally, we show that monotonic
solution concepts are convex in the order-theoretic sense. We conclude by
speculating that monotonic solution concepts might be derivable from
non-monotonic ones by taking convex hull. Since several intuitive solution
concepts like average fitness are not monotonic, there is practical value in
creating monotonic solution concepts from non-monotonic ones.
Download this paper as:
Postscript
(thoughts_soln.ps)
Gzipped Postscript
(thoughts_soln.ps.gz)
PDF
(thoughts_soln.pdf)
Ficici, S.G. and
Bucci, A.
(2007). Advanced Tutorial on Coevolution.
Presented at the 2007 Genetic and Evolutionary Computation Conference, London, UK.
Abstract
The advanced tutorial on coevolution given at GECCO 2007.
Download this paper as:
PDF
(adv_coev_tut.pdf)
Viswanathan, S.
(2007). The secondary substrate problem in Co-Evolution and Developmental-Evolution.
PhD Dissertation, Brandeis University, May 2007
.
Abstract
The performance of an Evolutionary Algorithm on a search problem is critically effected
by the substrate used to encode the candidate solutions of the problem. In addition to
the challenge of designing evolvable genetic substrates, two-population competitive
coevolutionary algorithms (coEAs) and developmental Evolutionary Algorithms(devo-EAs)
present another substrate-related design problem. Both involve an additional substrate with its
own mechanism of change. In coEAs, test-cases are encoded with an independent genetic
substrate having its own variation operators. In devo-EAs, phenotypes are composed of a
distinct substrate with associated generative mechanisms capable of changing an individual’s
form and size during development. Though this “secondary” substrate is a distinctive
feature of both algorithms, the design problem it poses remains poorly understood.
This dissertation proposes novel formal models to characterize how the properties of
the secondary substrate influences the performance devo-EAs and coEAs respectively.
Firstly, we propose a computational model for devo-EAs which shows that the point in time at which the development of a phenotype halts can introduce selection biases that can cause an empirically measurable retardation in the performance of a devo-EA. Furthermore, a Genotype-Phenotype map that is bias-free is formally equivalent to a Nash equilibrium in a non-cooperative multi-player game, where each genotype is a player, the possible halting points are strategies and the payoffs are related to the fitness function. We show that algorithmic solutions to find this Nash map are expensive without a suitable secondary substrate.
Secondly, we propose a novel search space model for Pareto coevolution that formally
defines the evolvability properties required of the secondary substrate for pathology-free
learning with a mutation-only coEA.With this model, we show that on boolean classification
problems (a) the variational properties of the secondary substrate are a property of the
problem class rather than tied to individual problems, and (b) the absence of coevolutionary
pathologies does not imply success in finding high-quality solutions. Rather than being
mysterious dynamical properties of coEAs, these findings are transparently explained using
Machine Learning first principles.
Keywords: development, evolution, coevolution, representations, evolvability
.
Download this paper as:
Postscript
(shiva_dissertation.ps)
Gzipped Postscript
(shiva_dissertation.ps.gz)
PDF
(shiva_dissertation.pdf)
Bader-Natal, A. and
Pollack, J.B.
(2006). BEEweb: A Multi-Domain Platform for Reciprocal Peer-Driven Tutoring Systems.
Proceedings of the 8th International Conference on Intelligent Tutoring Systems, Springer, 2006.
Abstract
Tutoring systems that engage each student as both a tutee and a tutor can be powerfully enhanced by motivating each tutor to try to appropriately challenge their tutee. The BEEweb platform is presented as a foundation upon which to build such systems, based upon the Reciprocal Tutoring protocol and the Teachers Dilemma. Three systems that have recently been built on the BEEweb platform are introduced
.
Download this paper as:
PDF
(badernatal2006its.pdf)
Burjorjee, K. and
Pollack, J.B,
(2006). A General Coarse-Graining Framework for Studying Simultaneous Inter-Population Constraints Induced by Evolutionary Operations.
Proceedings of the 2006 Genetic and Evolutionary Computation Conference, ACM Press, 2006.
Abstract
The use of genotypic populations is necessary for adaptation in
Evolutionary Algorithms. We use a technique called form-invariant commutation to study the immediate effect of evolutionary operations on populations of genotypes. This technique allows us to understand compositional changes induced by evolutionary operations in terms of constraints between populations. Deep insight into the population-level effect of some evolutionary operation is possible when multiple constraints can be derived for all pairs of pre and post operative populations; for each such pair of populations the constraints between them are then said to hold simultaneously. When selection is fitness proportional we show that any coarse-graining of the genotype set can be used to systematically derive single constraints between between all pairs of pre and post selection populations. Matters are not so simple in the case of variation. We develop an abstract condition called ambivalence and show that when a coarse-graining and a variation operation satisfy this condition then a systematic derivation of single constraints between all pairs of pre and post variation populations is possible. Finally we show that it is possible to use schema partitions to systematically derive simultaneous constraints for any combination of variation operations that are commonly used in GAs.
.
Keywords: Genetic Algorithms, Schema Theory, Coarse-Graining, Constraints.
Download this paper as:
Postscript
(burjorjee06.ps)
Gzipped Postscript
(burjorjee06.ps.gz)
PDF
(burjorjee06.pdf)
De Jong, E.D. and
Bucci, A.
(2006). DECA: Dimension Extracting Coevolutionary Algorithm.
Proceedings of the 2006 Genetic and Evolutionary Computation Conference,
ACM Press, 2006.
Abstract
Coevolution has often been based on averaged outcomes, resulting in unstable
evaluation. Several theoretical approaches have used archives to provide
stable evaluation. However, the number of tests required by some of these
approaches can be prohibitive of practical applications. Recent work has
shown the existence of a set of underlying objectives which compress
evaluation information into a potentially small set of dimensions. We
consider whether these underlying objectives can be approximated online, and
used for evaluation in a coevolution algorithm. The Dimension Extracting
Coevolutionary Algorithm (DECA) is compared to several recent reliable
coevolution algorithms on a Numbers game problem, and found to perform
efficiently. Application to the more realistic Tartarus problem is shown to
be feasible. Implications for current coevolution research are discussed.
Keywords: coevolution, dimension extraction, underlying objectives, DECA.
Download this paper as:
Postscript
(dejong_bucci_gecco2006.ps)
Gzipped Postscript
(dejong_bucci_gecco2006.ps.gz)
PDF
(dejong_bucci_gecco2006.pdf)
Ficici, S.G. and
Bucci, A.
(2006). Introductory Tutorial on Coevolution.
Presented at the 2006 Genetic and Evolutionary Computation Conference, Seattle, WA, USA.
Abstract
The introductory tutorial on coevolution given at GECCO 2006.
Download this paper as:
PDF
(intro_coev_tut.pdf)
Rieffel, J. and
Pollack, J.
(2006). An Endosymbiotic Model for Modular Acquisition in Stochastic Developmental Systems.
Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems (ALIFE X).
Abstract
Hierarchical modular composition is often cited as a requisite for
scalable complexity. The most popular reference in this regard is
Herbert Simon's allegory of the watchmakers Tempus and Hora. And yet,
while numerous studies have used this story as a jumping-off point to
explain the emergence of hierarchical modular composition in
evolutionary systems, relatively few emphasize the role of noise
in the parable. Developmental representations, which model
``biological assembly'', are a suitable lens through which to explore
this latter aspect, since noise and error during ontogeny can have a significant
negative impact on the progress of evolution. In this work we present
an endosymbiotic model for modular acquisition in a developmental
representation, and demonstrate its ability to hierarchically assemble large
objects in the presence of developmental noise.
.
Keywords: evolutionary design, evolutionary robotics, artificial ontogeny, evolutionary fabrication, assembly, modularity, symbiosis.
Download this paper as:
Postscript
(rieffel-alife-06.ps)
PDF
(rieffel-alife-06.pdf)
Rieffel, J.
(2006). Evolutionary Fabrication: The Co-Evolution of Form and Formation .
PhD Dissertation, Brandeis University, May 2006.
Abstract
Evolutionary Design has been used to automatically generate a wide variety of novel
and creative objects such as circuits, robots, and satellite antennae. And yet, despite
the availability of sophisticated rapid prototyping machines capable of printing objects
out of plastic, metal, and even circuitry, relatively few of these evolved designs have
been physically manufactured in the real world.
We argue that the cause of this paucity of physical artifacts lies in the design first, build later philosophy of contemporary Evolutionary Design. By only specifying the form of an object, this approach leaves unanswered the vital question of formation. As evolved forms become more complex, their formation becomes increasingly difficult for both humans and computers to discover. As a consequence, there is a growing Fabrication Gap between the complexity of objects which we can evolve and those which we can manufacture.
The alternative proposed here is to use Artificial Ontogenies, a computational method inspired by the biological processes of growth, in order to directly evolve the formation of objects. We introduce Evolutionary Fabrication, the direct evolution of assembly instructions within a simulated manufacturing system, and show that this approach is capable of injecting the novelty and creativity associated with evolution- ary approaches into the realm of fabrication, generating not just novel objects, but novel means of assembling those objects as well.
Ultimately, the evolution of form and formation become fully intertwined when the language of assembly itself becomes subject to evolution, capable of discovering increasingly large sub-assemblies and adding them to its vocabulary. Through this co-evolution of form and formation, Evolutionary Fabrication discovers both how to build objects and what to build them out of. In this manner, Evolutionary Fabrication is capable of designing and assembling scalably complex objects in a hierarchical manner, even in the presence of error during assembly.
Via this co-evolution of form and formation, Evolutionary Fabrication circum-
vents the Fabrication Gap, leading the way to systems which can move from broad
specification to complete artifact without the need for further human intervention.
This budding field of Fully Automated Design and Manufacture will have an impact
on realms ranging from product design to planetary exploration.
Keywords: evolutionary design, evolutionary robotics, artificial ontogeny, evolutionary fabrication, assembly, modularity, symbiosis.
Download this paper as:
PDF
(rieffel-dissertation.pdf)
Bader-Natal, A. and
Pollack, J.B.
(2005). Motivating Appropriate Challenges in a Reciprocal Tutoring System.
Proceedings of the 12th International Conference on Artificial Intelligence in Education, IOS Press, 2005.
Abstract
Formalizing a student model for an educational system requires an engineering effort that is highly domain-specific. This model-specificity limits the ability to scale a tutoring system across content domains. In this work we offer an alternative, in which the task of student modeling is not performed by the system designers. We achieve this by using a reciprocal tutoring system in which peer-tutors are implicitly tasked with student modeling. Students are motivated, using the Teacher's Dilemma, to use these models to provide appropriately-difficult challenges. We implement this as a basic literacy game in a spelling-bee format, in which players choose words for each other to spell across the internet. We find that students are responsive to the game's motivational structure, and we examine the affect on participants' spelling accuracy, challenge difficulty, and tutoring skill.
Keywords: Teacher's Dilemma, reciprocal tutoring system.
Download this paper as:
PDF
(badernatal2005aied.pdf)
Bader-Natal, A. and
Pollack, J.
(2005). Towards Metrics and Visualizations Sensitive to Coevolutionary Failures.
AAAI Technical Report FS-05-03 Coevolutionary and Coadaptive Systems, AAAI Fall Symposium 2005, Washington D.C. .
Abstract
The task of monitoring success and failure in coevolution is inherently difficult, as domains need not have any external metric to measure performance. Past metrics and visualizations for coevolution have been limited to identification and measurement of success but not failure. We suggest circumventing this limitation by switching from "best-of-generation"-based techniques to "all-of-generation"-based techniques. Using "all-of-generation" data, we demonstrate one such techique -- a population-differential technique -- that allows us to profile and distinguish an assortment of coevolutionary successes and failures, including arms-race dynamics, disengagement, cycling, forgetting, and relativism. .
Download this paper as:
PDF
(badernatal_2005aaai_fs.pdf)
Bucci, A. and
Pollack, J.B.
(2005). On Identifying Global Optima in Cooperative Coevolution.
Proceedings of the 2005 Genetic and Evolutionary Computation Conference,
ACM Press, 2005.
Abstract
When applied to optimization problems, Cooperative Coevolutionary Algorithms
(CCEA) have been observed to exhibit a behavior called relative
overgeneralization. Roughly, they tend to identify local optima with large
basins of attraction which may or may not correspond to global optima. A
question which arises is whether one can modify the algorithm to promote the
discovery of global optima. We argue that a mechanism from Pareto
coevolution can achieve this end. We observe that in CCEAs candidate
individuals from one population are used as tests or measurements of
individuals in other populations; by treating individuals as tests in this
way, a finer-grained comparison can be made among candidate individuals.
This finer-grained view permits an algorithm to see when two candidates are
differently capable, even when one's evident value is higher than the
other's. By modifying an existing CCEA to compare individuals using
Pareto dominance we have produced an algorithm which reliably finds global
optima. We demonstrate the algorithm on two \emph{Maximum of Two Quadratics}
problems and discuss why it works.
Keywords: coevolution, cooperative coevolution, Pareto coevolution.
Download this paper as:
Postscript
(f535-bucci.ps)
PDF
(f535-bucci.pdf)
Burjorjee, Keki
and
Pollack, Jordan
(2005). Theme Preservation and the Evolution of Representation
.
Theory of Representation Workshop at the the 2005 Genetic and Evolutionary Computation Conference
.
Abstract
In his thesis Toussaint calls for a ``general project to develop theories on adaptation processes that account for the adaptation of representations". The theory developed in this paper is a contribution to this project. We first define the simple concept of a genotypic theme and define what it means for mutation operators to be theme preserving and theme altering. We use the idea of theme preservation to develop the concept of subrepresentation. Then we develop a theory that illuminates the behavior of a mutation-only fitness proportional evolutionary algorithm in which mutation preserves genotypic themes with high probability. Our theory shows that such evolutionary algorithms implicitly implement what we call \emph{subrepresentation evolving multithreaded evolution} (SEME), i.e. such EAs conduct second-order search over a predetermined set of representations and exploit promising representations for first order evolutionary search. We illuminate SEME by comparing and contrasting it with the
behavior of island model EAs. Our theory is immediately useful in understanding the significance of the low probability with which theme altering type 2 mutations are applied to genotypes of the evolutionary systems in Toussaint's thesis.
.
Keywords: Evolutionary algorithms, theme preservation, evolution of representation
.
Download this paper as:
Postscript
(burjorjee05.ps)
Gzipped Postscript
(burjorjee05.ps.gz)
PDF
(burjorjee05.pdf)
Burjorjee, Keki
and
Pollack, Jordan
(2005). Theme Preservation and the Evolution of Representation
.
2nd Indian International Conference on Artificial Intelligence (IICAI-05)
.
Abstract
The identification of mechanisms by which constraints on phenotypic variability are tuned in nature, and the implementation of these mechanisms in Evolutionary Algorithms (EAs) carries the promise of making EAs less ``wasteful". The constraints on phenotypic variability are determined by the way genotypic variability maps to phenotypic variability. This in turn is determined by the way that phenotypes are represented genotypically. We use a formal model of an EA to show that when some part of the genome is mutated with a much lower probability than some other part, representations used to search the phenotype space - and hence the constraints on phenotypic variability - can themselves be thought to evolve. Specifically, we formally analyze a class of mutation-only fitness proportional evolutionary algorithms and show that these evolutionary algorithms implicitly implement what we call subrepresentation evolving multithreaded evolution. These EAs conduct second-order search over a predetermined set of representations and exploit promising representations within this set for first order evolutionary search. We compare our analytical method and results
with those employed in schema analysis and note that by examining systems that are simpler than the ones examined in a typical schema analysis (mutation is the only variational operator in our systems), and by changing how we define the subsets of the genotype space that are analyzed, we have obtained results that are more intuitively understandable and are not specific to a particular data-structure.
.
Keywords: Evolutionary algorithms, theme preservation, evolution of representation, schema theory
.
Download this paper as:
Postscript
(burjorjee05-b.ps)
Gzipped Postscript
(burjorjee05-b.ps.gz)
PDF
(burjorjee05-b.pdf)
Ficici, Sevan G.,
Melnik, Ofer and
Pollack, Jordan B.
(2005). A Game-Theoretic and Dynamical-Systems Analysis of Selection Methods in Coevolution.
IEEE Transactions on Evolutionary Computation 9(6), 580-602.
Abstract
We use evolutionary game theory (EGT) to investigate the dynamics and equilibria of selection methods in
coevolutionary algorithms. The canonical selection method used in EGT is equivalent to the standard
"fitness-proportional" selection method used in evolutionary algorithms. All attractors of the EGT dynamic
are Nash equilibria; we focus on simple symmetric variable-sum games that have polymorphic
Nash-equilibrium attractors. Against the dynamics of proportional selection, we contrast the behaviors of
truncation selection, (mu, lambda), (mu + lambda), linear ranking, Boltzmann, and tournament selection. Except
for Boltzmann selection, each of the methods we test unconditionally fail to achieve polymorphic Nash
equilibrium. Instead, we find point attractors that lack game-theoretic justification, cyclic dynamics, or
chaos. Boltzmann selection converges onto polymorphic Nash only when selection pressure is sufficiently low;
otherwise, we obtain attracting limit-cycles or chaos. Coevolutionary algorithms are often used to search for
solutions (e.g., Nash equilibria) of games of strategy; our results show that many selection methods are
inappropriate for finding polymorphic Nash solutions to variable-sum games. Another application of
coevolution is to model other systems; our results emphasize the degree to which the model's behavior is
sensitive to implementation details regarding selection---details that we might not otherwise believe to be
critical.
Keywords: Coevolutionary algorithms, selection methods, solution concepts, game theory, dynamical systems.
Ficici, Sevan G.
(2005). Monotonic Solution Concepts in Coevolution.
Proc. 2005 Genetic and Evolutionary Computation Conference, H.-G. Beyer, et al (eds.).
ACM Press, 2005 pp. 499--506. (content identical to definitive ACM version.).
Abstract
Assume a coevolutionary algorithm capable of storing and utilizing all phenotypes discovered during
its operation, for as long as it operates on a problem; that is, assume an algorithm with a
monotonically increasing knowledge of the search space. We ask: If such an algorithm were to
periodically report, over the course of its operation, the best solution found so far, would the
quality of the solution reported by the algorithm improve monotonically over time?
To answer this question, we construct a simple preference relation to reason about the goodness of
different individual and composite phenotypic behaviors.
We then show that whether the solutions reported by the coevolutionary
algorithm improve monotonically with respect to this preference relation depends upon the solution
concept implemented by the algorithm. We show that the solution concept implemented by the
conventional coevolutionary algorithm does not guarantee monotonic improvement; in contrast, the
game-theoretic solution concept of Nash equilibrium does guarantee monotonic improvement. Thus, this
paper considers 1) whether global and objective metrics of goodness can be applied to coevolutionary
problem domains (possibly with open-ended search spaces), and 2) whether coevolutionary algorithms
can, in principle, optimize with respect to such metrics and find solutions to games of strategy.
Keywords: Coevolution, monotonic progress, solution concepts.
Download this paper as:
Postscript
(ficici_gecco_05.ps)
Gzipped Postscript
(ficici_gecco_05.ps.gz)
PDF
(ficici_gecco_05.pdf)
Rieffel, J. and
Pollack, J.
(2005). Automated Assembly as Situated Development: Using Artificial Ontogenies to Evolve Buildable 3-D Objects .
Proceedings of the 2005 Genetic and Evolutionary Computation Conference .
Abstract
Artificial Ontogenies, which are inspired by biological development, have been used to automatically generate a wide array of
novel objects, some of which have recently been manufactured in the real world. The majority of these evolved designs have been evaluated in simulation as completed objects, with no attention paid to how, or even if, they can be realistically built. As a consequence, significant human effort is required to transfer the designs to the real world. One way to reduce human involvement in
this regard is to evolve how to build rather than what to build, by using prescriptive rather than descriptive
representations. In the context of Artificial Ontogenies, this requires what
we call Situated Development, in which an object's development
occurs in the same environment as its final evaluation. Not only does
this produce sufficient information on how to build evolved designs,
but it also ensures that only buildable designs are evolved. In this
paper we explore the consequences of Situated Development, and
demonstrate how it can be incorporated into Artificial Ontogenies in order to
generate buildable objects, which can be sequentially assembled in a
realistic 3-D physics environment.
Keywords: evolutionary design, evolutionary robotics, artificial ontogeny, assembly, fabrication.
Download this paper as:
Postscript
(rieffel-gecco-05.ps)
PDF
(rieffel-gecco-05.pdf)
Rieffel, J. and
Pollack, J.B.
(2005). Crossing the Fabrication Gap: Evolving Assembly Plans to Build 3-D Objects.
2005 IEEE Congress on Evolutionary Computation.
Abstract
Evolutionary Computation has demonstrated the ability to design novel and interesting objects. Such objects are increasingly being assembled in the physical world, albeit with some difficulty . An obstacle to this assembly is that most evolved designs are descriptive representations: they specify what to build, but carry no information on how to build it. Inferring a corresponding assembly sequence for such an object is a complex task for any but the most trivial designs. We offer an alternative solution to this spectre of the \emph{Fabrication Gap}, namely the direct evolution of assembly sequences. As we show, such methods not only lead to the evolution of buildable objects, but also lead to the emergence of novel means of assembly as well.
.
Keywords: Artificial Ontogeny, Evolutionary Design, Assembly, Fabrication .
Download this paper as:
Postscript
(jrieffel_cec05.ps)
PDF
(jrieffel_cec05.pdf)
Rieffel, J. and
Pollack, J.B.
(2005). Evolutionary Fabrication: The Emergence of Novel Assembly Methods in Artificial Ontogenies .
SEEDS workshop, at the 2005 Genetic and Evolutionary Computation Conference.
Abstract
Evolutionary Design Systems (EDSs) have demonstrated the ability to generate
a wide array of novel objects, including robots, tables, and
antennas. Often, the novelty of these evolved designs is due to their
ability to discover and exploit important principles of the design
space, such as the truss and the ratchet. One current obstacle to the
real-world application of such EDSs is that they often create purely
descriptive representations, and are therefore capable of
generating designs whose specific assembly is difficult, if not
impossible, to infer. One solution that we offer is to evolve
how to build, rather than what to build. When evolution
occurs in assembly space rather than design space, only
buildable objects are produced. Furthermore, as we demonstrate in
this paper, doing so allows for the emergence not just of novel
designs, but of novel means of assembly.
.
Keywords: Artificial Ontogeny, Evolutionary Design, Assembly, Fabrication .
Download this paper as:
Postscript
(jrieffel_seeds05.ps)
PDF
(jrieffel_seeds05.pdf)
Rieffel, J. and
Pollack, J.
(2005). Evolving Assembly Plans for Fully Automated Design and Assembly.
Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware .
Abstract
Evolutionary Design has demonstrated great potential to automatically
generate a wide array of novel, interesting, and human-competitive
designs. Few of these evolved designs, however, have in turn been
physically manufacture. This is due largely to the fact
that most evolved designs only specify what to build, and carry no
information on how, or even if, a designed object can be assembled in the real
world. When the goal is a physical object, rather than a mere
schematic, substantial further effort, most often
human-level, is subsequently required to develop a physical assembly
process. Evolution of such descriptive representations therefore
stands as an obstacle to the full automation of both design and
assembly. In this paper we describe an alternative, the evolution of
prescriptive representations, which offers to remove human
effort from the design-and-assembly loop.
.
Keywords: evolutionary design, evolutionary robotics, artificial ontogeny, assembly, fabrication.
Download this paper as:
Postscript
(rieffel-eh-05.ps)
PDF
(rieffel-eh-05.pdf)
Viswanathan, S. and
Pollack, J.B.
(2005). How Artificial Ontogenies can retard evolution.
SEEDS workshop, 2005 Genetic and Evolutionary Computation Conference
(GECCO 2005), ACM Press, 2005.
Abstract
Recently there has been much interest in the role of indirect
genetic encodings as a means to achieve increased evolvability.
From this perspective, artificial ontogenies have largely been seen
as a vehicle to relate the indirect encodings to complex phenotypes.
However, the introduction of a development phase does not come without
other consequences. We show that the conjunction of the latent
ontogenic stucture and the common practice of only evaluating the final
phenotype obtained from development can have a net retarding effect
on evolution. Using a formal model of development, we show that
this effect arises primarily due to the relationship of the ontogenic
structure to the fitness function that impacts the properties
being evaluated and selected for during evolution. This effect is
empirically demonstrated with a toy search problem using LOGO-turtle
based embryogenic processes.
Keywords: development, evolution.
Download this paper as:
Postscript
(shiva_seeds05.ps)
Gzipped Postscript
(shiva_seeds05.ps.gz)
PDF
(shiva_seeds05.pdf)
Viswanathan, S. and
Pollack, J.B.
(2005). On the coevolutionary construction of learnable gradients.
Coevolutionary and Coadaptive Systems, AAAI Fall Symposium 2005,
Washington D.C.
Abstract
``The best way for adaptive agents to learn is to be exposed to
problems that are just a little more difficult than those they
already know how to solve''. While this has been a guiding
concept in developing algorithms for gradient construction
in coevolution, it has remained largely an intuition
rather than a formal concept. In this paper, we build on the
order-theoretic formulation of coevolution to develop some
preliminary formal concepts towards clarifying the nature of
the relation between the variational structure imposed by the
representation and coevolutionary learning. By explicitly
marrying the learnability problem to the variational structure
of the learner space, we describe a basic idealization of
how coevolution with an Ideal Teacher could inherently address
the problem of appropriate gradient creation with the intent
that this could serve as a basis to developing practical algorithmic
mechanisms that approximate this idealized behavior.
Keywords: coevolution, representation.
Download this paper as:
Postscript
(AAAI_FS05_shiva.ps)
Gzipped Postscript
(AAAI_FS05_shiva.ps.gz)
PDF
(AAAI_FS05_shiva.pdf)
Viswanathan, S. and
Pollack, J.B.
(2005). On the robustness achievable with stochastic development processes.
The 2005 NASA/DoD Conference on Evolvable Hardware, IEEE Press, 2005
.
Abstract
Manufacturing processes are a key source of faults in complex hardware systems.
Minimizing this impact of manufacturing uncertainties is one way towards
achieving fault tolerant systems. By treating manufacturing as a stochastic
development process, we characterize some of the constraints limiting the levels
of robustness that can be achieved with evolution. The analysis is by introducing
a novel abstraction of development as a strategic decision-making process. Using
this abstraction to analyze a toy-system that simulates a process of noisy assembly,
we compare the maximum robustness achievable with adaptive and non-adaptive
developmental strategies. Even in this highly simplified setup the optimal adaptive
and non-adaptive genotypes reveal a significant empirical difference in their robustness
characteristics. This suggests that the choice of developmental strategy and the properties
of the setup are major constraints on the robustness achievable, even prior
to evolution-related considerations.
Download this paper as:
Postscript
(nasa_eh2005_shiva.ps)
Gzipped Postscript
(nasa_eh2005_shiva.ps.gz)
PDF
(nasa_eh2005_shiva.pdf)
Bader-Natal, A. and
Pollack, J.
(2004). A Population-Differential Method of Monitoring Success and Failure in Coevolution.
Proceedings of the 2004 Genetic and Evolutionary Computation Conference, Springer Verlag, 2004.
Abstract
Coevolutionary algorithms require no domain-specific measure of objective fitness, enabling these algorithms to be applied to domains for which no objective metric is known or for which known metrics are too expensive. But this flexibility comes at the expense of accountability. Past work on monitoring has focused on measuring success, but has ignored failure. This limitation is due to a common reliance on "best-of-generation" (BOG) based analysis, and we propose a population-differential analysis based on an alternate "all-of-generation" (AOG) framework that is not similarly limited.
.
Download this paper as:
PDF
(badernatal_gecco04_poster.pdf)
Bucci, A.,
Pollack, J.B. and
De Jong, E.D.
(2004). Automated Extraction of Problem Structure.
Proceedings of the 2004 Genetic and Evolutionary Computation Conference,
Springer Verlag, 2004.
Abstract
Most problems studied in artificial intelligence possess some form of
structure, but a precise way to define such structure is so far lacking. We
investigate how the notion of problem structure can be made precise, and
propose a formal definition of problem structure. The definition is
applicable to problems in which the quality of candidate solutions is
evaluated by means of a series of tests. This specifies a wide range of
problems: tests can be examples in classification, test sequences for a
sorting network, or opponents for board games. Based on our definition of
problem structure, we provide an automatic procedure for problem structure
extraction, and results of proof-of-concept experiments. The definition of
problem structure assigns a precise meaning to the notion of the underlying
objectives of a problem, a concept which has been used to explain how one
can evaluate individuals in a coevolutionary setting. The ability to
analyze and represent problem structure may yield new insight into existing
problems, and benefit the design of algorithms for learning and search.
Keywords: coevolution, problem structure, geometry, dimensions, underlying
objectives.
Download this paper as:
Postscript
(extr_dims_gecco04.ps)
Gzipped Postscript
(extr_dims_gecco04.ps.gz)
PDF
(extr_dims_gecco04.pdf)
Ficici, Sevan G.
(2004). Solution Concepts in Coevolutionary Algorithms.
Ph.D Dissertation, Brandeis University, May 2004. (Computer Science Department Technical Report CS-03-243).
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.
Keywords: Coevolutionary Algorithms, Evolutionary Game Theory, Machine Learning.
Download this paper as:
Postscript
(ficici_thesis_04.ps)
Gzipped Postscript
(ficici_thesis_04.ps.gz)
PDF
(ficici_thesis_04.pdf)
Ficici, Sevan G.,
Melnik, Ofer and
Pollack, Jordan B.
(2004). Selection in Coevolutionary Algorithms and the Inverse Problem.
Collectives and the Design of Complex Systems, Kagan Tumer and David Wolpert (eds.).
Springer, 2004 pp. 277-294.
Abstract
The inverse problem in the Collective Intelligence framework concerns how the
private utility functions of agents can be engineered such that their selfish
behaviors collectively give rise to a desired world state. In this paper we examine
several selection and fitness-sharing methods used in coevolution and consider their
operation with respect to the inverse problem. The methods we test are truncation and
linear-rank selection, and competitive and similarity-based fitness sharing. Using
evolutionary game theory to establish the desired world state, our analyses show that
variable-sum games with polymorphic Nash are problematic for these methods. Rather
than converge to polymorphic Nash, the methods we test produce cyclic behavior, chaos,
or attractors that lack game-theoretic justification, and therefore fail to solve the
inverse problem. The private utilities of the evolving agents may thus be viewed as
poorly factored---improved private utility does not correspond to improved
world utility. (C) 2004 Springer.
Keywords: Collective Intelligence, Coevolutionary Algorithms, Selection Methods, Fitness Sharing.
Rieffel, J. and
Pollack, J.
(2004). Artificial Ontogenies for Real World Design and Assembly.
Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9) Workshop: Self-Organization and Development in Artificial and Natural Systems (SODANS) 2004.
Abstract
Relatively few evolved designs have made the transition to the real
world. Of those that have, all have been built by hand based upon
descriptive representations (i.e. blueprints) of the evolved object.
As such, human effort is transferred from the design to the assembly
domain. In this paper we suggest harnessing the procedural
representations provided by Artificial Ontogenies to fully automate
both design \emph{and} assembly. We demonstrate the ability of
Artificial Ontogenies to cross one hurdle of real-world assembly,
namely reliably building structures in noisy
environments. We then discuss the advantages of Artificial Ontogenies
for Automated Design and Assembly, and offer suggestions for the
future of the field. .
Keywords: evolutionary design, evolutionary robotics, artificial ontogeny.
Download this paper as:
PDF
(jrieffel_alife_04.pdf)
Rieffel, J. and
Pollack, J.
(2004). The Emergence of Ontogenic Scaffolding in a Stochastic Development Environment.
Proceedings of the 2004 Genetic and Evolutionary Computation Conference, Springer Verlag, 2004.
Abstract
Evolutionary designs based upon Artificial Ontogenies are beginning to
cross from virtual to real environments. In such systems the
evolved genotype is an indirect, procedural representation of the final
structure. To date, most Artificial Ontogenies have relied upon an
error-free development process to generate their phenotypic structure.
In this paper we explore the effects and consequences of developmental
error on Artificial Ontogenies. In a simple evolutionary design task,
and using an indirect procedural representation that lacks the ability to test
intermediate results of development, we demonstrate the emergence of
ontogenic mechanisms which are able to cope with developmental error.
Keywords: evolutionary design, evolutionary robotics, artificial ontogeny.
Download this paper as:
Postscript
(jrieffel_gecco_04.ps)
Gzipped Postscript
(jrieffel_gecco_04.ps.gz)
PDF
(jrieffel_gecco_04.pdf)
Viswanathan, S. and
Pollack, J.
(2004). Towards an evolutionary-developmental approach for real-world substrates.
in Pollack et al., Proceedings of the ninth international conference on the
simulation and synthesis of living systems (Artificial Life IX), Boston, USA
(September 2004), pp. 45 - 50, MIT Press, 2004
.
Abstract
Extending "body-brain" evolution to the real-world presents a number of difficulties
due to conflicting idealizations between evolutionary and constructional models. Toward
addressing this gap, we develop a simple model system to analyze the effects of undoing
these idealizations. Preliminary experiments with this system show that high variability
developmental substrates can influence evolutionary dynamics by causing ambiguities
in selection. Furthermore the substrate can enable the evolution of adaptive responses
to non-deterministic developmental effects.
Download this paper as:
Postscript
(alife2004.ps)
Gzipped Postscript
(alife2004.ps.gz)
PDF
(alife2004.pdf)
Bucci, A. and
Pollack, J.B.
(2003). Focusing versus Intransitivity: Geometrical Aspects of Co-evolution.
Proceedings of the 2003 Genetic and Evolutionary Computation Conference,
Springer Verlag, 2003.
Abstract
Recently, a minimal domain dubbed the numbers game has been proposed to
illustrate well-known issues in co-evolutionary dynamics. The domain
permits controlled introduction of features like intransitivity, allowing
researchers to understand failings of a co-evolutionary algorithm in terms
of the domain. In this paper, we show theoretically that a large class of
co-evolution problems closely resemble this minimal domain. In particular,
all the problems in this class can be embedded into an ordered,
$n$-dimensional Euclidean space, and so can be construed as greater-than
games. Thus, conclusions derived using the numbers game are more widely
applicable than might be presumed. In light of this observation, we present
a simple algorithm aimed at remedying focusing problems and relativism in
the numbers game. With it we show empirically that, contrary to
expectations, focusing in transitive games can be more troublesome for
co-evolutionary algorithms than intransitivity. Practitioners should
therefore be just as wary of focusing issues in application domains.
Keywords: Pareto coevolution, coevolution, coevolutionary theory, posets, intransitivity, focusing, overspecialization.
Download this paper as:
Postscript
(bucci_gecco_focus_03.ps)
Gzipped Postscript
(bucci_gecco_focus_03.ps.gz)
PDF
(bucci_gecco_focus_03.pdf)
De Jong, Edwin D. and
Pollack, Jordan B.
(2003). Learning the Ideal Evaluation Function.
Proceedings of GECCO 2003, pp. 277-288.
Abstract
Designing an adequate fitness function requires substantial knowledge of a problem and of features that indicate progress towards a solution. Coevolution takes the human out of the loop by dynamically constructing the evaluation function based on interactions between evolving individuals. A question is to what extent such automatic evaluation can be adequate. We define the notion of an ideal evaluation function. It is shown that coevolution can in principle achieve ideal evaluation. Moreover, progress towards ideal evaluation can be measured. This observation leads to an algorithm for coevolution. The algorithm makes stable progress on several challenging abstract test problems.
Keywords: coevolution, Pareto-Coevolution, Complete Evaluation Set, ideal evaluation, underlying objectives, Pareto-hillclimber, over-specialization
.
Download this paper as:
Postscript
(dejongpollack03.ps)
Gzipped Postscript
(dejongpollack03.ps.gz)
PDF
(dejongpollack03.pdf)
Ficici, Sevan G. and
Pollack, Jordan B.
(2003). A Game-Theoretic Memory Mechanism for Coevolution.
Proc. 2003 Genetic and Evolutionary Computation Conference, Cantú-Paz, et al (eds.).
Springer, 2003 pp. 286--297.
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. (C) 2003 Springer.
Keywords: Coevolutionary Algorithms, Evolutionary Forgetting, Memory Mechanisms, Game Theory.
Download this paper as:
Postscript
(ficici_gecco03.ps)
Gzipped Postscript
(ficici_gecco03.ps.gz)
PDF
(ficici_gecco03.pdf)
Hornby, Gregory S.
(2003). Generative Representations for Evolutionary Design Automation.
Brandeis University Dept. of Computer Science, Ph.D. Dissertation.
Abstract
In this thesis the class of generative representations is defined and it
is shown that this class of representations improves the scalability
of evolutionary design systems by automatically learning inductive bias of the
design problem thereby capturing design dependencies and better enabling
search of large design spaces.
First, properties of representations are identified as:
combination, control-flow, and abstraction.
Using these properties, representations are classified as
non-generative, or generative.
Whereas non-generative representations use elements of encoded artifacts at
most once in translation from encoding to actual artifact,
generative representations have the ability to reuse parts of the data
structure for encoding artifacts through control-flow (using iteration)
and/or abstraction (using labeled procedures).
Unlike non-generative representations, which do not scale with design
complexity because they cannot capture design dependencies in their structure,
it is argued that evolution with generative representations can better scale
with design complexity because of their ability to hierarchically create
assemblies of modules for reuse, thereby enabling better search of large
design spaces.
Second, GENRE, an evolutionary design system using a generative
representation, is described.
Using this system, a non-generative and a generative representation are
compared on four classes of designs:
three-dimensional static structures constructed from voxels;
neural networks; actuated robots controlled by oscillator networks;
and neural network controlled robots.
Results from evolving designs in these substrates show that the
evolutionary design system is capable of finding solutions of higher fitness
with the generative representation than with the non-generative representation.
This improved performance is shown to be a result
of the generative representation's ability to capture intrinsic properties of
the search space and its ability to reuse parts of the encoding in
constructing designs.
By capturing design dependencies in its structure, variation operators
are more likely to be successful with a generative representation than
with a non-generative representation.
Second, reuse of data elements in encoded designs improves the ability
of an evolutionary algorithm to search large design spaces.
The project page for this work is at:
http://www.demo.cs.brandeis.edu/pr/evo_design/evo_design.html
and the source code can be
downloaded from here.
Keywords: animation, artificial life, representation, intelligent agents, Lindenmayer systems (L-systems).
Download this paper as:
Postscript
(hornby_phd.ps)
Gzipped Postscript
(hornby_phd.ps.gz)
PDF
(hornby_phd.pdf)
Levy, Simon D. and
Pollack, Jordan B.
(2003). Escape the Building-Block / Rule Dichotomy: A Case Study.
AAAI Spring Symposium on Computational Synthesis.
Abstract
The traditional approach to complex problems in science and
engineering is to break down each problem into a set of primitive
building blocks, which are then combined by rules to form structures.
In general, this approach has proved successful enough that it is rarely
mentioned, let alone questioned, in traditional approaches to AI and
related fields.
The literature on connectionist networks, on the other hand, is
fraught with attempts to address the issue of rule-governed
compositionality. On the whole, attempts to scale up recursive
compositional structures using a neural network have met with only
modest success. In this paper we describe a particular recurrent
neural network, Recursive Auto-Associative Memory (RAAM), whose
initial scaling limitations we can now understand as an artifact of
our misunderstanding of its "natural" behavior. Specifically, we show
how treating the building blocks and compositional operators as merely
different aspects of the same underlying (fractal) dynamical system
allows even small RAAM networks to represent compositional, modular
structures of arbitrary complexity. We believe that the insight
gained from the result may have profound implications for the field of
computational synthesis as a whole.
Keywords: Building Blocks, Rules, Neural Networks, Fractals.
Download this paper as:
Postscript
(aaai03.ps)
Gzipped Postscript
(aaai03.ps.gz)
PDF
(aaai03.pdf)
Bucci, A. and
Pollack, J.B.
(2002). A Mathematical Framework for the Study of Coevolution (prepublication).
Foundations of Genetic Algorithms 7. Proceedings of FOGA VII,
Torremolinos Spain, 4-6 September 2002 (prepublication version -- to appear
spring 2003).
Abstract
Despite achieving compelling results in engineering and optimization
problems, coevolutionary algorithms remain difficult to understand, with
most knowledge to date coming from practical successes and failures, not
from theoretical understanding. Thus, explaining why coevolution succeeds is
still more art than science. In this paper, we present a theoretical
framework for studying coevolution based on the mathematics of ordered sets.
We use this framework to describe solutions for coevolutionary optimization
problems, generalizing the notion of Pareto non-dominated front from the
field of multi-objective optimization. Our framework focuses attention on
the order structure of solution and test sets, which we argue is a key
source of difficulty in coevolutionary optimization problems. As an
application of the framework we show, in the special case of two-player
games, that Pareto dominance is closely related to intransitivities in the
game.
Keywords: Pareto coevolution, coevolution, coevolutionary algorithms, coevolution theory, order theory.
Download this paper as:
Postscript
(bucci_foga_po_02.ps)
Gzipped Postscript
(bucci_foga_po_02.ps.gz)
PDF
(bucci_foga_po_02.pdf)
Bucci, A. and
Pollack, J.B.
(2002). Order-theoretic Analysis of Coevolution Problems: Coevolutionary Statics.
2002 Genetic and Evolutionary Computation Conference Workshop: Understanding Coevolution.
Abstract
We present an order-theoretic framework for analyzing coevolution
problems. The framework focuses attention on the underlying problem
definition, or statics of coevolution, as opposed to the dynamics of
search algorithms. We define a notion of solution for coevolution which
generalizes similar solution concepts in GA function optimization and
MOO. We then define the ideal test set, a potentially small set of
tests which allow us to find the solution set of a problem. One feature
of the ideal test set is that we are able to categorize problems by
considering its cardinality. We conclude by discussing three issues
which commonly arise in coevolution from the point of view of
coevolutionary statics, pointing out analytical attacks on these issues.
Keywords: Pareto coevolution, coevolution, coevolutionary algorithms, coevolution theory, order theory.
Download this paper as:
Postscript
(bucci_gecco_po_02.ps)
Gzipped Postscript
(bucci_gecco_po_02.ps.gz)
PDF
(bucci_gecco_po_02.pdf)
De Jong, E.D. and
Oates, T.
(2002). A Coevolutionary Approach to Representation Development .
Proceedings of the ICML-2002 Workshop on Development of Representations.
Abstract
The representation of a learning or search problem can greatly impact its performance. An alternative to hand-constructing an appropriate representation is to let the learning method adapt its own representation. We investigate this in a setup where building blocks and assemblies thereof are coevolved. Building blocks may employ other building blocks, thus leading to hierarchical constructions. In experiments, this is observed to lead to highly compact representations of sequences that are useful as building blocks. The method is able to solve problems requiring long sequences of primitive operators. Control experiments using a conventional evolutionary method were much less efficient, and did not find solutions to the problems. Limitations of the current method are discussed.
.
Keywords: Development of representations, coevolution, bias learning.
Download this paper as:
Postscript
(dejongoates02.ps)
Gzipped Postscript
(dejongoates02.ps.gz)
PDF
(dejongoates02.pdf)
Hornby, Gregory S. and
Pollack, Jordan. B.
(2002). Creating High-Level Components with a Generative Representation for Body-Brain Evolution.
Artificial Life, 8:3.
Abstract
One of the main limitations of scalability in body-brain evolution
systems is the representation chosen for encoding creatures.
This paper defines a class of representations called
generative representations,
which are identified by their ability to reuse
elements of the genotype in the translation to the phenotype.
This paper presents an example of a generative representation
for the concurrent evolution of the morphology and neural controller of
simulated robots,
and also introduces Genre, an evolutionary system for
evolving designs using this representation.
Applying Genre to the task of evolving robots for locomotion
and comparing it against a non-generative (direct) representation,
shows that the generative representation system rapidly produces robots
with significantly greater fitness.
Analyzing these results shows that the generative representation system achieves
better performance by capturing useful bias from the design space
and by allowing viable large scale mutations in the phenotype.
Generative representations thereby enable the
encapsulation, coordination, and reuse of assemblies of parts.
The project page for this work is at:
http://www.demo.cs.brandeis.edu/pr/evo_design/evo_design.html
and the source code can be
downloaded from here.
Keywords: animation, artificial life, representation, intelligent agents, Lindenmayer systems (L-systems).
Download this paper as:
Postscript
(hornby_alife02.ps)
Gzipped Postscript
(hornby_alife02.ps.gz)
PDF
(hornby_alife02.pdf)
Levy, Simon D.
(2002). Infinite RAAM: Initial Investigations into a Fractal Basis for Cognition.
Ph.D. Thesis, Brandeis University, July 2002.
Abstract
This thesis attempts to provide an answer to the question ``What is
the mathematical basis of cognitive representations?'' The answer we
present is a novel connectionist framework called Infinite RAAM. We
show how this framework satisfies the cognitive requirements of
systematicity, compositionality, and scalable representational
capacity, while also exhibiting ``natural'' properties like
learnability, generalization, and inductive bias.
The contributions of this work are twofold: First, Infinite RAAM shows
how connectionist models can exhibit infinite competence for
interesting cognitive domains like language. Second, our
attractor-based learning algorithm provides a way of learning
structured cognitive representations, with robust decoding and
generalization. Both results come from allowing the dynamics of the
network to devise emergent representations during learning.
An appendix provides Matlab code for the experiments described in the thesis.
Keywords: Neural Networks, Fractals, Connectionism, Language, Grammar.
Download this paper as:
Postscript
(levythesis.ps)
Gzipped Postscript
(levythesis.ps.gz)
PDF
(levythesis.pdf)
Melnik, O.
(2002). Decision Region Connectivity Analysis: A method for analyzing high-dimensional classifiers.
Machine Learning 48:(1/2/3) .
Abstract
In this paper we present a method to extract qualitative
information from any classification model that uses decision regions
to generalize (e.g., feed-forward neural nets, SVMs, etc). The
method's complexity is independent of the dimensionality of the input
data or model, making it computationally feasible for the analysis of
even very high-dimensional models. The qualitative information
extracted by the method can be directly used to analyze the
classification strategies employed by a model, and also to compare
strategies across different model types.
Keywords: Decision Regions, Classifiers, Classifier Analysis, Representation,
Representation Extraction, Rule Extraction, Classifier Construction,
Neural Networks, Principal Component Analysis, Graph Algorithms,
Support Vector Machines, K Nearest Neighbors, Convex, Concave,
Generalization, Artifacts, Noise, Minimum Volume Ellipsoid,
High-Dimensional Visualization.
Download this paper as:
Postscript
(drca_ml.ps)
Gzipped Postscript
(drca_ml.ps.gz)
PDF
(drca_ml.pdf)
Melnik, O. and
Pollack, J.B.
(2002). Theory and scope of exact representation extraction from feed-forward networks.
Cognitive Systems Research 3(2), previously Brandeis CS Tech Report CS-99-205, see also a Results Web Page.
Abstract
An algorithm to extract representations from feed-forward perceptron
networks (threshold) is outlined. The representation is based on polytopic
decision regions in the input space-- and is exact not an approximation.
Using this exact representation we explore scope questions, such as
when and where do networks form artifacts, or what can we tell about
network generalization from its representation. The exact nature of
the algorithm also lends itself to theoretical questions about representation
extraction in general, such as what is the relationship between factors
such as input dimensionality, number of hidden units, number of hidden
layers, how the network output is interpreted to the potential complexity
of the network's function. .
Keywords: neural networks, representation, rule-extraction, polytope, computational ge
ometry, generalization, artifacts, complexity .
Download this paper as:
Gzipped Postscript
(nc1.ps.gz)
PDF
(nc1.pdf)
Peshkin, L. and
De Jong, E.D.
(2002). Context-based policy search: transfer of experience across problems.
Proceedings of the ICML-2002 Workshop on Development of Representations.
Abstract
An important question in reinforcement learning is how generalization may be performed. This problem is especially important if the learning agent receives only partial information about the state of the environment. Typically, the bias required for generalization is chosen by the experimenter. Here, we investigate a way for the {\em learning method} to extract bias from learning one problem and apply it in subsequent problems. We use a gradient-based policy search method, and look for controllers that consist of a context component and an action component. Empirical results on a two-agent coordination problem are reported. It was found that learning a bias made it possible to address problems that were not solved otherwise.
.
Keywords: Policy search, bias learning, context-based policy, generalization, POMDPs.
Download this paper as:
Postscript
(peshkindejong02.ps)
Gzipped Postscript
(peshkindejong02.ps.gz)
PDF
(peshkindejong02.pdf)
Watson, R.A.
(2002). Compositional Evolution: Interdisciplinary Investigations in Evolvability, Modularity, and Symbiosis.
PhD Dissertation, Brandeis University, May 2002.
Abstract
Conventionally, evolution by natural selection is almost inseparable from the notion of accumulating successive slight variations. Although it has been suggested that symbiotic mechanisms that combine together existing entities provide an alternative to gradual, or 'accretive', evolutionary change, there has been disagreement about what impact these mechanisms have on our understanding of evolutionary processes. Meanwhile, in artificial evolution methods used in computer science, it has been suggested that the composition of genetic material under sexual recombination may provide adaptation that is not available under mutational variation, but there has been considerable difficulty in demonstrating this formally. Thus far, it has been unclear what types of systems, if any, can be evolved by such 'compositional' mechanisms that cannot be evolved by accretive mechanisms.
This dissertation takes an interdisciplinary approach to this question by building abstract computational simulations of accretive and compositional mechanisms. We identify a class of complex systems possessing 'modular interdependency', incorporating highly epistatic but modular substructure. This class typifies characteristics that are pathological for accretive evolution - the corresponding fitness landscape is highly rugged, has many local optima creating broad fitness saddles, and includes 'irreducibly complex' adaptations that cannot be reached by a succession of gradually changing proto-systems. Nonetheless, we provide simulations to show that this class of system is easily evolvable under sexual recombination or a mechanism of 'symbiotic encapsulation'. Our simulations and analytic results help us to understand the fundamental differences in the adaptive capacities of these mechanisms, and the conditions under which they provide an adaptive advantage. These models exemplify how certain kinds of complex systems, considered unevolvable under normal accretive change, are, in principle, easily evolvable under compositional evolution.
Keywords: genetic algorithms, building-block hypothesis, hierarchical if-and-only-if (HIFF), sexual recombination, symbiogenesis, major evolutionary transitions .
Download this paper as:
Postscript
(watson_thesis_2002.ps)
Gzipped Postscript
(watson_thesis_2002.ps.gz)
PDF
(watson_thesis_2002.pdf)
Watson, R.A.
and
Pollack, J.B.
(2002). A Computational Model of Symbiotic Composition in Evolutionary Transitions (PREPRINT)
.
Biosystems, Special Issue on Evolvability, (preprint 2001 - to appear 2002)
.
Abstract
Several of the major transitions in evolutionary history, such as the symbiogenic origin of eukaryotes from prokaryotes, share the feature that existing entities became the components of composite entities at a higher level of organisation. This composition of pre-adapted extant entities into a new whole is a fundamentally different source of variation from the gradual accumulation of small random variations, and it has some interesting consequences for issues of evolvability. Intuitively, the pre-adaptation of sets of features in reproductively independent specialists suggests a form of ‘divide and conquer’ decomposition of the adaptive domain. Moreover, the compositions resulting from one level may become the components for compositions at the next level, thus scaling-up the variation mechanism. In this paper, we explore and develop these concepts using a simple abstract model of symbiotic composition to examine its impact on evolvability. To exemplify the adaptive capacity of the composition model, we employ a scale-invariant fitness landscape exhibiting significant ruggedness at all scales. Whilst innovation by mutation and by conventional evolutionary algorithms becomes increasingly more difficult as evolution continues in this landscape, innovation by composition is not impeded as it discovers and assembles component entities through successive hierarchical levels.
.
Keywords: symbiogenesis, major evolutionary transitions, evolutionary computation, evolutionary algorithms, Symbiogenic Evolutionary Adaptation Model (SEAM), Hierarchical-if-and-only-if, (HIFF).
.
Download this paper as:
Postscript
(biosystems_scet.ps)
Gzipped Postscript
(biosystems_scet.ps.gz)
PDF
(biosystems_scet.pdf)
Watson, Richard A.,
Ficici, Sevan G. and
Pollack, Jordan B.
(2002). Embodied Evolution: Distributing an Evolutionary Algorithm in a Population of Robots.
Robotics and Autonomous Systems 39/1 (2002) 1-18.
Abstract
We introduce Embodied Evolution (EE) as a new methodology for evolutionary robotics (ER).
EE uses a population of physical robots that autonomously reproduce with one another while
situated in their task environment. This constitutes a fully distributed evolutionary algorithm
embodied in physical robots. Several issues identified by researchers in the evolutionary
robotics community as problematic for the development of ER are alleviated by the use of a
large number of robots being evaluated in parallel. Particularly, EE avoids the pitfalls of
the simulate-and-transfer method and allows the speed-up of evaluation time by utilizing
parallelism. The more novel features of EE are that the evolutionary algorithm is entirely
decentralized, which makes it inherently scalable to large numbers of robots, and that it
uses many robots in a shared task environment, which makes it an interesting platform for
future work in collective robotics and Artificial Life. We have built a population of eight
robots and successfully implemented the first example of Embodied Evolution by designing a fully
decentralized, asynchronous evolutionary algorithm. Controllers evolved by EE outperform a
hand-designed controller in a simple application. We introduce our approach and its
motivations, detail our implementation and initial results, and discuss the advantages and
limitations of EE.
Keywords: Evolutionary Robotics, Artificial Life, Evolutionary Algorithms, Distributed Learning, Collective Robotics.
De Jong, Edwin D.,
Watson, Richard A. and
Pollack, Jordan B.
(2001). Reducing Bloat and Promoting Diversity using Multi-Objective Methods.
Proceedings of GECCO 2001.
Abstract
Two important problems in genetic programming (GP) are its
tendency to find unnecessarily large trees (bloat), and the general
evolutionary algorithms problem that diversity in the population can
be lost prematurely. The prevention of these problems is frequently
an implicit goal of basic GP. We explore the potential of techniques
from multi-objective optimization to aid GP by adding explicit
objectives to avoid bloat and promote diversity. The even 3, 4, and
5-parity problems were solved efficiently compared to basic GP results
from the literature. Even though only non-dominated individuals were
selected and populations thus remained extremely small, appropriate
diversity was maintained. The size of individuals visited during
search consistently remained small, and solutions of what we believe
to be the minimum size were found for the 3, 4, and 5-parity problems.
Keywords: genetic programming, code growth, bloat, introns, diversity maintenance, evolutionary multi-objective optimization, Pareto optimality.
Download this paper as:
Postscript
(rbpd_gecco01.ps)
Gzipped Postscript
(rbpd_gecco01.ps.gz)
PDF
(rbpd_gecco01.pdf)
De Jong, Edwin D. and
Pollack, Jordan B.
(2001). Utilizing Bias to Evolve Recurrent Neural Networks.
Proceedings of IJCNN 2001.
Abstract
Since architectures and weights for recurrent neural networks are difficult to design, evolutionary methods may be applied to search the space of such networks. However, for all but trivial problems, this space is very large. Hence, biases are required that guide the search. Here, we investigate solving a smaller related problem to establish such a bias. Networks are specified by trees containing operators that act on nodes (neurons) and edges (connections). We demonstrate the approach on a signal reproduction task that requires internal state. Performance on a small problem size was improved by solving a smaller problem first. By repeatedly applying the principle, versions of the problem were solved that were not solved by a direct approach.
.
Keywords: recurrent neural networks, evolution of neural networks, cellular encoding, useful bias.
Download this paper as:
Postscript
(ubternn_ijcnn.ps)
Gzipped Postscript
(ubternn_ijcnn.ps.gz)
PDF
(ubternn_ijcnn.pdf)
Ficici, Sevan G. and
Pollack, Jordan B.
(2001). Game Theory and the Simple Coevolutionary Algorithm: Some Preliminary Results on Fitness Sharing.
GECCO 2001 Workshop on Coevolution: Turning Adaptative Algorithms upon Themselves.
Abstract
Coevolutionary domains are fundamentally game-theoretic in nature because the merit of
an agent cannot be surmised without having it interact with other agents. In this
paper, we explore the relevance of game-theory to the analysis of coevolutionary
algorithm dynamics. Particularly, we show how a game-theoretic framework allows us to
ascertain the effects that fitness sharing can have on a coevolutionary algorithm in a
variable-sum game. We show analytically that competitive fitness sharing and
similarity-based fitness sharing can cause a coevolutionary algorithm to converge to
solutions that lack game-theoretic justification.
Keywords: Coevolutionary Algorithms, Fitness Sharing, Game Theory.
Download this paper as:
Postscript
(prfs_gecco_01.ps)
Gzipped Postscript
(prfs_gecco_01.ps.gz)
Ficici, Sevan G. and
Pollack, Jordan B.
(2001). Pareto Optimality in Coevolutionary Learning.
Advances in Artificial Life: 6th European Conference (ECAL 2001)J. Kelemen, P. Sosik (eds.), Springer, 2001.
Abstract
We develop a novel coevolutionary algorithm based upon the concept of Pareto optimality.
The Pareto criterion is core to conventional multi-objective optimization (MOO) algorithms.
We can think of agents in a coevolutionary system as performing MOO, as well: An agent
interacts with many other agents, each of which can be regarded as an objective for
optimization. We adapt the Pareto concept to allow agents to follow gradient and
create gradient for others to follow, such that co-evolutionary learning succeeds.
We demonstrate our Pareto coevolution methodology with the majority function, a density
classification task for cellular automata.
Keywords: Coevolution, Pareto Optimality, Gradient, Majority Function.
Download this paper as:
Postscript
(ficici_ecal_01.ps)
Gzipped Postscript
(ficici_ecal_01.ps.gz)
PDF
(ficici_ecal_01.pdf)
Funes, Pablo
(2001). Evolution of Complexity in Real-World Domains.
Brandeis University Dept. of Computer Science PhD Dissertation.
Abstract
Artificial Life research brings together methods from Artificial Intelligence
(AI), philosophy and biology, studying the problem of evolution of complexity
from what we might call a constructive point of view, trying to replicate adaptive
phenomena using computers and robots.
Here we wish to shed new light on the issue by showing how computer-simulated
evolutionary learning methods are capable of discovering complex emergent properties
in complex domains. Our stance is that in AI the most interesting results come
from the interaction between learning algorithms and real domains, leading to
discovery of emergent properties, rather than from the algorithms themselves.
The theory of natural selection postulates that generate-test-regenerate dynamics,
exemplified by life on earth, when coupled with the kinds of environments found
in the natural world, have lead to the appearance of complex forms. But artificial
evolution methods, based on this hypothesis, have only begun to be put in contact
with real-world environments.
In the present thesis we explore two aspects of real-world environments as they
interact with an evolutionary algorithm. In our first experimental domain (chapter
2) we show how structures can be evolved under gravitational
and geometrical constraints, employing simulated physics. Structures evolve
that exploit features of the interaction between brick-based structures and
the physics of gravitational forces.
In a second experimental domain (chapter 3) we study how a
virtual world gives rise to co-adaptation between human and agent species. In
this case we look at the competitive interaction between two adaptive species.
The purely reactive nature of artificial agents in this domain implies that
the high level features observed cannot be explicit in the genotype but rather,
they emerge from the interaction between genetic information and a changing
domain.
Emergent properties, not obvious from the lower level description, amount to
what we humans call complexity, but the idea stands on concepts which resist
formalization -- such as difficulty or complicatedness. We show how simulated
evolution, exploring reality, finds features of this kind which are preserved
by selection, leading to complex forms and behaviors. But it does so without
creating new levels of abstraction -- thus the question of evolution of modularity
remains open. .
Download this paper as:
HTML
(funes_phd.html)
Postscript
(funes_phd.ps)
PDF
(funes_phd.pdf)
Hornby, Gregory. S. and
Pollack, Jordan. B.
(2001). Body-Brain Co-evolution Using L-systems as a Generative Encoding.
Genetic and Evolutionary Computation Conference.
Abstract
We co-evolve the morphology and controller of artificial creatures
using two integrated generative processes.
L-systems are used as the common generative encoding for both
body and brain.
Combining the languages of both into a single L-system allows
for linkage between the genotype of the controller and the parts
of the morphology that it controls.
Creatures evolved by this system are more complex than previous
work, having an order of magnitude more parts and a higher degree
of regularity.
The project page for this work is at:
http://www.demo.cs.brandeis.edu/pr/evo_design/evo_design.html
and the source code can be
downloaded from here.
Keywords: L-systems, generative encoding, design.
Download this paper as:
Postscript
(hornby_gecco01.ps)
Gzipped Postscript
(hornby_gecco01.ps.gz)
PDF
(hornby_gecco01.pdf)
Hornby, Gregory. S.,
Lipson, Hod and
Pollack, Jordan. B.
(2001). Evolution of Generative Design Systems for Modular Physical Robots.
IEEE International Conference on Robotics and Automation.
Abstract
Recent research has demonstrated the ability for automatic design
of the morphology and control of real physical robots using techniques
inspired by biological evolution. The main criticism of the
evolutionary design approach, however, is that it is doubtful
whether it will reach the high complexities necessary for
practical engineering.
Here we claim that for automatic design systems to scale in complexity
the designs they produce must be made of re-used modules.
Our approach is based on the use of a generative design grammar subject
to an evolutionary process.
Unlike a direct encoding of a design,
a generative design specification can re-use components,
giving it the ability to create more complex modules
from simpler ones.
Re-used modules are also valuable for improved efficiency
in testing and construction.
We describe a system for creating generative specifications
capable of hierarchical modularity by combining Lindenmayer
systems with evolutionary algorithms.
Using this system we demonstrate for the first time a generative
system for physical, modular, 2D locomoting robots and their controllers.
The project page for this work is at:
http://www.demo.cs.brandeis.edu/pr/evo_design/evo_design.html
and the source code can be
downloaded from here.
Keywords: L-systems, generative encoding, design, robotics.
Download this paper as:
Postscript
(hornby_icra01.ps)
Gzipped Postscript
(hornby_icra01.ps.gz)
PDF
(hornby_icra01.pdf)
Hornby, Gregory S. and
Pollack, Jordan. B.
(2001). Evolving L-Systems To Generate Virtual Creatures.
Computers and Graphics, 25:6, pp 1041-1048.
Abstract
Virtual creatures play an increasingly important role in
computer graphics as special effects and background characters.
The artificial evolution of such creatures potentially offers
some relief from the difficult and time consuming task of
specifying morphologies and behaviors. But, while artificial
life techniques have been used to create a variety of virtual
creatures, previous work has not scaled beyond creatures with
50 components and the most recent work has generated creatures
that are unnatural looking. Here we describe a system that
uses Lindenmayer systems (L-systems) as the encoding of an
evolutionary algorithm (EA) for creating virtual creatures.
Creatures evolved by this system have hundreds of parts, and
the use of an L-system as the encoding results in creatures
with a more natural look.
The project page for this work is at:
http://www.demo.cs.brandeis.edu/pr/evo_design/evo_design.html
and the source code can be
downloaded from here.
Keywords: animation, artificial life, representation, intelligent agents, Lindenmayer systems (L-systems).
Download this paper as:
Postscript
(hornby_cag01.ps)
Gzipped Postscript
(hornby_cag01.ps.gz)
PDF
(hornby_cag01.pdf)
Hornby, Gregory. S. and
Pollack, Jordan. B.
(2001). The Advantages of Generative Grammatical Encodings for Physical Design.
Congress on Evolutionary Computation.
Abstract
One of the applications of evolutionary algorithms is the automatic
creation of designs. For evolutionary techniques to scale
to the complexities necessary for actual engineering problems, it has
been argued that generative systems, where the genotype is
an algorithm for constructing the final design, should be used as
the encoding.
We describe a system for creating generative specifications
by combining Lindenmayer systems with evolutionary algorithms
and apply it to the problem of generating table designs.
Designs evolved by our system reach an order of magnitude more
parts than previous generative systems.
Comparing it against a non-generative encoding we find that
the generative system produces designs with higher fitness and
is faster than the non-generative system.
Finally, we demonstrate the ability of our system to go from
design to manufacture by constructing evolved table designs
using rapid prototyping equipment.
The project page for this work is at:
http://www.demo.cs.brandeis.edu/pr/evo_design/evo_design.html
and the source code can be
downloaded from here.
.
Keywords: L-systems, generative encoding, design.
Download this paper as:
Postscript
(hornby_cec01.ps)
Gzipped Postscript
(hornby_cec01.ps.gz)
PDF
(hornby_cec01.pdf)
Levy, S. and
Pollack, J.
(2001). Infinite RAAM: A Principled Connectionist Substrate for Cognitive Modeling.
ICCM2001, Lawrence Erlbaum Associates.
Abstract
Unification-based approaches have come to play an important role in
both theoretical and applied modeling of cognitive processes, most
notably natural language. Attempts to model such
processes using neural networks have met with some success, but have
faced serious hurdles caused by the limitations of standard
connectionist coding schemes. As a contribution to this effort, this
paper presents recent work in Infinite RAAM (IRAAM), a new
connectionist unification model. Based on a fusion of recurrent neural
networks with fractal geometry, IRAAM allows us to understand the
behavior of these networks as dynamical systems. Using a logical
programming language as our modeling domain, we show how this
dynamical-systems approach solves many of the problems faced by
earlier connectionist models, supporting unification over arbitrarily
large sets of recursive expressions. We conclude that IRAAM can
provide a principled connectionist substrate for unification in a
variety of cognitive modeling domains.
Keywords: unification, neural networks, fractals, dynamical systems, iterated
function systems, recurrent neural networks, language, grammar, competence.
Download this paper as:
Postscript
(raam-iccm01.ps)
PDF
(raam-iccm01.pdf)
Levy, S. and
Pollack, J.B.
(2001). Logical Computation on a Fractal Neural Substrate.
IJCNN 2001, IEEE press .
Abstract
Attempts to use neural networks to model recursive symbolic
processes like logic have met with some success, but have
faced serious hurdles caused by the limitations of standard
connectionist coding schemes. As a contribution to this effort, this
paper presents recent work in Infinite RAAM (IRAAM), a new
connectionist unification model based on a fusion of recurrent neural
networks with fractal geometry. Using a logical
programming language as our modeling domain, we show how this
approach solves many of the problems faced by
earlier connectionist models, supporting arbitrarily
large sets of logical expressions.
Keywords: neural networks, fractals, unification, logic,
dynamical systems, iterated function systems, recurrent neural networks.
Download this paper as:
Gzipped Postscript
(raam-ijcnn01.ps.gz)
PDF
(raam-ijcnn01.pdf)
Noble, J.
and
Watson, R.A.
(2001). Pareto coevolution: Using performance against coevolved opponents in a game as dimensions for Pareto selection
.
In Spector, L., Goodman, E., Wu, A., Langdon, W.B., Voigt, H.-M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M., & Burke, E. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pp. 493-500. Morgan Kauffman, San Francisco.
.
Abstract
When using an automatic discovery method to find a good strategy in a game, we hope to find one that performs well against a wide variety of opponents. An appealing notion in the use of evolutionary algorithms to coevolve strategies is that the population represents a set of different strategies against which a player must do well. Implicit here is the idea that different players represent different “dimensions” of the domain, and being a robust player means being good in many (preferably all) dimensions of the game. Pareto coevolution makes this idea of “players as dimensions” explicit. By explicitly treating each player as a dimension, or objective, we may then use established multi-objective optimisation techniques to find robust strategies. In this paper we apply Pareto coevolution to Texas Hold’em poker, a complex real-world game of imperfect information. The performance of our Pareto coevolution algorithm is compared with that of a conventional genetic algorithm and shown to be promising.
.
Download this paper as:
Postscript
(gecco01_noble.ps)
Gzipped Postscript
(gecco01_noble.ps.gz)
PDF
(gecco01_noble.pdf)
Pollack, Jordan B.,
Lipson, Hod,
Ficici, Sevan G.,
Funes, Pablo,
Hornby, Greg and
Watson, Richard A.
(2001). .
"Evolutionary Techniques in Physical Robots," in Creative Evolutionary Systems, Peter J. Bently and David W. Corne (eds). Morgan-Kaufmann, 2001.
Pollack, Jordan. B.,
Lipson, Hod,
Hornby, Gregory S. and
Funes, Pablo
(2001). Three Generations of Automatically Designed Robots.
Artificial Life, 7:3.
Abstract
The difficulties associated with designing, building and
controlling robots have led their development to a stasis:
applications are limited mostly to repetitive tasks with
predefined moves. Over the last few years we have been trying
to address this challenge through an alternative approach:
Rather than trying to control an existing macine, or create
a general-purpose robot, we propose that both the morphology
and the controller should evolve at the same time. This
process can lead to the automatic design and fabrication
of special purpose mechanisms and controllers that achieve
specific short-term objectives. Here we provide a brief
review of three generations of our recent research, underlying
the robots shown on the cover of this issue: Automatically
designed static structures, automatically designed and manufactured
dynamic electromechanical systems, and modular robots automatically
designed through a generative DNA-like encoding.
Keywords: robotics.
Download this paper as:
Postscript
(pollack_alife01.ps)
Gzipped Postscript
(pollack_alife01.ps.gz)
PDF
(pollack_alife01.pdf)
Watson, R.A. and
Pollack, J.B.
(2001). Symbiotic Composition and Evolvability.
Advances in Artificial Life, 6th European Conference, (ECAL 2001) , Prague, Czech Republic, September 10-14, 2001, Proceedings.
Jozef Kelemen, Petr Sosik (Eds.): Lecture Notes in Computer Science 2159 Springer 2001, ISBN 3-540-42567-5. pp. 480-490.
Abstract
Several of the Major Transitions in natural evolution, such as the symbiogenic origin of eukaryotes from prokaryotes, share the feature that existing entities became the components of composite entities at a higher level of organisation. This composition of pre-adapted extant entities into a new whole is a fundamentally different source of variation from the gradual accumulation of small random variations, and it has some interesting consequences for issues of evolvability. In this paper we present a very abstract model of `symbiotic composition' to explore its possible impact on evolvability. A particular adaptive landscape is used to exemplify a class where symbiotic composition has an adaptive advantage with respect to evolution under mutation and sexual recombination. Whilst innovation using conventional evolutionary algorithms becomes increasingly more difficult as evolution continues in this problem, innovation via symbiotic composition continues through successive hierarchical levels unimpeded. © Springer-Verlag. Springer Verlag on-line
.
Keywords: evolvability, symbiosis, 'Symbiogenic Evolutionary Adaptation Model' (SEAM), Hierarchical-IFF (HIFF), hierarchically decomposable modularity.
Download this paper as:
Postscript
(ecal01_sce.ps)
Gzipped Postscript
(ecal01_sce.ps.gz)
PDF
(ecal01_sce.pdf)
Watson, R.A.
(2001). Analysis of Recombinative Algorithms on a Non-Separable Building-Block Problem.
Foundations of Genetic Algorithms, Volume 6 , proceedings of FOGA VI, Charlottesville, VA, July 21-23, 2000, Edited by Worthy N. Martin and William M. Spears, Morgan Kaufmann.
Abstract
Our analysis seeks to exemplify the utility of crossover by studying a non-separable building-block problem that is as easy as possible under recombination but very hard for any kind of mutation-based algorithm. The interdependent fitness contributions of blocks in this problem produce a search space that has an exponential number of local optima for a mutation-only algorithm. In contrast, the problem has no local optima for a recombinative algorithm - that is, there is always a path of monotonically increasing fitness leading to the global optimum. We give an upper bound on the expected time for a recombinative algorithm to solve this problem by proving the existence of a path to the solution and calculating the time for each step on this path. Ordinarily, such a straightforward approach would be defeated because both the existence of a path, and the time for a step, are dependent on the state of the population when using recombination. However, to calculate an upper bound on the expected time it is sufficient to know certain properties, or invariants, of the population rather than its exact state. Our initial proofs utilise a 'recombinative hill-climber', which applies crossover repeatedly to just two strings, for this purpose. Though our analysis does not transfer directly to a GA with a full population, a solution time based on the assumption that the population has the necessary invariant properties agrees with empirical results.
Keywords: genetic algorithms, building-block hypothesis, hierarchical if-and-only-if, recombinative hill-climber, non-separable building-block problem. .
Download this paper as:
Postscript
(foga6_ara.ps)
Gzipped Postscript
(foga6_ara.ps.gz)
PDF
(foga6_ara.pdf)
Watson, R.A. and
Pollack, J.B.
(2001). Coevolutionary Dynamics in a Minimal Substrate.
Proceedings of the 2001 Genetic and Evolutionary Computation Conference, Spector, L, et al (eds.), Morgan Kaufmann, 2001.
Abstract
One of the central difficulties of coevolutionary methods arises from 'intransitive superiority' - in a two-player game, for example, the fact that A beats B, and B beats C, does not exclude the possibility that C beats A. Such cyclic superiority in a coevolutionary substrate is hypothesized to cause cycles in the dynamics of the population such that it 'chases its own tail' - traveling through some part of strategy space more than once despite apparent improvement with each step. It is often difficult to know whether an application domain contains such difficulties and to verify this hypothesis in the failure of a given coevolutionary set-up. In this paper we wish to elucidate some of the issues and concepts in an abstract domain where the dynamics of coevolution can be studied simply and directly. We define three simple 'number games' that illustrate intransitive superiority and resultant oscillatory dynamics, as well as some other relevant concepts. These include the distinction between a player's perceived performance and performance with respect to an external metric, and the significance of strategies with a multi-dimensional nature. These features alone can also cause oscillatory behavior and coevolutionary failure.
.
Keywords: Coevolution, intransitive superiority, multiple dimensions, coevolutionary failure.
Download this paper as:
Postscript
(gecco2001_cdms.ps)
Gzipped Postscript
(gecco2001_cdms.ps.gz)
PDF
(gecco2001_cdms.pdf)
Ficici, Sevan G. and
Pollack, Jordan B.
(2000). A Game-Theoretic Approach to the Simple Coevolutionary Algorithm.
Parallel Problem Solving from Nature VI, M. Schoenauer, et al, (eds.), Springer Verlag, 2000.
Abstract
The fundamental distinction between ordinary evolutionary algorithms (EA) and
co-evolutionary algorithms lies in the interaction between coevolving
entities. We believe that this property is essentially game-theoretic in nature. Using
game theory, we describe extensions that allow familiar mixing-matrix and Markov-chain
models of EAs to address coevolutionary algorithm dynamics. We then employ concepts from
evolutionary game theory to examine design aspects of conventional coevolutionary
algorithms that are poorly understood.
Keywords: Evolutionary Game Theory, Coevolutionary Algorithms, Mathematical Models.
Download this paper as:
Postscript
(gtasca_ppsn6.ps)
Gzipped Postscript
(gtasca_ppsn6.ps.gz)
PDF
(gtasca_ppsn6.pdf)
Ficici, Sevan G.,
Melnik, Ofer and
Pollack, Jordan B.
(2000). A Game-Theoretic Investigation of Selection Methods Used in Evolutionary Algorithms.
Proceedings of the 2000 Congress on Evolutionary Computation, A. Zalzala, et al, (eds.), IEEE Press, 2000.
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 impose a fixed-point dynamic
virtually unrelated to the payoffs of the game matrix, give limit cycles, or induce chaos.
These results are significant to the field of evolutionary computation because EGT can be
understood as a \emph{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.
Keywords: Selection Methods, Evolutionary Game Theory, Evolutionary Stable Strategy, Mathematical Models, Coevolutionary Algorithms.
Download this paper as:
Postscript
(gtismea_cec00.ps)
Gzipped Postscript
(gtismea_cec00.ps.gz)
PDF
(gtismea_cec00.pdf)
Ficici, Sevan G. and
Pollack, Jordan B.
(2000). Effects of Finite Populations on Evolutionary Stable Strategies.
Proceedings of the 2000 Genetic and Evolutionary Computation Conference, L. Darrell Whitley (ed.), Morgan-Kaufmann, 2000.
Abstract
A strong assumption made in evolutionary game theory (EGT) [Maynard-Smith, 82] is that
the evolving population is infinitely large. Recent simulations by Fogel, et al,
[Fogel, et al, 95, 98; Fogel, et al, 97] show that finite populations produce behavior that, at
best, deviate with statistical significance from the evolutionary stable strategy (ESS)
predicted by EGT. They conclude that evolutionary game theory loses its predictive power
with finite populations. In this paper, we revisit the question of how finite populations
affect EGT dynamics. By paying particular attention to the operation of the selection
mechanisms used by Fogel, et al, we are able to account for the divergence between ESS
predictions (based on infinite populations) and results observed in our own
finite-population simulations. We then show that Baker's SUS [Baker, 87] selection
method corrects the divergence to a great extent. We thus conclude that the dynamics of
EGT, and particularly ESSs, can indeed apply to finite-population systems.
Keywords: Evolutionary Game Theory, Evolutionary Stable Strategy, Mathematical Models, Coevolutionary Algorithms, Selection Methods.
Download this paper as:
Postscript
(efpess_gecco00.ps)
Gzipped Postscript
(efpess_gecco00.ps.gz)
PDF
(efpess_gecco00.pdf)
Funes, Pablo,
Lapat, Louis and
Pollack, Jordan B.
(2000). EvoCAD: Evolution-Assisted Design.
Artificial Intelligence in Design'00 (Poster Abstracts)
Key Centre of Design Computing and Cognition, University of Sidney.
pp 21-24.
Abstract
Today's commercial CAD systems may
add a mechanical simulator to the usual 3D manipulation tools. But
the new field of Evolutionary Design (ED) has the potential to add
a third leg to computer-aided design: A creative role. Not only
designs can be drawn (as in CAD), or drawn and simulated (as in
CAD+simulation), but also designed by the computer following
guidelines given by the operator. Thus we envision future Evolutionary
CAD systems, EvoCADs .
To demonstrate our conception of EvoCAD, we have built a mini-CAD system to design 2D Lego structures. This Lego EvoCAD allows the user to manipulate Lego structures, and test their gravitational resistance using the same structural simulator we have been using in the past to do ED with Lego bricks. It also interfaces to an evolutionary algorithm that combines user-defined goals with simulation to evolve candidate solutions for the design problems. The results of evolution are sent back to the CAD front-end to allow for further re-design until a satisfactory solution is obtained.
Click here to see the full poster
.
Download this paper as:
PDF
(aidabstract.pdf)
Funes, Pablo and
Pollack, Jordan B.
(2000). Measuring Progress in Coevolutionary Competition.
From Animals to Animats 6: Proceedings of the Sixth International
Conference on Simulation of Adaptive Behavior. Meyer, J. et. al
(eds.) MIT Press. Pp. 450-459.
Abstract
Evolution, as trial-and-error based learning methods, usually
relies on the repeatability of an experience: Different behavioral
alternatives are tested and compared with each other. But agents
acting on real environments may not be able to choose which experience
to live. Instead, the environment provides varying initial conditions
for each trial.
In competitive games for example, it is difficult to compare players
with each other if they are not able to choose their opponents. Here
we describe a statistics-based approach to solving this problem,
developed in the context of the Tron system, a coevolutionary
experiment that matches humans against agents on a simple video game.
We are now able to show, among the results, that the complex
interactions led the artificial agents to evolve towards higher
proficiency, while at the same time, individual humans learned as they
gained experience interacting with the system. .
Keywords: internet evolution, computer game playing, adaptive behavior, virtual
creatures.
Download this paper as:
Postscript
(funes-sab00.ps)
PDF
(funes-sab00.pdf)
Hornby, G.S.,
Takamura, S.,
Yokono, J.,
Hanagata, O.,
Fujita, M. and
Pollack, J.
(2000). Evolution of Controllers from a High-Level Simulator to a High DOF Robot.
Miller, J. (ed) Evolvable Systems: from biology to hardware;
proceedings of the third international conference (ICES 2000).
Springer (Lecture Notes in Computer Science; Vol. 1801). pp. 80-89.
Abstract
Building a simulator for a robot with many degrees of freedom and various sensors, such as Sony's AIBO, is a daunting task. Our implementation does not simulate raw sensor values or actuator commands, rather we model an intermediate software layer which passes processed sensor data to the controller and receives high-level control co