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)
Blair, Alan D. ,
Sklar, Elizabeth and
Funes, Pablo
(1998). Co-evolution, Determinism and Robustness.
In Simulated Evolution and Learning (SEAL-98).
Lecture Notes in Artificial Intelligence 1585.
Bob McKay, Xin Yao, Charles S. Newton, Jong-Hwan Kim, Takeshi Furahashi, eds.,
Springer-Verlag.
Abstract
Robustness has long been recognised as a critical issue
for co-evolutionary learning.
It has been achieved in a number of cases,
though usually in domains which involve some form of
non-determinism.
We examine a deterministic domain --
a pseudo real-time two-player game called Tron --
and evolve
a neural network player using a simple hill-climbing
algorithm.
The results call into
question the importance of determinism
as a requirement for successful
co-evolutionary learning, and provide a good
opportunity to examine the relative importance of other
factors.
Keywords: co-evolutionary learning environments, determinism, neural networks, tron.
Download this paper as:
Postscript
(tron_seal98.ps)
Gzipped Postscript
(tron_seal98.ps.gz)
PDF
(tron_seal98.pdf)
Blair, Alan D. and
Sklar, Elizabeth
(1998). The evolution of subtle manoeuvres in simulated hockey.
Proceedings of the Fifth International Conference of the
Society for Adaptive Behavior.
Pfeifer, Blumberg, Kobayashi, eds. Cambridge: MIT Press, 1998.
Abstract
We introduce a simulated hockey environment, called Shock,
as a test bed for studying adaptive behaviour and
evolution of robot controllers.
A near-frictionless playing surface is employed,
partially mimicking zero gravity conditions.
We show how a neural network using a simple
evolutionary algorithm can develop nimble
strategies for moving about the rink
and scoring goals quickly and effectively.
Keywords: evolution, adaptive behaviour, robot controller, hockey.
Download this paper as:
Postscript
(shock_sab98.ps)
Gzipped Postscript
(shock_sab98.ps.gz)
PDF
(shock_sab98.pdf)
Ficici, Sevan G. and
Pollack, Jordan B.
(1998). Challenges in Coevolutionary Learning: Arms-Race Dynamics, Open-Endedness, and Mediocre Stable States.
Proceedings of the Sixth International Conference on Artificial Life.
Adami, Belew, Kitano, Talor, eds. Cambridge: MIT Press, 1998.
Abstract
Coevolution has been proposed as a way to evolve a learner and a
learning environment simultaneously such that open-ended progress
arises naturally, via a competitive arms race, with minimal
inductive bias. Nevertheless, the conditions necessary to initiate
and sustain arms-race dynamics are not well understood; mediocre
stable states frequently result from learning through self-play
(Angeline & Pollack 1994), while analysis usually requires closed
domains with known optima, like sorting-networks (Hillis 1992).
While intuitions regarding what enables successful coevolution
abound, none have been methodically tested. We present a game
that affords such methodical investigation. A population of
deterministic string generators is coevolved with two populations
of string predictors, one "friendly" and one "hostile"; generators
are rewarded to behave in a manner that is simultaneously
predictable to the friendly predictors and unpredictable to the
hostile predictors. This game design allows us to employ information
theory to provide rigorous characterizations of agent behavior and
coevolutionary progress. Further, we can craft agents of known
ability and environments of known difficulty, and thus precisely
frame questions regarding learnability. Our results show that subtle
changes to the game determine whether it is open-ended, and
profoundly affect the existence and nature of an arms race.
Keywords: coevolution, arms-race, open-endedness, mediocrity.
Download this paper as:
Postscript
(Challenges.ps)
Gzipped Postscript
(Challenges.ps.gz)
PDF
(Challenges.pdf)
Ficici, Sevan G. and
Pollack, Jordan B.
(1998). Coevolving Communicative Behavior in a Linear Pursuer-Evader Game.
Proceedings of the Fifth International Conference of the Society for Adaptive Behavior.
Pfeifer, Blumberg, Kobayashi, eds. Cambridge: MIT Press, 1998.
Abstract
The pursuer-evader (PE) game is recognized as an important domain in
which to study the coevolution of robust adaptive behavior and protean
behavior (Miller & Cliff 1994). Nevertheless, the potential of the
game is largely unrealized due to methodological hurdles in coevolutionary
research raised by PE; versions of the game that have optimal solutions
(Isaacs 1965) are closed-ended, while other formulations are opaque with
respect to their solution space, for the lack of a rigorous metric of agent
behavior. This inability to characterize behavior, in turn, obfuscates
coevolutionary dynamics. We present a new formulation of PE that affords
a rigorous measure of agent behavior and system dynamics. The game is moved
from the two-dimensional plane to the one-dimensional bitstring; at each
time step, the evader generates a bit that the pursuer must simultaneously
predict. Because behavior is expressed as a time series, we can employ
information theory to provide quantitative analysis of agent activity.
Further, this version of PE opens vistas onto the communicative component
of pursuit and evasion behavior, providing an open-ended serial
communications channel and an open world (via coevolution). Results show
that subtle changes to our game determine whether it is open-ended, and
profoundly affect the viability of arms-race dynamics.
Keywords: communication, pursuer-evader, coevolution.
Download this paper as:
Postscript
(LinearPE.ps)
Gzipped Postscript
(LinearPE.ps.gz)
PDF
(LinearPE.pdf)
Funes, P.,
Sklar, E.,
Juillé, H. and
Pollack, J.
(1998). Animal-Animat Coevolution: Using the Animal Population as Fitness Function.
Pfeifer, R. et. al. (eds.)
From Animals to Animats 5:
Proceedings of the Fifth International
Conference on Simulation of Adaptive Behavior
. MIT Press. pp 525-533.
Abstract
We show an artificial world where animals (humans) and
animats (software agents) interact in a coevolutionary
arms race. The two species each use adaptation schemes
of their own.
Learning through interaction with humans has been
out of reach for evolutionary learning techniques because
too many iterations are necessary. Our work demonstrates
that the Internet is a new environment where this may be
possible through an appropriate setup that creates
mutualism, a relationship where human and animat
species benefit from their interactions with each other.
Keywords: genetic algorithms, adaptive agents, internet evolution, computer
game playing.
Download this paper as:
HTML
(tronsab98.html)
Postscript
(tronsab98.ps)
Gzipped Postscript
(tronsab98.ps.gz)
PDF
(tronsab98.pdf)
Funes, P. J. and
Pollack, J. B.
(1998). Componential Structural Simulator.
Brandeis University Department of Computer Science Technical
Report CS-98-198.
Abstract
A procedure to predict stability of certain structures
Our componential structural simulator procedure provides an approximate simulation that predicts resistance of structures made of modular components. The simulation focuses on torque strains and is able to predict stability of a structure whose breakage depends on torque stress.
Structures that can be described in this fashion include those made out of building toy bricks such as Lego bricks, a well-known type of snap-on toy bricks, which we have used in our initial applications.
The
model could be applied to many other kinds of structures made out
of modular components. It is a prediction tool that can be
programmed in a computer and used to test the stability of a
structure before proceeding to its construction.
.
Download this paper as:
Postscript
(cs98-198.ps)
Gzipped Postscript
(cs98-198.ps.gz)
PDF
(cs98-198.pdf)
Funes, P. and
Pollack, J.
(1998). Evolutionary Body Building: Adaptive physical designs for robots.
Artificial Life 4: 337-357.
Abstract
Creating artificial life forms through evolutionary robotics faces a
"chicken and egg" problem: learning to control a complex body is
dominated by problems specific to its sensors and effectors, while
building a body that is controllable assumes the pre-existence of a
brain.
The idea of co-evolution of bodies and brains is becoming popular, but little work has been done in evolution of physical structure because of the lack of a general framework for doing it. Evo-lution of creatures in simulation has usually resulted in virtual entities which are not buildable, while embodied evolution in actual robotics is constrained by the slow pace of real time.
The work we
present takes a step in the problem of body evolution by applying
evolutionary techniques to the design of structures assembled out of
elementary components which stick together. Evolution takes place in a
simulator which computes forces and stresses and predicts stability of
3- dimensional brick structures. The final printout of our program is
a schematic assembly, which is then built physically. We demonstrate
the functionality of this approach to robot body building with many
evolved artifacts.
Keywords: evolutionary robotics, body and brain coevolution,
adaptive bodies, genetic algorithms, evolutionary design.
Download this paper as:
Postscript
(funpolalife.ps)
Gzipped Postscript
(funpolalife.ps.gz)
PDF
(funpolalife.pdf)
Juillé, H. and
Pollack, J. B.
(1998). A Sampling-Based Heuristic for Tree Search Applied to Grammar Induction.
Proceedings of the Fifteenth National Conference on Artificial Intelligence , Madison, Wisconsin, July 26 - 30, 1998.
Abstract
In the field of Operation Research and Artificial Intelligence,
several stochastic search algorithms have been designed based on the theory
of global random search.
Basically, those techniques iteratively sample the search space with
respect to a probability distribution which is updated according to the result
of previous samples and some predefined strategy.
Genetic Algorithms (GAs) or Greedy Randomized Adaptive
Search Procedures (GRASP) are two particular instances
of this paradigm.
In this paper, we present SAGE, a search algorithm based on the same fundamental
mechanisms as those techniques.
However, it addresses a class of problems for which it is difficult to design
transformation operators to perform local search because of intrinsic
constraints in the definition of the problem itself.
For those problems, a procedural approach is the natural way to construct
solutions, resulting in a state space represented as a tree or a DAG.
The aim of this paper is to describe the underlying heuristics
used by SAGE to address problems belonging to that class.
The performance of SAGE is analyzed on the problem of grammar induction and
its successful application to problems from the recent Abbadingo DFA learning
competition is presented.
Keywords: inductive learning, DFA induction.
Download this paper as:
Postscript
(aaai98.ps)
Gzipped Postscript
(aaai98.ps.gz)
PDF
(aaai98.pdf)
Juillé, H. and
Pollack, J. B.
(1998). A Stochastic Search Approach to Grammar Induction.
Proceedings of the Fourth International Colloquium on Grammar Inference , Ames, Iowa, July 12 - 14, 1998.
Abstract
This paper describes a new sampling-based heuristic for tree search
named SAGE and presents an analysis of its performance
on the problem of grammar induction.
This last work has been inspired by the Abbadingo DFA learning competition
which took place between Mars and November 1997.
SAGE ended up as one of the two winners in that competition.
The second winning algorithm, first proposed by Rodney Price,
implements a new evidence-driven heuristic for state merging.
Our own version of this heuristic is also described in this paper
and compared to SAGE.
.
Keywords: Inductive Learning, DFA Induction.
Download this paper as:
Postscript
(icgi98.ps)
Gzipped Postscript
(icgi98.ps.gz)
PDF
(icgi98.pdf)
Juillé, H. and
Pollack, J. B.
(1998). Coevolutionary Learning: a Case Study.
Proceedings of the Fifteenth International Conference on Machine Learning, Madison, Wisconsin, July 24 - 26, 1998.
Abstract
Coevolutionary learning, which involves the embedding of adaptive learning
agents in a fitness environment that dynamically responds to their progress,
is a potential solution for many technological chicken and egg problems.
However, several impediments have to be overcome in order for coevolutionary
learning to achieve continuous progress in the long term.
This paper presents some of those problems and proposes a framework
to address them.
This presentation is illustrated with a case study: the evolution of CA rules.
Our application of coevolutionary learning resulted in a very significant
improvement for that problem compared to the best known results.
.
Keywords: Coevolutionary Learning, Cellular Automata.
Download this paper as:
Postscript
(icml98.ps)
Gzipped Postscript
(icml98.ps.gz)
PDF
(icml98.pdf)
Juillé, H. and
Pollack, J. B.
(1998). Coevolving the "Ideal" Trainer: Application to the Discovery of Cellular Automata Rules.
Proceedings of the Third Annual Genetic Programming Conference , Madison, Wisconsin, July 22 - 25, 1998.
Abstract
Coevolution provides a framework to implement search heuristics
that are more elaborate than those driving the exploration of
the state space in canonical evolutionary systems.
However, some drawbacks have also to be overcome in order
to ensure continuous progress on the long term.
This paper presents the concept of coevolutionary learning
and introduces a search procedure which successfully addresses
the underlying impediments in coevolutionary search.
The application of this algorithm to the discovery of
cellular automata rules for a classification task is described.
This work resulted in a significant improvement over previously
known best rules for this task.
Keywords: Cellular Automata.
Download this paper as:
Postscript
(gp98.ps)
Gzipped Postscript
(gp98.ps.gz)
PDF
(gp98.pdf)
Melnik, O. and
Pollack, J.B.
(1998). A Gradient Descent Method for a Neural Fractal Memory.
WCCI 98 (IJCNN), IEEE, Received "Best Student Paper Award".
Abstract
It has been demonstrated that higher order recurrent neural networks
exhibit an underlying fractal attractor as an artifact of their
dynamics. These fractal attractors offer a very efficent mechanism to
encode visual memories in a neural substrate, since even a simple
twelve weight network can encode a very large set of different images.
The main problem in this memory model, which so far has remained
unaddressed, is how to train the networks to learn these different
attractors. Following other neural training methods this paper
proposes a Gradient Descent method to learn the attractors. The method
is based on an error function which examines the effects of the
current network transform on the desired fractal attractor. It is
tested across a bank of different target fractal attractors and at
different noise levels. The results show positive performance across
three error measures.
Keywords: neural networks, fractals, learning rules, gradient descent,
dynamical systems, iterated function systems, recurrent neural networks.
Download this paper as:
Postscript
(wcci98.ps)
Gzipped Postscript
(wcci98.ps.gz)
PDF
(wcci98.pdf)
Pollack, Jordan. B. and
Blair, Alan D.
(1998). Co-Evolution in the Successful Learning of Backgammon Strategy.
Machine Learning 32(3): 225-240, September 1998.
Abstract
Following Tesauro s work on TD-Gammon, we used a 4000 parameter
feed-forward neural network to develop a competitive backgammon
evaluation function. Play proceeds by a roll of the dice, application
of the network to all legal moves, and choosing the move with the
highest evaluation. However, no back-propagation, reinforcement or
temporal difference learning methods were employed. Instead we apply
simple hill-climbing in a relative fitness environment. We start with
an initial champion of all zero weights and proceed simply by playing
the current champion network against a slightly mutated challenger and
changing weights if the challenger wins. Surprisingly, this worked
rather well. We investigate how the peculiar dynamics of this domain
enabled a previously discarded weak method to succeed, by preventing
suboptimal equilibria in a metagame of self-learning.
Keywords: coevolution, backgammon, reinforcement, temporal difference learning, self-learning.
Download this paper as:
Postscript
(bkg_ml.ps)
PDF
(bkg_ml.pdf)
Sklar, E.,
Blair, A.D. and
Pollack, J.B.
(1998). Co-evolutionary Learning: Machines and Humans Schooling Together.
Workshop on Current Trends and Applications of Artificial Intelligence in Education: Fourth World Congress on Expert Systems.
Abstract
We consider a new form of co-evolutionary learning in which
human students and software tutors become partners in a
cooperative learning process. While the students are
learning from the tutors, the tutors will also be learning
how to do their job more effectively through their
interactions with the students. Earlier work on
game-playing machine learners has brought to light
important issues for co-evolutionary learning; in
particular, that these interactions can be modeled as a
meta-game between teachers and students, and that
learning may fail due to
suboptimal equilibria -- for example,
because of collusion between the individual players
-- in this meta-game of learning. We discuss some of the
challenges that these issues may raise for the designers of
intelligent software tutoring systems and describe a
prototype Java applet that we have built in an effort to
explore how these challenges may best be met.
Keywords: machine learning, co-evolutionary learning, meta-game of learning.
Download this paper as:
Gzipped Postscript
(mex-aied.ps.gz)
PDF
(mex-aied.pdf)
Sklar, E. and
Pollack, J.B.
(1998). Toward a Community of Evolving Learners.
Third International Conference on the Learning Sciences (ICLS-98).
Abstract
We discuss the
co-evolutionary learning method,
applied to human learning,
as a means toward a mediated,
competitively motivated, educational
environment on the Internet.
This method was developed in our work with machine
learners,
where we have been examining environmental
characteristics that enable successful and
effective learning through "self-play" in games.
Critical features include the ability to provide
tasks consistently just beyond or just within a learner's
grasp.
We carry these observations into the human education arena,
using them to help us enable a Community of Evolving
Learners (CEL) on the Internet.
This paper describes the design of the CEL system.
Keywords: machine learning, co-evolutionary learning, educational software, internet.
Download this paper as:
Postscript
(icls98.ps)
Gzipped Postscript
(icls98.ps.gz)
PDF
(icls98.pdf)
Watson, Richard A. ,
Hornby, G. S. and
Pollack, J. B.
(1998). Modeling Building-Block Interdependency .
Parallel Problem Solving from Nature, proceedings of Fifth International Conference /PPSN V, Springer 1998, pp.97-106 .
Abstract
The Building-Block Hypothesis appeals to the notion of problem decomposition and the assembly of solutions from sub-solutions. Accordingly, there have been many varieties of GA test problems with a structure based on building-blocks. Many of these problems use deceptive fitness functions to model interdependency between the bits within a block. However, very few have any model of interdependency between building-blocks; those that do are not consistent in the type of interaction used intra-block and inter-block. This paper discusses the inadequacies of the various test problems in the literature and clarifies the concept of building-block interdependency. We formulate a principled model of hierarchical interdependency that can be applied through many levels in a consistent manner and introduce Hierarchical If-and-only-if (H-IFF) as a canonical example. We present some empirical results of GAs on H-IFF showing that if population diversity is maintained and linkage is tight then the GA is able to identify and manipulate building-blocks over many levels of assembly, as the Building-Block Hypothesis suggests.
.
Keywords: genetic algorithms, building-block hypothesis.
Download this paper as:
Postscript
(hiff_ppsn.ps)
Gzipped Postscript
(hiff_ppsn.ps.gz)
PDF
(hiff_ppsn.pdf)
Blair, A.D. and
Pollack, J.B.
(1997). Analysis of Dynamical Recognizers.
Neural Computation 9(5), 1127-1142.
Abstract
Pollack (1991) demonstrated that second-order recurrent neural
networks can act as dynamical recognizers for formal languages when
trained on positive and negative examples, and observed both phase
transitions in learning and IFS-like fractal state sets. Follow-on work
focused mainly on the extraction and minimization of a finite state
automaton (FSA) from the trained network. However, such networks are
capable of inducing languages which are not regular, and therefore not
equivalent to any FSA. Indeed, it may be simpler for a small network
to fit its training data by inducing such a non-regular language. But
when is the network's language not regular? In this
paper, using a low dimensional network capable of learning all the
Tomita data sets, we present an empirical method for testing whether
the language induced by the network is regular or not. We also provide
a detailed &epsilon-machine analysis of trained networks for both
regular and non-regular languages.
Keywords: language induction, neural networks, iterated function systems.
Download this paper as:
Postscript
(adr97.ps)
Gzipped Postscript
(adr97.ps.gz)
PDF
(adr97.pdf)
Blair, A.D.
(1997). Scaling Up RAAMs.
Brandeis University Computer Science Technical Report CS-97-192.
Abstract
Modifications to
Recursive Auto-Associative Memory
are presented,
which allow it to store deeper and
more complex data structures than
previously reported.
These modifications include adding extra layers
to the compressor and reconstructor networks,
employing integer rather than real-valued
representations, pre-conditioning the weights
and pre-setting the representations to be
compatible with them.
The resulting system is tested on a data set
of syntactic trees
extracted from the Penn Treebank.
Download this paper as:
Postscript
(sur97.ps)
Compressed Postscript
(sur97.ps.Z)
PDF
(sur97.pdf)
Funes, P. and
Pollack, J.
(1997). Computer Evolution of Buildable Objects.
Fourth European Conference on Artificial Life,
P. Husbands and I. Harvey, eds.,
MIT Press 1997. pp 358-367.
Abstract
Creating artificial life forms through evolutionary
robotics faces a "chicken and egg" problem: learning to control a complex body is dominated by
inductive biases specific to its sensors and effectors,
while building a body which is controllable is conditioned on the pre-existence of a brain.
The idea of co-evolution of bodies and brains is becoming popular, but little work has been done in evolution of physical structure because of the lack of a general framework for doing it. Evolution of creatures in simulation has been constrained by the "reality gap" which implies that resultant objects are usually not buildable.
The work we present takes a step in the problem of body evolution by applying evolutionary techniques to the design of structures assembled out of parts. Evolution takes place in a simulator we designed, which computes forces and stresses and predicts failure for 2-dimensional Lego structures. The final printout of our program is a schematic assembly, which can then be built physically. We demonstrate its functionality in several different evolved entities.
Note: An earlier revision of this paper is available
in html: Brandeis University
Computer Science Technical Report CS-97-191.
Keywords: genetic algorithms, evolutionary design, evolutionary robotics, computer simulation.
Download this paper as:
Gzipped Postscript
(ecal97.ps.gz)
PDF
(ecal97.pdf)
Funes, P.,
Sklar, E.,
Juillé, H. and
Pollack, J.
(1997). The Internet as a Virtual Ecology: Coevolutionary Arms
Races Between Human and Artificial Populations.
Brandeis University Computer Science Technical Report CS-97-197.
Abstract
In this paper, we propose that learning complex behaviors can be
achieved in a coevolutionary environment where one population
consists of the human users of an interactive adaptive software tool
and the "opposing" population is artificial, generated by a coevolu
tionary learning engine. We take advantage of the Internet, a con
nected community where people and software coexist. A new kind
of adaptive agent can exploit its interactions with thousands of
users-inside a virtual "niche"-to learn in a coevolutionary
human-robot arms race. Our model is Tron, a simple dynamic game
where introspective self-play quickly leads to collusive stagnation.
We describe an application where thousands of small programs are
sent to play with people through the Java interpreter running in
their web browsers. The feedback provided by these agents is col
lected in our server and used to augment an ever improving fitness
landscape for local robot-robot games. Speciation and fitness shar
ing provide diversity to challenge humans with a variety of differ
ent strategies. In this way, we obtain an evolving environment
where human as well as artificial adaptation are simultaneously tak
ing place.
.
Keywords: genetic algorithms, autonomous agents, adaptive software, evolutionary
robotics, game learning, coevolution.
Download this paper as:
Postscript
(cs-97-197.ps)
Gzipped Postscript
(cs-97-197.ps.gz)
PDF
(cs-97-197.pdf)
Pollack, J.P. and
Blair, A.D.
(1997). Co-Evolution in the Successful Learning of Backgammon Strategy.
Brandeis University Computer Science Technical Report CS-97-193.
Abstract
Following Tesauro's work on TD-Gammon, we used a 4000
parameter feed-forward neural network to develop a
competitive backgammon evaluation function.
Play proceeds by a roll of the dice, application of the
network to all legal moves, and choosing the move with
the highest evaluation.
However, no back-propagation, reinforcement learning
methods were employed. Instead we apply simple
hill-climbing in a relative fitness environment.
We start with an initial champion of all zero weights
and proceed simply by playing the current champion
network against a slightly mutated challenger and
changing weights if the challenger wins.
Surprisingly, this worked rather well.
We investigate how the peculiar dynamics of this domain
enabled a previously discarded weak method to succeed,
by preventing suboptimal equilibria in a `meta-game'
of self-learning.
.
Download this paper as:
Postscript
(hcgam97.ps)
Compressed Postscript
(hcgam97.ps.Z)
PDF
(hcgam97.pdf)
Darwen, P. J. and
Yao, X.
(1996). Automatic Modularization by Speciation.
Third IEEE International Conference on Evolutionary Computation.
Abstract
Real-world problems are often too difficult to be solved by
a single monolithic system. There are many examples of natural
and artificial systems which show that a modular approach can
reduce the total complexity of the system whilesolving a difficult
problem satisfactorily. The success of modular artificial neural
networks in speech and image processing is a typical example.
However, designing a modular system is a difficult task. It relies heavily on human experts and prior knowledge about the problem. There is no systematic and automatic way to form a modular system for a problem.
This paper proposes a novel evolutionary learning approach to designing a modular system automatically, without human intervention. Our starting point is speciation, using a technique based on fitness sharing. While speciation in genetic algorithms is not new, no effort has been made towards using a speciated population as a complete modular system. We harness the specialized expertise in the species of an entire population, rather than a single individual, by introducing a gating algorithm.
We demonstrate our approach to automatic modularization by improving
co-evolutionary game learning. Following earlier researchers, we learn
to play iterated prisoner's dilemma. We review some problems of earlier
co-evolutionary learning, and explain their poor generalization ability
and sudden mass extinctions. The generalization ability of our approach
is significantly better than past efforts. Using the specialized expertise
of the entire speciated population though a gating algorithm, instead of
the best individual, is the main contributor to this improvement.
.
Download this paper as:
Gzipped Postscript
(icec96darwen.ps.gz)
Hornby, G.S.
(1996). The Recombination Operator, its Correlation to the Fitness Landscape and Search Performance.
Master's Thesis, University of Alberta, Department of Computing Science, 1996.
Abstract
A common misconception in evolutionary algorithms (EAs) is that one recombination operator is universally better than another. In fact, a recombination operator will only get better performance on a function if it incorporates some knowledge about that function -- called tuning it to the function's fitness landscape. In this thesis we identify three ways in which a recombination operator can be tuned to a real-valued landscape: distance, directionality, and distributional bias. We empirically show that a directionally tuned recombination operator gives better search performance than an untuned operator. We also show that a recombination operator that is tuned to one landscape can be mis-tuned to a similar landscape. In addition we find several surprises that contradict our initial intuition but yield to further analysis. For example one interesting observation is a decrease in the number of individuals on the global optimum. We show this to be caused by the attractive pull of a larger group of individuals on a peak with a larger basin of attraction.
Keywords: crossover, recombination, genetic algorithms, evolutionary algorithms.
Download this paper as:
Postscript
(hornby_msc.ps)
Gzipped Postscript
(hornby_msc.ps.gz)
PDF
(hornby_msc.pdf)
Juillé, H. and
Pollack, J.
(1996). Massively Parallel Genetic Programming.
Advances in GP II, Kinnear & Angeline, Ed. MIT Press.
Abstract
As the field of Genetic Programming (GP) matures and its breadth of
application increases, the need for parallel implementations becomes
absolutely necessary. The transputer-based system presented by Koza
is one of the rare such parallel implementations. Until today, no
implementation has been proposed for parallel GP using a SIMD
architecture, except for a data-parallel approach, although others
have exploited workstation farms and pipelined supercomputers. One
reason is certainly the apparent difficulty of dealing with the
parallel evaluation of different S-expressions when only a single
instruction can be executed at the same time on every processor. The
aim of this chapter is to present such an implementation of parallel
GP on a SIMD system, where each processor can efficiently evaluate a
different S-expression. We have implemented this approach on a MasPar
MP-2 computer, and will present some timing results. To the extent
that SIMD machines, like the MasPar are available to offer
cost-effective cycles for scientific experimentation, this is a useful
approach.
Keywords: coevolution, genetic programming, competitive fitness, spirals problem.
Download this paper as:
Postscript
(gp2.ps)
Compressed Postscript
(gp2.ps.Z)
PDF
(gp2.pdf)
Juillé, H. and
Pollack, J. B.
(1996). Co-evolving Intertwined Spirals.
Proceedings of the Fifth Annual Conference on Evolutionary Programming, San Diego, CA, February 29 - March 2, 1996, MIT Press, pp. 461-468.
Abstract
We recently solved the two spirals problem,
a difficult neural network benchmark
classification problem, using the genetic programming primitives
set up by [Koza92]. Instead of using absolute fitness,
we use a relative fitness based on a competition for
coverage of the data set. This is a form of co-evolutionary
search because the fitness function changes with the
population. Because niches are opened by proportionate reproduction,
rather than crowded out,
and because of the crossover operator, we find solutions which
have a nice modular structure.
Our experiments used our Massively Parallel Genetic
Programming (MPGP) system running on a SIMD machine of 4096
processors, the Maspar MP-2.
Keywords: Spirals, Coevolution.
Download this paper as:
Postscript
(ep96.ps)
Gzipped Postscript
(ep96.ps.gz)
PDF
(ep96.pdf)
Juillé, H. and
Pollack, J. B.
(1996). Dynamics of Co-evolutionary Learning.
Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior, Cape Cod, MA, September 9 - 13, 1996, MIT Press, pp. 526-534.
Abstract
Co-evolutionary learning, which involves
the embedding of adaptive learning agents in a fitness
environment which dynamically responds to their
progress, is a potential solution for many
technological chicken and egg problems,
and is at the heart of several recent and surprising successes,
such as Sim's artificial robot and Tesauro's backgammon player.
We recently solved the two spirals problem,
a difficult neural network benchmark
classification problem, using the genetic programming primitives
set up by \cite{koza92}. Instead of using absolute fitness,
we use a relative fitness \cite{angelinepollack93b}
based on a competition for coverage of the data set. As the population
reproduces, the fitness function driving the
selection changes, and subproblem niches are opened, rather than
crowded out. The solutions found by our method have a symbiotic
structure which suggests that by holding niches open, crossover
is better able to discover modular building blocks. .
Keywords: Spirals, Coevolution.
Download this paper as:
Postscript
(sab96b.ps)
Gzipped Postscript
(sab96b.ps.gz)
PDF
(sab96b.pdf)
Pollack, J,
Blair, A. and
Land, M.
(1996). Coevolution of A Backgammon Player.
Proceedings Artificial Life V, C. Langton, (Ed), MIT Press.
Abstract
One of the persistent themes in Artificial Life research is the use of
co-evolutionary arms races in the development of specific and complex
behaviors. However, other than Sims's work on artificial robots, most
of the work has at tacked very simple games of prisoners dilemma or
predator and prey. Following Tesauro's work on TD-Gammon, we used a
4000 parameter feed-forward neural network to develop a competitive
backgammon evaluation function. Play proceeds by a roll of the dice,
application of the network to all legal moves, and choosing the move
with the highest evaluation. However, no back-propagation,
reinforcement or temporal difference learning methods were
employed. Instead we apply simple hill-climbing in a relative fitness
environment. We start with an initial champion of all zero weights and
proceed simply by playing the current champion network against a
slightly mutated challenger, changing weights when the challenger
wins. Our results show co-evolution to be a powerful machine learning
method, even when coupled with simple hill-climbing, and suggest that
the surprising success of Tesauro's program had more to do with the
co-evolutionary structure of the learning task and the dynamics of the
backgammon game itself, than to sophistication in the learning
techniques.
Keywords: co-evolution, learning, games.
Download this paper as:
Postscript
(alife5.ps)
Compressed Postscript
(alife5.ps.Z)
PDF
(alife5.pdf)
Saunders, G. M. and
Pollack, J. B.
(1996). The Evolution of communication schemes of continuous channels.
Proceedings 4th International conference on Simulation of Adaptive Behavior.
Abstract
Many problems impede the design of multi- agent systems, not the least
of which is the passing of information between agents. While others
hand implement communication routes and semantics, we explore a method
by which communication can evolve. In the experiments described here,
we model agents as connectionist networks. We supply each agent with
a number of communications channels implemented by the addition of
both input and output units for each channel. The output units
initiate environmental signals whose amplitude decay over distance
and are perturbed by environmental noise. An agent does not receive
input from other individuals, rather the agent's input reflects the
summation of all other agents' output signals along that
channel. Because we use real-valued activations, the agents
communicate using real-valued vectors. Under our evolutionary program,
GNARL, the agents coevolve a communication scheme over continuous
channels which conveys task-specific information.
Download this paper as:
Compressed Postscript
(sab96.ps.Z)
Darwen, P. J. and
Yao, X.
(1995). A Dilemma for Fitness Sharing with a Scaling Function.
Second IEEE International Conference on Evolutionary Computation.
Abstract
Fitness sharing has been used widely in genetic algorithms for
multi-objective function optimization and machine learning.
It is often implemented with a scaling function,
which adjusts an individual's raw fitness to improve the
performance of the genetic algorithm. However, choosing a
scaling function is an {\em ad hoc} affair that lacks
sufficient theoretical foundation.
Although this is already known, an explanation
of why scaling works is lacking.
This paper explains why a scaling function
is often needed for fitness sharing.
We investigate fitness sharing's performance at
multi-objective optimization,
demonstrate the need for a scaling function of some kind, and
discuss what form of scaling function would be best.
We provide both
theoretical and empirical evidence that fitness sharing with
a scaling function suffers a dilemma which can easily be mistaken
for deception.
Our theoretical analyses and empirical studies explain why
a larger-than-necessary population is needed for fitness sharing
with a scaling function to work, and give an explanation for
common fixes such as further processing with a hill-climbing
algorithm. Our explanation predicts that annealing the scaling
power during a run will improve results, and we verify that it
does. .
Download this paper as:
Gzipped Postscript
(icec95darwen.ps.gz)
Juillé, H.
(1995). Evolution of Non-Deterministic Incremental Algorithms as a New Approach for Search in State Spaces.
Proceedings of the Sixth International Conference on Genetic Algorithms, Pittsburgh, PA, July 1995, pp. 351-358.
Abstract
Let us call a non-deterministic incremental algorithm one that
is able to construct any solution to a combinatorial problem by selecting
incrementally an ordered sequence of choices that defines this solution,
each choice being made non-deterministically.
In that case, the state space can be represented as a tree, and a solution
is a path from the root of that tree to a leaf.
This paper describes how the simulated evolution of a population of such
non-deterministic incremental algorithms offers a new approach for the
exploration of a state space, compared to other techniques like Genetic
Algorithms (GA), Evolutionary Strategies (ES) or Hill Climbing.
In particular, the efficiency of this method, implemented as the Evolving
Non-Determinism (END) model, is presented for the sorting network
problem, a reference problem that has challenged computer science.
Then, we shall show that the END model remedies some drawbacks of these
optimization techniques and even outperforms them for this problem.
Indeed, some 16-input sorting networks as good as the best known have been
built from scratch, and even a 25-year-old result for the 13-input problem
has been improved by one comparator.
Keywords: Sorting Networks, Stochastic Search.
Download this paper as:
Postscript
(icga95.ps)
PDF
(icga95.pdf)
Juillé, H.
(1995). Incremental Co-evolution of Organisms: A New Approach for Optimization and Discovery of Strategies.
Proceedings of the Third European Conference on Artificial Life, Granada, Spain, June 1995, pp.246-260.
Abstract
In the field of optimization and machine learning techniques, some very
efficient and promising tools like Genetic Algorithms (GAs) and
Hill-Climbing have been designed.
In this same field, the Evolving Non-Determinism (END) model presented
in this paper proposes an inventive way to explore the space of states
that, using the simulated "incremental" co-evolution of some organisms,
remedies some drawbacks of these previous techniques and even allow this
model to outperform them on some difficult problems.
This new model has been applied to the sorting network problem, a
reference problem that challenged many computer scientists, and an
original one-player game named Solitaire.
For the first problem, the END model has been able to build from "scratch"
some sorting networks as good as the best known for the 16-input problem.
It even improved by one comparator a 25 years old result for the 13-input
problem.
For the Solitaire game, END evolved a strategy comparable to a human
designed strategy.
Keywords: Sorting Network, Stochastic Search.
Download this paper as:
Postscript
(ecal95.ps)
Gzipped Postscript
(ecal95.ps.gz)
PDF
(ecal95.pdf)
Kolen, J. F. and
Pollack, J. B.
(1995). The Observer's Paradox: Apparent computational
complexity in physical systems.
J Experimental and Theoretical AI, 7, 253-277.
Abstract
Many researchers in AI and cognitive science believe that the
complexity of a behavioral description reflects the underlying
information processing complexity of the mechanism producing the
behavior. This paper explores the foundations of this complexity
argument. We first distinguish two types of complexity judgements that
can be applied to these descriptions and then argue that neither type
can be an intrinsic property of the underlying physical system. In
short, we demonstrate how changes in the method of observation can
radically alter both the number of apparent states and the apparent
generative class of a system's behavioral description. From these
examples we conclude that the act of observation can suggest frivolous
computational explanations of physical phenomena, up to and including
cognition.
Keywords: dynamical systems, generative capacity, formal language.
Download this paper as:
Gzipped Postscript
(jetai.ps.gz)
PDF
(jetai.pdf)
Large, E. W.,
Palmer, C and
Pollack, J
(1995). Reduced Memory Representations for Music.
Cognitive Science, 19,1,53-96.
Abstract
We address the problem of musical variation (identification of
different musical sequences as variations) and its implications for
mental representations of music. According to reductionist theories,
listeners judge the structural importance of musical events while
forming mental representations. These judgments may result from the
production of reduced memory representations that retain only the
musical gist. In a study of improvised music performance, pianists
produced variations on melodies. Analyses of the musical events
retained across variations provided support for the reductionist
account of structural importance. A neural network trained to produce
reduced memory representations for the same melodies represented
structurally important events more efficiently than others. Agreement
among the musicians' improvisations, the network model, and
music-theoretic predictions suggest that perceived constancy across
musical variation is a natural result of a reductionist mechanism for
producing memory representations.
.
Download this paper as:
Gzipped Postscript
(cogscimusic.ps.gz)
PDF
(cogscimusic.pdf)
Mou, Z. George and
Ficici, Sevan G.
(1995). A Scalable Divide-and-Conquer Parallel Algorithm for Finite State Automata and Its Applications.
Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing.
Philadelphia: Society for Industrial and Applied Mathematics, 1995.
Abstract
Our algorithm is a hybrid of two divide-and-conquer (DC) algorithms. A problem is first
compressed to one of smaller size (measured by input length), the compressed problem is
computed, and the solution is expanded. An unbalanced DC algorithm is used in the
compression and expansion, while a balanced DC algorithm is used in the computation. This
approach effectively reduces the computation and communication cost by a factor of n/p,
where n is input length, and p number of processors. The time complexity is O(n/p) for n >>
p, hence the algorithm is scalable to both n and p. Benchmarks on the MasPar MP-2 and
applications are presented. .
Keywords: parallel computation, finite-state automata.
Download this paper as:
Postscript
(dcfsa.ps)
Gzipped Postscript
(dcfsa.ps.gz)
PDF
(dcfsa.pdf)
Angeline, P. J.,
Saunders, G. M. and
Pollack, J. B.
(1994). Complete Induction of Recurrent Neural Networks,.
Proceedings of the Third International Conference on Evolutionary Programming.
Abstract
It has occurred to many researchers to apply genetic algorithms to the
training of recurrent neural networks. These studies generally avoid
total network induction, i.e., inducing both the topology and
parametric values of a network, favoring instead simple parametric
learning. Also, they often rely on standard forms of crossover to
manipulate network structures, a process which actually inhibits
network evolution. In addition, the common commitment to bit string
representations introduces an artificial limitation on the range of
networks that can be created. In this paper, an evolutionary program,
called GNARL, is presented that performs total network
induction. GNARL's ability to induce a range of appropriate solutions
is demonstrated on an interesting control task.
Download this paper as:
Gzipped Postscript
(ep94.ps.gz)
PDF
(ep94.pdf)
Angeline, P.,
Saunders, G and
Pollack, J.
(1994). An evolutionary algorithm that constructs recurrent networks.
IEEE Trans. on Neural Networks, 5, 54-65.
Abstract
Standard methods for inducing both the structure and weight values of
recurrent neural networks fit an assumed class of architectures to
every task. This simplification is necessary because the
interactions between network structure and function are not well
understood. Evolutionary computation, which includes genetic
algorithms and evolutionary programming, is a population-based search
method that has shown promise in such complex tasks. This paper
argues that genetic algorithms are inappropriate for network acqui-
sition and describes an evolutionary program, called GNARL, that
simultaneously acquires both the structure and weights for recurrent
networks. This algorithm's empirical acquisition method allows for the
emergence of complex behaviors and topologies that are potentially
excluded by the artificial architectural constraints imposed in
standard network induction methods.
Download this paper as:
Gzipped Postscript
(ieeenn.ps.gz)
PDF
(ieeenn.pdf)
Angeline, P. J. and
Pollack, J. B.
(1994). Coevolving High-Level Representations. .
Artificial Life III, C. Langton (ed.), Addison-Wesley: Reading MA,
pp. 55-71. .
Abstract
Several evolutionary simulations allow for a dynamic resizing of the
genotype. This is an important alternative to constraining the
genotype's maximum size and complexity. In this paper, we add an
additional dynamic to simulated evolution with the description of a
genetic algorithm that coevolves its representation language with the
genotypes. We introduce two mutation operators that permit the
acquisition of modules from the genotypes during evolution. These
modules form an increasingly high-level representation language
specific to the developmental environment. Experimental results
illustrating interesting properties of the acquired modules and the
evolved languages are provided.
Download this paper as:
Gzipped Postscript
(alife3.ps.gz)
PDF
(alife3.pdf)
Juillé, H.
(1994). Evolving Non-Determinism: An Inventive and Efficient Tool for Optimization and Discovery of Strategies.
Technical Report.
Abstract
In the field of optimization and machine learning techniques, some very
efficient and promising tools like Genetic Algorithms (GAs) and
Hill-Climbing have been designed.
In this same field, the Evolving Non-Determinism (END) model proposes an
inventive way to explore the space of states that, combined with the
use of simulated co-evolution, remedies some drawbacks of these previous
techniques and even allow this model to outperform them on some difficult
problems.
This new model has been applied to the sorting network problem, a
reference problem that challenged many computer scientists, and an
original one-player game named Solitaire.
For the first problem, the END model has been able to build from scratch
some sorting networks as good as the best known for the 16-input problem.
It even improved by one comparator a 25 years old result for the 13-input
problem.
For the Solitaire game, END evolved a strategy comparable to a human
designed strategy.
Keywords: evolutionary strategies, sorting networks, optimization techniques.
Download this paper as:
Postscript
(END_tech_report.ps)
Gzipped Postscript
(END_tech_report.ps.gz)
PDF
(END_tech_report.pdf)
Saunders, G.,
Angeline, P. and
Pollack, J. B.
(1994). Structural and Behavioral Evolution of Recurrent Networks.
Neural Information Processing Systems Conference 6.
Abstract
This paper introduces GNARL, an evolutionary program which induces
recurrent neural networks that are structurally unconstrained. In
contrast to constructive and destructive algorithms, GNARL employs a
population of networks and uses a fitness function's unsupervised
feedback to guide search through network space. Annealing is used in
generating both gaussian weight changes and structural
modifications. Applying GNARL to a complex search and collection task
demonstrates that the system is capable of inducing networks with
complex internal dynamics.
Download this paper as:
Gzipped Postscript
(nips94.ps.gz)
PDF
(nips94.pdf)
Saunders, G. M. and
Pollack, J. B.
(1994). The Evolution of communication schemes of continuous channels.
Ohio State University LAIR Tech report 94-GS-EVCOMM.
Abstract
This paper explores how communication can be understood as an
adaptation by agents to their environment. We model agents as
recurrent neural networks. After arguing against systems which use
discrete symbols to evolve communication, we supply our agents with a
number of continuous communications channels. The agents use these
channels to initiate real-valued signals which propagate through the
environment, decaying over distance, perhaps being perturbed by
environmental noise. Initially, the agents' signals appear random;
over time, a structure emerges as the agents learn to communicate
task-specific information about their environment. We demonstrate how
different communication schemes can evolve for a task, and then
discover a commonality between the schemes in terms of information
passed between agents. From this we discuss what it means to communi-
cate, and describe how a semantics emerges in the agents' signals
relative to their task domain.
Download this paper as:
Gzipped Postscript
(evcommtr.ps.gz)
PDF
(evcommtr.pdf)
Saunders, G.,
Kolen, J. F. and
Pollack, J. B
(1994). The Importance of Leaky Levels for behavior based AI.
Proceedings of Third Int'l conference on Simulation of Adaptive Behavior.
Abstract
From the many possible perspectives in which an agent may be
viewed, behavior-based AI selects observable actions as a particularly
useful level of description. Yet behavior is clearly not structure,
and anyone using behavior-based constraints to construct an agent
still faces many implementational roadblocks. Such obstacles are
typically avoided by adopting a finite state automaton (FSA) as a base
representation. As a result, potential benefits from alternative
formalisms are ignored. To explore these benefits, our work adopts a
multi-level view of an agent: behaviors and FSAs are but two of many
levels of description. We still focus on behaviors for the expression
of design constraints, but we avoid using FSAs as an
implementation. Our particular agent, Addam, is comprised of a set of
connectionist networks, a substrate which promotes the automatic
design of subsumptive systems. Moreover, the implementational choice
has important behavioral consequences some complex behaviors
emerge due to interactions among networks and need not be specified
explicitly. In this way, the underlying layers leak into one another,
each affecting the others in subtle and desirable ways.
.
Download this paper as:
Gzipped Postscript
(sab94.ps.gz)
PDF
(sab94.pdf)
Angeline, P. J. and
Pollack, J. B.
(1993). Competitive environments evolve better solutions to complex problems.
Fifth International Conference on Genetic Algorithms. 264-270.
Abstract
In the typical genetic algorithm experiment, the fitness function is
constructed to be independent of the contents of the population to
provide a consistent objective measure. Such objectivity entails
significant knowledge about the environment which suggests either the
problem has previously been solved or other non-evolutionary
techniques may be more efficient. Furthermore, for many complex tasks
an independent fitness function is either impractical or impossible to
provide. In this paper, we demonstrate that competitive fitness
functions, i.e. fitness functions that are dependent on the
constituents of the population, can provide a more robust training
environment than independent fitness functions. We describe three
differing methods for competitive fitness, and discuss their
respective advantages.
Download this paper as:
Gzipped Postscript
(icga5.ps.gz)
PDF
(icga5.pdf)
Angeline, P. J. and
Pollack, J. B.
(1993). Evolutionary Module Acquisition.
Second Evolutionary Programming Meeting, 154-163.
Abstract
Abstract Evolutionary programming and genetic algorithms share many
features, not the least of which is a reliance of an analogy to
natural selection over a population as a means of implementing
search. With their commonalities come shared problems whose solutions
can be investigated at a higher level and applied to both. One such
problem is the manipulation of solution parameters whose values encode
a desirable sub-solution. In this paper, we define a superset of
evolutionary programming and genetic algorithms, called evolutionary
algorithms, and demonstrate a method of automatic modularization
that protects promising partial solutions and speeds acquisition time.
Download this paper as:
Gzipped Postscript
(ep93.ps.gz)
PDF
(ep93.pdf)
Angeline, P. J. and
Pollack, J. B
(1992). Evolutionary Induction of subroutines. .
14th Annual Cognitive Science Conference, 236-241.
Abstract
In this paper we describe a genetic algorithm capable of evolving
large programs by exploiting two new genetic operators which construct
and deconstruct parameterized subroutines. These subroutines protect
useful partial solutions and help to solve the scaling problem for a
class of genetic problem solving methods. We demonstrate that our
algorithm acquires useful subroutines by evolving a modular program
from scratch to play and win at Tic-Tac-Toe against a flawed expert.
This work also serves to amplify our previous note (Pollack, 1991)
that a phase transition is the principle behind induction in
dynamical cognitive models.
Download this paper as:
Gzipped Postscript
(glib92.ps.gz)
PDF
(glib92.pdf)
Brinkman, Alexander and
Ficici, Sevan G.
(1992). Computational Tools for the Analysis of Rhythm.
Proceedings of the 1992 International Computer Music Conference. San Francisco:
International Computer Music Association, 1992.
Abstract
Reciprocal Duration Representation (RDR) facilitates development of tools that can express,
and therefore compare, metric accent. We present a method for deriving accentual profiles of
rhythms, which contain information about how notes relate to each other and to the meter. .
Keywords: music, rhythm.
Pollack, J. B.
(1992). On Wings of Knowledge: A review of Newell's Unified Theories of Cognition.
Artificial Intelligence, 59, 355-369.
Abstract
"The next risk is to be found guilty of the sin of
presumption. Who am I, Allen Newell, to propose a unified theory of
cognition...Psychology must wait for its Newton" (Newell, p. 37)
Newell is clearly entitled by a life of good scientific works to write
a book at such a level, and in my opinion, it is the most substantial
and impressive, by far, of recent offerings on the grand unified
mind. My entitlement to review his book is less self-evident, however
who am I to stand in judgement over one of the founding fathers of the
field? And so I fear I am about to commit the sin of presumption as
well, and to compound it, moreover, with the sin of obliqueness:
Because my argument is not with the quality of Newell's book, but with
the direction he is advocating for Cognitive Science, I will not
review his theory in detail. Rather, I will adopt a bird's eye view
and engage only the methodological proposal. I will, however, belabor
one small detail of Newell's theory, its name, SOAR, and only to use as my
symbolic launching pad.
Download this paper as:
Gzipped Postscript
(newellrev.ps.gz)
PDF
(newellrev.pdf)
Saunders, G.,
Kolen, J,
Angeline, P and
Pollack, J.
(1992). Additive Modular learning in Preemptrons.
14th Annual Cognitive Science Conference, 1098-1103.
Abstract
Cognitive scientists, AI researchers in particular, have
long-recognized the enormous benefits of modularity (e.g., Simon,
1969), as well as the need for self-organization (Samuel, 1967) in
creating artifacts whose complexity approaches that of human
intelligence. And yet these two goals seem almost incompatible, since
truly modular systems are usually designed, and systems that truly
learn are inherently nonmodular and produce only simple behaviors. Our
paper seeks to remedy this shortcoming by developing a new
architecture of Additive Adaptive Modules which we instantiate as
Addam, a modular agent whose behavioral repertoire evolves as the
complexity of the environment is increased.
Download this paper as:
Gzipped Postscript
(addam92.ps.gz)
PDF
(addam92.pdf)
Stucki, D. S. and
Pollack, J. B.
(1992). Fractal (Reconstructive Analogue) Memory.
14th Annual Cognitive Science Conference, 118-123.
Abstract
This paper proposes a new approach to mental imagery that has the
potential for resolving an old debate. We show that the methods by
which fractals emerge from dynamical systems provide a natural
computational framework for the relationship between the deep rep-
resentations of long-term visual memory and the surface
representations of the visual array, a distinction which was proposed
by (Kosslyn, 1980). The concept of an iterated function system (IFS)
as a highly compressed representation for a complex topological set of
points in a metric space (Barnsley, 1988) is embedded in a con-
nectionist model for mental imagery tasks. Two advantages of this
approach over previous models are the capability for topological
transformations of the images, and the continuity of the deep
representations with respect to the surface representations.
Download this paper as:
Gzipped Postscript
(fracmem.ps.gz)
PDF
(fracmem.pdf)
Ficici, Sevan G.
(1991). Computer Analysis of Surface Detail in Tonal Music.
Proceedings of the 1991 International Computer Music Conference.
San Francisco: International Computer Music Association, 1991.
Abstract
Models of musical structures are expressed as constraint systems and used to generate
bottom-up analyses of tonal function in 4-part Bach chorales. The constraint system reconciles
melodic structures (temporally contiguous events) with harmonic structures (temporally
simultaneous events) as it relaxes into a stable state. The final state of the system provides
unique interpretations of each event with regard to melodic and harmonic function where
possible, but is also capable of indicating musical ambiguity. Additionally, the constraint
system serves as a testbed for modelling musical structure, as it detects logical inconsistencies
within a model, and thus constitutes a proof of soundness. .
Keywords: music, tonal analysis.
Kolen, J. F. and
Pollack, J. B
(1991). Multi-Associative Memory.
13th Annual Cognitive Science Conference, 785-789.
Abstract
This paper discusses the problem of how to implement
many-to-many, or multi-associative, mappings within connectionist
models. Traditional symbolic approaches wield explicit
representation of all alternatives via stored links, or implicitly
through enumerative algorithms. Classical pattern association models
ignore the issue of generating multiple outputs for a single input
pattern, and while recent research on recurrent networks is promising,
the field has not clearly focused upon multi-associativity as a
goal. In this paper, we define multiassociative memory MM, and several
possible variants, and discuss its utility in general cognitive
modeling. We extend sequential cascaded networks to fit the task,
and perform several initial experiments
which demonstrate the feasibility of the concept.
Download this paper as:
Gzipped Postscript
(mam92.ps.gz)
PDF
(mam92.pdf)
Pollack, J.B.
(1991). The Induction of Dynamical Recognizers.
Machine Learning 7, 227-252.
Abstract
A higher order recurrent neural network architecture learns to
recognize and generate languages after being "trained" on
categorized exemplars. Studying these networks from the perspective of
dynamical systems yields two interesting discoveries: First, a
longitudinal examination of the learning process illustrates a new
form of mechanical inference: Induction by phase transition. A small
weight adjustment causes a "bifurcation" in the limit behavior of
the network. This phase transition corresponds to the onset of the
network's capacity for generalizing to arbitrary length
strings. Second, a study of the automata resulting from the
acquisition of previously published training sets indicates that while
the architecture is not guaranteed to find a minimal finite
automaton consistent with the given exemplars, which is an NP-Hard
problem, the architecture does appear capable of generating
non-regular languages by exploiting fractal and chaotic dynamics. I
end the paper with a hypothesis relating linguistic generative
capacity to the behavioral regimes of non-linear dynamical
systems.
.
Download this paper as:
PDF
(dyrec.pdf)
Kolen, J. F. and
Pollack, J. B.
(1990). Back-Propagation is Sensitive to Initial Conditions .
Complex Systems, 4,3, 269-280.
Abstract
This paper explores the effect of initial weight selection on
feed-forward networks learning simple functions with the
back-propagation technique. We first demonstrate, through the use of
Monte Carlo techniques, that the magnitude of the initial condition
vector (in weight space) is a very significant parameter in
convergence time variability. In order to further understand this
result, additional deterministic experiments were performed. The
results of these experiments demonstrate the extreme sensitivity of
back propagation to initial weight configuration.
Download this paper as:
Gzipped Postscript
(bpsic.ps.gz)
PDF
(bpsic.pdf)
Pollack, J. B.
(1990). Recursive Distributed Representations.
Artificial Intelligence 46, 1, 77-105.
Abstract
A long-standing difficulty for connectionist modeling has been how
to represent variable-sized recursive data structures, such as trees
and lists, in fixed-width patterns. This paper presents a
connectionist architecture which automatically develops compact
distributed representations for such compositional structures, as well
as efficient accessing mechanisms for them. Patterns which stand
for the internal nodes of fixed-valence trees are devised through
the recursive use of back-propagation on three-layer auto-associative
encoder networks. The resulting representations are novel, in that
they combine apparently immiscible aspects of features, pointers,
and symbol structures. They form a bridge between the data structures
necessary for high-level cognitive tasks and the associative, pattern
recognition machinery provided by neural networks.
Download this paper as:
Gzipped Postscript
(raam.ps.gz)
PDF
(raam.pdf)
Pollack, J. B.
(1989). Connectionism: Past, Present, and Future.
Artificial Intelligence Review, 3, 3-20.
Abstract
Research efforts to study computation and cognitive modeling
on neurally-inspired mechanisms have come to be called Connectionism.
Rather than being
brand-new, it is actually the rebirth of a research
program which thrived from the 40's through the 60's and
then was severely retrenched in the 70's.
Connectionism is often posed as a paradigmatic competitor
to the Symbolic Processing tradition of Artificial
Intelligence, and, indeed, the counterpoint
in the timing of their intellectual and commercial
fortunes may lead
one to believe that research in cognition is merely a
zero-sum game. This paper surveys the history of the
field, often in relation to AI,
discusses its current successes and failures, and makes
some predictions for where it might lead in the future.
.
Download this paper as:
Gzipped Postscript
(nnhistory.ps.gz)
PDF
(nnhistory.pdf)
Pollack, J. B.
(1989). Implications of Recursive Distributed Representations.
Advances in Neural Information Processing Systems I, 527-536.
Abstract
I will describe my recent results on the automatic development of
fixed-width recursive distributed representations of variable-sized
hierarchal data structures. One implication of this work is that
certain types of AI-style data-structures can now be represented in
fixd-width analog vectors. Simple inferences can be performed
using the type of pattern associations that neural networks excel
at. Another implication arises from noting that these representa-
tions become self-similar in the limit. Once this door to chaos is
opened, many interesting new questions about the representational
basis of intelligence emerge, and can (and will) be discussed.
Download this paper as:
Gzipped Postscript
(nips1.ps.gz)
PDF
(nips1.pdf)
Pollack, J. B.
(1989). No Harm Intended: A Review of the Perceptrons expanded edition. .
Journal of Mathematical Psychology, 33, 3, 358-365. .
Abstract
"We did not think of our work as killing Snow White... (Papert, 1988
p. 7)." Research on Connectionist and Neural
Networks has recently awakened, and is now expecting a valuable kiss
from Prince DARPA. In fact, 1988 may be the year of connectionism's
loss of innocence. Not only has 1988 seen the publication of articles,
including Papert's, about the symbolic/connectionist debate in
DAEDELUS, but also the publication of a provocative special
anti-connectionist issue of COGNITION. Finally, to top it off, MIT
Press has re-issued PERCEPTRONS, with a new prologue and epilogue,
titled, respectively, ``The View from 1988,'' and ``The New
Connectionism'' Because this is the third edition of the book, I will
focus attention on the new material, which is more political than
scientific. First, however, for those who have not read PERCEPTRONS,
I will summarize its scientific contents. This work, in retrospect,
will most likely be viewed as the greatest contribution to the
cognitive sciences made by Minsky or Papert, so it is still
important to understand their findings.
.
Download this paper as:
Gzipped Postscript
(perceptron.ps.gz)
PDF
(perceptron.pdf)
Pollack, J.B
(1987). (Excerpt) On Connectionist Models of Natural Language Processing.
Ph.D Dissertation in Computer Science, University of Illinois.
Abstract
The connectionist paradigm is much like a programming language, in
that it provides a framework for constructing computational models
which anticipates various changeable parts. This chapter examines the
connectionist framework and its underlying assumptions, and focuses on
certain limitations which recur frequently in connectionist modeling
efforts. Based on the elements used to construct a Turing Machine
within this framework, it is argued that some of the default
assumptions need to be rethought.
.
Download this paper as:
Gzipped Postscript
(neuring.ps.gz)
PDF
(neuring.pdf)