Lowell, J. H. and
Pollack, J. B.
(2017). The effects of environmental structure on the evolution of modularity in a pattern classifier.
Proceedings of European Conference on Artificial Life, Lyon France, 267-274.
Abstract
We examine hierarchical modularity - modularity on multiple
levels, in which the modules at a lower level of abstraction
can serve as nodes in a network at a higher level
of abstraction that also has positive modularity - as well
as degree of modularity on a single level of abstraction, in
evolved neural networks in single-task, parallel-subtask environments,
and sequential-subtask environments, using a common
benchmark problem. We determine that top-performing
networks evolved in the sequential-subtask environment have
both more levels of hierarchical modularity, and a higher degree
of modularity within levels, than those involved in either
the single-task or parallel-subtask environment. In the singletask
environment, both single-level and hierarchical modularity
tend to rise initially before stagnating and even declining,
while in the sequential-subtask environment, both singlelevel
and hierarchical modularity tend to rise throughout the
period of evolution.
Download this paper as:
PDF
(lowell-ecal-17.pdf)
Moran, N. E. and
Pollack, J. B.
(2017). Effects of Cooperative and Competitive Coevolution on Complexity in a Linguistic Prediction Game.
Proceedings of European Conference on Artificial Life, Lyon France, 298-305.
Abstract
We propose a linguistic prediction game with competitive and
cooperative variants, and a model of game players based on
finite state automata. We present a complexity metric for
these automata, and study the coevolutionary dynamics of
complexity growth in a variety of multi-species simulations.
We present quantitative results using this complexity metric
and analyze the causes of varying rates of complexity growth
across different types of interactions. We find that while
both purely competitive and purely cooperative coevolution
are able to drive complexity growth above the rate of genetic
drift, mixed systems with both competitive and cooperative
interactions achieve significantly higher evolved complexity.
Download this paper as:
PDF
(moran-ecal-17.pdf)
Lowell, J. H. and
Pollack, J. B.
(2016). Developmental Encodings Promote the Emergence of Hierarchical Modularity.
Proceedings of Artificial Life Conference, Cancun Mx, 344-351.
Abstract
While it has been observed (Hornby et al., 2001) that developmental
encodings in evolved systems may promote modularity,
there has been little quantitative study of this phenomenon.
There has also been little study of the factors driving
the emergence of hierarchical modularity - modularity on
multiple levels, in which the modules found at a finer-grained
level can serve as elements in a coarser-grained network that
is also modular - despite the fact that most fields with an interest
in modularity, including biology and engineering, define
hierarchy as an important aspect of modularity. We examine
the effect of developmental encodings on the emergence
of multiple levels of modularity through the lens of two developmental
systems, GRNEAT and GENRE, and find evidence
that developmental encodings promote this emergence
of modular hierarchy.
Download this paper as:
PDF
(lowell-alife-16.pdf)
Moran, N. E. and
Pollack, J. B.
(2016). Route Assignment for Autonomous Vehicles.
10th Conference on Swarm Intelligence, Brussels Belgium 265-272.
Abstract
We demonstrate a self-organizing, multi-agent system to
generate approximate solutions to the route assignment problem for a large
number of vehicles across many origins and destinations. Our algorithm
produces a set of mixed strategies over the set of paths through the
network, which are suitable for use by autonomous vehicles in the absence of
centralized control or coordination. Our approach combines ideas from
co-evolutionary dynamics in which many species coordinate and
compete for efficient navigation, and ideas from swarm intelligence in which
many simple agents self-organize into successful behavior using limited
between-agent communication. Experiments demonstrate a marked
improvement of both individual and total travel times as compared to
greedy uncoordinated strategies, and we analyze the differences in
outcomes for various routes as the simulation progresses.
Download this paper as:
PDF
(moran-ants-16.pdf)
Lowell, J. H. and
Pollack, J. B
(2014). The Effect of Connection Cost on Modularity in Evolved Neural Networks.
Proceedings of Artificial Life 2014.
Abstract
Modularity, often observed in biological systems, does not
easily arise in computational evolution. We explore the effect
of adding a small fitness cost for each connection between
neurons on the modularity of neural networks produced by
the NEAT neuroevolution algorithm. We find that this connection
cost does not increase the modularity of the best network
produced by each run of the algorithm, but that it does
lead to increased consistency in the level of modularity produced
by the algorithm.
Download this paper as:
PDF
(lowell-alife-14a.pdf)
Lowell, J. H.,
Harrington, K. I. and
Pollack, J. B.
(2014). The Resilience of a Swarm Ecosystem Under Environmental Variation.
Proceedings of Artificial Life 2014.
Abstract
Evolving swarms can be used both to solve real-world problems and to study biological and ecological phenomena. We simulated an evolving swarm of birds under three different types of climate-change-related environmental variation.a temperate environment becoming tropical, a temperate enviroment becoming a desert, and a tropical environment becoming a desert. We found that desertification increased expirations within the swarm and decreased population stability. The direction of the variation.tropicalification or desertification .had a greater impact on the dynamics of the swarm than the degree of variation when it came to these outcomes. The environmental variation also affected the genetics of the birds, with decreased food availability leading to collision avoidance genes being downplayed, and searching behavior for food being changed. High-intensity environmental variation led to less genetic stability post-change than lower-intensity environmental variation.
Download this paper as:
PDF
(lowell-alife-14b.pdf)
Harrington, K.,
Awa, E.,
Cussat-Blanc, S. and
Pollack, J.
(2013). Robot Coverage Control by Evolved Neuromodulation.
Proceedings of the International Joint Conference on Neural Networks, pp.543-550.
Abstract
An important connection between evolution and learning was made over a century ago and is now termed as the Baldwin effect. Learning acts as a guide for an evolutionary search process. In this study reinforcement learning agents are trained to solve the robot coverage control problem. These agents are improved by evolving neuromodulatory gene regulatory networks (GRN) that influence the learning and memory of agents. Agents trained by these neuromodulatory GRNs can consistently generalize better than agents trained with fixed parameter settings. This work introduces evolutionary GRN models into the context of neuromodulation and illustrates some of the benefits that stem from neuromodulatory GRNs.
Download this paper as:
PDF
(harrington2013ijcnn.pdf)
Harrington, K. I.,
Spector, L.,
Pollack, J. B. and
O'Reilly, U.M.
(2012). Autoconstructive Evolution for Structural Problems.
Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference companion , pp.75-82.
Abstract
While most hyper-heuristics search for a heuristic that is later used to solve classes of problems, autoconstructive evolution represents an alternative which simultaneously searches both heuristic and solution space. In this study we contrast autoconstructive evolution, in which intergenerational variation is accomplished by the evolving programs themselves, with a genetic programming system, PushGP, to understand the dynamics of this hybrid approach. A problem size scaling analysis of these genetic programming techniques is performed on structural problems. These problems involve fewer domain-specic features than most model problems while maintaining core features representative of program search. We use two such problems, Order and Majority, to study autoconstructive evolution in the Push programming language.
Download this paper as:
PDF
(harrington2012autoconstruction.pdf)
Harrington, K. I.,
Olsen, M. and
Siegelmann, H.
(2012). Computational Neuroecology of Communicated Somatic Markers.
Proceedings of Artificial Life XIII, pp.555-556.
Abstract
The somatic marker hypothesis offers a physiological basis for emotion. Somatic markers are thought to stem from basic survival behaviors, and it has been hypothesized that emotional communication can increase the survival rate of a population. We investigate these neuroecological questions in predator-prey simulations by exploring the effect of communicated somatic markers on individuals and their ecology in order to establish an understanding of their evolvability. In particular, we show how fear, happiness, and to a lesser extent surprise, can be favored by natural selection.
Download this paper as:
PDF
(harrington2012neuroeco.pdf)
Harrington, K. I.,
Ozisik, A. P. and
Pollack, J.
(2012). The Effects of Finite Populations and Selection on the Emergence of Signaling.
Proceedings of Artificial Life XIII, pp.194-201.
Abstract
In the research described here we examine the emergence of signaling from non-communicative origins, using the Sir Philip Sidney Game as a framework for our analysis. This game is known to exhibit a number of interesting dynamics. In our study, we quantify the difficulty of reaching multiple types of equilibria from initially non-communicative populations with an infinite population model. We then compare the ability of finite populations with typical tournament selection to approximate the behaviors observed in infinite populations. Our findings suggest that honest signaling equilibria are difficult to reach from non-communicative origins. In the second part of the paper, we show that the finite model fails to model dynamics that permit deceptive signaling under typical evolutionary conditions, where infinite populations exhibit spiraling behavior between honest and deceptive signaling.
Download this paper as:
PDF
(harrington2012signaling.pdf)
Ozisik, A. P. and
Harrington, K. I.
(2012). The Effect of Tags on the Evolution of Honest Signaling.
Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp.345-352.
Abstract
In the study described here we examine the importance of social tags in the emergence and maintenance of signaling, using the Sir Philip Sydney Game. We use tags in the calculation of inclusive tness for members in a nite population, and analyze their evolution under dierent population distributions. We support the claim that inclusive tness theory may not be sufficient to explain the evolution of cooperation. While cooperativity through honest signaling is sometimes achieved with tag-based relatedness, we suggest that the importance of tag-based mechanisms may not simply be due to their role in kin selection.
Download this paper as:
PDF
(ozisik2012signalingtags.pdf)
Spector, L.,
Harrington, K. and
Helmuth, T.
(2012). Tag-based Modularity in Tree-based Genetic Programming.
Proceedings of the Genetic and Evolutionary Computation Conference, pp.815-822.
Abstract
Several techniques have been developed for allowing genetic programming systems to produce programs that make use of subroutines, macros, and other modular program structures. A recently proposed technique, based on the "tagging" and tag-based retrieval of blocks of code, has been shown to have novel and desirable features, but this was demonstrated only within the context of the PushGP genetic programming system. Following a suggestion in the GECCO-2011 publication on this technique we show here how tag-based modules can be incorporated into a more standard tree-based genetic programming system. We describe the technique in detail along with some possible extensions, outline arguments for its simplicity and potential power, and present results obtained using the technique on problems for which other modularization techniques have been shown to be useful. The results are mixed; substantial benets are seen on the lawnmower problem but not on the Boolean even-4-parity problem. We discuss the observed results and directions for future research.
Download this paper as:
PDF
(spector2012tags.pdf)
Harrington, K.,
Olsen, M. and
Siegelmann, H.
(2011). Communicated Somatic Markers Benefit the Individual and the Species.
Proceedings of the International Joint Conference on Neural Networks, pp.3272-3278.
Abstract
We use emotional communication within a predator-prey game to evaluate the tradeoff between socio-emotional behavior at individual- and species- scales. In this predator-prey game, individual predators and prey use emotion in their decision making, and communicate their emotional state with neighboring conspecifics. The model of emotion is based upon the somatic marker hypothesis. In comparing individual utility and population dynamics we find emotion is capable of both supporting species and individual gain. We suggest this type of dynamic may provide a mechanism for the emergence of altruistic behavior within a species under individual and/or group selection.
Download this paper as:
PDF
(harrington2011ijcnn.pdf)
Harrington, K.,
Tosch, E.,
Spector, L. and
Pollack, J.
(2011). Compositional Autoconstructive Dynamics.
Unifying Themes in Complex Systems Volume VIII: Proceedings of the Eighth International Conference on Complex Systems, pp.856-870.
Abstract
Autoconstructive evolution is the idea of evolving programs through self-creation. This is an alternative to the hand-coded variation operators utilized in traditional genetic programming (GP) and the deliberately limited implementations of meta-GP. In the latter case strategies generally involve adapting the variation operators which are then used in accordance with traditional GP. On the other hand, autoconstruction offers the ability to adapt algorithmic reproductive mechanisms specific to individuals in the evolving population. We study multiple methods of compositional autoconstruction, a form of autoconstruction based on function composition. While much of the previous work on autoconstruction has investigated traditional GP problems, we investigate the effect of autoconstructive evolution on two problems: Order, which models order-sensitive program semantics, and Majority, which models the evolutionary acquisition of semantic components. In doing so we show that compositional autoconstruction exhibits surprising dynamics of evolutionary improvement, and that compositional autoconstruction can be comparable to GP. This advance is a step towards the search for the open-ended evolution of problem-solving techniques.
Download this paper as:
PDF
(harrington2011iccs.pdf)
Harrington, K. and
Pollack, J.
(2011). Zipper-based Meta-Genetic Programming.
Technical Report Brandeis University CS-11-275.
Abstract
We present a zipper-based instruction set for constructing genetic programming variation operators. We study the effects of such variation operators on the lawnmower problem. Operators in this language possess the ability to outperform standard mutation and crossover in terms of both decreasing the average population error as well as the best population error. Furthermore, the expression of standard mutation and crossover in this language is trivial, allowing evolution to re-discover these operators when necessary. We conclude by using these operators in a meta-genetic programming context, showing that it is possible for zipper-based meta-genetic programming to expedite evolutionary search.
Download this paper as:
PDF
(harrington2011metagp.pdf)
Olsen, M.,
Harrington, K. and
Siegelmann, H.
(2011). Computational Emotions in a Population Dynamics Cellular Automata Encourage Collective Behavior.
Unifying Themes in Complex Systems Volume VIII: Proceedings of the Eighth International Conference on Complex Systems, pp.196-210.
Abstract
We evaluate how a computational model of emotions may enable collective behavior in a predator-prey system. Our cellular automata model combines emotion-based decision rules with simple communication. Although there are a number of human psychological theories of emotion, it is generally agreed that emotions increase our ability to interact with our environment. Human emotions may have initially evolved for survival, showing many commonalities with predator-prey scenarios. Additionally, groups of prey will exchange information about their surroundings to increase their survival. We therefore define emotions for predators and prey based on these theories of emotions and Ekman’s basic emotions. Our system describes the interactions of foxes that feed on rabbits that feed on carrots. Emotions are used by foxes and rabbits and encode data pertaining to survival. We examine variations of the communication, and to what extent an individual’s decisions should be based on the communicated emotion versus the personal emotion. We find that the emotion rules and communication allow each population to cooperate and improve their population’s fitness.
Download this paper as:
PDF
(olsen2011iccs.pdf)
Shang, Y.,
Haynes, P.,
Pírez, N.,
Harrington, K.,
Guo, F.,
Pollack, J.,
Hong, P.,
Griffith, L. and
Rosbash, M.
(2011). Imaging analysis of clock neurons: light buffers the wake-promoting effect of dopamine.
Nature Neuroscience 7(14), pp.889-895.
Abstract
How animals maintain proper amounts of sleep yet remain flexible to changes in environmental conditions remains unknown. We found that environmental light suppressed the wake-promoting effects of dopamine in fly brains. The ten large lateral-ventral neurons (l-LNvs), a subset of clock neurons, are wake-promoting and respond to dopamine, octopamine and light. Behavioral and imaging analyses suggested that dopamine is a stronger arousal signal than octopamine. Notably, light exposure not only suppressed l-LNv responses, but also synchronized responses of neighboring l-LNvs. This regulation occurred by distinct mechanisms: light-mediated suppression of octopamine responses was regulated by the circadian clock, whereas light regulation of dopamine responses occurred by upregulation of inhibitory dopamine receptors. Plasticity therefore alters the relative importance of diverse cues on the basis of the environmental mix of stimuli. The regulatory mechanisms described here may contribute to the control of sleep stability while still allowing behavioral flexibility.
Download this paper as:
PDF
(shang2011imaging.pdf)
Spector, L.,
Helmuth, T. and
Harrington, K.
(2011). Fecundity and Selectivity in Evolutionary Computation.
Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, pp.
Abstract
The number of ospring produced by each parent--that is, the fecundity of reproducing individuals--varies among evolutionary computation methods and settings. In most prior work fecundity has been tied directly to selectivity, with higher selection pressure giving rise to higher fecundity among individuals selected to reproduce. In nature, however, there is a wider variety of strategies, with different organisms producing dierent numbers of ospring under the in uence of a range of factors including not only selection pressure but also other factors such as environmental stability and competition within a niche. In this work we consider possible lessons that may be drawn from nature's approaches to these issues and applied to evolutionary computation systems. In particular, we consider ways in which fecundity can be dissociated from selectivity and situations in which it may be benecial to do so. We present a simple modication to the standard evolutionary algorithm, called decimation, that permits high fecundity in conjunction with modest selection pressure and which could be used in various forms of evolutionary computation. We also present a simple example, showing that decimation can improve the problem-solving performance of a genetic algorithm when applied to a deceptive problem.
Download this paper as:
PDF
(spector2011decimation.pdf)
Spector, L.,
Martin, B.,
Harrington, K. and
Helmuth, T.
(2011). Tag-Based Modules in Genetic Programming.
Proceedings of the Genetic and Evolutionary Computation Conference, pp.
Abstract
In this paper we present a new technique for evolving modular programs with genetic programming. The technique is based on the use of "tags" that evolving programs may use to label and later to refer to code fragments. Tags may refer inexactly, permitting the labeling and use of code fragments to co-evolve in an incremental way. The technique can be implemented as a minor modication to an existing, general purpose genetic programming system, and it does not require pre-specication of the module architecture of evolved programs. We demonstrate that tag-based modules readily evolve and that this allows problem solving eort to scale well with problem size. We also show that the tag-based module technique is eective even in complex, non-uniform problem environments for which previous techniques perform poorly. We demonstrate the technique in the context of the stack-based genetic programming system PushGP, but we also brie y discuss ways in which it may be used with other kinds of genetic programming systems.
Download this paper as:
PDF
(spector2011tags.pdf)
Spector, L.,
Harrington, K.,
Martin, B. and
Helmuth, T.
(2011). What's in an Evolved Name? The Evolution of Modularity via Tag-Based Reference.
Genetic Programming Theory and Practice IX, pp.1-16.
Abstract
Programming languages provide a variety of mechanisms to associate names with values, and these mechanisms play a central role in programming practice. For example, they allow multiple references to the same storage location or function in dierent parts of a complex program. By contrast, the representations used in current genetic programming systems provide few if any naming mechanisms, and it is therefore generally not possible for evolved programs to use names in sophisticated ways. In this chapter we describe a new approach to names in genetic programming that is based on Holland's concept of tags. We demonstrate the use of tag-based names, we describe some of the ways in which they may help to extend the power and reach of genetic programming systems, and we look at the ways that tag-based names are actually used in an evolved program that solves a robot navigation problem.
Download this paper as:
PDF
(spector2011gptp.pdf)
Harrington, K. I. and
Pollack, J. B.
(2010). Robot Phylogenetics.
Proceedings of the 12th annual conference companion on Genetic and evolutionary computation, pp.2077-2078.
Abstract
Bioinformatics techniques are introduced for the analysis of evolutionary search. These techniques are tested on buildable robots evolved in a virtual simulator for a locomotion task. By using bioinformatic visualizations properties of evolutionary search and relatedness between differing robot genotypes and phenotypes can be examined.
Download this paper as:
PDF
(harrington2010robot.pdf)
Heymann, M.,
Harrington, K. I.,
Pollack, J. and
Fraden, S.
(2010). En route to signal inversion in chemical computing.
Proceedings of Artificial Life XII, pp.166-167.
Abstract
We investigate the Belousov-Zhabotinzky (BZ) reaction as a substrate for computation. Expanding on previous research we present a new technique that utilizes two modes of the BZ reaction, excitation and oscillation, and selective diffusive coupling. We show in simulation that this technique can be used to invert input signals, providing the logical operator, NOT. Our system can readily compute NOR, which when connected in multiples is sufficient for simulating any other logical operator. Furthermore, progress to experimentally implement these operators and to wire them into circuits using soft lithography and replica molding is presented.
Download this paper as:
PDF
(heymann2010chemical.pdf)
Olsen, M.,
Harrington, K. and
Siegelmann, H.
(2010). Conspecific Emotional Cooperation Biases Population Dynamics: A Cellular Automata Approach.
International Journal of Natural Computing Research 3(1), pp.51-65.
Abstract
In this paper, the authors evaluate the benefit of emotions in population dynamics and evolution. The authors enhance cellular automata (CA) simulating the interactions of competing populations with emotionally inspired rules in communication, interpretation, and action. While CAs have been investigated in studies of population dynamics due to their ability to capture spatial interactions, emotion-like interactions have yet to be considered. Our cellular stochastic system describes interacting foxes that feed on rabbits that feed on carrots. Emotions enable foxes and rabbits to improve their decisions and share their experiences with neighboring conspecifics. To improve the system's biological relevance, it includes inter-species disease transmission, and emotions encode data pertaining to both survival and epidemic reduction. Results indicate that emotions increase adaptability, help control disease, and improve survival for the species that utilizes them. Simulations support the hypothesis that the acquisition of emotion may be an evolutionary result of competitive species interactions.
Download this paper as:
PDF
(olsen2010ca.pdf)
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)
Pollack, J.
(2006). Mindless Intelligence.
IEEE Trans. on Intelligent Systems, 21, 3, 50-56.
Abstract
For the past 50 years, the field of AI has pursued the goal
of replicating elements of human cognition. I argue that
the goal underestimates the complexity of the cognitive
architecture which has been developed by evolution, a
form of intelligence which lacks the symbolic accoutrements of
human minds. Evolution and other naturally occuring
mindless intelligence are thus worthy of study for the next 50 years.
.
Download this paper as:
PDF
(mindlessintelligence.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 commands. This allows us to construct a simulator that runs at over 11000 times faster than real time. Using our simulator we evolve a ball-chasing behavior that successfully transfers to an actual AIBO.
Keywords: robotics, evolutionary robotics, neural networks, simulation.
Download this paper as:
Postscript
(hornby_ices00.ps)
Gzipped Postscript
(hornby_ices00.ps.gz)
PDF
(hornby_ices00.pdf)
Hornby, G.S.,
Takamura, S.,
Yokono, J.,
Hanagata, O.,
Yamamoto, T. and
Fujita, M.
(2000). Evolving Robust Gaits with AIBO.
IEEE International Conference on Robotics and Automation.
pp. 3040-3045.
Abstract
An evolutionary algorithm is used to evolve gaits with the Sony entertainment robot, AIBO. All processing is handled by the robot's on-board computer with individuals evaluated using the robot's hardware. By sculpting the experimental environment, we increase robustness to different surface types and different AIBOs. Evolved gaits are faster than those created by hand. Using this technique we evolve a gait used in the consumer
version of AIBO.
Keywords: robotics, evolutionary robotics, locomotion.
Download this paper as:
Postscript
(hornby_icra00.ps)
Gzipped Postscript
(hornby_icra00.ps.gz)
PDF
(hornby_icra00.pdf)
Levy, S.,
Melnik, O. and
Pollack, J.B.
(2000). Infinite RAAM: A Principled Connectionist Basis for Grammatical Competence.
COGSCII 2000, IEEE press .
Abstract
This paper presents Infinite RAAM (IRAAM), a new fusion of recurrent
neural networks with fractal geometry, allowing us to understand the
behavior of these networks as dynamical systems. Our recent work with
IRAAMs has shown that they are capable of generating the context-free
(non-regular) language $a^{n}b^{n}$ for arbitrary values of $n$. This
paper expands upon that work, showing that IRAAMs are capable of
generating syntactically ambiguous languages but seem less capable of
generating certain context-free constructions that are absent or
disfavored in natural languages. Together, these demonstrations
support our belief that IRAAMs can provide an explanatorily adequate
connectionist model of grammatical competence in natural language.
Keywords: neural networks, fractals, dynamical systems, iterated function systems,
recurrent neural networks, language, grammar, competence.
Download this paper as:
Postscript
(raam-cogsci00.ps)
Gzipped Postscript
(raam-cogsci00.ps.gz)
PDF
(raam-cogsci00.pdf)
Melnik, O.
(2000). Representation of Information in Neural Networks.
PhD Dissertation, Brandeis University, October 2000.
Abstract
Artificial neural networks are a computational paradigm inspired by
neurobiology. As with any computational paradigm, its strengths are a
direct result of how it represents and processes information. Despite
being widely used and researched, many questions remain about how
artificial neural networks represent information.
Feed-forward networks have seen wide application, but as complex,
interdependent, non-linear models the question of assessing the exact
computation performed by one has never been fully addressed. This
thesis fills that void with a new algorithm that can extract an exact
alternative representation of a multi-layer perceptron's
function. Using this exact representation we explore scope questions,
such as when and where do networks form artifacts, and what can we
tell about network generalization from its representation. The exact
nature of the algorithm also lends itself to answer theoretical
questions about representation extraction in general. For example,
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.
Building on understanding gained from the first algorithm, a
complementary method is developed that while not being exact allows
the computationally efficient analysis of different types of very
high-dimensional models. This non-specificity to model type and
ability to contend with high-dimensionality is a unique feature due to
the method's direct focus on the parts of a model's computation that
reflect generalization.
The addition of recurrent connections to feed-forward networks
transforms them from functions to dynamical systems, making their
interpretation significantly more difficult. In fact, recurrent neural
networks can not have a correct interpretation, as what part of their
operation constitutes computation is biased by the observer. Thus the
same exact network is capable of performing completely different
computations under different interpretations. In this thesis two such
interpretations of representation are explored for a four neuron
highly-recurrent network. Despite its miniscule size we demonstrate
that it can be used, on the one hand, to store and learn highly
complex fractal images, or on the other hand, to represent an infinite
context-free grammar.
Combining these elements, this thesis advances our understanding of
how neural networks compute, both feed-forward and recurrent. It
provides a coherent perspective on how to understand and analyze the
function of feed-forward networks, and develops new perspectives on
computation in recurrent networks.
Download this paper as:
Gzipped Postscript
(melnik_thesis.ps.gz)
PDF
(melnik_thesis.pdf)
Melnik, O. and
Pollack, J.B.
(2000). Exact Representations from Feed-Forward Networks .
IJCNN 2000, IEEE press, shorter conference version of some of tech-report .
Abstract
We present an algorithm to extract representations from multiple
hidden layer, multiple output feed-forward perceptron threshold
networks. The representation is based on polytopic decision regions in
the input space-- and is exact not an approximation like most other
network analysis methods. Multiple examples show some of the knowledge
that can be extracted from networks by using this algorithm, including
the geometrical form of artifacts and bad generalization. We compare threshold
and sigmoidal networks with respect to the expressiveness of their
decision regions, and also prove lower bounds for any algorithm which
extracts decision regions from arbitrary neural networks. .
Keywords: neural networks, representation, rule-extraction, polytope, computational geometry, generalization, artifacts, complexity.
Download this paper as:
Postscript
(nc1-ijcnn.ps)
Gzipped Postscript
(nc1-ijcnn.ps.gz)
PDF
(nc1-ijcnn.pdf)
Melnik, O.,
Levy, S. and
Pollack, J.B.
(2000). RAAM for Infinite Context-Free Languages.
IJCNN 2000, IEEE press .
Abstract
With its ability to represent variable sized trees in fixed width
patterns, RAAM is a bridge between connectionist and symbolic
systems. In the past, due to limitations in our understanding, its
development plateaued. By examining RAAM from a dynamical systems
perspective we overcome most of the problems that previously plagued
it. In fact, using a dynamical systems analysis we can now prove that
not only is RAAM capable of generating parts of a context free
language (a^nb^n) but is capable of expressing the whole language. .
Keywords: neural networks, fractals, learning rules, gradient descent,
dynamical systems, iterated function systems, recurrent neural networks.
Download this paper as:
Postscript
(raam-ijcnn.ps)
Gzipped Postscript
(raam-ijcnn.ps.gz)
PDF
(raam-ijcnn.pdf)
Melnik, O. and
Pollack, J.B.
(2000). Using Graphs to Analyze High-Dimensional Classifiers .
IJCNN 2000, IEEE press, Presented at Montreal Workshop on Selecting and Combining Models with Machine Learning Algorithms .
Abstract
In this paper we present a method to extract qualitative information
from any classification model that uses decision regions to generalize
(e.g. neural nets, SVMs, graphical models etc) that is independent on
the dimensionality of the data and model. The qualitative information
can be directly used to analyze the classification strategies employed
by a model, and also to directly compare strategies across different
models. We apply the method to comp are between two types of
classifiers using real-world high-dimensional data.
Keywords: classifier, classifier analysis, generalization, k-nearest neighbor, graph theory, neural networks.
Download this paper as:
Postscript
(CA-ijcnn.ps)
Gzipped Postscript
(CA-ijcnn.ps.gz)
PDF
(CA-ijcnn.pdf)
Pollack, J. B.,
Lipson. H., ,
Ficici, S.,
Funes, P.,
Hornby, G. and
Watson, R.
(2000). Evolutionary Techniques in Physical Robotics.
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. 175-186.
Abstract
Evolutionary and coevolutionary techniques have become a popular
area of research for those interested in automated design. One of
the cutting edge issues in this field is the ability to apply
these techniques to real physical systems with all the
complexities and affordances that such systems present. Here we
present a selection of our work each of which advances the
richness of the evolutionary substrate in one or more dimensions.
We overview research in four areas: a) High part-count static
structures that are buildable, b) The use of commercial CAD/CAM
systems as a simulated substrate, c) Dynamic electromechanical
systems with complex morphology that can be built automatically,
and d) Evolutionary techniques distributed in a physical
population of robots.
Download this paper as:
HTML
(ices00.html)
Gzipped Postscript
(ices00.ps.gz)
PDF
(ices00.pdf)
Shipman, R.,
Shackleton, M.,
Ebner, M. and
Watson, R.A.
(2000). Neutral Search Spaces for Artificial Evolution: A Lesson from Life.
Proceedings of Artificial Life VII, Bedau, M, McCaskill, J, Packard, N, Rasmussen, S (eds.), 2000.
Abstract
Natural evolutionary systems exhibit a complex mapping from genotype to phenotype. One property of these mappings is neutrality, where many mutations do not have an appreciable effect on the phenotype. In this case the mapping from genotype to phenotype contains redundancy such that a phenotype is represented by many genotypes. Studies of RNA and protein molecules, the fundemental building-blocks of life, reveal that this can result in neutral networks - sets of genotypes connected by single point mutations that map into the same phenotype. This allows genetic changes to be made while maintaining the current phenotype and thus may reduce the chance of becoming trapped in sub-optimal regions of genotype space. In this paper we present several redundant mappings and explore their properties by performing random walks on the neutral networks in their genotype spaces. We investigate whether the properties found in nature's search space can be engineered into our artificial evolutionary systems. A mapping based on a random boolean network was found to give particularly promising results.
Keywords: neutral networks, morphogenic mappings, encoding schemes, random boolean networks, cellular automata.
Download this paper as:
Postscript
(alife7_shipman.ps)
Gzipped Postscript
(alife7_shipman.ps.gz)
PDF
(alife7_shipman.pdf)
Sklar, Elizabeth and
Pollack, Jordan
(2000). A Framework for Enabling an Internet Learning Community.
Educational Technology & Society 3(3), Kinshuk, A. Patel and R. Oppermann (eds.).
Abstract
We view the Internet as a "virtual laboratory" and have developed a
framework to support experiments in web-based community learning. Our system
is called the Community of Evolving Learners, or CEL. The target user group is
primary school children, therefore we pay particular attention to privacy
issues and provide a safe environment in which learners can succeed and fail
incognito. This article describes the CEL system, the types of interactions
that it enables and the kinds of data that can be collected. We present
preliminary results from a pilot study that was used to validate the CEL
mechanism.
Keywords: Internet, Virtual community, Human learning .
Download this paper as:
Postscript
(ifets.ps)
Gzipped Postscript
(ifets.ps.gz)
PDF
(ifets.pdf)
Sklar, Elizabeth and
Pollack, Jordan
(2000). An evolutionary approach to guiding students in an educational game.
In From Animals to Animats 6: Proceedings of the Sixth International Conference on Simulation of Adaptive Behavior. Meyer, J. et. al (eds.)
MIT Press.
Abstract
We describe an evolutionary approach to selecting content
for educational games in a web-based learning community.
Our approach offers an alternative to methods typically
used in educational domains, with the goal of combining the
curricular structure of an engineered application along
with the flexibility of a learner-centered setting.
Our method operates in a real-time environment, so
performance requirements differ from those of an off-line
implementation.
We tested our method during a pilot study involving fourth
and fifth grade students at a public primary school.
This paper details our approach and presents results from
the pilot study.
Keywords: education, Internet, world-wide web, CEL, evolutionary algorithm.
Download this paper as:
Postscript
(cel-sab2k.ps)
Gzipped Postscript
(cel-sab2k.ps.gz)
PDF
(cel-sab2k.pdf)
Sklar, Elizabeth,
Johnson, Jeffrey and
Lund, Henrik Hautop
(2000). Children Learning From Team Robotics: RoboCup Junior 2000.
Educational Research Report,
Department of Design and Innovation, Faculty of Technology,
The Open University, Milton Keynes, UK.
Abstract
RoboCup Junior is a division of the international RoboCup initiative.
It involves children participating in various competitive and cooperative
robot challenges.
Experience at three international venues shows that these challenges generate
great excitement and interest from both children and adults.
We question whether there is any educational value in these challenges, and
this report presents results of a study we conducted in conjunction with
the third international event -- RoboCup Junior 2000.
Our tentative conclusion is that there is enormous educational value for
children involved in team robotics, both academically and in terms of their
personal development.
Keywords: education, robots, RoboCup, RoboCup Junior.
Download this paper as:
Postscript
(rcj2000.ps)
Gzipped Postscript
(rcj2000.ps.gz)
PDF
(rcj2000.pdf)
Watson, Richard A.,
Ficici, Sevan G. and
Pollack, Jordan B.
(2000). Embodied Evolution: Distributing an Evolutionary Algorithm in a Population of Robots.
Technical Report CS-00-208.
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 evolution
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.
Download this paper as:
Postscript
(ee_journal.ps)
Gzipped Postscript
(ee_journal.ps.gz)
PDF
(ee_journal.pdf)
Watson, R.A. ,
Reil, T. and
Pollack, J.B.
(2000). Mutualism, Parasitism, and Evolutionary Adaptation.
Proceedings of Artificial Life VII, Bedau, M, McCaskill, J, Packard, N, Rasmussen, S (eds.), 2000.
Abstract
Our investigations concern the role of symbiosis as an enabling mechanism in evolutionary adaptation. Previous work has illustrated how the formation of mutualist groups can guide genetic variation so as to enable the evolution of ultimately independent organisms that would otherwise be unobtainable. The new experiments reported here show that this effect applies not just in genetically related organisms but may also occur from symbiosis between distinct species. In addition, a new detail is revealed: when the symbiotic group members are drawn from two separate species only one of these species achieves eventual independence and the other remains parasitic. It is nonetheless the case that this second species, formerly mutualistic, was critical in enabling the independence of the first. We offer a biological example that is suggestive of the effect and discuss the implications for evolving complex organisms, natural and artificial.
.
Keywords: Baldwin effect, symbiogenesis, symbiotic scaffolding, Solemya Reidi, parasitism, mutualism.
Download this paper as:
Postscript
(alife7_mpea.ps)
Gzipped Postscript
(alife7_mpea.ps.gz)
PDF
(alife7_mpea.pdf)
Watson, R.A. and
Pollack, J.B.
(2000). Recombination Without Respect: Schema Combination and Disruption in Genetic Algorithm Crossover.
Proceedings of the 2000 Genetic and Evolutionary Computation Conference, Whitley, D., et al (eds.), Morgan Kaufmann, 2000.
Abstract
One-point (or n-point) crossover has the property that schemata exhibited by both parents are 'respected' - transferred to the offspring without disruption. In addition, new schemata may, potentially, be created by combination of the genes on which the parents differ. Some argue that the preservation of similarity is the important aspect of crossover, and that the combination of differences (key to the building-block hypothesis) is unlikely to be valuable. In this paper, we discuss the operation of recombination on a hierarchical building-block problem. Uniform crossover, which preserves similarity, fails on this problem. Whereas, one-point crossover, that both preserves similarity and combines differences, succeeds. In fact, a somewhat perverse recombination operator, that combines differences but destroys schemata that are common to both parents, also succeeds. Thus, in this problem, combination of schemata from dissimilar parents is required, and preserving similarity is not required. The test problem represents an extreme case, but it serves to illustrate the different aspects of recombination that are available in regular operators such as one-point crossover.
Keywords: genetic algorithms, disrespectful recombination, crossover operators, building-block hypothesis, hierarchical if-and-only-if, headless chicken test, macro-mutation, schema combination .
Download this paper as:
Postscript
(gecco2000_rwr.ps)
Gzipped Postscript
(gecco2000_rwr.ps.gz)
PDF
(gecco2000_rwr.pdf)
Watson, R.A. and
Pollack, J.B.
(2000). Symbiotic Combination as an Alternative to Sexual Recombination in Genetic Algorithms.
Proceedings of Parallel Problem Solving from Nature (PPSNVI), Marc Schoenauer, Kalyanmoy Deb, Guenter Rudolph, Xin Yao, Evelyne Lutton, Juan Julian Merelo, Hans-Paul Schwefel (Eds)., 2000. Springer Verlag, Lecture Notes in Computer Science 1917 © Springer-Verlag.
Abstract
Recombination in the Genetic Algorithm (GA) is supposed to enable the component characteristics from two parents to be extracted and then reassembled in different combinations hopefully producing an offspring that has the good characteristics of both parents. However, this can only work if it is possible to identify which parts of each parent should be extracted. Crossover in the standard GA takes subsets of genes that are adjacent on the genome. Other variations of the GA propose more sophisticated methods for identifying good subsets of genes within an individual. Our approach is different; rather than devising methods to enable successful extraction of gene-subsets from parents, we utilize variable-size individuals which represent subsets of genes from the outset. Joining together two individuals, creating an offspring that is twice the size, straight-forwardly produces the sum of the parents characteristics. This form of component assembly is more closely analogous to combination of symbiotic organisms than it is to sexual recombination. Whereas sexual recombination, modeled by crossover, occurs between similar individuals and exchanges subsets of genes, symbiotic combination, as modeled in our operator, can occur between entirely unrelated species and combines together whole organisms. This paper summarizes our research on this approach to recombination in GAs and describes new methods that illustrate its potential.
Keywords: genetic algorithms, crossover operators, hierarchical if-and-only-if, schema combination, symbiogenesis, symbiotic combination, pareto coevolution, multi-objective optimization, Symbiogenic Evolutionary Adaptation Model (SEAM).
Download this paper as:
Postscript
(ppsn6_scasr.ps)
Gzipped Postscript
(ppsn6_scasr.ps.gz)
PDF
(ppsn6_scasr.pdf)
Blair, Alan D. and
Sklar, Elizabeth
(1999). Exploring evolutionary learning in a simulated hockey environment.
1999 Congress on Evolutionary Computation.
Peter J. Angeline, Zbyszek Michalewicz, Marc Schoenauer, Xin Yao, Ali Zalzala, eds. .
Abstract
As a test-bed for studying evolutionary and other
machine learning techniques, we have developed a simulated
hockey game called Shock
in which players attempt to shoot a
puck into their enemy's goal during a fixed time period.
Multiple players may participate --
one can be controlled by a human user, while
the others are guided by artificial controllers.
In previous work, we introduced the
Shock environment and presented players that
received global input (as if from an overhead camera)
and were trained on a restricted task,
using an evolutionary hill-climbing algorithm,
with a staged learning approach.
Here, we expand upon this work by developing
players which instead receive input from local,
Braitenberg-style sensors.
These players are able to learn
the task with fewer restrictions,
using a simpler fitness measure based purely
on whether or not a goal was scored.
Moreover, they evolve to develop robust
strategies for moving around the rink
and scoring goals.
Keywords: evolution, adaptive behaviour, robot controller, hockey.
Download this paper as:
Postscript
(shock_cec99.ps)
Gzipped Postscript
(shock_cec99.ps.gz)
PDF
(shock_cec99.pdf)
Ficici, Sevan G.,
Watson, Richard A. and
Pollack, Jordan B.
(1999). Embodied Evolution: A Response to Challenges in Evolutionary Robotics.
Eighth European Workshop on Learning Robots. Jeremy L. Wyatt, John Demiris, eds., 14-22.
Abstract
We introduce Embodied Evolution (EE), a new methodology for conducting evolutionary robotics (ER).
Embodied evolution uses a population of physical robots that evolve by reproducing with one another in the
task environment. EE addresses several issues identified by researchers in the evolutionary robotics
community as problematic for the development of ER. We review results from our first experiments
and discuss the advantages and limitations of the EE methodology.
Keywords: evolutionary robotics, collective robotics.
Download this paper as:
Postscript
(ewlr8.ps)
Gzipped Postscript
(ewlr8.ps.gz)
PDF
(ewlr8.pdf)
Ficici, Sevan G. and
Pollack, Jordan B.
(1999). Statistical Reasoning Strategies in the Pursuit and Evasion Domain.
Fifth European Conference on Artificial Life. Dario Floreano, Jean-Daniel Nicoud, Francesco Mondada, eds. Springer, 1999.
Abstract
Isaacs' treatise on differential games was a break-through for the analysis of the
pursuit-and-evasion (PE) domain within the context of strategies representable by differential equations.
Current experimental work in Artificial Life steps outside of the formalism of
differential games, but the formalism it steps into is yet to be identified. We introduce
a formulation of PE that allows a formalism to be developed. Our game minimizes kinematic factors
and instead emphasizes the informational aspect of the domain. We use information-theoretic
tools to describe agent behavior and implement a pursuit strategy based on statistical decision
making; evaders evolved against this pursuit strategy exhibit a wide range of sophisticated behavior
that can be quantitatively described. Agent performance is related to these quantifiables.
Keywords: pursuit and evasion, differential games, information theory, autonomous agents.
Download this paper as:
Postscript
(srsped_ecal99.ps)
Gzipped Postscript
(srsped_ecal99.ps.gz)
PDF
(srsped_ecal99.pdf)
Funes, P. and
Pollack, J.
(1999). Computer Evolution of Buildable Objects.
In Evolutionary Design by Computers. P. Bentley (editor).
Morgan Kaufmann, San Francisco. pp. 387-403.
Abstract
1. Introduction
This chapter describes our work in evolution of buildable
designs using miniature plastic bricks as modular components.
Lego bricks are well known for their flexibility when it comes
to creating low cost, handy designs of vehicles and structures.
Their simple modular concept make toy bricks a good ground for
doing evolution of computer simulated structures which can be
built and deployed.
.
Keywords: genetic algorithms, evolutionary design, evolutionary robotics,
computer simulation.
Download this paper as:
Postscript
(edc98.ps)
Gzipped Postscript
(edc98.ps.gz)
PDF
(edc98.pdf)
Hornby, G.S.,
Fujita, M.,
Takamura, S.,
Yamamoto, T. and
Hanagata, O.
(1999). Autonomous Evolution of Gaits with the Sony Quadruped Robot.
Proceedings of 1999 Genetic and Evolutionary Computation Conference (GECCO). Banzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, Smith, eds., Morgan Kauffmann, pp. 1297-1304.
Abstract
A trend in robotics is towards legged robots. One of the issues with legged robots is the development of gaits. Typically gaits are developed manually. In this paper we report our results of autonomous evolution of dynamic gaits for the Sony Quadruped Robot. Fitness is determined using the robot's digital camera and infrared sensors. Using this system we evolve faster dynamic gaits than previously manually developed.
Keywords: robotics, evolutionary robotics, locomotion.
Download this paper as:
Postscript
(hornby_gecco99_sony.ps)
Gzipped Postscript
(hornby_gecco99_sony.ps.gz)
PDF
(hornby_gecco99_sony.pdf)
Hornby, G.S. and
Mirtich, B.
(1999). Diffuse versus True Coevolution in a Physics-based World.
Proceedings of 1999 Genetic and Evolutionary Computation Conference (GECCO). B\anzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, Smith, eds., Morgan Kauffmann, pp. 1305-1312.
Abstract
We compare two types of coevolutionary tournaments, true and diffuse, in contests using a general-purpose, physics-based simulator. Previous work in coevolving agents has used true coevolution and found that populations tend to enter mediocre states. One hypothesis for alleviating these problems is to use diffuse coevolution. Our results show that agents evaluated with diffuse tournaments are more generalized than those evaluated with true tournaments.
Keywords: co-evolution, pursuer-evader, neural networks.
Download this paper as:
Postscript
(hornby_gecco99_merl.ps)
Gzipped Postscript
(hornby_gecco99_merl.ps.gz)
PDF
(hornby_gecco99_merl.pdf)
Juillé, H.
(1999). Methods for Statistical Inference: Extending the Evolutionary Computation Paradigm.
Doctoral Dissertation, Brandeis University, Department of Computer Science, May 1999.
Abstract
In many instances, Evolutionary Computation (EC) techniques
have demonstrated their ability to tackle ill-structured
and poorly understood problems against which traditional
Artificial Intelligence (AI) search algorithms fail.
The principle of operation behind EC techniques can be described
as a statistical inference process which
implements a sampling-based strategy to gather information
about the state space, and then exploits this knowledge
for controlling search.
However, this statistical inference process is supported by
a rigid structure that is an integral part of an EC technique.
For instance, {\em schemas} seem to be the basic components
that form this structure in the case of Genetic Algorithms (GAs).
Therefore, it is important that the encoding of a problem
in an EC framework exhibits some regularities that correlate
with this underlying structure.
Failure to find an appropriate representation prevents
the evolutionary algorithm from making accurate decisions.
This dissertation introduces new methods that
exploit the same principles of operation as those embedded in
EC techniques and provide more flexibility for the choice
of the structure supporting the statistical inference process.
The purpose of those methods is to generalize the EC paradigm,
thereby expanding its domain of applications
to new classes of problems.
Two techniques implementing those methods are described in this work.
The first one, named SAGE, extends the sampling-based strategy
underlying evolutionary algorithms to perform search
in trees and directed acyclic graphs.
The second technique considers coevolutionary learning,
a paradigm which involves the embedding of adaptive
agents in a fitness environment that dynamically responds
to their progress.
Coevolution is proposed as a framework
in which evolving agents would be permanently challenged,
eventually resulting in continuous improvement of their performance.
After identifying obstacles to continuous progress,
the concept of an ``Ideal'' trainer is presented
as a paradigm which successfully achieves that goal
by maintaining a pressure toward adaptability.
The different algorithms discussed in this dissertation have been applied
to a variety of difficult problems in learning and combinatorial optimization.
Some significant achievements that resulted from those experiments concern:
(1) the discovery of new constructions for 13-input sorting networks
using fewer comparators than the best known upper bound,
(2) an improved procedure for the induction of DFAs from sparse training data
which ended up as a co-winner in a grammar inference competition, and
(3) the discovery of new cellular automata rules to implement the majority
classification task which outperform the best known rules.
By describing evolutionary algorithms from the perspective of statistical
inference techniques, this research work contributes to a better
understanding of the underlying search strategies embedded
in EC techniques.
In particular, an extensive analysis of the coevolutionary paradigm
identifies two fundamental requirements for achieving continuous progress.
Search and machine learning are two fields that are closely related.
This dissertation emphasizes this relationship and demonstrates
the relevance of the issue of generalization in the context of
coevolutionary races.
Keywords: Coevolutionary Learning, Stochastic Search.
Download this paper as:
Postscript
(hugues_thesis.ps)
Gzipped Postscript
(hugues_thesis.ps.gz)
PDF
(hugues_thesis.pdf)
Pollack, Jordan B.,
Lipson, Hod,
Funes, Pablo,
Ficici, Sevan G. and
Hornby, Greg
(1999). Coevolutionary Robotics.
The First NASA/DoD Workshop on Evolvable Hardware (EH'99). John R. Koza, Adrian Stoica, Didier Keymeulen, Jason Lohn, eds., IEEE Press.
Abstract
(excerpt) We address the fundamental issue of fully automated design (FAD) and construction of inexpensive robots and
their controllers. Rather than seek an intelligent general purpose robot - the humanoid robot, ubiquitous
in today's research as the long term goal - we are developing the information technology that can design
and fabricate special-purpose mechanisms and controllers to achieve specific short term objectives. These robots
would be constructed from reusable sensors, effectors, and computers held together with materials custom "printed"
by rapid prototyping (RP) equipment. By releasing the goal of designing software controllers for EXISTING
machines in favor of the automated co-design of software and hardware together, we will be replicating the
principles used by biology in the creation of complex groups of animals adapted to specific environments.
Keywords: evolutionary robotics, coevolution, fully-automated design, autonomous agents, multi-agent systems.
Download this paper as:
PDF
(nasa_eh99.pdf)
Sklar, Elizabeth,
Blair, Alan D. ,
Funes, Pablo and
Pollack, Jordan
(1999). Training Intelligent Agents using Human Internet Data .
IAT-99.
(to appear).
Abstract
We describe a method for training intelligent agents using
human data collected at a novel Internet learning site
where humans and software agents play games against each
other. To facilitate human learning, it is desirable to
select proper opponents for humans so that they will
advance and not become bored or frustrated.
In the work presented here, we use human data as the basis
for constructing a population of graded agents,
so that in future we can choose opponents (from this
population) that will challenge individual human
learners appropriately.
Keywords: human-agent interaction, learning, neural networks, tron.
Download this paper as:
Postscript
(tron_iat99.ps)
Gzipped Postscript
(tron_iat99.ps.gz)
PDF
(tron_iat99.pdf)
Watson, Richard A.,
Ficici, Sevan G. and
Pollack, Jordan B.
(1999). Embodied Evolution: Embodying an Evolutionary Algorithm in a Population of Robots.
1999 Congress on Evolutionary Computation. Angeline, Michalewicz, Schoenauer, Yao, Zalzala, eds. IEEE Press, 335-342.
Abstract
We introduce Embodied Evolution (EE) as a methodology for the automatic design of robotic controllers. EE is an
evolutionary robotics (ER) technique that avoids the pitfalls of the simulate-and-transfer method, allows the speed-up
of evaluation time by utilizing parallelism, and is particularly suited to future work on multi-agent behaviors. In EE,
an evolutionary algorithm is distributed amongst and embodied within a population of physical robots that reproduce
with one another while situated in the task environment. We have built a population of eight robots and successfully
implemented our first experiments. The controllers evolved by EE compare favorably to hand-designed solutions for
a simple task. We detail our methodology, report our initial results, and discuss the application of EE to more
advanced and distributed robotics tasks.
Keywords: evolutionary robotics, autonomous agents, multi-agent systems, artificial life.
Download this paper as:
Postscript
(ee_cec99.ps)
Gzipped Postscript
(ee_cec99.ps.gz)
PDF
(ee_cec99.pdf)
Watson, R.A. and
Pollack, J.B.
(1999). Hierarchically-Consistent Test Problems for Genetic Algorithms .
Proceedings of 1999 Congress on Evolutionary Computation (CEC 99). Angeline, Michalewicz, Schoenauer, Yao, Zalzala, eds. IEEE Press, pp.1406-1413.
Abstract
The Building-Block Hypothesis suggests that the genetic algorithm (GA) will perform well when it is able to identify above-average-fitness low-order schemata and recombine them to produce higher-order schemata of higher fitness. We suppose that the recombinative process continues recursively, combining schemata of successively higher orders as search progresses. Historically, attempts to illustrate this intuitively straight-forward process on abstract test problems, most notably the Royal Road problems, have been somewhat perplexing. More recent building-block test problems have abandoned the multi-level hierarchical structure of the Royal Roads, and thus departed from the original recursive aspects of the hypothesis. This paper defines the concept of hierarchical consistency, which captures the recursive nature of problems implied by the Building-Block Hypothesis. We introduce several variants of problems that are hierarchically consistent and begin to explore aspects of problem difficulty with respect to these models. .
Keywords: Hierarchical-if-and-only-if (H-IFF), Royal Roads, Building-Block Hypothesis.
Download this paper as:
Gzipped Postscript
(cec_hctp.ps.gz)
PDF
(cec_hctp.pdf)
Watson, R.A. and
Pollack, J.B.
(1999). How Symbiosis Can Guide Evolution .
Fifth European Conference on Artificial Life. Dario Floreano, Jean-Daniel Nicoud, Francesco Mondada, eds. Springer, 1999.
Abstract
Hinton and Nowlan have demonstrated a model of how lifetime plasticity can guide evolution. They show how acquired traits change the shape of the reward landscape in which subsequent genetic variation takes place, and in so doing encourage the discovery of equivalent heritable traits. This enables the seemingly Lamarkian inheritance of acquired characteristics without the direct transfer of information from the phenotype to the genotype. This paper draws direct inspiration from their work to illustrate a different phenomenon. We demonstrate how the formation of symbiotic relationships in an ecosystem can guide the course of subsequent genetic variation. This phenomenon can be described as two phases: First, symbiotic groups find solutions where individual organisms cannot, simply because lifetime interaction produces new combinations of abilities more rapidly than the relatively slow genetic variation of individuals. Second, these symbiotic groups subsequently change the shape of the reward landscape for evolution, providing a gradient that guides genetic variation to the same solution. Ultimately, an individual organism exhibits the capabilities formerly exhibited by the group. This process enables the combination of characteristics from organisms of distinct species without direct transfer of genetic information.
Keywords: Baldwin effect, symbiogenesis, symbiotic scaffolding, Solemya Reidi .
Download this paper as:
Gzipped Postscript
(ecal_hsge.ps.gz)
PDF
(ecal_hsge.pdf)
Watson, R.A. and
Pollack, J.B.
(1999). Incremental Commitment in Genetic Algorithms .
Proceedings of 1999 Genetic and Evolutionary Computation Conference (GECCO 99). Banzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, Smith, eds., Morgan Kauffmann, pp.710-717.
Abstract
Successful recombination in the simple GA requires that interdependent genes be close to each other on the genome. Several methods have been proposed to reorder genes on the genome when the given ordering is unfavorable. The Messy GA (MGA) is one such 'moving-locus' scheme. However, gene reordering is only part of the Messy picture. The MGA uses another mechanism that is influential in enabling successful recombination. Specifically, the use of partial specification (or variable length genomes) allows the individuals themselves, rather than the ordering of genes within an individual, to represent which genes 'go together' during recombination. This paper examines this critical feature of the MGA and illustrates the impact that partial specification has on recombination. We formulate an Incremental Commitment GA that uses partially specified representations and recombination inspired by the MGA but separates these features from the moving-locus aspects and many of the other features of the existing algorithm.
.
Keywords: Messy Genetic Algorithms, Hierarchical-if-and-only-if (H-IFF).
Download this paper as:
Gzipped Postscript
(gecco_icga.ps.gz)
PDF
(gecco_icga.pdf)