Computer Science Department : George Mason University
 
  home     people     publications     tools     research     activities     community  

EC lab Publications (long)

This page contains a list of publications authored by members of the Evolutionary Computation Laboratory at George Mason University. PostScript copies of most of these papers are available online. Click here to get the short version (without abstracts, keywords, etc.). Click here to obtain the bib file for this page.

Kenneth A. De Jong's Dissertation

 
2009   2008   2007   2006   2005   2004   2003   2002   2001   2000   1999   1998   1997   Pre-1997  

2009 Publications

Keith Sullivan, Christopher Vo, Brian Hrolenok, and Sean Luke (2009)
RoboPatriots: George Mason University 2009 RoboCup Team. In Proceedings of 2009 RoboCup Workshop.
[PDF

Christopher Vo, Liviu Panait, and Sean Luke (2009)
Cooperative Coevolution and Univariate Estimation of Distribution Algorithms. In Proceedings of Foundation of Genetic Algorithms.
Abstract:
In this paper, we discuss a curious relationship between Cooperative Coevolutionary Algorithms (CCEAs) and univariate Estimation of Distribution Algorithms (EDAs). Specifically, the distribution model for univariate EDAs is equivalent to the infinite population EGT model common in the analysis of CCEAs. This relationship may permit cross- pollination between these two disparate fields. As an example, we derive a new EDA based on a known CCEA from the literature, and provide some preliminary experimental analysis of the algorithm.

2008 Publications

Gabriel Balan, Dana Richards, and Sean Luke (2008)
Long-term Fairness with Bounded Worst-case Losses. In Proceedings of AAAI Advances in Preference Workshop.  Pages 7-12.
Abstract:
How does one repeatedly choose actions so as to be fairest to the multiple beneficiaries of those actions? We examine approaches to discovering sequences of actions for which the worst-off beneficiaries are treated maximally well, then secondarily the second-worst-off, and so on. We formulate the problem for the situation where the sequence of action choices continues forever; this problem may be reduced to a set of linear programs. We then extend the problem to situations where the game ends at some unknown finite time in the future. We demonstrate that an optimal solution is NP-hard, and present two good approximation algorithms.

Gabriel Balan, Dana Richards, and Sean Luke (2008)
Algorithms for Leximin-Optimal Fair Policies in Repeated Games.
George Mason University, technical report GMU-CS-TR-2008-1.
[PDF
Abstract:
Solutions to non-cooperative multiagent systems often require achieving a joint policy which is as fair to all parties as possible. There are a variety of methods for determining the fairest such joint policy. One approach, min fairness, finds the policy which maximizes the minimum average reward given to any agent. We focus on an extension, leximin fairness, which breaks ties among candidate policies by choosing the one which maximizes the second-to-minimum average reward, then the third-to-minimum average reward, and so on. This method has a number of advantages over others in the literature, but has so far been little-used because of the computational cost in employing it to find the fairest policy. In this paper we propose a linear programming based algorithm for computing leximin fairness in repeated games which has a polynomial time complexity given certain reasonable assumptions.

Kenneth A. De Jong (2008)
Evolving intelligent agents: A 50 year quest. IEEE Computational Intelligence Magazine, 3(1) : 12-17.
Abstract:
Already in the early 1960s, Larry Fogel and his colleagues were exploring the possibility of creating artificial intelligence using simulated evolution. Over the past 50 years, that idea has captured the imagination of many people and has led to a wide variety of approaches. In this article, this quest is summarized, the current state of the art is described, and some of the remaining open questions are discussed.

Zohreh Nazeri, Daniel Barbara, Kenneth De Jong, George Donohue, and Lance Sherry (2008)
Contrast-Set Mining of Aircraft Accidents and Incidents. In Proceedings of Advances in Data Mining: Medical Applications, E-Commerce, Marketing, and Theoretical Aspects.
Abstract:
Identifying patterns of factors associated with aircraft accidents is of high interest to the aviation safety community. However, accident data is not large enough to allow a significant discovery of repeating patterns of the factors. We applied the STUCCO algorithm to analyze aircraft accident data in contrast to the aircraft incident data in major aviation safety databases and identified factors that are significantly associated with the accidents. The data pertains to accidents and incidents involving commercial flights within the United States. The NTSB accident database was analyzed against four incident databases and the results were compared. We ranked the findings by the Factor Support Ratio, a measure introduced in this work.

Liviu Panait, Karl Tuyls, and Sean Luke (2008)
Theoretical Advantages of Lenient Learners: An Evolutionary Game Theoretic Perspective. The Journal of Machine Learning Research, 9(Mar) : 423–457.
Abstract:
This paper presents the dynamics of multiple learning agents from an evolutionary game theoretic perspective. We provide replicator dynamics models for cooperative coevolutionary algorithms and for traditional multiagent Q-learning, and we extend these differential equations to account for lenient learners: agents that forgive possible mismatched teammate actions that resulted in low rewards. We use these extended formal models to study the convergence guarantees for these algorithms, and also to visualize the basins of attraction to optimal and suboptimal solutions in two benchmark coordination problems. The paper demonstrates that lenience provides learners with more accurate information about the benefits of performing their actions, resulting in higher likelihood of convergence to the globally optimal solution. In addition, the analysis indicates that the choice of learning algorithm has an insignificant impact on the overall performance of multiagent learning algorithms; rather, the performance of these algorithms depends primarily on the level of lenience that the agents exhibit to one another. Finally, the research herein supports the strength and generality of evolutionary game theory as a backbone for multiagent learning.

Alexei V. Samsonovich, Anastasia Kitsantas, Nada Dabbagh, and Kenneth A. De Jong (2008)
Self-Awareness as Metacognition about Own Self Concept. In Proceedings of AAAI Workshop on Metareasoning: Thinking about Thinking.
Abstract:
Implementation of agency in a cognitive system implies that certain beliefs, values and/or goals represented in the system become, if implicitly, attributed to the self of the agent. When the cognitive system becomes explicitly aware of this attribution, it acquires a self-regulation capacity allowing it to control, modify and develop its self-concept together with the attitudes attributed to the self, adjusting to dynamically changing contexts and personal experience. The leverage of self-awareness understood in this sense consists in increased robustness, flexibility and integrity of the cognitive system, as illustrated by a paradigm of self-regulated learning.

Zbigniew Skolicki, Tomasz Arciszewski, Houck, and Kenneth De Jong (2008)
Co-evolution of terrorist and security scenarios for water distribution systems. Advances in Engineering Software, 39(10) : 801–811.
Abstract:
Identification of vulnerabilities of water distribution systems and identification of appropriate counter-measures are important components of homeland security. These are difficult and time consuming tasks. This paper provides a new approach to resolve these problems in complex infrastructure systems. It is based on the use of co-evolutionary computation for the generation of both terrorist and security scenarios. The basic concepts of co-evolutionary computation are briefly explained. The concept of co-evolutionary generation of terrorist and security scenarios is introduced in the context of a hypothetical water distribution system for a small town. A tool developed at George Mason University is used for a number of experiments that reveal a variety of emerging security patterns. The experiments show that these patterns may be helpful in effectively protecting the network.

Keith Sullivan, Brian Davidson, Christopher Vo, Brian Hrolenok, and Sean Luke (2008)
RoboPatriots: George Mason University 2008 RoboCup Team. In Proceedings of 2008 RoboCup Workshop.
[PDF

Keith Sullivan, Sean Luke, Curt Larock, Sean Cier, and Steven Armentrout (2008)
Opportunistic Evolution: Efficient Evolutionary Computation on Large-Scale Computational Grids. In Genetic and Evolutionary Computation Conference Late Breaking Papers.
[PDF
Abstract:
We examine opportunistic evolution, a variation of master- slave distributed evaluation designed for deployment of evolutionary computation to very large grid computing architectures with limited communications, severe evaluation overhead, and wide variance in evaluation node speed. In opportunistic evolution, slaves receive some N individuals at a time, evaluate them, and then run those individuals through their own mini evolutionary loop until some fixed wall clock time has been exceeded. Our implementation of opportunistic evolution may be used in conjunction with either a generational or, for maximum throughput, an asynchronous steady-state evolutionary model in the master. Opportunistic evolution is strongly exploitative. We perform initial experiments comparing the technique with a traditional master/slave model, and suggest possible classes of problems for which it might be apropos.

2007 Publications

Anthony Bigbee, Claudio Cioffi-Revilla, and Sean Luke (2007)
Replication of Sugarscape using MASON. Chapter in Agent-Based Approaches in Economic and Social Complex Systems IV.  Pages 183–190.  (c) Springer.
Abstract:
The purpose of this research was to replicate the Sugarscape model (Eptstein and Axtell 1996) and simulation outcomes as described in Growing Artificial Societies (GAS). Sugarscape is a classic agent-based model and contemporary simulation toolkits usually only have a very simple replication of a few core rules. There is scant evidence of significant replication of the rules and simulation outcomes; code supplied with Repast, Swarm, and NetLogo implement a minority of the rules in Sugarscape. In particular, the standard Repast distribution only implements Growback, Movement, and Replacement. Sugarscape implementations in these toolkits are clearly provided only as basic demonstrations of how wellknown social models might be implemented, rather than complete achievements of scientific replication.

Kenneth De Jong (2007)
Parameter Setting in EAs: a 30 Year Perspective. In Parameter Setting in Evolutionary Algorithms.  Pages 1-18.

Adrian Grajdeanu (2007)
Methods for Open-box Analysis in Artificial Development. In Proceedings of Genetic and Evolutionary Computation Conference.  Pages 1005 – 1012.
Abstract:
Even a developmental system with very simple building blocks can evolve significantly complex artifacts. Understanding such complexity poses a significant challenge. This paper shows how various investigative methods that are typically used in biology, can be transferred and used in an artificial development context. As an instance of evolved complexity, a self-repairing artifact is analyzed using the following methods: ablation of environmental features, chemical concentrations monitors, in silico subsystem simulations, gene knock-outs, and modeling of the gene regulatory map. A number of mechanisms governing size-regulation and self repair are uncovered, such as: subtle timing of gene activations, stable regulation based on attractor points, opportunistic use of the environment and information content replication.

Adrian Grajdeanu (2007)
Modeling Diffusion in a Discrete Environment.
George Mason University, technical report GMU-CS-TR-2008-1.
[PDF
Abstract:
The present report details a model for implementing diffusion in a discrete space. Formulated in 2004 in support of artificial development experiments, the model is mathematically justified starting from the diffusion equation. It has physical plausibility and handles well different shaped and sized diffusion neighborhoods in the sense that it achieves isotropic diffusion in spite of the bias introduced by the discretizing grid. It provides one formulation that encapsulates the diffusion neighborhood details and renders it applicable to linear, planar, spatial and even n-dimensional constructs.

Sean Luke, Deepankar Sharma, and Gabriel Catalin Balan (2007)
Finding Interesting Things. In Proceedings of Genetic and Evolutionary Computation Conference.
Abstract:
Model- and simulation-designers are often interested not in the optimum output of their system, but in understanding how the output is sensitive to different parameters. This can require an inefficient sweep of a multidimensional parameter space, with many samples tested in regions of the space where the output is essentially all the same, or a sparse sweep which misses crucial "interesting" regions where the output is strongly sensitive. In this paper we introduce a novel population-oriented approach to adaptive parameter sweeping which focuses its samples on these sensitive areas. The method is easy to implement and model-free, and does not require any previous knowledge about the space. In a weakened form the method can operate in non-metric spaces such as the space of genetic program trees. We demonstrate the method on three test problems, showing that it identifies regions of the space where the slope of the output is highest, and concentrates samples on those regions.

Z. Skolicki and K. De Jong (2007)
The importance of a two-level perspective for island model design. In Proceedings of IEEE Congress on Evolutionary Computation.  Pages 4623-4630.
Abstract:
Our theoretical understanding of island models (IMs) is much worse than of single-population evolutionary algorithms (EAs). As a consequence there is relatively little guidance available to a practitioner for even the most basic aspects of IM design such as choosing the size and number of the islands. In this paper we improve on this situation by showing how a particular two-level perspective can in fact provide guidance for IM design.

Keith Sullivan and Sean Luke (2007)
Evolving Kernel for Support Vector Machine Classification. In Proceedings of Genetic and Evolutionary Computation Conference.
[PDF
Abstract:
While support vector machines (SVMs) have shown great promise in supervised classification problems, researchers have had to rely on expert domain knowledge when choosing the SVM's kernel function. This project seeks to replace this expert with a genetic programming (GP) system. Using strongly typed genetic programming and principled kernel closure properties, we introduce a new algorithm, called KGP, which finds near-optimal kernels. The algorithm shows wide applicability, but the combined computational overhead of GP and SVMs remains a major unresolved issue.

2006 Publications

Gabriel Balan and Sean Luke (2006)
History-Based Traffic Control. In Proceedings of Autonomous Agents and Multiagent Systems.
Abstract:
What if traffic lights gave you a break after you've spent a long time waiting in traffic elsewhere? In this paper we examine a variety of multi-agent traffic light controllers which consider vehicles' past stopped-at-red histories. For example, a controller might distribute credits to cars as they wait and award the green light to lanes with the most credits, allowing cars to keep the credits they accumulate during travel. Such history-based controllers are intended to provide a kind of global fairness, reducing the variance in mean time spent waiting at lights during trips. We compare these controllers against other multi-agent controllers which only consider present information, and discover, among other things, that while the history-based controllers are among the most robust, they often unexpectedly provide more efficiency than fairness.

Adam Campbell, Annie S. Wu, Keith Garfield, Randall Shumaker, Sean Luke, and Kenneth A. De Jong (2006)
Empirical Study on the Effects of Synthetic Social Structures on Teams of Autonomous Vehicles. In Proceedings of International Conference on Networking, Sensing, and Control.  Pages 440 – 445.
Abstract:
The goal of this research is to explore the effects of social interactions between individual autonomous vehicles (AVs) in various problem scenarios. We will take a look at one way to construct the social relationships and generate data from computer simulations to compare the behaviors of each. A difference can be noticed when Synthetic Social Structures (SSS) are used to control the interactions between neighboring AVs. Our experiments show that SSSs can be used to improve team performance on a problem in which a team of AVs must maneuver through a narrow corridor to reach a goal.

Claudio Cioffi-Revilla, Sean Luke, Dawn C. Parker, J. D. Rogers, W. W. Fitzhugh, W. Honeychurch, B. Frohlich, P. DePriest, and Chanag Amartuvshin (2006)
Computational Modeling Frontiers in International Politics: Agent-based Modeling and Simulation of Adaptive Behavior and Long-Term Change in Inner Asia. In Proceedings of First World Congress on Social Simulation.
Abstract:
We present a new international project to develop temporally and spatially calibrated agent-based models of the rise and fall of polities in Inner Asia (Central Eurasia) in the past 5,000 years. Gaps in theory, data, and computational models for explaining long-term sociopolitical change—both growth and decay—motivate this project. We expect three contributions: (1) new theoretically grounded simulation models validated and calibrated by the best available data; (2) a new long-term cross-cultural database with several data sets; and (3) new conceptual, theoretical, and methodological contributions for understanding social complexity and long-term change and adaptation in real and artificial societies. Our theoretical framework is based on explaining sociopolitical evolution by the process of "canonical variation".

Kenneth A. De Jong (2006)
Evolutionary Computation: A Unified Approach.   MIT Press
Abstract:
Evolutionary computation, the use of evolutionary systems as computational processes for solving complex problems, is a tool used by computer scientists and engineers who want to harness the power of evolution to build useful new artifacts, by biologists interested in developing and testing better models of natural evolutionary systems, and by artificial life scientists for designing and implementing new artificial evolutionary worlds. In this clear and comprehensive introduction to the field, Kenneth De Jong presents an integrated view of the state of the art in evolutionary computation. Although other books have described such particular areas of the field as genetic algorithms, genetic programming, evolution strategies, and evolutionary programming, Evolutionary Computation is noteworthy for considering these systems as specific instances of a more general class of evolutionary algorithms. This useful overview of a fragmented field is suitable for classroom use or as a reference for computer scientists and engineers.

Adrian Grajdeanu and Sanjeev Kumar (2006)
A Novel Developmental System for the Study of Evolutionary Design.
Developmental Systems; AAAI Fall Symposium, technical report FS-06-03.
[PDF
Abstract:
A novel developmental system designed to facilitate the study of generative encoding-based evolutionary design is presented. An aim of this work is to explore the simplest system and genetic encoding capable of exhibiting phenomena akin to size regulation and self-repair in developmental biology. Here we show that in the absence of complicated developmental mechanisms - such as ligand-receptor mediated cell signaling, asymmetric or mitotic spindle-based cell division, cell motility, or cellular forces - a simple rule-like GRN encoding and a simple internal/external chemical exchange mechanism confer the ability to generate patterns that are size regulated, and able to self-repair when damaged. In addition, we analyze the mechanisms that achieve size regulation and self-repair.

Sean Luke and Liviu Panait (2006)
A Comparison of Bloat Control Methods for Genetic Programming. Evolutionary Computation, 14(3) : 309 – 344.
Abstract:
Genetic programming has highlighted the problem of bloat, the uncontrolled growth of the average size of an individual in the population. The most common approach to dealing with bloat in tree-based genetic programming individuals is to limit their maximal allowed depth. An alternative to depth limiting is to punish individuals in some way based on excess size, and our experiments have shown that the combination of depth limiting with such a punitive method is generally more effective than either alone. Which such combinations are most effective at reducing bloat? In this article we augment depth limiting with nine bloat control methods and compare them with one another. These methods are chosen from past literature and from techniques of our own devising. Testing with four genetic programming problems, we identify where each bloat control method performs well on a per-problem basis, and under what settings various methods are effective independent of problem. We report on the results of these tests, and discover an unexpected winner in the cross-platform category.

Liviu Panait and Sean Luke (2006)
Selecting Informative Actions Improves Cooperative Multiagent Learning. In Proceedings of Autonomous Agents and Multiagent Systems.
Abstract:
In concurrent cooperative multiagent learning, each agent simultaneously learns to improve the overall performance of the team, with no direct control over the actions chosen by its teammates. An agent's action selection directly influences the rewards received by all the agents, resulting in a co-adaptation among the concurrent learning processes. Co-adaptation can drive the team towards suboptimal solutions because agents tend to select those actions that are rewarded better, without any consideration for how such actions may affect the search of their teammates. We argue that to counter this tendency, agents should also prefer actions that inform their teammates about the structure of the joint search space in order to help them choose from among various action options. We analyze this approach in a cooperative coevolutionary framework, and we propose a new algorithm, iCCEA, that highlights the advantages of selecting informative actions. We show that iCCEA generally outperforms other cooperative coevolution algorithms on our test problems.

Liviu Panait, Sean Luke, and Joseph F. Harrison (2006)
Archive-Based Cooperative Coevolutionary Algorithms. In Proceedings of Genetic and Evolutionary Computation Conference.
Abstract:
Archive-based cooperative coevolutionary algorithms attempt to retain a set of individuals which act as good collaborators for other coevolved individuals in the evolutionary system. We introduce a new archive-based algorithm, called iCCEA, which compares favorably with other cooperative coevolutionary algorithms. We explain the current problems with cooperative coevolution which have given rise to archive methods, detail the iCCEA algorithm, compare it against other traditional and archive-based methods on basic problem domains, and discuss the reasons behind the performance of various algorithms.

Liviu Panait, Sean Luke, and R. Paul Wiegand (2006)
Biasing Coevolutionary Search for Optimal Multiagent Behavior. IEEE Transactions on Evolutionary Computation, 10(6) : 629 – 645.
Abstract:
Cooperative coevolutionary algorithms offer great potential for concurrent multiagent learning domains and are of special utility to domains involving teams of multiple agents. Unfortunately, they also exhibit pathologies resulting from their game-theoretic nature, and these pathologies interfere with finding solutions that correspond to optimal collaborations of interacting agents. We address this problem by biasing a cooperative coevolutionary algorithm in such a way that the fitness of an individual is based partly on the result of interactions with other individuals (as is usual), and partly on an estimate of the best possible reward for that individual if partnered with its optimal collaborator. We justify this idea using existing theoretical models of a relevant subclass of coevolutionary algorithms, demonstrate how to apply biasing in a way that is robust with respect to parameterization, and provide some experimental evidence to validate the biasing approach. We show that it is possible to bias coevolutionary methods to better search for optimal multiagent behaviors.

Liviu Panait, Keith Sullivan, and Sean Luke (2006)
Lenient Learners in Cooperative Multiagent Systems. In Proceedings of Autonomous Agents and Multiagent Systems.
Abstract:
In concurrent learning algorithms, an agent's perception of the joint search space depends on the actions currently chosen by the other agents. These perceptions change as each agent's action selection is influenced by its learning. We observe that agents that show lenience to their teammates achieve more accurate perceptions of the overall learning task. Additionally, lenience appears more beneficial at early stages of learning, when the agent's teammates are merely exploring their actions, and less helpful as the agents start to converge. We propose two multiagent learning algorithms where agents exhibit a variable degree of lenience, and we demonstrate their advantages in several coordination problems.

Elena Popovici and Kenneth De Jong (2006)
Sequential Versus Parallel Cooperative Coevolutionary Algorithms for Optimization. In Proceedings of Congress on Evolutionary Computation.
Abstract:
Cooperative coevolution is often used to solve difficult optimization problems by means of problem decomposition. Its performance on this task is influenced by many design decisions. It would be useful to have some knowledge of the performance effects of these decisions, in order to make the more beneficial ones. In this paper we study the effects on performance of the frequency of interaction between populations. We show them to be problem-dependent and use dynamics analysis to explain this dependency.

Elena Popovici and Kenneth De Jong (2006)
The Effects of Interaction Frequency on the Optimization Performance of Cooperative Coevolution. In Proceedings of Genetic and Evolutionary Computation Conference.
Abstract:
Cooperative coevolution is often used to solve difficult optimization problems by means of problem decomposition. Its performance on this task is influenced by many design decisions. It would be useful to have some knowledge of the performance effects of these decisions, in order to make the more beneficial ones. In this paper we study the effects on performance of the frequency of interaction between populations. We show them to be problem-dependent and use dynamics analysis to explain this dependency.

Elena Popovici and Kenneth De Jong (2006)
The Dynamics of the Best Individuals in Co-Evolution. Natural Computing, 5(3) : 229 – 255.
Abstract:
There continues to be a growing interest in the use of co-evolutionary algorithms to solve difficult computational problems. However, their performance has varied widely from good to disappointing. The main reason for this is that co-evolutionary systems can display quite complex dynamics. Therefore, in order to efficiently use co-evolutionary algorithms for problem solving, one must have a good understanding of their dynamical behavior. To build such understanding, we have constructed a methodology for analyzing co-evolutionary dynamics based on trajectories of best-of-generation individuals. We applied this methodology to gain insights into how to tune certain algorithm parameters in order to improve performance.

Alexei V. Samsonovich, Giorgia Ascoli, and Kenneth De Jong (2006)
Computational Assessment of the 'Magic' of Human Cognition. In Proceedings of World Congress on Computational Intelligence.
Abstract:
The task of designing cognitive tests and challenges for robots and intelligent agents is vital for guidance and evaluation of the development of cognitive architectures aimed at the human level of intelligence. In addressing this task, the tremendous store of knowledge of experimental psychology cannot be ignored. At the same time, methods and test paradigms used for evaluation of humans and/or brain models need to be adjusted before they can be used for evaluation of artifacts. The present work is focused on this problem and its possible solutions in one general paradigm of ontogenesis in virtual environment. We propose several test scenarios and metrics that are adequate to assess cognitive features in computational agents.

Keith Sullivan, Liviu Panait, and Sean Luke (2006)
Can Good Learners Always Compensate for Poor Learns?. In Proceedings of Autonomous Agents and Multiagent Systems.
Abstract:
Can a good learner compensate for a poor learner when paired in a coordination game? Previous work presented an example where a special learning algorithm (FMQ) is capable of doing just that when paired with a specific less capable algorithm even in games which stump the poorer algorithm when paired with itself. We argue that this result is not general. We give a straightforward extension to the coordination game in which FMQ cannot compensate for the lesser algorithm. We also provide other problematic pairings, and argue that another high-quality algorithm cannot do so either.

R. Paul Wiegand, Mitchell A. Potter, Donald Sofge, and William M. Spears (2006)
A Generalized Graph-Based Method for Engineering Swarm Solutions to Multiagent Problems.. In Proceedings of the 9th International Parallel Problem Solving from Nature - PPSN IX.  Pages 741–750.  (c) Springer.
[PDF
Abstract:
We present two key components of a principled method for constructing modular, heterogeneous swarms. First, we generalize a well-known technique for representing swarm behaviors to extend the power of multiagent systems by specializing agents and their interactions. Second, a novel graph-based method is introduced for designing swarm-based behaviors for multiagent teams. This method includes engineer-provided knowledge through explicit design decisions pertaining to specialization, heterogeneity, and modularity. We show the representational power of our generalized representation can be used to evolve a solution to a challenging multiagent resource protection problem. We also construct a modular design by hand, resulting in a scalable and intuitive heterogeneous solution for the resource protection problem.

2005 Publications

Tomasz Arciszewski and Rafal Kicinger (2005)
Proactive security: From evolutionary approaches to cellular automata. In Working Together: Conference on Public/Private R&D Partnerships in Homeland Security.  Pages (poster).  DHS.
[PDF
Keywords: infrastructure security and critical infrastructure protection and cellular automata and evolutionary computation and coevolutionary algorithms
Abstract:
The main objective of the paper is to propose several novel approaches to security of complex infrastructure systems, which can be utilized in the development of a class of computer tools for infrastructure protection. First, the paper introduces the concept of proactive infrastructure security and compares it with reactive security. The comparison is done in the context of the generation and evaluation of both the terrorist and security scenarios, which are also introduced and described. Next, the paper discusses both the evolutionary and co-evolutionary generation of terrorist and security scenarios and discusses various computer tools, which have been developed at George Mason University for infrastructure protection. Finally, the paper briefly overviews the concept of cellular automata and proposes how cellular automata could be used in the development of computer tools for infrastructure protection. The paper ends with the initial research conclusions and various suggestions for further research.

Tomasz Arciszewski and Rafal Kicinger (2005)
Structural design inspired by nature. In Innovation in Civil and Structural Engineering Computing.   Barry H. V. Topping editor(s).  Pages 25-48.  Saxe-Coburg Publications.
[Link to the book
Keywords: creative design and morphogenesis and morphogenic evolutionary design and evolutionary computation and design inspired by nature and bio-inspired design and structural design and evolutionary design and coevolutionary design and generative representations and cellular automata
Abstract:
This paper explores the state of the art in structural design inspired by nature and proposes an improved understanding of this emerging paradigm and its major components. First, it introduces and discusses the nature of three categories of inspiration, including visual, conceptual, and computational inspiration. Next, several important inspiration sources are identified and briefly described, including Evolutionary Computation, Coevolutionary Computation, Cellular Automata, and TRIZ. In particular, design generation mechanisms based on cellular automata are introduced with some details. They are inspired by the processes of morphogenesis occurring in nature and have great potential to generate novel designs. In this case, the design generation mechanisms are encoded in so-called generative representations, which are also described. Three major design objectives are introduced and discussed, namely optimality, creativity, and robustness. They are related to the sources of inspiration and the corresponding computational mechanisms inspired by nature. Also, three levels of integration of computational mechanisms inspired by nature are proposed and their relationship to design objectives is discussed. Finally, a general design situation, when inspiration by nature is considered, is introduced and its unified description is proposed as the first step in the direction of building a unified approach to structural design inspired by nature. The paper provides initial conclusions and discusses the most promising directions for future research.

Tomasz Arciszewski, Zbigniew Skolicki, and Kenneth De Jong (2005)
Intelligent Agent Fundamentals. In Agents and Multi-Agent Systems in Construction.   C. J. Anumba, O. O. Ugwu, and Z. Ren editor(s).  Pages 6 – 30.  Taylor and Francis.

Jeffrey K. Bassett, Mitchell A. Potter, and Kenneth A. De Jong (2005)
Applying Price's Equation to Survival Selection. In Proceedings of Genetic and Evolutionary Computation Conference -- GECCO-2005.  Pages 1371–1378.  ACM Press.
[PDF
Abstract:
Several researchers have used Price's equation (from biology theory literature) to analyze the various components of an Evolutionary Algorithm (EA) while it is running, giving insights into the components contributions and interactions. While their results are interesting, they are also limited by the fact that Price's equation was designed to work with the averages of population fitness. The EA practitioner, on the other hand, is typically interested in the best individuals in the population, not the average. In this paper we introduce an approach to using Price's equation which instead calculates the upper tails of population distributions. By applying Price's equation to EAs that use survival selection instead of parent selection, this information is calculated automatically.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth De Jong (2005)
Parameterized versus Generative Representations in Structural Design: An Empirical Comparison. In Proceedings of Genetic and Evolutionary Computation Conference -- GECCO-2005.  Pages 2007–2014.  ACM Press.
[PDF
Abstract:
Any computational approach to design, including the use of evolutionary algorithms, requires the transformation of the domain-specific knowledge into a formal design representation. This is a difficult and still not completely understood process. Its critical part is the choice of a type of design representation. The paper addresses this important issue by presenting and discussing results of a large number of design experiments in which parameterized and generative representations were used. Particularly, their computational and design related advantages and disadvantages were investigated and compared. Evolutionary design experiments reported in this paper considered two classes of structural design problems, including the design of a wind bracing system and the design of an entire structural system in a tall building. Parameterized and generative representations of the structural systems were introduced and their basic features discussed. The generative representations investigated in the paper were inspired by the processes of morphogenesis occurring in nature. Specifically, one-dimensional cellular automata were used to develop, or "grow," structural designs from the corresponding "design embryos." The conducted research led to three major conclusions. First, generative representations based on cellular automata proved to scale well with the size of the considered design problems. Second, generative representations outperformed parameterized representations in minimizing weight of the structural systems in our problem domain by generating better designs and finding them faster. Finally, extensive experimental studies showed significant differences in optimal settings for evolutionary design experiments for the two representation types. The rate of mutation operator, the size of the parent population, and the type of the evolutionary algorithm were identified as the evolutionary parameters having the largest impact on the performance of evolutionary design processes in our problem domain.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2005)
Evolutionary design of steel structures in tall buildings. Journal of Computing in Civil Engineering, 19(3) : 223-238.
Keywords: evolutionary computation and optimization and evolutionary design and tall buildings and structural design
Abstract:
This paper presents results of a study on evolutionary computation in the design of the steel structural systems of tall buildings. It describes results of extensive research on both short-term (up to a few hundred generations) and long-term evolutionary design processes (at least a few thousand generations). The experiments were conducted with Inventor 2001, an evolutionary design support tool developed at George Mason University, for generating conceptual and detailed designs of steel structural systems in tall buildings. First, the paper discusses conceptual design of steel structural systems in tall buildings and briefly introduces Inventor 2001 as well as its design representation and evolutionary computation characteristics. Next, it provides the results obtained from systematic parametric design experiments conducted with Inventor 2001. The objective of these experiments was to qualitatively and quantitatively investigate evolution of steel structural systems of tall buildings during a multistage evolutionary design process as well as the influence of various evolutionary computation parameters. Mutation and crossover rates, population size, the length of the evolutionary processes, and the importance of symmetry requirement have been analyzed and results produced. Emergence of structural shaping patterns has been also studied and several interesting patterns found in the evolutionary design process. Finally, research conclusions are presented as well as recommendations for further research and development of evolutionary design support tools.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2005)
Evolutionary computation and structural design: A survey of the state of the art. Computers & Structures, 83(23-24) : 1943-1978.
[PDF
Keywords: evolutionary computation and structural design and review and engineering design and creative design and inventive design and design representations and constraint-handling methods and multiobjective optimization and coevolutionary design
Abstract:
Evolutionary computation is emerging as a new engineering computational paradigm, which may significantly change the present structural design practice. For this reason, an extensive study of evolutionary computation in the context of structural design has been conducted in the Information Technology and Engineering School at George Mason University and its results are reported here. First, a general introduction to evolutionary computation is presented and recent developments in this field are briefly described. Next, the field of evolutionary design is introduced and its relevance to structural design is explained. Further, the issue of creativity/novelty is discussed and possible ways of achieving it during a structural design process are suggested. Current research progress in building engineering systems' representations, one of the key issues in evolutionary design, is subsequently discussed. Next, recent developments in constraint-handling methods in evolutionary optimization are reported. Further, the rapidly growing field of evolutionary multiobjective optimization is presented and briefly described. An emerging subfield of coevolutionary design is subsequently introduced and its current advancements reported. Next, a comprehensive review of the applications of evolutionary computation in structural design is provided and chronologically classified. Finally, a summary of the current research status and a discussion on the most promising paths of future research are also presented.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2005)
Generative design in structural engineering. In Proceedings of the 2005 ASCE International Conference on Computing in Civil Engineering.   Lucio Soibelman and Feniosky Pena-Mora editor(s).  American Society of Civil Engineers Press.
[PDF
Keywords: generative representations and morphogenic evolutionary design and evolutionary computation and structural design and cellular automata and morphogenesis
Abstract:
This paper proposes a new approach to representing structural system inspired by various models of complex systems. Several types of generative representations of steel structural systems are provided and empirically investigated. These representations utilize various kinds of cellular automata to generate design concepts of steel structures in tall buildings. In the paper, a brief overview of the state-of-the-art in cellular automata and generative design is presented. Next, several types of generative representations of steel structural systems in tall buildings are described. The paper also reports the results of several design experiments. They have shown that generative representations produce novel structural shaping patterns which are qualitatively different than the patterns obtained using traditionally used parameterized representations. They also significantly improve the performance of evolutionary algorithms optimizing the structural systems. Finally, research conclusions are presented and most promising paths of future research are discussed.

Sanjeev Kumar (2005)
A Developmental Genetics-Inspired Approach to Robot Control. In Proceedings of the Second Workshop On Self-Organization in Representations For Evolutionary Algorithms: Building complexity from simplicity, GECCO-2005.  ACM Press.
[PDF
Abstract:
The need to build modular, scalable, and complex technology capable of adaptation, self-assembly, and self-repair has fuelled renewed interest in using approaches inspired by developmental biology. To meet this need, a new field, called Computational Development (CD), has emerged. Its focus is on adapting processes and mechanisms from developmental biology so as to help us build scalable, complex technology. Due to the embryonic nature of the eld, however, research investigating the potential of such approaches for different problem domains is crucial to its success. In this paper, the plausibility of applying a developmental biology-inspired approach to the demanding problem domain of reactive robot control is explored. Using developmental genetics as a source of inspiration, a model of genetic regulatory networks is used in conjunction with a spatially distributed evolutionary algorithm to evolve real-time robot controllers for tasks such as general purpose obstacle avoidance.

Sean Luke (2005)
Evolutionary Computation and the C-value Paradox. In Proceedings of Genetic and Evolutionary Computation Conference -- GECCO-2005.  Pages 91–97.  ACM Press.
[PDF
Abstract:
The C-value Paradox is the name given in biology to the wide variance in and often very large amount of DNA in eukaryotic genomes and the poor correlation between DNA length and perceived organism complexity. Several hypotheses exist which purport to explain the Paradox. Surprisingly there is a related phenomenon in evolutionary computation, known as code bloat, for which a different set of hypotheses has arisen. This paper describes a new hypothesis for the Cvalue Paradox derived from models of code bloat. The new explanation is that there is a selective bias in preference of genetic events which increase DNA material over those which decrease it. The paper suggests one possible concrete mechanism by which this may occur: deleting strands of DNA is more likely to damage genomic material than migrating or copying strands. The paper also discusses other hypotheses in biology and in evolutionary computation, and provides a simulation example as a proof of concept.

Sean Luke, Keith Sullivan, Liviu Panait, and Gabriel Balan (2005)
Tunably Decentralized Algorithms for Cooperative Target Observation. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2005).
[PDF
Abstract:
Multi-agent problem domains may require distributed algorithms for a variety of reasons: local sensors, limitations of communication, and availability of distributed computational resources. In the absence o f these constraints, centralized algorithms are often more efficient, simply because they are able to take advantage of more information. We introduce a variant of the cooperative target observation domain w which is free of such constraints. We propose two algorithms, inspired by K-means clustering and hill-climbing respectively, which are scalable in degree of decentralization. Neither algorithm consistently o outperforms the other across over all problem domain settings. Surprisingly, we find that hill-climbing is sensitive to degree of decentralization, while K-means is not. We also experiment with a combination n of the two algorithms which draws strength from each.

Liviu Panait and Sean Luke (2005)
Cooperative Multi-Agent Learning: The State of the Art. Autonomous Agents and Multi-Agent Systems, 11(3) : 387–434.   (c) Springer
[PDF
Abstract:
Multi-agent problem domains may require distributed algorithms for a variety of reasons: local sensors, limitations of communication, and availability of distributed computational resources. In the absence of these constraints, centralized algorithms are often more efficient, simply because they are able to take advantage of more information. We introduce a variant of the cooperative target observation domain which is free of such constraints. We propose two algorithms, inspired by K-means clustering and hill-climbing respectively, which are scalable in degree of decentralization. Neither algorithm consistently outperforms the other across over all problem domain settings. Surprisingly, we find that hill-climbing is sensitive to degree of decentralization, while K-means is not. We also experiment with a combination of the two algorithms which draws strength from each.

Elena Popovici (2005)
Evolving Families of Designs Using L-Systems.
Department of Computer Science, George Mason University, technical report GMU-CS-TR-2005-8.
Abstract:
Evolutionary computation has proven its utility in automating the process of engineering design. However, little attention has been paid to the scalability of generated designs, which is an important issue. This paper addresses this issue and proves the viability of evolving families of designs using parameterized L-Systems as a representation. The rest of the paper is organized as follows: first, an introduction as to why scalability is important and difficult; second, a review of existing work on evolving L-Systems; the third section contains a description of the application domain used for this feasibility study, details on the L-Systems and the EA used; section four presents experiments conducted and their results; the paper ends with a discussion, drawing conclusions and setting goals for future work.

Elena Popovici and Kenneth De Jong (2005)
Relationships Between Internal and External Metrics in Co-Evolution. In Proceedings of Congress on Evolutionary Computation.
Abstract:
Co-evolutionary algorithms (CEAs) have been applied to optimization and machine learning problems with often mediocre results. One of the causes for the unfulfilled expectations is the discrepancy between the external problem solving goal and the internal mechanisms of the algorithm. In this paper, we investigate in a principled way the relationships between the internal subjective metric used as fitness by a co-evolutionary algorithm and the external objective metric measuring the algorithm's progress towards the envisioned goal. We point out the complexity of these relationships and explain their causes.

Elena Popovici and Kenneth De Jong (2005)
A Dynamical Systems Analysis of Collaboration Methods in Cooperative Co-Evolution. In Coevolutionary and Coadaptive Systems Workshop.
Abstract:
Cooperative co-evolution is often used to solve difficult optimization problems by means of problem decomposition. In order to do so efficiently, one must have a good understanding of co-evolution's dynamical behavior. To build such understanding, we have constructed a methodology for analyzing co-evolution based on dynamical systems theory. In this paper we show how it can be applied to investigate the effects that collaboration methods have on performance and to identify a problem property relevant in this respect.

Elena Popovici and Kenneth De Jong (2005)
Understanding Cooperative Co-evolutionary Dynamics via Simple Fitness Landscapes. In Proceedings of Genetic and Evolutionary Computation Conference -- GECCO-2005.  Pages 507–514.  ACM Press.
[PDF
Abstract:
Cooperative co-evolution is often used to solve difficult optimization problems by means of problem decomposition. Its performance for such tasks can vary widely from good to disappointing. One of the reasons for this is that attempts to improve co-evolutionary performance using traditional EC analysis techniques often fail to provide the necessary insights into the dynamics of co-evolutionary systems,a key factor affecting performance. In this paper we use two simple fitness landscapes to illustrate the importance of taking a dynamical systems approach to analyzing co-evolutionary algorithms in order to understand them better and to improve their problem solving performance.

Mitchell A. Potter, R. Paul Wiegand, H. Joseph Blumenthal, and Donald A. Sofge (2005)
Effects of Experience Bias When Seeding With Prior Results. In Proceedings of the 2005 Congress on Evolutionary Computation (CEC'2005).  Pages 2730–2737.  IEEE Press.
[PDF
Keywords: evolutionary computation and experience bias and multiagent systems and transfer learning
Abstract:
Seeding the population of an evolutionary algorithm with solutions from previous runs has proved to be useful when learning control strategies for agents operating in a complex, changing environment. It has generally been assumed that initializing a learning algorithm with previously learned solutions will be helpful if the new problem is similar to the old. We will show that this assumption sometimes does not hold for many reasonable similarity metrics. Using a more traditional machine learning perspective, we explain why seeding is sometimes not helpful by looking at the learning experience bias produced by the previously evolved solutions.

Alexei V. Samsonovich and Kenneth A. De Jong (2005)
Designing a Self-Aware Neuromorphic Hybrid. In Workshop on Modular Construction of Human-Like Intelligence.
Abstract:
A top-level integration of symbolic and connectionist components of a cognitive architecture can be achieved through the blending of innovative concepts used in both components. i) On the connectionist side the key innovative elements are neuromorphic cognitive maps that provide for associative indexing and organization of symbolic memories and path-finding in modeled cognitive spaces. On the symbolic side the key innovative elements are: ii) a unique, central notion of ``self'', and iii) a formal representation system based on the general notion of a ``schema''. In this work we describe a theoretical framework allowing us to design an implementable cognitive architecture of this sort.

Alexei V. Samsonovich and Kenneth A. De Jong (2005)
A General-Purpose Computational Model of the Conscious Mind. In Proceedings of the Sixth International Conference on Cognitive Modeling.   K. Forbus, D. Gentner, and T. Reigier editor(s).  Pages 382 – 383.
Abstract:
Building artificial cognitive systems that possess a concept of ``self'', as well as cognitive and behavioral abilities of a conscious being is a difficult task, but one with tremendous practical significance and potential. In this work we outline general principles of a new approach to this task and illustrate them with detailed computational analysis based on a simple paradigm. Our approach to this task is grounded on three conceptual components -- three key ideas (schemas, charts and the self) that underlie three levels of organization of our cognitive system. They are explained below.

Alexei V. Samsonovich and Kenneth A. De Jong (2005)
Pricing the \"Free Lunch\" of Meta-Evolution. In Proceedings of Genetic and Evolutionary Computation Conference -- GECCO-2005.  Pages 1355–1362.  ACM Press.
[PDF
Abstract:
A number of recent studies introduced meta-evolutionary strategies and successfully used them for solving problems in genetic programming. While individual results indicate possibilities of successes and failures (e.g., Kantschik, Dittrich et al., 1998, 1999), the emerging global picture suggests that the approach may have universal, domain-independent advantages over traditional methods. Trying to develop a general theoretical understanding of this concept, we use Price's theorem to define fitness at a meta-level and show with two simple case studies (two-dimensional optimization and the Eight puzzle) that the ideology based on Price's theorem can work at a meta-level in a similar manner for very different problems. Specifically, Pricean definition of fitness for reproductive operators appears to be practically useful and essential for performance and stability of a certain class of meta-evolutionary algorithms.

Zbigniew Skolicki (2005)
An Analysis of Island Models in Evolutionary Computation. In Proceedings of Graduate Student Workshop, Genetic and Evolutionary Computation Conference -- GECCO-2005.  ACM Press.
[PDF
Abstract:
A need for solving more and more complex problems drives the Evolutionary Computation community towards advanced models of Evolutionary Algorithms. One such model is the island model which, although the subject of a variety of studies, still needs additional fundamental research. In my Ph.D. thesis I am aiming at studying the behavior of island models with regard to the amount of cooperation between islands, the level of heterogeneity and the difficulty of the problem being solved. This paper presents the main ideas and gathers preliminary results.

Zbigniew Skolicki, Tomasz Arciszewski, M. Houck, and Kenneth De Jong (2005)
Emerging Security Patterns: Co-Evolution of Terrorist and Security Scenarios. In Proceedings of 8th International Conference on the Applications of AI to Civil, Structural, and Environmental Engineering.   B. H. V. Topping editor(s).
Abstract:
Identification of vulnerabilities of water distribution systems and identification of appropriate counter-measures are important components of homeland security. These are difficult and time consuming tasks. This paper provides a new approach to resolve these problems in complex infrastructure systems. It is based on the use of co-evolutionary computation for the generation of both terrorist and security scenarios. In the paper, the basic concepts of co-evolutionary computation are briefly explained. Next, the concept of co-evolutionary generation of terrorist and security scenarios is introduced in the context of a hypothetical water distribution system for a small town. A co-evolutionary experimental tool, SecurityMax/Water2005, developed at George Mason University , is also briefly described. It has been used for a number of experiments, reported in the paper. The results of these experiments reveal a number of emerging security patterns regarding the locations of ``dangerous'' fire hydrants, unique for a given water distribution system. Finally, the paper contains conclusions and recommendations for further research.

Zbigniew Skolicki and Kenneth De Jong (2005)
The Influence of Migration Sizes and Intervals on Island Models. In Proceedings of Genetic and Evolutionary Computation Conference -- GECCO-2005.  Pages 1295–1302.  ACM Press.
[PDF
Abstract:
A need for solving more and more complex problems drives the Evolutionary Computation community towards advanced models of Evolutionary Algorithms. One such model is the island model which, although the subject of a variety of studies, still needs additional fundamental research. In this paper we have experimentally studied the influence of various migrations sizes and intervals on island models using a set of special functions. One of the surprising observations from these experiments is that the migration interval seems to be a dominating factor, with migration size generally playing a minor role with regard to the best solution found. Additional experiments measuring genetic diversity show that too frequent migrations cause islands to dominate others and lose global diversity before they are able to exchange solutions to produce better results. Also, we observe that even small migrations already make a significant impact on the behavior of an island model and therefore the effects are comparable to those of bigger migrations. On the other hand rare migrations cause a degraded performance due to the slow convergence. Collectively, these observations provide useful guidance for island model applications.

Zbigniew Skolicki, M. Houck, and Tomasz Arciszewski (2005)
Improving the Security of Water Distribution Systems Using a Co-Evolutionary Approach. In Proceedings of the Working Together: Conference on Public/Private R&D Partnerships in Homeland Security.
Abstract:
The objective of the paper is to introduce the concept of a co-evolutionary approach to the security of water distribution systems. It briefly describes the co-evolution in the context of security and discusses the co-evolution of terrorist and security scenarios. Next, the paper explains how the general principia of co-evolution can be related to a water distribution system and utilized for building a computer tool for the protection of such a system. An example of a specific computer tool, developed at George Mason University, is provided. In the tool, a co-evolutionary component for the generation of terrorist and security scenarios is integrated with a model of a hypothetical water distribution network in a small city. EPANet is used to simulate hydraulic and contaminant transport phenomena. Also, the selected research results produced using the developed tool are provided. Finally, initial research conclusions are discussed and directions of future research proposed.

Zbigniew Skolicki, M. Venigalla, and Tomasz Arciszewski (2005)
Security of Transportation Systems: An Evolutionary Approach. In Proceedings of the Working Together: Conference on Public/Private R&D Partnerships in Homeland Security.
Abstract:
The objective of the paper is to introduce the concept of an evolutionary approach to the security of transportation systems. It briefly describes the evolution in the context of security and discusses the subsequent evolution of terrorist and security scenarios. Next, the paper explains how the general principia of evolution can be related to a transportation system and utilized for building a computer tool for the protection of such a system. The development of a prototype computer tool at George Mason University is presented. The tool combines a component for the generation of terrorist and security scenarios with a model of a hypothetical transportation system variables developed using planning and simulation tools. Also, selected research results produced using the tool are provided. Finally, the initial research conclusions are discussed and directions of future research proposed.

Z. Skolicki, M. M. Wadda, M. H. Houck, and T. Arciszewski (2005)
Water Supply Threat Reduction Using Evolutionary Approaches. In Proceedings of World Water Congress.  Pages 61.
Abstract:
The potential threats to US water supply systems have changed fundamentally in the past four years. Prior to 2001, the major threats were natural causes, accidents, and some malicious behavior by a small group of individuals. Against these threats, water supply agencies have done a truly remarkable job of ensuring a safe, dependable supply. However, threats posed by an organized group of actors may represent a new and different challenge to the security of water supplies. A tool to assist in identifying possible attacks and simultaneously providing remedies to counter these attacks has been developed. The tool uses evolutionary computation as the optimization method, and EPANET as the system simulator. Preliminary examples of its use to identify optimal attacks against a realistic but hypothetical pipe network and corresponding counter measures are presented.

2004 Publications

Gabriel Catalin Balan and Sean Luke (2004)
A Demonstration of Neural Programming Applied to Non-Markovian Problems. In Proceedings of Genetic and Evolutionary Computation Conference.  Pages 422 – 433.
Abstract:
Genetic programming may be seen as a recent incarnation of a long-held goal in evolutionary computation: to develop actual computational devices through evolutionary search. Genetic programming is particularly attractive because of the generality of its application, but it has rarely been used in environments requiring iteration, recursion, or internal state. In this paper we investigate a version of genetic programming developed originally by Astro Teller called neural programming. Neural programming has a cyclic graph representation which lends itself naturally to implicit internal state and recurrence, but previously has been used primarily for problems which do not need these features. In this paper we show a successful application of neural programming to various partially observable Markov decision processes, originally developed for the learning classifier system community, and which require the use of internal state and iteration.

Jeffrey K. Bassett, Mitchell A. Potter, and Kenneth A. De Jong (2004)
Looking Under the EA Hood with Price's Equation. In Genetic and Evolutionary Computation Conference -- GECCO-2004.  (c) Springer.
[PDF
Abstract:
In this paper we show how tools based on extensions of Price's equation allow us to look inside production-level EAs to see how selection, representation, and reproductive operators interact with each other, and how these interactions affect EA performance. With such tools it is possible to understand at a deeper level how existing EAs work as well as provide support for making better design decisions involving new EC applications.

Guido Cervone, Liviu Panait, Ramesh Singh, and Sean Luke (2004)
An Application of Evolutionary Algorithms to Study the Extent of SLHF Anomaly Associated with Coastal Earthquakes. In Late Breaking Papers of the Genetic and Evolutionary Computation Conference -- GECCO-2004.  (c) Springer.
Abstract:
Multi sensor remote sensing provides real time high resolution data that can be used to study anomalous changes on land, in the ocean, and in the atmosphere associated with an impending earthquake. Anomalous behavior in Surface Latent Heat Flux (SLHF) prior to large coastal earthquakes has been recently found. However, an SLHF time series usually contains several sharp peaks that may be associated either with earthquakes or with atmospheric perturbations. In this paper we have used evolutionary algorithms to perform a search in a large space bounded by longitude, latitude and time, to distinguish between signals associated with earthquakes and those associated with atmospheric phenomena. The algorithm finds paths which delimit the extent of the detected anomalies by optimizing an objective function that takes into consideration several aspects, such as spatial and time continuity, the magnitude of the anomalies, and the distance to the continental boundary. This search strategy is crucial for the development of a fully automated early warning system for providing information about impending earthquakes in a seismically active coastal region. Experiments have been performed over a 2000 km2 area comprising a part of the continental boundary between the African and Eurasian plate, roughly corresponding to Italy and Greece, one of the most seismically active regions. Using a 365-days-long time series, we identified three signals associated with seismic events. Additionally, it was possible to establish that the extent of the signal does not propagate further than 600 km from the epicenter of the earthquake.

Claudio Cioffi-Revilla, Sean Paus, Sean Luke, James Olds, and Jason Thomas (2004)
Mnemonic Structure and Sociality: A Computational Agent-Based Simulation Model. In Proceedings of the Conference on Collective Intentionality IV.
[PDF
Abstract:
How does group memory affect sociality? Most computational multi-agent social simulation models are designed with agents lacking explicit internal information-processing structure in terms of basic cognitive elements. In particular, memory is usually not explicitly modeled. We present initial results from a new prototype called ``Wetlands'', designed to investigate the effect of group memory structures and interaction situations on emergent patterns of sociality or collective intentionality. Specifically, we report on initial computational experiments conducted on culturally-differentiated agents endowed with finite and degradable memory that simulate bounded mnemonic function and forgetfulness. Our main initial findings are that memory capacity and engram retention both promote sociality among groups, probably as nonlinear (inverse) functions. Wetlands 1.1 is implemented in the new MASON 3 (Multi- Agent Simulator of Networks and Neighborhoods) computational environment developed at George Mason University.

Adrian Grajdeanu and Kenneth A. De Jong (2004)
Improving the Locality Properties of Binary Representations. In Genetic and Evolutionary Computation Conference.   K. Deb et al. editor(s).  Pages 1186–1196.  Springer-Verlag.
[PDF
Abstract:
Choosing representations and operators that preserve locality between genotype and phenotype space is an important goal in EA design. In the GA literature there has been considerable discussion of this issue with respect to the choice between standard binary encoding and Gray codes. In this paper we argue that an important and unappreciated aspect of such discussions is the degree to which locality preservation is isotropic in phenotype space (i.e., independent of location in phenospace). We show that using a traditional bit-flip mutation operator with either of these two representations results in rather weak isotropic locality. These insights lead to the design of a new binary mutation operator that increases isotropic locality. The results from an initial set of experiments supports the hypothesis that this improvement in isotropic locality leads to improvements in GA performance as well.

Thomas Jansen and R. Paul Wiegand (2004)
Bridging the Gap Between Theory and Practice. In Parallel Problem Solving from Nature -- PPSN-2004.  Pages 61–71.  (c) Springer.
Abstract:
While the gap between theory and practice is slowly closing, the evolutionary computation community needs to concentrate more heavily on the middle ground. This paper defends the position that contemporary analytical tools facilitate such a concentration. Empirical research can be improved by considering modern analytical techniques in experimental design. In addition, formal analytical extensions of empirical works are possible. We justify our position by way of a constructive example: we consider a recent empirically-based research paper and extend it using modern techniques of asymptotic analysis of run time performance of the algorithms and problems investigated in that paper. The result is a more general understanding of the performance of these algorithms for any size of input, as well as a better understanding of the underlying reasons for some of the previous results. Moreover, our example points out how important it is that empirical researchers motivate their parameter choices more clearly. We believe that providing theorists with empirical studies that are well-suited for formal analysis will help bridge the gap between theory and practice, benefitting the empiricist, the theorist, and the community at large.

Thomas Jansen and R. Paul Wiegand (2004)
The Cooperative Coevolutionary (1+1) EA. Evolutionary Computation, 12(4) : 405–434.   MIT Press
Keywords: cooperative coevolution, run time analysis, separability, global optimization
Abstract:
Coevolutionary algorithms are variants of traditional evolutionary algorithms and are often considered more suitable for certain kinds of complex tasks than non-coevolutionary methods. One example is a general cooperative coevolutionary framework for function optimization. This paper presents a thorough and rigorous introductory analysis of the optimization potential of cooperative coevolution. Using the cooperative coevolutionary framework as a starting point, the CC (1+1) EA is defined and investigated from the perspective of the expected optimization time. The research concentrates on separability, a key property of objective functions. We show that separability alone is not sufficient to yield any advantage of the CC (1+1) EA over its traditional, non-coevolutionary counterpart. Such an advantage is demonstrated to have its basis in the increased explorative possibilities of the cooperative coevolutionary algorithm. For inseparable functions, the cooperative coevolutionary set-up can be harmful. We prove that for some objective functions the CC (1+1) EA fails to locate a global optimum with overwhelming probability, even in infinite time; however, inseparability alone is not sufficient for an objective function to cause difficulties. It is demonstrated that the CC (1+1) EA may perform equal to its traditional counterpart, and may even outperform it on certain inseparable functions.

Rafal Kicinger (2004)
Emergent Engineering Design: Design creativity and optimality inspired by nature.
Ph.D. Thesis, George Mason University, Fairfax, VA.
[PDF]  [Downloading instructions
Keywords: engineering design and morphogenic evolutionary design and design methods and complex systems and evolutionary computation and evolutionary design and cellular automata and optimization and creative design
Abstract:
For a long time, engineering design research has been focused on the development of various design theories, methodologies, methods, tools, and procedures. The design methods have been subsequently used by engineers to more efficiently design artifacts. However, as the artifacts have grown in complexity, the need for new methods has become obvious. Also, in a nowadays world, increased competition and globalization require organizations to reexamine traditional product development strategies. Traditional methods focused exclusively on the numerical optimality of produced artifacts, or their manufacturing processes, are no longer adequate. Creativity and innovation of designed artifacts provide organizations not only with a competitive advantage but are, in fact, a matter of their survival. This dissertation addresses this problem by posing and answering the question: "How can one construct an effective method for designing engineering systems that would support development of novel/creative designs and their efficient optimization?" It proposes a new and conceptually coherent design method, called Emergent Engineering Design. The proposed design method is inspired by the fundamental processes occurring in nature, which has arguably created the most fascinating designs known to humankind. All major phases of Emergent Engineering Design are represented by complex systems, including cellular automata and evolutionary algorithms, which have been successfully used to model the processes governing the complex behavior occurring in nature. In order to facilitate the development of the proposed design method, Emergent Engineering Design was implemented in a computer system called Emergent Designer. It is an integrated research and design support tool which applies models of complex systems to represent engineering systems and analyze design processes. Emergent Designer was used to conduct the empirical validation of the proposed design method for two classes of conceptual design problems in structural engineering. The extensive design experiments reported in this dissertation have shown that Emergent Engineering Design not only generates novel design concepts exhibiting remarkable structural shaping patterns but it also efficiently optimizes them.

Rafal Kicinger and Tomasz Arciszewski (2004)
Multiobjective evolutionary design of steel structures in tall buildings. In Proceedings of the AIAA 1st Intelligent Systems Technical Conference, Chicago, IL, September 20-23, 2004.  Pages AIAA 2004-6438.  American Institute of Aeronautics and Astronautics Press.
[PDF
Keywords: evolutionary computation and multiobjective optimization and evolutionary design and tall buildings
Abstract:
This paper presents initial results of a study on the application of evolutionary multi-objective optimization methods in the design of the steel structural systems of tall buildings. In the paper, a brief overview of the state-of-the-art in evolutionary multi-objective optimization in structural engineering is provided. Next, conceptual design of steel structural systems in tall buildings is overviewed and the representations of steel structural systems used in the paper are discussed. Furthermore, Emergent Designer, a unique evolutionary design tool developed at George Mason University, is briefly described. It is an integrated research and design support tool which applies models of complex adaptive systems to represent engineering systems and to analyze design processes and their results. The paper also presents the results of several multi-objective structural design experiments conducted with Emergent Designer in which steel structural systems in tall buildings were optimized with respect to their total weight and maximum deflection (two-objective minimization problem). The goal of these experiments was to determine feasibility of evolutionary multi-objective optimization of steel structural systems of tall buildings as well as to qualitatively and quantitatively compare the results with the previous findings obtained with single-objective evolutionary optimization methods. Finally, initial research conclusions are presented as well as promising research directions.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth De Jong (2004)
Emergent Designer: Generative Design in Structural Engineering. In Proceedings of the Workshop on the Implementation Issues in Generative Design Systems at the First International Conference on Design Computing and Cognition.   L. G. Caldis and J. P. Duarte editor(s).  Pages 93 – 112.  MIT Press.
Abstract:
The paper introduces an integrated research and design support tool, called Emergent Designer, developed at George Mason University. It is a tool that implements models of various complex systems, including cellular automata and evolutionary algorithms, to represent engineering systems and design processes. The system is intended for conducting design experiments in the area of structural design and for the analysis of their results. It implements state-of-the-art representations supporting generation of novel design concepts and efficient mechanisms for their subsequent optimization at the topology and sizing level. It also implements advanced methods, models, and tools from statistics and from the linear as well as nonlinear time series analysis to conduct the analysis of the design processes. Thus, it is a versatile tool that can be used both as a state-of-the-art design support tool and as an advanced research tool equipped with the methods and tools for the analysis of the design processes and of the obtained experimental results.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2004)
Emergent Designer: An integrated research and design support tool based on models of complex systems. In Proceedings of the Workshop on the Implementation Issues in Generative Design Systems at the First International Conference on Design Computing and Cognition (DCC'04), Massachusetts Institute of Technology, Cambridge, MA, July 17-21, 2004.   Luisa G. Caldas and Jose P. Duarte editor(s).  Pages 93-112.
[PDF
Keywords: evolutionary computation and generative representations and morphogenic evolutionary design and cellular automata and design support tools and evolutionary design
Abstract:
The paper introduces an integrated research and design support tool, called Emergent Designer, developed at George Mason University. It is a tool that implements models of various complex systems, including cellular automata and evolutionary algorithms, to represent engineering systems and design processes. The system is intended for conducting design experiments in the area of structural design and for the analysis of their results. It implements state-of-the-art representations supporting generation of novel design concepts and efficient mechanisms for their subsequent optimization at the topology and sizing level. It also implements advanced methods, models, and tools from statistics and from the linear as well as nonlinear time series analysis to conduct the analysis of the design processes. Thus, it is a versatile tool that can be used both as a state-of-the-art design support tool and as an advanced research tool equipped with the methods and tools for the analysis of the design processes and of the obtained experimental results.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2004)
Morphogenesis and structural design: cellular automata representations of steel structures in tall buildings. In Proceedings of the Congress on Evolutionary Computation (CEC'2004), Portland, Oregon, June 19-23, 2004.  Pages 411-418.  IEEE Press.
[PDF
Keywords: evolutionary computation and morphogenesis and morphogenic evolutionary design and evolutionary design and cellular automata and tall buildings and structural design
Abstract:
This paper provides the initial results of a study on the applications of generative cellular automata-based representations in evolutionary structural design. First, recent developments in evolutionary design representations and an overview of cellular automata are presented. Next, a complex problem of topological design of steel structural systems in tall buildings is briefly described. Further, morphogenic evolutionary design is introduced and exemplified by cellular automata representations. The paper also reports the initial results of several structural design experiments whose objective was to determine feasibility of the proposed approach. Finally, initial research conclusions are provided.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2004)
Distributed evolutionary design: island-model based optimization of steel skeleton structures in tall buildings. In Proceedings of the Xth International Conference on Computing in Civil and Building Engineering (ICCCBE-X), Weimar, Germany, June 2-4, 2004.   Karl Beucke, Berthold Firmenich, Dirk Donath, Renate Fruchter, and Kim Roddis editor(s).  Pages 190.  VDG.
[PDF
Keywords: evolutionary computation and evolutionary design and distributed evolutionary algorithm and island-model and tall buildings
Abstract:
This paper presents results of a study on distributed, or parallel, evolutionary computation in the topological design of steel structural systems in tall buildings. It describes results of extensive experimental research on various parallel evolutionary architectures applied to a complex structural design problem. The experiments were conducted using Inventor 2003, a network-based evolutionary design support tool developed at George Mason University. First, a general introduction to evolutionary computation is provided with an emphasis on recent developments in parallel evolutionary architectures. Next, a discussion of conceptual design of steel structural systems in tall buildings is presented. Further, Inventor 2003 is briefly introduced as well as its design representation and evolutionary computation characteristics. Next, the results obtained from systematic design experiments conducted with Inventor 2003 are discussed. The objective of these experiments was to qualitatively and quantitatively investigate evolution of steel structural systems in tall buildings during a distributed evolutionary design process as well as to compare efficiency and effectiveness of various parallel evolutionary architectures with the traditional evolutionary design approaches. Two connectivity topologies (ring topology and fully-connected topology) have been investigated for four populations of structural designs evolving in parallel and using various migration strategies. Also, results of the initial sensitivity studies are reported in which two ways of initializing distributed evolutionary design processes were investigated, using either arbitrarily selected designs as initial parents or randomly generated ones. Finally, initial research conclusions are presented.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2004)
Morphogenic evolutionary design: cellular automata representations in topological structural design. In Adaptive Computing in Design and Manufacture VI.   Ian C. Parmee editor(s).  Pages 25-38.  Springer-Verlag.
[PDF
Keywords: cellular automata and morphogenesis and morphogenic evolutionary design and evolutionary computation and evolutionary design and tall buildings and structural design
Abstract:
This paper provides the initial results of a study on the applications of cellular automata representations in evolutionary design of topologies of steel structural systems in tall buildings. In the paper, a brief overview of the state of the art in cellular automata and evolutionary design representations is presented. Next, morphogenic evolutionary design is introduced and illustrated by several types of cellular automata representations. Further, Emergent Designer, a unique evolutionary design tool developed at George Mason University, is briefly described. It is an integrated research and design support tool which applies models of complex adaptive systems to represent engineering systems and analyze design processes. The paper also reports the initial results of several structural design experiments conducted with Emergent Designer. The objective of the experiments was to determine feasibility of various types of cellular automata representations in topological structural optimization. Finally, initial research conclusions and recommendations for the further research are provided.

Sean Luke, Claudio Cioffi-Revilla, Liviu Panait, and Keith Sullivan (2004)
MASON: A New Multi-Agent Simulation Toolkit. In Proceedings of the 2004 SwarmFest Workshop.
[PDF
Abstract:
We introduce MASON, a fast, easily extendable, discrete event multi-agent simulation toolkit in Java. MASON was designed to serve as the basis for a wide range of multiagent simulation tasks ranging from swarm robotics to machine learning to social complexity environments. MASON carefully delineates between model and visualization, allowing models to be dynamically detached from or attached to visualizers, and to change platforms mid-run. We describe the MASON system, its motivation, and its basic architectural design. We then discuss five applications of MASON we have built over the past year to suggest its breadth of utility.

Sean Luke and Liviu Panait (2004)
Alternative Bloat Control Methods. In Genetic and Evolutionary Computation Conference -- GECCO-2004.  (c) Springer.
Abstract:
Bloat control is an important aspect of evolutionary computation methods, such as genetic programming, which must deal with genomes of arbitrary size. We introduce three new methods for bloat control: Biased Multi-Objective Parsimony Pressure (BMOPP), the Waiting Room, and Death by Size. These methods are unusual approaches to bloat control, and are not only useful in various circumstances, but two of them suggest novel approaches to attack the problem. BMOPP is a more traditional parsimony-pressure style bloat control method, while the other two methods do not consider parsimony as part of the selection process at all, but instead penalize for parsimony at other stages in the evolutionary process. We find parameter settings for BMOPP and the Waiting Room which are effective across all tested problem domains. Death by Size does not appear to have this consistency, but we find it a useful tool as it has particular applicability to steady-state evolution.

Sean Luke, Keith Sullivan, Gabriel Catalin Balan, and Liviu Panait (2004)
Tunably Decentralized Algorithms for Cooperative Target Observation.
Department of Computer Science, George Mason University, technical report GMU-CS-TR-2004-1.
[PDF
Abstract:
Multi-agent problem domains may require distributed algorithms for a variety of reasons: local sensors, limitations of communication, and availability of distributed computational resources. In the absence of these constraints, centralized algorithms are often more efficient, simply because they are able to take advantage of more information. We introduce a variant of the cooperative target observation domain which is free of such constraints. We propose two algorithms, inspired by Kmeans clustering and hill-climbing respectively, which are scalable in degree of decentralization. Neither algorithm consistently outperforms the other across over all problem domain settings. Surprisingly, we find that hillclimbing is sensitive to degree of decentralization, while K-means is not. We also experiment with a combination of the two algorithms which draws strength from each.

Emeka Oguejiofor, Rafal Kicinger, Elena Popovici, Tomasz Arciszewski, and Kenneth A. De Jong (2004)
Intelligent tutoring systems: an ontology-based approach. International Journal of IT in Architecture, Engineering and Construction, 2(2) : 115-128.
[PDF
Keywords: ontology and intelligent agents and tutoring systems and engineering design and knowledge-based systems
Abstract:
A novel methodology for building tutoring system is proposed. It includes the integration of state of the art computer science methods and tools and the use of an ontology for the core knowledge representation. First, the paper presents the ongoing Information Technology revolution in engineering and the related paradigm changes in education. Next, an overview of the concept of an ontology and its various definitions are provided, along with available ontology development tools. In the following section, an architecture of an ontology-based tutoring system is proposed. As a proof of concept, the proposed architecture has been used in GMU Educator, an intelligent tutoring system developed at George Mason University in the School of Information Technology and Engineering. A detailed description of the GMU Educator is then presented with various examples. Finally, conclusions and plans for further research are provided in the last section of the paper.

Liviu Panait and Sean Luke (2004)
Learning Ant Foraging Behaviors. In Proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9).
[PDF
Abstract:
Insects are good at cooperatively solving many complex tasks. For example, foraging for food far away from a nest can be solved through relatively simple behaviors in combination with pheromones. As task complexity increases, however, it may become difficult to find individual agent rules which yield a desired emergent cooperative behavior, or to know if any such rules exist at all. For such tasks, machine learning techniques like evolutionary computation (EC) may prove a valuable approach to searching the space of possible rule combinations. This paper presents an application of genetic programming to search for foraging behaviors. The learned foraging behaviors use only pheromone information to find the path to the nest and to the food source.

Liviu Panait and Sean Luke (2004)
Ant Foraging Revisited. In Proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9).
[PDF
Abstract:
Most previous artificial ant foraging algorithms have to date relied to some degree on a priori knowledge of the environment, in the form of explicit gradients generated by the nest, by hard-coding the nest location in an easily-discoverable place, or by imbuing the artificial ants with the knowledge of the nest direction. In contrast, the work presented solves ant foraging problems using two pheromones, one applied when searching for food and the other when returning food items to the nest. This replaces the need to use complicated nest-discovery devices with simpler mechanisms based on pheromone information, which in turn reduces the ant system complexity. The resulting algorithm is orthogonal and simple, yet ants are able to establish increasingly efficient trails from the nest to the food in the presence of obstacles. The algorithm replaces the blind addition of new amounts of pheromones with an adjustment mechanism that resembles dynamic programming.

Liviu Panait and Sean Luke (2004)
A Pheromone-Based Utility Model for Collaborative Foraging. In AAMAS-2004 -- Proceedings of the Third International Joint Conference on Autonomous Agents and Multi Agent Systems.
[PDF
Abstract:
Multi-agent research often borrows from biology, where remarkable examples of collective intelligence may be found. One interesting example is ant colonies' use of pheromones as a joint communication mechanism. In this paper we propose two pheromone-based algorithms for artificial agent foraging, trail-creation, and other tasks. Whereas practically all previous work in this area has focused on biologically-plausible but ad-hoc single pheromone models, we have developed a formalism which uses multiple pheromones to guide cooperative tasks. This model bears some similarity to reinforcement learning. However, our model takes advantage of symmetries common to foraging environments which enables it to achieve much faster reward propagation than reinforcement learning does. Using this approach we demonstrate cooperative behaviors well beyond the previous ant-foraging work, including the ability to create optimal foraging paths in the presence of obstacles, to cope with dynamic environments, and to follow tours with multiple waypoints. We believe that this model may be used for more complex problems still.

Liviu Panait, R. Paul Wiegand, and Sean Luke (2004)
A Sensitivity Analysis of a Cooperative Coevolutionary Algorithm Biased for Optimization. In Genetic and Evolutionary Computation Conference -- GECCO-2004.  (c) Springer.
Abstract:
Recent theoretical work helped explain certain optimization-related pathologies in cooperative coevolutionary algorithms (CCEAs). Such explanations have led to adopting specific and constructive strategies for improving CCEA optimization performance by biasing the algorithm toward ideal collaboration. This paper investigates how sensitivity to the degree of bias (set in advance) is affected by certain algorithmic and problem properties. We discover that the previous static biasing approach is quite sensitive to a number of problem properties, and we propose a stochastic alternative which alleviates this problem. We believe that finding appropriate biasing rates is more feasible with this new biasing technique.

Liviu Panait, R. Paul Wiegand, and Sean Luke (2004)
A Visual Demonstration of Convergence Properties of Cooperative Coevolution. In Parallel Problem Solving from Nature -- PPSN-2004.  Pages 892–901.  (c) Springer.
Abstract:
We introduce a model for cooperative coevolutionary algorithms (CCEAs) using partial mixing, which allows us to compute the expected long-run convergence of such algorithms when individuals' fitness is based on the maximum payoff of some N evaluations with partners chosen at random from the other population. Using this model, we devise novel visualization mechanisms to attempt to qualitatively explain a difficult-to-conceptualize pathology in CCEAs: the tendency for them to converge to suboptimal Nash equilibria. We further demonstrate visually how increasing the size of N, or biasing the fitness to include an ideal-collaboration factor, both improve the likelihood of optimal convergence, and under which initial population configurations they are not much help.

Elena Popovici and Kenneth De Jong (2004)
Understanding Cooperative Co-evolutionary Dynamics via Fitness Landscapes. In Artificial Multiagent Learning Workshop.
Abstract:
Co-evolutionary EAs are often applied to optimization and machine learning problems with disappointing results. One of the con- tributing factors to this is the complexity of the dynamics exhibited by co-evolutionary systems. In this paper we focus on a particular form of competitive co-evolutionary EA and study the dynamics of the fitness of the best individuals in the evolving populations. Our approach is to try to understand the characteristics of the fitness landscapes that produce particular kinds of fitness dynamics such as stable fixed points, stable cycles, and instability. In particular, we show how landscapes can be constructed that produce each of these dynamics. These landscapes are extremely similar when inspected with respect to traditional properties such as ruggedness / modality, yet they yield very different results. This shows there is a need for co-evolutionary specific analysis tools.

Zbigniew Skolicki and Kenneth De Jong (2004)
Improving Evolutionary Algorithms with Multi-representation Island Models. In Parallel Problem Solving from Nature -- PPSN-2004.  Pages 420–429.  (c) Springer.
[PDF
Abstract:
We present an island model that uses different representations in each island. The model transforms individuals from one representation to another during migrations. We show that such a model helps the evolutionary algorithm to escape from local optima and to solve problems that are difficult for single representation EAs. We illustrate this approach with a two population island model in which one island uses a standard binary encoding and the other island uses a standard reflective Gray code. We compare the performance of this multi-representation island model with single population EAs using only binary or Gray codes. We show that, on a variety of difficult multi-modal test functions, the multi-representation island model does no worse than a standard EA on all of the functions, and produces significant improvements on a subset of them.

Keith Sullivan and Sean Luke (2004)
Autonomous UUV Control via Decentralized Algorithms. In Proceedings of IEEE Autonomous Underwater Vehicles Workshop.
Abstract:
We apply previous studied control algorithms to the cooperative target observation (CTO) task for multiple UUVs. The algorithms are based on k-means clustering and hill climbing, and each are scalable in the degree of decentralization. In the underwater formulation of the CTO problem, k-means is not sensitive to the degree of decentralization, while the hill climber is sensitive. Unlike in previous work, K-means outperformed hill-climbing across all environmental parameters.

M. Wadda, Zbigniew Skolicki, and Tomasz Arciszewski (2004)
Generation of Terrorist Scenarios for Water Distribution Systems: An Evolutionary Computation Approach. In Proceedings of the Workshop Critical Infrastructure Protection Project.
Abstract:
The events of September 11, 2001 highlighted the importance of protecting vital infrastructure systems against terrorist attacks. Infrastructure such as a water supply system is particularly vulnerable because of the large number of potential entry points and facilities associated with it. Because of the potential for public harm, actual or psychological, communities must prepare and respond to the threats with new or enhanced security measures. This paper explores the use of an evolutionary computation approach to generating terrorist scenarios for water distribution systems.

M. Wadda, Zbigniew Skolicki, Tomasz Arciszewski, and Kenneth De Jong (2004)
A Generation of Terrorist Scenarios for Water Distribution Systems: An Evolutionary Computation Approach. In Proceedings of the 11th International EG-ICE Workshop.  Pages 110 – 119.
Abstract:
The events of September 11, 2001 highlighted the importance of protecting vital infrastructure systems against terrorist attacks. Infrastructure such as a water supply system is particularly vulnerable because of the large number of potential entry points and facilities associated with it. Because of the potential for public harm, actual or psychological, communities must prepare and respond to the threats with new or enhanced security measures. This paper explores the use of an evolutionary computation approach to generating terrorist scenarios for water distribution systems.

R. Paul Wiegand (2004)
An Analysis of Cooperative Coevolutionary Algorithms.
Ph.D. Thesis, George Mason University, Fairfax, VA.
[Abstract]  [Downloading Instructions
Abstract:
Coevolutionary algorithms behave in very complicated, often quite counterintuitive ways. Researchers and practitioners have yet to understand why this might be the case, how to change their intuition by understanding the algorithms better, and what to do about the differences. Unfortunately, there is little existing theory available to researchers to help address these issues. Further, little empirical analysis has been done at a component level to help understand intrinsic differences and similarities between coevolutionary algorithms and more traditional evolutionary algorithms. Finally, attempts to categorize coevolution and coevolutionary behaviors remain vague and poorly defined at best. The community needs directed investigations to help practitioners understand what particular coevolutionary algorithms are good at, what they are not, and why. This dissertation improves our understanding of coevolution by posing and answering the question: "Are cooperative coevolutionary algorithms (CCEAs) appropriate for static optimization tasks?" Two forms of this question are "How long do they take to reach the global optimum" and "How likely are they to get there?" The first form of the question is addressed by analyzing their performance as optimizers, both theoretically and empirically. This analysis includes investigations into the effects of coevolution-specific parameters on optimization performance in the context of particular properties of potential problem domains. The second leg of this dissertation considers the second form of the question by looking at the dynamical properties of these algorithms, analyzing their limiting behaviors again from theoretical and empirical points of view. Two common cooperative coevolutionary pathologies are explored and illustrated, in both formal and practical settings. The result is a better understanding of, and appreciation for, the fact that CCEAs are not generally appropriate for the task of static, single-objective optimization. In the end a new view of the CCEA is offered that includes analysis-guided suggestions for how a traditional CCEA might be modified to be better suited for optimization tasks, or might be applied to more appropriate tasks, given the nature of its dynamics.

R. Paul Wiegand and Jayshree Sarma (2004)
Spatial Embedding and Loss of Gradient in Cooperative Coevolutionary Algorithms. In Parallel Problem Solving from Nature -- PPSN-2004.  Pages 912–921.  (c) Springer.
Abstract:
Coevolutionary algorithms offer great promise as adaptive problem solvers but suffer from several known pathologies. Historically, spatially embedded coevolutionary algorithms seem to have succeeded where other coevolutionary approaches fail; however, explanations for this have been largely unexplored. We examine this idea more closely by looking at spatial models in the context of a particular coevolutionary pathology: loss of gradient. We believe that loss of gradient in cooperative coevolution is caused by asymmetries in the problem or initial conditions between populations, driving one population to convergence before another. Spatial models seem to lock populations together in terms of evolutionary change, helping establish a type of dynamic balance to thwart loss of gradient. We construct a tunably asymmetric function optimization problem domain and conduct an empirical study to justify this assertion. We find that spatial restrictions for collaboration and selection can help keep population changes balanced when presented with severe asymmetries in the problem.

2003 Publications

Tomasz Arciszewski, Kenneth A. De Jong, Andrew Sage, Mike Goode, Rafal Kicinger, and Zbigniew Skolicki (2003)
Proactive infrastructure security: evolutionary generation of terrorist scenarios. In Proceedings of the Workshop on the Critical Infrastructure Protection Project, Airlie Center, Warrenton, VA, August, 2003.   Alexander Woodcock and Kevin Thomas editor(s).  Pages 378-391.  George Mason University Press.
[PDF
Keywords: infrastructure security and evolutionary computation and proactive security and coevolutionary algorithms and terrorist scenarios
Abstract:
The objectives of this working paper are to propose a general concept of proactive security in the context of co-evolutionary computation and to briefly discuss the initial results of research recently began. First, the paper provides an overview of infrastructure security in the context of asymmetric threats. Next, concepts of proactive security are proposed based on co-evolution of terrorist scenarios and security plans. The paper also presents an outline of generation of terrorist scenarios in the context of conceptual design. Finally, it describes TerrorMax/Capitol Hill, a demonstration system being developed for dealing with the generation of terrorist scenarios related to the Capitol Hill in Washington DC. The paper also provides initial discussions of this recently initiated project.

Adrian Grajdeanu and Kenneth A. De Jong (2003)
Fixed Budget Allocation Strategies for Noisy Fitness Landscapes. In Genetic and Evolutionary Computation Conference (LBP).
[PDF
Abstract:
A well-known problem in dealing with noisy fitness landscapes is the diculty in deciding a priori how many samples per individual to take in order to get a useful estimate of an individual's tness. This is particularly im- portant when an EA is given a priori a xed total budget of samples and must trade o increased accuracy of tness estimates over fewer generations vs. less accurate tness estimates over more generations. This pa- per investigates a technique for dynamically adapting the tness estimation accuracy as evolution proceeds and compares the results of such adaptive runs with others in which the accuracy is chosen a priori and kept con- stant.

Thomas Jansen and R. Paul Wiegand (2003)
Exploring the Explorative Advantage of the CC (1+1) EA. In Proceedings of the 2003 Genetic and Evolutionary Computation Conference.  (c) Springer.
[PDF]  [PostScript
Abstract:
Using a well-known cooperative coevolutionary function optimization framework, a very simple cooperative coevolutionary (1+1) EA is defined. This algorithm is investigated under the perspective of the expected optimization time. The focus is on the impact the cooperative coevolutionary approach has and on the possible advantage it may have over more traditional evolutionary approaches. Therefore, a systematic comparison between the expected optimization times of this coevolutionary algorithm and the ordinary (1+1) EA is presented. The main result is that separability of the objective function alone is is not sufficient to make the cooperative coevolutionary approach beneficial. By presenting a clear structured example function and analyzing the algorithms' performance, it is shown that the cooperative coevolutionary approach comes with new explorative possibilities. This can lead to an immense speed-up of the optimization.

Rafal Kicinger, Tomasz Arciszewski, and Kenneth A. De Jong (2003)
Conceptual design in structural engineering: an evolutionary computation approach. In Proceedings of the 2nd International Specialty Conference on the Conceptual Approach to Structural Design, Milan, Italy, July 1-2, 2003.  Pages 529-536.  CI-Premier PTE Ltd..
[PDF
Keywords: conceptual design and evolutionary design and tall buildings and evolutionary computation and structural design
Abstract:
This paper describes a new design paradigm, evolutionary structural design, that involves the entire design process, including conceptual and detailed design stages. In this paper, first a brief overview of the fundamentals of evolutionary computation is provided. Next, the concept of evolutionary structural design and its principia are discussed. Inventor 2001 is described in the following section. It is an experimental research and design system based on evolutionary computation. The system has been developed by the authors at George Mason University for applications in the design of tall buildings. Inventor 2001 allows for the conducting of evolutionary structural design, including the generation of structural concepts and the detailed design, analysis of internal forces, dimensioning, and optimization. Selected specific research results are also provided, including a discussion of the discovered emergent structural shaping patterns that are surprisingly consistent with the state of the art in structural shaping of steel skeleton structures of tall buildings. Finally, the initial research conclusions are provided.

Sean Luke, Gabriel Catalin Balan, and Liviu Panait (2003)
MASON: A Java Multi-agent Simulation Library. In Proceedings of the Second International Workshop on the Mathematics and Algorithms of Social Insects.

Sean Luke, Gabriel Catalin Balan, and Liviu Panait (2003)
Population Implosion in Genetic Programming.. In Genetic and Evolutionary Computation -- GECCO-2003.   E. Cantú-Paz, J. A. Foster, K. Deb, D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. Dowsland, N. Jonoska, and J. Miller editor(s).  Pages 1729–1739.  (c) Springer.
Abstract:
With the exception of a small body of adaptive-parameter literature, evolutionary computation has traditionally favored keeping the population size constant through the course of the run. Unfortunately, genetic programming has an aging problem: for various reasons, late in the run the technique become less effective at optimization. Given a fixed number of evaluations, allocating many of them late in the run may thus not be a good strategy. In this paper we experiment with gradually decreasing the population size throughout a genetic programming run, in order to reallocate more evaluations to early generations. Our results show that over four problem domains and three different numbers of evaluations, decreasing the population size is always as good as, and frequently better than, various fixed-sized population strategies.

Sean Luke, Gabriel Catalin Balan, Liviu Panait, Claudio Cioffi-Revilla, and Sean Paus (2003)
MASON: A Java Multi-agent Simulation Library. In Proceedings of Agent 2003 Conference on Challenges in Social Simulation.
Abstract:
Agent-based modeling (ABM) has transformed social science research by allowing researchers to replicate or generate the emergence of empirically complex social phenomena from a set of relatively simple agent-based rules at the micro-level. Swarm, RePast, Ascape, and others currently provide simulation environments for ABM social science research. After Swarm — arguably the first widely used ABM simulator employed in the social sciences — subsequent simulators have sought to enhance available simulation tools and computational capabilities by providing additional functionalities and formal modeling facilities. Here we present MASON (Multi-Agent Simulator Of Neighborhoods), following in a similar tradition that seeks to enhance the power and diversity of the available scientific toolkit in computational social science. MASON is intended to provide a core of facilities useful not only to social science but to other agent-based modeling fields such as artificial intelligence and robotics. We believe this can foster useful “cross-pollination” between such diverse disciplines, and further that MASON's additional facilities will become increasing important as social complexity simulation matures and grows into new approaches. We illustrate the new MASON simulation library with a replication of HeatBugs and a demonstration of MASON applied to two challenging case studies: ant-like foragers and micro-aerial agents. Other applications are also being developed. The HeatBugs replication and the two new applications provide an idea of MASON’s potential for computational social science and artificial societies.

Ronald W. Morrison (2003)
Dispersion Based Population Initialization. In Genetic and Evolutionary Computation, Lecture Notes in Computer Science, Vol.2723.   Erick Cantu-Paz editor(s).  Pages 1210–1221.  (c) Springer.
[PDF
Abstract:
Reliable execution and analysis of an evolutionary algorithm (EA) normally requires many runs to provide reasonable assurance that stochastic effects have been properly considered. One of the first stochastic influences on the behavior of an EA is the population initialization. This has been recognized as a potentially serious problem to the performance of EAs but little progress has been made in improving the situation. Using a better population initialization algorithm would not be expected to improve the many-run average performance of an EA, but instead, it would be expected to reduce the variance of the results, without loss of average performance. This would provide researchers the opportunity to reliably examine their experimental results while requiring fewer EA runs for an appropriate statistical sample. This paper uses recent advances in the measurement and control of a population’s dispersion in a search space to present a novel algorithm for better population initialization. Experimental verification of the usefulness of the new technique is provided.

Ronald W. Morrison (2003)
Performance Measurement in Dynamic Environments. In Workshop Program, Genetic and Evolutionary Computation Conference, 2003.   Alwyn Barry editor(s).  Pages 1210–1221.  GECCO.
[PDF
Abstract:
There has not been a uniform agreement regarding what constitutes "good" performance for evolutionary algorithms in dynamic environments. A performance measurement method should, as a minimum, have an intuitive meaning and provide straightforward methods for statistical significance testing of comparative results. In this paper we attempt to resolve some issues related to EA performance measurement in dynamic environments.

Emeka Oguejiofor, Rafal Kicinger, Elena Popovici, Tomasz Arciszewski, and Kenneth A. De Jong (2003)
George Mason University Intelligent Educator. In Innovative Developments in Architecture, Engineering and Construction. Proceedings of the 2nd International Conference on Innovation in Architecture, Engineering and Construction, Loughborough University, UK, 25 - 27 June 2003.   Chimay J. Anumba editor(s).  Pages 355-366.  Millpress Science Publishers.
[PDF
Keywords: intelligent agents and tutoring systems and engineering design and knowledge-based systems
Abstract:
Engineering education is undergoing significant changes, mostly driven by the ongoing Information Technology Revolution. One of the most promising technologies becoming available to educators is that of intelligent software agents. Such agents can be used in building tutoring systems, which in this way become intelligent in terms of knowledge content, their ability to learn (acquire knowledge), and to adapt to the needs and learning preferences of their users. The paper discusses the development of a prototype intelligent tutoring system, called "George Mason University Intelligent Educator." It has been built as a result of a complex process in which various software development tools have been used in a novel way, including ConceptMap, Prot{\~A}{\copyright}g{\~A}{\copyright}2000, Macromedia Flash and JRun. The reported research is part of a NASA-sponsored project in the area of engineering education called "Hierarchical Learning Network" and is coordinated by the Old Dominion University in Virginia. The primary objective of the research at George Mason University is to develop a methodology for building intelligent tutoring systems and to demonstrate its feasibility. First, the paper provides a brief description of the process that was used for knowledge acquisition and its representation in the form of an ontology. The description includes examples from the area of personal air vehicles. Next, the development process for the proposed intelligent tutoring system is presented, along with a discussion of the integration of various software development tools. Finally, the initial research conclusions and plans for further research are discussed.

Liviu Panait and Sean Luke (2003)
Evolving Foraging Behaviors. In Proceedings of the Second International Workshop on the Mathematics and Algorithms of Social Insects.
Abstract:
Insects are particularly good at cooperatively solving multiple complex tasks. For example, foraging for food far away from the nest can be solved through relatively simple behaviors in combination with communication through pheromones. As task complexity increases, however, it may become difficult to determine the proper simple rules which yield the desired emergent cooperative behavior, or to know if any such rules exist at all. For such tasks, machine learning techniques like evolutionary computation (EC) may prove a valuable approach to searching the space of possible rule combinations. The paper shows that by allowing simultaneous learning of both the pheromone-depositing and pheromone-using policies, good performing foraging behaviors can be obtained. Additionally, the learned foraging behaviors use only pheromone information to find the path to the nest and to the food source, not requiring compasses or other complex mechanisms to return back to the nest.

Liviu Panait and Sean Luke (2003)
Ant Foraging Revisited. In Proceedings of the Second International Workshop on the Mathematics and Algorithms of Social Insects.
Abstract:
Most previous artificial ant foraging algorithms have to date relied to some degree on a priori knowledge of the environment, in the form of explicit gradients generated by the nest, by hard-coding the nest location in an easily-discoverable place, or by imbuing the artificial ants with the knowledge of the nest direction. In contrast, the work presented solves ant foraging problems using two pheromones, one applied when searching for food and the other when returning food items to the nest. This replaces the need to use complicated nest-discovery devices with simpler mechanisms based on pheromone information, which in turn reduces the ant system complexity. The resulting algorithm is orthogonal and simple, yet ants are able to establish increasingly efficient trails from the nest to the food in the presence of obstacles. The algorithm replaces the blind addition of new amounts of pheromones with an adjustment mechanism that resembles dynamic programming.

Liviu Panait and Sean Luke (2003)
Collaborative Multi-Agent Learning: A Survey.
Department of Computer Science, George Mason University, technical report GMU-CS-TR-2003-01.
[PDF

Liviu Panait and Sean Luke (2003)
Methods for Evolving Robust Programs. In Genetic and Evolutionary Computation -- GECCO-2003.   E. Cantú-Paz, J. A. Foster, K. Deb, D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. Dowsland, N. Jonoska, and J. Miller editor(s).  Pages 1740–1751.  (c) Springer.
Abstract:
Many evolutionary computation search spaces require fitness assessment through the sampling of and generalization over a large set of possible cases as input. Such spaces seem particularly apropos to Genetic Programming, which notionally searches for computer algorithms and functions. Most existing research in this area uses ad-hoc approaches to the sampling task, guided more by intuition than understanding. In this initial investigation, we compare six approaches to sampling large training case sets in the context of genetic programming representations. These approaches include fixed and random samples, and adaptive methods such as coevolution or fitness sharing. Our results suggest that certain domain features may lead to the preference of one approach to generalization over others. In particular, coevolution methods are strongly domain-dependent. We conclude the paper with suggestions for further investigations to shed more light onto how one might adjust fitness assessment to make various methods more effective.

Liviu Panait, R. P. Wiegand, and Sean Luke (2003)
Improving Coevolutionary Search for Optimal Multiagent Behaviors. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03).   Georg Gottlob and Toby Walsh editor(s).  Pages 653–658.
Abstract:
Evolutionary computation is a useful technique for learning behaviors in multiagent systems. Among the several types of evolutionary computation, one natural and popular method is to coevolve multiagent behaviors in multiple, cooperating populations. Recent research has suggested that coevolutionary systems may favor stability rather than performance in some domains. In order to improve upon existing methods, this paper examines the idea of modifying traditional coevolution, biasing it to search for maximal rewards. We introduce a theoretical justification of the improved method and present experiments in three problem domains. We conclude that biasing can help coevolution find better results in some multiagent problem domains.

Elena Popovici and Kenneth De Jong (2003)
Understanding EA Dynamics via Population Fitness Distributions (poster version). In Proceedings of the Genetic and Evolutionary Computation Conference 2003.   Erick Cantu-Paz et. al. editor(s).  Pages 1604–1605.  (c) Springer.
[PDF

Elena Popovici and Kenneth De Jong (2003)
Understanding EA Dynamics via Population Fitness Distributions (full version). In Proceedings of the Genetic and Evolutionary Computation Conference 2003.   Erick Cantu-Paz et. al. editor(s).  Pages 1604–1605.  (c) Springer.
[PDF
Abstract:
It is clear from the study of complex non-linear systems in general, and evolutionary algorithms (EAs) in particular, that there is no single analysis tool or technique capable of providing a reasonably comprehensive understanding of the behavior of a complex non-linear system. Rather, we continue to develop sets of tools that collectively provide a more comprehensive view than any one tool. In this paper we provide an initial assessment of a new technique that is based on an old idea: the importance of understanding how the tness distribution of an EA population changes over time.

Mitchell A. Potter, Jeffrey K. Bassett, and Kenneth A. De Jong (2003)
Visualizing evolvability with Price's equation. In Proceedings of the 2003 Congress on Evolutionary Computation.  IEEE Press.
[PDF
Abstract:
The term ``premature convergence'' has been used for many years as an explanation as to why an evolutionary algorithm fails to find a global optimum, without providing much insight into how to fix the problem and/or avoid it in the future. In this paper we tie these issues to notions of (lack of) evolvability that have been explored in the population genetics community for many years. In particular, we show how the central equation in Price's Theorem can be extended in such a way as to separate out the individual contributions that reproductive operators make to evolvability, paving the way for better designed EAs in the future.

T. Pullman, Zbigniew Skolicki, M. Freischlad, Tomasz Arciszewski, and Kenneth De Jong (2003)
Structural Design of Reinforced Concrete Tall Buildings: Evolutionary Computation Approach using Fuzzy Sets. In Proceedings of the 10th Workshop on the European Group for Intelligent Computing.
Abstract:
The paper reports the results of a joint project on evolutionary design of reinforced concrete structures in tall buildings. It has been conducted at the Center for Concrete Structures at the Darmstadt University of Technology in Germany and in the School of Information Technology and Engineering at George Mason University. Its ultimate objective is to revolutionize design of both steel and concrete structural systems through the introduction of evolutionary design processes and tools. In this paper, we first provide a general overview of structural design of reinforced concrete structures in tall buildings. Next, various issues of design representation space are addressed, including a general design space for a building for which both crisp and fuzzy approaches are used. Also, a more specific issue of developing a design representation space for a reinforced concrete structure of a tall building is addressed and the concept of a floor template is introduced. The central part of the paper is a description of the proposed evolutionary design process and of the related computer design support tools. Finally, the results of various conducted design experiments are reported. They include the comparison of various selection strategies and the comparison of evolutionary design processes when crisp and fuzzy evaluation of designs is used.

Alexei V. Samsonovich and Kenneth A. De Jong (2003)
Meta-Cognitive Architecture for Team Agents. In Proceedings of the 25th Annual Meeting of the Cognitive Science Society.   R. Alterman and D. Kirsh editor(s).  Pages 1029 – 1034.
Abstract:
A key element of our approach is the interpretation of ``self''in a meta-cognitive sense: that is, ``self'' is understood as a virtual character representing an agent as the subject of experience, as the target of attribution of experiences and deliberate actions performed by this agent. Thus understood, ``self'' can be represented as an element in an agent's cognitive system and can be used for meta-cognitive processing: i.e., reasoning about one's own self and other selves. This general idea reflects a simulationist theory-of mind viewpoint (Nichols & Stich, 2000), which is taken as the basis for our approach. Our model of an agent's mind includes multiple instances of ``self'' representing notions of INow, I-Yesterday, I-Imagine, I-Goal, etc. Each instance of ``self'' is represented by a ``chart'' with a set of properties and mental states attributed to it. Thus, mental states in this framework are representations of experiences attributed to a particular instance of ``self''. This attribution further implies certain rules and constraints imposed on the contents and the dynamics of representations. The result is a general architecture that will enable in intelligent agents a metacognitive ``common sense'', which proves to be vital in a variety of paradigms and scenarios requiring cooperation within a team.

D. Sofge, M.A. Potter, and A.C. Schultz (2003)
Challenges and Opportunities of Evolutionary Robotics. In Proceedings of 2nd International Conference on Computational Intelligence, Robotics, and Autonomous Systems (CIRAS2003).  IEEE.
[PDF
Abstract:
Robotic hardware designs are becoming more complex as the variety and number of on-board sensors increase and as greater computational power is provided in ever smaller packages on-board robots. These advances in hardware, however, do not automatically translate into better software for controlling complex robots. Evolutionary techniques hold the potential to solve many difficult problems in robotics which defy simple conventional approaches, but present many challenges as well. Numerous disciplines including artificial life, cognitive science and neural networks, rule-based systems, behavior based control, genetic algorithms and other forms of evolutionary computation have contributed to shaping the current state of evolutionary robotics. This paper provides an overview of developments in the emerging field of evolutionary robotics, and discusses some of the opportunities and challenges which currently face practitioners in the field. The need for ER arises from the fact that as robotic systems and the environments into which they are placed increase in complexity, the difficulty of programming their control systems to respond appropriately increases to the point where it becomes impracticable to foresee every possible state of the robot in its environment. Evolutionary algorithms are used to generate control algorithms using the Darwinian principle of survival-of-the-fittest. A population of controllers is maintained and evolved by evaluating individual control systems based on a measure of how well they achieve desired characteristics such as executing appropriate behaviors at appropriate times. Only the fitter members of the population survive and pass the characteristics that made them successful on to future generations. The ultimate goal is to produce the best possible controller given some design criteria. As discussed in the following sections, this approach has proven very successful in a wide variety of challenging robotics domains. The remainder of this paper will provide a sampling of recent development efforts in evolutionary robotics research with the goal of showing both the opportunities presented by the use of evolutionary techniques for solving difficult problems in robotics, but also in showing some of the challenges of applying these techniques.

2002 Publications

Jeffrey K. Bassett (2002)
A Study of Generalization Techniques in Evolutionary Rule Learning.
Masters Thesis, George Mason University, Fairfax VA, USA.
[PDF]  [PostScript]  [GZipped PostScript
Abstract:
Generalization is an important aspect of all machine learning algorithms. Without it, learning can only occur in the simplest of problem domains. The most interesting domains tend to be more complex though. As we scale-up our algorithms to work in these complex domains, an understanding of the different generalization techniques available and the trade-offs between them becomes increasingly important. This thesis is primarily concerned with rule learning using evolutionary algorithms. We examine two commonly used generalization techniques called wildcards and partial matching, as well as a third which is a hybrid of these two. We demonstrate that the wildcards are more effective at generalizing in some domains, and partial matching is more effective in others. It is our hypothesis that the hybrid will be the more robust of the three techniques. In other words, the hybrid will generalize as well, or almost as well, as the better of the other two in a variety of domains. Two very different domains were chosen as testbeds for our experiments. The first is a concept learning domain, which tends to favor wildcards. The second is a multi-agent robotics task, where partial matching is more effective. When the hybrid was tested in these environments, the results show that it was either equivalent or superior to the other two techniques, thus verifying our hypothesis. Finally we attempt to find an explanation for these results that will help predict behavior in other domains. We examine how these generalization techniques alter the inductive bias of the learning algorithm. The analysis demonstrates weaknesses in both wildcards and partial matching. It also suggests that the weaknesses of each technique is offset by the strength of the other, thus allowing the hybrid to be more effective. An attempt was made to verify the inductive bias explanation. We use this knowledge to devise a concept learning problem which will favor partial matching instead of wildcards. But the results of this experiment show that the most accurate classifiers were produced using the wildcard generalization mechanism. The inductive bias hypothesis is clearly helpful for understanding some of the behaviors observed in the learning algorithm. None the less, further study will be required to understand a problem as complex as this one fully.

Rafal Kicinger, Kenneth A. De Jong, and Tomasz Arciszewski (2002)
Long term versus short term evolutionary design. In Advances in Intelligent Computing in Engineering. Proceedings of the 9th International Workshop of the European Group for Intelligent Computing in Engineering, Darmstadt, Germany, August 1-2, 2002.   Martina Schnellenbach-Held and Heiko Denk editor(s).  Pages 184-195.  VDI Verlag.
[PDF
Keywords: evolutionary computation and evolutionary design and structural design and tall buildings and optimization

Sean Luke and Liviu A. Panait (2002)
Fighting Bloat With Nonparametric Parsimony Pressure. In Parallel Problem Solving from Nature - PPSN VII (LNCS 2439).   Juan Julian Merelo Guervos et al editor(s).  Pages 411–421.  (c) Springer.
Abstract:
Many forms of parsimony pressure are parametric, that is final fitness is a parametric model of the actual size and raw fitness values. The problem with parametric techniques is that they are hard to tune to prevent size from dominating fitness late in the evolutionary run, or to compensate for problem-dependent nonlinearities in the raw fitness function. In this paper we briefly discuss existing bloat-control techniques, then introduce two new kinds of non-parametric parsimony pressure, Direct and Proportional Tournament. As their names suggest, these techniques are based on simple modifications of tournament selection to consider both size and fitness, but not together as a combined parametric equation. We compare the techniques against, and in combination with, the most popular genetic programming bloat-control technique, Koza-style depth limiting, and show that they are effective in limiting size while still maintaining good best-fitness-of-run results.

Sean Luke and Liviu A. Panait (2002)
Is the Perfect the Enemy of the Good?. In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference.   W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska editor(s).  Pages 820–828.  Morgan Kaufmann Publishers.
Abstract:
Much of the genetic programming literature compares techniques using counts of ideal solutions found. These counts in turn form common comparison measures such as Koza's Computational Effort or cumulative Probability of Success. The use of these measures continues despite past warnings that they are not statistically valid. In this paper we too criticize the measures for serious statistical problems, and also argue that their motivational justification is faulty. We then present evidence suggesting that ideal solution counts are not necessarily positively related to best-fitness-of-run statistics: in fact they are often inversely correlated. Thus claims based on ideal solution counts can mislead readers into thinking techniques will provide superior final results, when in fact the opposite is true.

Sean Luke and Liviu A. Panait (2002)
Lexicographic Parsimony Pressure. In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference.   W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska editor(s).  Pages 829–836.  Morgan Kaufmann Publishers.
Abstract:
We introduce a technique called lexicographic parsimony pressure, for controlling the significant growth of genetic programming trees during the course of an evolutionary computation run. Lexicographic parsimony pressure modifies selection to prefer smaller trees only when fitnesses are equal (or equal in rank). This technique is simple to implement and is not affected by specific differences in fitness values, but only by their relative ranking. In two experiments we show that lexicographic parsimony pressure reduces tree size while maintaining good fitness values, particularly when coupled with Koza-style maximum tree depth limits.

Sean Luke and R. Paul Wiegand (2002)
When Coevolutionary Algorithms Exhibit Evolutionary Dynamics. In Workshop Proceedings of the 2003 Genetic and Evolutionary Computation Conference.  (c) Springer.
[PDF]  [PostScript
Abstract:
The task of understanding the dynamics of coevolutionary algorithms or comparing performance between such algorithms is complicated by the fact the internal fitness measures are subjective. Though a variety of techniques have been proposed to use external or objective measures to help in analysis, there are clearly properties of fitness payoff (e.g., intransitivity) which call such methods into question in certain contexts. We present a model of competitive fitness assessment with a single population and non-parametric selection (such as tournament selection), and show minimum conditions and examples under which an objective measure exists, and when the dynamics of the coevolutionary algorithm are identical to those of a traditional EA.We also discuss terminological difficulties in the coevolution literature, and present a detailed description of external measures presently in use in the literature.

Sean Luke and R. Paul Wiegand (2002)
Guaranteeing Coevolutionary Objective Measures. In Foundations of Genetic Algorithms VII.  Pages 237-251.  Morgan Kaufman.
[PDF]  [PostScript
Abstract:
The task of understanding the dynamics of coevolutionary algorithms or com- paring performance between such algorithms is complicated by the fact the internal tness measures are subjective. Though several techniques have been proposed to use external or objective measures to help in analysis, there are clearly properties of fitness payoff , like intransitivity, for which these techniques are ine ective. We feel that a principled approach to this problem is to rst establish the theoretical bounds to guarantee objective measures in one CEA model; from there one can later examine the e ects of deviating from the as- sumptions made by these bounds. To this end, we present a model of compet- itive tness assessment with a single population and non-parametric selection (such as tournament selection), and show minimum conditions and examples under which an objective measure exists, and when the dynamics of the coevo- lutionary algorithm are identical to those of a traditional EA.

Ronald W. Morrison and Kenneth A. De Jong (2002)
Measurement of Population Diversity. In Artificial Evolution, Lecture Notes in Computer Science, Vol.2310.   Pierre Collet, Cyril Fonlupt, Jon-Kao Hao, Evelyne Lutton, and Marc Schoenauer editor(s).  Pages 31–41.  (c) Springer.
[PDF
Abstract:
In evolutionary algorithms (EAs), the need to efficiently measure population diversity arises in a variety of contexts, including operator adaption, algorithm stopping and re-starting criteria, and fitness sharing. In this paper we introduce a unified measure of population diversity and define its relationship to the most common phenotypic and genotypic diversity measures. We further demonstrate that this new measure provides a new and efficient method for computing population diversity, where the cost of computation increases linearly with population size.

Liviu A. Panait and Sean Luke (2002)
A Comparison of Two Competitive Fitness Functions. In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference.   W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska editor(s).  Pages 503–511.  Morgan Kaufmann Publishers.
Abstract:
Competitive fitness is the assessment of an individual's fitness in the context of competition with other individuals in the evolutionary system. This commonly takes one of two forms: one-population competitive fitness, where competition is solely between individuals in the same population; and N-population competitive fitness, often termed competitive coevolution. In this paper we discuss common topologies for one-population competitive fitness functions, then test the performance of two such topologies, Single-Elimination Tournament and K-Random Opponents, on four problem domains. We show that neither of the extremes of K-Random Opponents (Round Robin and Random-Pairing) gives the best results when using limited computational resources. We also show that while Single-Elimination Tournament usually outperforms variations of K-Random Opponents in noise-free problems, it can suffer from premature convergence in noisy domains.

Alexei V. Samsonovich and Kenneth A. De Jong (2002)
General-purpose meta-cognitive systems: From philosophical ideas to a computational framework. Artificial Intelligence -- Ukraine, 4 : 67 – 73.

Zbigniew Skolicki and Rafal Kicinger (2002)
Intelligent agent for designing steel skeleton structures of tall buildings. In Computing in Civil Engineering. Proceedings of the International Workshop on Information Technology in Civil Engineering, Washington, DC, November 2-3, 2002.   Anthony D. Songer and John C. Miles editor(s).  Pages 25-35.  American Society of Civil Engineers.
[PDF
Keywords: intelligent agents and tall buildings and topological optimum design
Abstract:
The paper discusses a study on the application of intelligent agents (IAs) to conceptual designing. It provides an overview of the state-of-the-art in the areas of ontologies and IAs. Next, the system Disciple, a learning intelligent agent shell, and the system Inventor 2001, evolutionary design support tool, both developed at George Mason University, are briefly presented. Further, the paper introduces the developed ontology for a class of steel skeleton structures of tall buildings. This ontology was used to build an IA for the selection of initial parent design concepts in evolutionary designing. A description of the developed agent is provided as well. Finally, examples of design concepts proposed by the agent are presented. The paper also contains conclusions and recommendations for further research.

Donald Sofge (2002)
Using Genetic Algorithm Based Variable Selection to Improve Neural Network Models for Real-World Systems. In Proceedings of the 2002 International Conference on Machine Learning and Applications - ICMLA 2002.   M. Arif Wani, Hamid R. Arabnia, Krzysztof J. Cios, Khalid Hafeez, and Graham Kendall editor(s).  Pages 16–19.  CSREA Press.
[PDF
Abstract:
Real-world systems are often modeled by sampling sensor data taken during system operation. System states may not be all known or measurable, sensor data may be biased or noisy, and it is not often known which sensor data may be useful for predictive modeling. Neural network models generated from this data must therefore rely on how effectively the chosen sensor data represents the system. Genetic algorithms may help to address this problem by determining a near optimal subset of sensor variables most appropriate to produce good models. This paper describes the use of genetic algorithms to optimize variable selection to determine inputs into a neural network system model. The use of this technique for modeling a typical industrial application, a liquid fed ceramic melter, and the results of the genetic search to optimize the neural network model for this application, are described.

D. Sofge, K. De Jong, and A. Schultz (2002)
A Blended Population Approach to Cooperative Coevolution for Decomposition of Complex Problems. In Proceedings of the 2002 Congress on Evolutionary Computation (CEC2002).  Pages 413–418.  IEEE.
[PDF
Abstract:
Cooperative coevolutionary architectures provide a framework for solving complex problems by decomposing them into constituent subproblems, solving the subproblems, and then reintegrating the solutions. This paper presents a blended cooperative coevolution model which offers advantages over traditional evolutionary algorithms and currently used cooperative coevolutionary architectures.

R. Paul Wiegand, William C. Liles, and Kenneth A. De Jong (2002)
The Effects of Representational Bias on Collaboration Methods in Cooperative Coevolution. In Proceedings of the Seventh Conference on Parallel Problem Solving from Nature.  Pages 257-268.  (c) Springer.
[PDF]  [PostScript
Abstract:
Cooperative coevolutionary algorithms (CCEAs) have been applied to many optimization problems with varied success. Recent empirical studies have shown that choices surrounding methods of collaboration may have a strong impact on the success of the algorithm. Moreover, certain properties of the problem landscape, such as variable interaction, greatly influence how these choices should be made. A more general view of variable interaction is one that considers epistatic linkages which span population boundaries. Such linkages can be caused by the decomposition of the actual problem, as well as by CCEA representation decisions regarding population structure. We posit that it is the way in which represented problem components interact, and not necessarily the existence of cross population epistatic linkages that impacts these decisions. In order to explore this issue, we identify two different kinds of representational bias with respect to the population structure of the algorithm, decompositional bias and linkage bias. We provide analysis and constructive examples which help illustrate that even when the algorithm's representation is poorly suited for the problem, the choice of how best to select collaborators can be unaffected.

R. Paul Wiegand, William C. Liles, and Kenneth A. De Jong (2002)
Analyzing Cooperative Coevolution with Evolutionary Game Theory. In Proceedings of the 2002 Congress on Evolutionary Computation.  Pages 1600-1605.  IEEE Press.
[PDF]  [PostScript
Abstract:
The task of understanding coevolutionary algorithms is a very difficult one. These algorithms search landscapes which are in some sense adaptive. As a result, the dynamical behaviors of coevolutionary systems can frequently be even more complex than traditional evolutionary algorithms (EAs). Moreover, traditional EA theory tells us little about coevolutionary algorithms. One major question that has yet to be clearly addressed is whether or not coevolutionary algorithms are well--suited for optimization tasks. Although this question is equally applicable to competitive, as well as cooperative approaches, answering the question for cooperative coevolutionary algorithms is perhaps more attainable. Recently, evolutionary game theoretic (EGT) models have begun to be used to help analyze the dynamical behaviors of coevolutionary algorithms. One type of EGT model which is already reasonably well understood are multi--population symmetric games. We believe these games can be used to analytically model cooperative coevolutionary algorithms. This paper introduces our analysis framework, explaining how and why such models may be generated. It includes some examples illustrating specific theoretical and empirical analysis. We demonstrate that using our framework, a better understanding for the degree to which cooperative coevolutionary algorithms can be used for optimization can be achieved.

R. Paul Wiegand, William C. Liles, and Kenneth A. De Jong (2002)
Modeling Variation in Cooperative Coevolution Using Evolutionary Game Theory. In Foundations of Genetic Algorithms VII.  Pages 203-220.  Morgan Kaufman.
[PDF]  [PostScript
Abstract:
Though coevolutionary algorithms are currently used for optimization purposes, practitioners are often plagued with difficulties due to the fact that such systems frequently behave in counter intuitive ways that are not well understood. This paper seeks to extend work which uses evolutionary game theory (EGT) as a form of dynamical systems modeling of coevolutionary algorithms in order to begin to answer questions regarding how these systems work. It does this by concentrating on a particular subclass of cooperative coevolutionary algorithms, for which multi-population symmetric evolutionary game theoretic models are known to apply. We examine dynamical behaviors of this model in the context of static function optimization, by both formal analysis, as well as model validation study. Finally, we begin looking at the effects of variation by extending traditional EGT, offering some introductory analysis, as well as model validation. In the course of this study, we investigate the effects of parameterized uniform crossover and bit-flip mutation.

2001 Publications

Tomasz Arciszewski and Kenneth De Jong (2001)
Evolutionary Computation in Civil Engineering: Research Frontiers. In Civil and Structural Engineering Computing.  Pages 161 – 184.  Saxe-Coburg Publications.
Abstract:
This paper provides an overview of the state of the art of evolutionary computation in civil engineering. First, it discusses the fundamentals of evolutionary computation in the context of a unified approach recently proposed by one of the authors. Second, it discusses the main research directions, including morphogenic design and co-evolutionary design. Next, it provides a description of the emerging evolutionary computation analysis, including an analysis in the context of complex adaptive systems and one based on the visualization of the gene pool and of the fitness function. Finally, the paper contains the conclusions and recommendations for the further research.

Jeffrey K. Bassett, R. Paul Wiegand, and Kenneth A. De Jong (2001)
Evolving Multi--Agent Behaviors Using a Tunable Problem Landscape. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2001.  Pages 1133 (Poster).  Morgan Kaufmann Publishers.

Sean Luke (2001)
When short runs beat long runs. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2001.  Pages 74–80.  Morgan Kaufmann Publishers.
[PDF]  [GZipped PostScript
Abstract:
What will yield the best results: doing one run n generations long or doing m runs n/m generations long each? This paper presents a technique independent analysis which answers this question, and has direct applicability to scheduling and restart theory in evolutionary computation and other stochastic methods. The paper then applies this technique to three problem domains in genetic programming. It discovers that in two of these domains there is a maximal number of generations beyond which it is irrational to plan a run; instead it makes more sense to do multiple short runs.

Sean Luke and Liviu Panait (2001)
A survey and comparison of tree generation algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2001.  Pages 81–88.  Morgan Kaufmann Publishers.
[PDF]  [GZipped PostScript
Abstract:
This paper discusses and compares five major tree-generation algorithms for genetic programming, and their effects on fitness: RAMPED HALF-AND-HALF, PTC1, PTC2, RANDOM-BRANCH, and UNIFORM. The paper compares the performance of these algorithms on three genetic programming problems (11-Boolean Multiplexer, Artificial Ant, and Symbolic Regression), and discovers that the algorithms do not have a significant impact on fitness. Additional experimentation shows that tree size does have an important impact on fitness, and further that the ideal initial tree size is very different from that used in traditional GP.

R. Paul Wiegand, William C. Liles, and Kenneth A. De Jong (2001)
An Empirical Analysis of Collaboration Methods in Cooperative Coevolutionary Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2001.  Pages 1235–1245.  Morgan Kaufmann Publishers.
[PostScript]  [GZipped PostScript]  [PDF]  [Errata
Abstract:
Although a variety of coevolutionary methods have been explored over the years, it has only been recently that a general architecture for cooperative coevolution has been proposed. Since that time, the flexibility and success of this cooperative coevolutionary architecture (CCA) has been shown in an array of different kinds of problems. However, many questions about the dynamics of this model, as well as the efficacy of various CCA-specific choices remain unanswered. One such choice surrounds the issue of how the algorithm selects collaborators for evaluation. This paper offers an empirical analysis of various types of collaboration mechanisms and presents some basic advice about how to choose a mechanism which is appropriate for a particular problem.

2000 Publications

Jeffrey K. Bassett and Kenneth A. De Jong (2000)
Evolving Behaviors for Cooperating Agents. In Proceedings of the Twelfth International Symposium on Methodologies for Intelligent Systems.   Z. Ras and S. Ohsuga editor(s).  Pages 157–165.  (c) Springer.
[PDF]  [PostScript]  [GZipped PostScript
Abstract:
A good deal of progress has been made in the past few years in the design and implementation of control programs for autonomous agents. A natural extension of this work is to consider solving difficult tasks with teams of cooperating agents. Our interest in this area is motivated in part by our involvement in a Navy-sponsored micro air vehicle (MAV) project in which the goal is to solve difficult surveillance tasks using a large team of small inexpensive autonomous air vehicles rather than a few expensive piloted vehicles. Our approach to developing control programs for this MAVs is to use evolutionary computation techniques to evolve behavioral rule sets. In this paper we describe our architecture for achieving this, and we present some of our initial results.

Sean Luke (2000)
Two Fast Tree-Creation Algorithms for Genetic Programming. IEEE Transactions on Evolutionary Computation : 274–283.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming, Population Initialization, Tree Creation, Subtree Mutation, Tree Growth, Introns, Bloat
Abstract:
Genetic programming is an evolutionary optimization method that produces functional programs to solve a given task. These programs commonly take the form of trees representing LISP s-expressions, and a typical evolutionary run produces a great many of these trees. For this reason, a good tree generation algorithm is very important to genetic programming. This paper presents two new tree-generation algorithms for genetic programming and for strongly-typed genetic programming, a common variant. These algorithms are fast, allow the user to request specific tree sizes, and guarantee probabilities of certain nodes appearing in trees. The paper analyzes these two algorithms and compares them with traditional and recently proposed approaches.

Sean Luke (2000)
Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and Code Bloat.
Ph.D. Thesis, Department of Computer Science, University of Maryland, A. V. Williams Building, University of Maryland, College Park, MD 20742 USA.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming
Abstract:
Genetic Programming is an evolutionary computation technique which searches for those computer programs that best solve a given problem. As genetic programming is applied to increasingly difficult problems, its effectiveness is hampered by the tendency of candidate program solutions to grow in size independent of any corresponding increases in quality. This bloat in solutions slows the search process, interferes with genetic programming's searching, and ultimately consumes all available memory. The challenge for scaling up genetic programming is to find the best solutions possible before bloat puts a stop to evolution. This can be tackled either by finding better solutions more rapidly, or by taking measures to delay bloat as long as possible.

This thesis discusses issues both in speeding the search process and in delaying bloat in order to scale genetic programming to tackle harder problems. It describes evolutionary computation and genetic programming, and details the application of genetic programming to cooperative robot soccer and to language induction. The thesis then compares genetic programming breeding strategies, showing the conditions under which each strategy produces better individuals with less bloating. It then analyzes the tree growth properties of the standard tree generation algorithms used, and proposes new, fast algorithms which give the user better control over tree size. Lastly, it presents evidence which directly contradicts existing bloat theories, and gives a more general theory of code growth, showing that the issue is more complicated than it first appears.

Sean Luke (2000)
Code Growth is Not Caused by Introns. In Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference.   Darrell Whitley editor(s).  Pages 228–235.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming, bloat, introns, ineffective code
Notes: Part of whitley:2000:GECCOlb
Abstract:
Genetic programming trees have a strong tendency to grow rapidly and relatively independent of fitness, a serious flaw which has received considerable attention in the genetic programming literature. Much of this literature has implicated introns, subtree structures with no effect on the an individual's fitness assessment. The propagation of inviable code, a certain kind of intron, has been especially linked to tree growth. However this paper presents evidence which shows that denying inviable code the opportunity to propagate actually increases tree growth. The paper argues that rather than causing tree growth, a rise in inviable code is in fact an expected result of tree growth. Lastly, this paper proposes a more general theory of growth for which introns are merely a symptom.

R. Morrison and K. De Jong (2000)
Triggered Hypermutation Revisited. In Proceedings of Congress on Evolutionary Computation.  Pages 1025–1032.  IEEE.
Abstract:
With the emergence of standardized problem generators for dynamic problem environments, we are just starting to systematically measure the performance of different evolutionary-algorithm (EA) extensions against standard classes of problems. We revisit triggered hypermutation, one of the early and most successful implementations of EA's for dynamic environments. Using an implementation of this algorithm, we systematically evaluate the performance of triggered hypermutation on specific test problems across a range of values for the environmental change rate relative to the EA ``time'' measured in generations. We examine the results, identify a probable cause for the algorithm's behavior, and suggest some improvements to the algorithm

K. Murawski, Tomasz Arciszewski, and Kenneth De Jong (2000)
Evolutionary Computation in Structural Design. Journal of Engineering with Computers, 16 : 275 – 286.
Abstract:
The paper provides the results of preliminary research on the application of evolutionary computation to integrated structural design in which a complex design support tool automatically conducts both conceptual and detailed design. In the paper, a brief overview of the state of the art in evolutionary computation and its applications to structural design is provided. Next, Inventor 2000 is described, a unique research and structural design tool developed by the authors at George Mason University that combines an evolutionary computation component with a system for wind forces analysis, and a system for the analysis, design and optimization of steel structures. The paper also presents the results of four structural design experiments conducted with Inventor 2000. The objective of experiments was to investigate various forms of evolutionary computation as applied to structure design. Finally, the paper provides the initial research conclusions and recommendations for further research.

1999 Publications

Tomasz Arciszewski, Kenneth De Jong, and H. Vyas (1999)
Inventive Design in Structural Engineering: Evolutionary Computing Approach. In Proceedings of the Fifth International Conference on the Applications of AI to Civil and Structural Engineering.

Mark Coletti, Tom Lash, Craig Mandsager, and R. Michalski (1999)
A Preliminary Experimental Application of Learnable Evolution Model and Evolutionary Algorithms to Parameter Estimation in Non-linear Digital Signal Filters Design.
George Mason University, technical report MLI 99-5.
[PostScript]  [GZipped PostScript

Kenneth De Jong, Tomasz Arciszewski, and H. Vyas (1999)
An Overview of Evolutionary Computation and Its Applications to Engineering Design. In Proceedings of 6th Workshop of the European Group for Structural Engineering Applications of AI.

Sean Luke, Shugo Hamahashi, and Hiroaki Kitano (1999)
``Genetic'' Programming. In Proceedings of the Genetic and Evolutionary Computation Conference.   Wolfgang Banzhaf, Jason Daida, Agoston E. Eiben, Max H. Garzon, Vasant Honavar, Mark Jakiela, and Robert E. Smith editor(s).  Pages 1098–1105.  Morgan Kaufmann.
[PDF]  [GZipped PostScript
Keywords: genetic programming and evolvable hardware
Notes: GECCO-99 A joint meeting of the eighth international conference on genetic algorithms (ICGA-99) and the fourth annual genetic programming conference (GP-99)
Abstract:
Much of evolutionary computation was inspired by Mendelian genetics. But modern genetics has since advanced considerably, revealing that genes are not simply parameter settings, but interactive cogs in a complex chemical machine. At the same time, an increasing number of evolutionary computation domains are evolving non-parameterized mechanisms such as neural networks or symbolic computer programs. As such, we think modern biological genetics offers much in helping us understand how to evolve such things. In this paper, we present a gene regulation model for Drosophila melanogaster. We then apply gene regulation to evolve deterministic finite-state automata, and show that our approach does well compared to past examples from the literature.

R. Morrison and K. De Jong (1999)
A test problem generator for non-stationary Environments. In Proceedings of Congress on Evolutionary Computation.  Pages 2047–2053.  IEEE.
Abstract:
There has recently been a growing interest in the study of EA performance in changing environments. Studies of EAs in dynamic environments, however, have used only a few limited fitness functions. As has been shown in the study of EAs in static environments, comparative studies of the effectiveness of various EAs in dynamic environments will require more rigorous and standardized test functions. These functions should have a simple representation mechanism, so that a wide range of complexity and sophisticated dynamics can be unambiguously described in an elementary manner. The paper proposes an initial test function generator with these characteristics to facilitate further understanding of the effectiveness of different EA implementations in different types of dynamic environments

Jayshree Sarma and Kenneth De Jong (1999)
The behavior of Spatially Distributed Evolutionary Algorithms in Non-Stationary Environments. In Proceedings of the Genetic and Evolutionary Computation Conference.   Wolfgang Banzhaf, Jason Daida, Agoston E. Eiben, Max H. Garzon, Vasant Honavar, Mark Jakiela, and Robert E. Smith editor(s).  Pages 572–578.  Morgan Kaufmann.
[PostScript]  [GZipped PostScript

R. P. Wiegand (1999)
Applying Diffusion to a Cooperative Coevolutionary Model. In Proceedings of the Fifth International Conference on Parallel Problem Solving fron Nature (PPSN V).  Pages 560–569.  (c) Springer.
[PDF]  [PostScript]  [GZipped PostScript
Abstract:
Perhaps one the newest and of the more interesting cooperative approaches to evolutionary computation which has been more recently explored is the area of mutualism. In mutualistic methods, the problem is subdivided into modular components where each component evolves separately, but is evaluated in terms of the other components. In this way the problem may be cooperatively solved. In an attempt to give this novel approach more adaptive ability, in this paper we explore the effects of adding varying degrees of population diffusion via a mutatable tagging scheme applied to individual chromosomes.

1998 Publications

James Kennedy and William M. Spears (1998)
Matching Algorithms to Problems: An Experimental Test of the Particle Swarm and Some Genetic Algorithms on the Multimodal Problem Generator. In IEEE International Conference on Evolutionary Computation.  Pages 78–83.
[PostScript]  [GZipped PostScript

Sean Luke (1998)
Evolving SoccerBots: A Retrospective. In Proceedings of the 12th Annual Conference of the Japanese Society for Artificial Intelligence.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming
Notes: Invited Article. This short invited paper was meant to complement the more complete GP98 and RoboCup97 papers, and an AI Magazine sidebar, by discussing things that could have been improved from our previous attempt.
Abstract:
In the RoboCup97 robot soccer tournament, we entered a team of softbot programs whose player strategies had been entirely learned by computer. Our team beat other human-coded competitors and received the RoboCup97 Scientific Challenge award. This paper discusses our approach, and details various ways that, in retrospect, it could have been improved.

Sean Luke (1998)
Genetic Programming Produced Competitive Soccer Softbot Teams for RoboCup97. In Genetic Programming 1998: Proceedings of the Third Annual Conference.   John R. Koza, Wolfgang Banzhaf, Kumar Chellapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Garzon, David E. Goldberg, Hitoshi Iba, and Rick Riolo editor(s).  Pages 214–222.  Morgan Kaufmann.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming
Notes: GP-98 This paper is similar to an earlier workshop paper luke:1997:csstcGP. The key difference being that the workshop paper, which was not for a Genetic Programming audience, is short on experimental details and long on introductions to how GP works. There also exists a short invited paper luke:1998:sretro detailing how this experiment could have been improved. Also available is a short sidebar for an AI Magazine article.
Abstract:
At RoboCup, teams of autonomous robots or software softbots compete in simulated soccer matches to demonstrate cooperative robotics techniques in a very difficult, real-time, noisy environment. At the IJCAI/RoboCup97 softbot competition, all entries but ours used human-crafted cooperative decision-making behaviors. We instead entered a softbot team whose high-level decision making behaviors had been entirely evolved using genetic programming. Our team won its first two games against human-crafted opponent teams, and received the RoboCup Scientific Challenge Award. This report discusses the issues we faced and the approach we took to use GP to evolve our robot soccer team for this difficult environment.

Sean Luke, Shugo Hamahashi, Koji Kyoda, and Hiroki Ueda (1998)
Biology: See It Again -- for the First Time. IEEE Intelligent Systems, 13(5) : 6 – 8.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming, biological modelling, DNA
Notes: Invited Article. Argues for a revisitation of the biological roots behind artificial intelligence and evolutionary computation
Abstract:
Computer science owes a huge debt to biological systems. The field itself came about largely as an attempt to understand and replicate the function and abilities of the brain, a complex biological creation. From this early lineage has sprung many subfields derived largely from biological metaphors: computer vision, neural networks, evolutionary computation, robotics, multi-agent studies, and much of artificial intelligence. In some areas, the computer has bested its biological counterparts in efficiency and simplicity. But for many domains, even after decades of hard work, the biological {"}real thing{"} is still superior to the artificial algorithms inspired by it.

Sean Luke and Lee Spector (1998)
A Revised Comparison of Crossover and Mutation in Genetic Programming. In Genetic Programming 1998: Proceedings of the Third Annual Conference.   John R. Koza, Wolfgang Banzhaf, Kumar Chellapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Garzon, David E. Goldberg, Hitoshi Iba, and Rick Riolo editor(s).  Pages 208–213.  Morgan Kaufmann.
[Figures]  [PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming
Notes: GP-98 This paper is a revision of a previous paper luke:1997:ccmGP, with statistical correction and a considerable new set of data. However, the original also has some data that does not appear here, so you may want to consider getting both. Also: Figures 1 through 4 are separated from the rest of the paper in the Gzipped PostScript version (not the PDF version). The figures are listed in the figure URLs below. Finally: if you downloaded a copy of this paper prior to May 20, 1998, its graphs were wrong; get the revised revised version. :-)
Abstract:
In [Luke and Spector 1997] we presented a comprehensive suite of data comparing GP crossover and point mutation over four domains and a wide range of parameter settings. Unfortunately, the results were marred by statistical flaws. This revision of the study eliminates these flaws, with three times as much the data as the original experiments had. Our results again show that crossover does have some advantage over mutation given the right parameter settings (primarily larger population sizes), though the difference between the two surprisingly small. Further, the results are complex, suggesting that the big picture is more complicated than is commonly believed.

Mitchell A. Potter and Kenneth A. De Jong (1998)
The Coevolution of Antibodies for Concept Learning. In Proceedings of the Fifth International Conference on Parallel Problem Solving fron Nature (PPSN V).  Pages 530–539.  (c) Springer.
[PostScript]  [GZipped PostScript

Jayshree Sarma (1998)
An Analysis of Decentralized and Spatially Distributed Genetic Algorithms.
Ph.D. Thesis, George Mason University, Fairfax VA, USA.
[PostScript (single sided)]  [GZipped PostScript (single sided)]  [PostScript (double sided)]  [GZipped PostScript (single sided)

Jayshree Sarma and Kenneth De Jong (1998)
Selection Pressure and Performance in Spatially Distributed Evolutionary Algorithms. In Proceedings of the IEEE World Congress on Computational Intelligence WCCI'98.  Pages 553–557.
[PostScript]  [GZipped PostScript

William M. Spears (1998)
The Role of Mutation and Recombination in Evolutionary Algorithms.
Ph.D. Thesis, George Mason University, Fairfax, VA.
[Downloading Instructions

William M. Spears (1998)
A Compression Algorithm for Probability Transitions Matrices. SIAM Journal of Matrix Analysis and Applications, 20(1) : 60–77.
[PostScript]  [GZipped PostScript
Abstract:
This paper describes a compression algorithm for probability transition matrices. The compressed matrix is itself a probability transition matrix. In general the compression is not error free, but the error appears to be small even for high levels of compression.

William M. Spears and Kenneth A. De Jong (1998)
Dining with GAs: Operator Lunch Theorem. In Proceedings of the Foundations of Genetic Algorithms.  (c) Springer.

1997 Publications

Kenneth A. De Jong, Mitchell A. Potter, and William M. Spears (1997)
Using Problem Generators to Explore the Effects of Epistasis. In Proceedings of the Seventh International Conference on Genetic Algorithms.  Pages 338–345.  Morgan Kaufmann.
[PDF

Pre-1997 Publications

K. Deb and William M. Spears (1997)
Speciation Methods. In The Handbook of Evolutionary Computation.   D. Fogel T. Baeck and Z. Michalewicz editor(s).  IOP Publishing and Oxford University Press.
[PostScript]  [GZipped PostScript

Sean Luke, Charles Hohn, Jonathan Farris, Gary Jackson, and James Hendler (1997)
Co-evolving Soccer Softbot Team Coordination with Genetic Programming. In Proceedings of the First International Workshop on RoboCup, at the International Joint Conference on Artificial Intelligence.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming
Abstract:
Genetic Programming is a promising new method for automatically generating functions and algorithms through natural selection. In contrast to other learning methods, Genetic Programming's automatic programming makes it a natural approach for developing algorithmic robot behaviors. In this paper we present an overview of how we apply Genetic Programming to behavior-based team coordination in the RoboCup Soccer Server domain. The result is not just a hand-coded soccer algorithm, but a team of softbots which have learned on their own how to play a reasonable game of soccer.

Sean Luke and Lee Spector (1997)
A Comparison of Crossover and Mutation in Genetic Programming. In Genetic Programming 1997: Proceedings of the Second Annual Conference.   John R. Koza, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max Garzon, Hitoshi Iba, and Rick L. Riolo editor(s).  Pages 240–248.  Morgan Kaufmann.
[Figures]  [Figures2]  [PDF]  [GZipped PostScript
Keywords: Genetic Programming, Genetic Algorithms
Notes: GP-97. 6-mux, lawn mower, symbolic regression, Santa Fe trail artificial ant. SEE ALSO luke:1998:rcxmGP. The Gzipped PostScript version (.ps.gz) does not come with figures; to get the figures for the PostScript version, use the figures URLs below
Abstract:
This paper presents a large and systematic body of data on the relative effectiveness of mutation, crossover, and combinations of mutation and crossover in genetic programming (GP). The literature of traditional genetic algorithms contains related studies, but mutation and crossover in GP differ from their traditional counterparts in significant ways. In this paper we present the results from a very large experimental data set, the equivalent of approximately 12,000 typical runs of a GP system, systematically exploring a range of parameter settings. The resulting data may be useful not only for practitioners seeking to optimize parameters for GP runs, but also for theorists exploring issues such as the role of {"}building blocks{"} in GP.

Mitchell A. Potter (1997)
The Design and Analysis of a Computational Model of Cooperative Coevolution.
Ph.D. Thesis, George Mason University, Fairfax, VA.
[Abstract]  [Downloading Instructions

Jayshree Sarma and Kenneth De Jong (1997)
An analysis of Local Selection Algorithms in a Spatially Structured Evolutionary Algorithm. In Proceedings of the Seventh International Conference on Genetic Algorithms.  Pages 181–186.  Morgan Kaufmann.
[PostScript]  [GZipped PostScript

Jayshree Sarma and Kenneth De Jong (1997)
Generation Gap Methods. In The Handbook of Evolutionary Computation.   D. Fogel T. Baeck and Z. Michalewicz editor(s).  Pages C2.7:1–C2.7:6.  IOP Publishing and Oxford University Press.
[PostScript]  [GZipped PostScript

William M. Spears (1997)
Recombination Parameters. In The Handbook of Evolutionary Computation.   D. Fogel T. Baeck and Z. Michalewicz editor(s).  IOP Publishing and Oxford University Press.
[PostScript]  [GZipped PostScript

Jerzy Bala, Kenneth A. De Jong, Jeffrey Huang, Haleh Vafaie, and H. Wechsler (1996)
Visual Routine for Eye Detection Using Hybrid Genetic Architectures. In Proceedings of the 13th International Conference on Pattern Recognition.  IEEE Computer Society Press.

Jerzy Bala, Kenneth A. De Jong, Jeffrey Huang, Haleh Vafaie, and H. Wechsler (1996)
Using Learning to Facilitate the Evolution of Features for Recognizing Visual Concepts. Evolutionary Computation : 297–311.   MIT press

Sean Luke and Lee Spector (1996)
Evolving Teamwork and Coordination with Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference.   John R. Koza, David E. Goldberg, David B. Fogel, and Rick L. Riolo editor(s).  Pages 150–156.  MIT Press.
[PDF]  [GZipped PostScript
Keywords: Genetic Programming, Genetic Algorithms
Notes: GP-96
Abstract:
Some problems can be solved only by multi-agent teams. In using genetic programming to produce such teams, one faces several design decisions. First, there are questions of team diversity and of breeding strategy. In one commonly used scheme, teams consist of clones of single individuals; these individuals breed in the normal way and are cloned to form teams during fitness evaluation. In contrast, teams could also consist of distinct individuals. In this case one can either allow free interbreeding between members of different teams, or one can restrict interbreeding in various ways. A second design decision concerns the types of coordination-facilitating mechanisms provided to individual team members; these range from sensors of various sorts to complex communication systems. This paper examines three breeding strategies (clones, free, and restricted) and three coordination mechanisms (none, deictic sensing, and name-based sensing) for evolving teams of agents in the Serengeti world, a simple predator/prey environment. Among the conclusions are the fact that a simple form of restricted interbreeding outperforms free interbreeding in all teams with distinct individuals, and the fact that name-based sensing consistently outperforms deictic sensing.

Sean Luke and Lee Spector (1996)
Evolving Graphs and Networks with Edge Encoding: Preliminary Report. In Late Breaking Papers at the Genetic Programming 1996 Conference Stanford University July 28-31, 1996.   John R. Koza editor(s).  Pages 117–124.  Stanford Bookstore.
[PDF]  [GZipped PostScript
Keywords: genetic algorithms, genetic programming
Notes: GP-96LB The email address for the bookstore for mail orders is mailorder at bookstore.stanford.edu Phone no 415-329-1217 or 800-533-2670
Abstract:
We present an alternative to the cellular encoding technique [Gruau 1992] for evolving graph and network structures via genetic programming. The new technique, called edge encoding, uses edge operators rather than the node operators of cellular encoding. While both cellular encoding and edge encoding can produce all possible graphs, the two encodings bias the genetic search process in different ways; each may therefore be most useful for a different set of problems. The problems for which these techniques may be used, and for which we think edge encoding may be particularly useful, include the evolution of recurrent neural networks, finite automata, and graph-based queries to symbolic knowledge bases. In this preliminary report we present a technical description of edge encoding and an initial comparison to cellular encoding. Experimental investigation of the relative merits of these encoding schemes is currently in progress.

Jayshree Sarma and Kenneth A. De Jong (1996)
An Analysis of the Effects of Neighborhood Size and Shape on Local Selection Algorithms. In Proceedings of the Fourth International Conference on Parallel Problem Solving from Nature (PPSN IV).  Pages 236–244.  (c) Springer.
[PDF]  [PostScript]  [GZipped PostScript

William M. Spears and Kenneth A. De Jong (1996)
Analyzing GAs Using Markov Models with Semantically Ordered and Lumped States. In Foundations of Genetic Algorithms.
[PDF]  [PostScript]  [GZipped PostScript

Lee Spector and Sean Luke (1996)
Culture Enhances the Evolvability of Cognition. In Cognitive Science (CogSci) 1996 Conference Proceedings.
[PDF]  [GZipped PostScript
Keywords: Genetic Programming, Genetic Algorithms
Abstract:
This paper discusses the role of culture in the evolution of cognitive systems. We define {"}culture{"} as any information transmitted between individuals and between generations by non-genetic means. Experiments are presented that use genetic programming systems that include special mechanisms for cultural transmission of information. These systems evolve computer programs that perform cognitive tasks including mathematical function mapping and action selection in a virtual world. The data show that the presence of culture-supporting mechanisms can have a clear beneficial impact on the evolvability of correct programs. The implications that these results may have for cognitive science are briefly discussed.

Lee Spector and Sean Luke (1996)
Cultural Transmission of Information in Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference.   John R. Koza, David E. Goldberg, David B. Fogel, and Rick L. Riolo editor(s).  Pages 209–214.  MIT Press.
[PDF]  [GZipped PostScript
Keywords: Genetic Programming, Genetic Algorithms
Notes: GP-96 Discussion of this paper appeared as part of the Scientific American (Oct. 96) column {"}Computing: Programming with Primordial Ooze{"} (p. 50).
Abstract:
This paper shows how the performance of a genetic programming system can be improved through the addition of mechanisms for non-genetic transmission of information between individuals (culture). Teller has previously shown how genetic programming systems can be enhanced through the addition of memory mechanisms for individual programs [Teller 1994]; in this paper we show how Teller's memory mechanism can be changed to allow for communication between individuals within and across generations. We show the effects of indexed memory and culture on the performance of a genetic programming system on a symbolic regression problem, on Koza's Lawnmower problem, and on Wumpus world agent problems. We show that culture can reduce the computational effort required to solve all of these problems. We conclude with a discussion of possible improvements.

Bradley C. Wallet, David J. Marchette, Jeffery L. Solka, and Edward J. Wegman (1996)
A Genetic Algorithm for Best Subset Selection in Linear Regression. In Proceedings of the 28th Symposium on the Interface.
[Zipped PostScript

Jerzy Bala, Kenneth A. De Jong, J. Haung, Haleh Vafaie, and H. Wechsler (1995)
Hybrid Learning Using Genetic Algorithms and Decision Trees for Pattern Classification. In Proceedings of the 14th International Joint Conference on Artificial Intelligence.
[PDF]  [PostScript]  [GZipped PostScript

Kenneth A. De Jong and Mitchell A. Potter (1995)
Complex Structures via Cooperative Coevolution. In Proceedings of the Fourth Annual Conference on Evolutionary Programming.
[PostScript

Kenneth A. De Jong and Jayshree Sarma (1995)
On Decentralizing Selection Algorithms. In Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95).  Pages 17–23.  Morgan Kaufmann.
[PDF]  [PostScript]  [GZipped PostScript

Mitchell A. Potter and Kenneth A. De Jong (1995)
Evolving Neural Networks with Collaborative Species. In Proceedings of the 1995 Summer Computer Simulation Conference.  Pages 340–345.  The Society for Computer Simulation.
[PostScript

Mitchell A. Potter, Kenneth A. De Jong, and John J. Grefenstette (1995)
Coevolutionary Approach to Learning Sequential Decision Rules. In Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95).  Pages 366–372.  Morgan Kaufmann.
[PostScript

William M. Spears (1995)
Adapting Crossover in Evolutionary Algorithms. In Proceedings of the Fourth Annual Conference on Evolutionary Programming.
[GZipped PostScript

Haleh Vafaie and Kenneth A. De Jong (1995)
Genetic Algorithms as a Tool for Restructuring Feature Space Representations. In Proceedings of the International Conference on Tools with AI.  IEEE Computer Society Press.
[PDF]  [PostScript]  [GZipped PostScript

Kenneth A. De Jong, William M. Spears, and Diana F. Gordon (1994)
Using Markov Chains to Analyze GAFOs. In Proceedings of FOGA94.  Pages 115–137.  Morgan Kaufmann.
[PDF
Abstract:
Our theoretical understanding of the properties of genetic algorithms (GAs) being used for function optimization (GAFOs) is not as strong as we would like. Traditional schema analysis provides some first order insights, but doesn't capture the non-linear dynamics of the GA search process very well. Markov chain theory has been used primarily for steady state analysis of GAs. In this paper we explore the use of transient Markov chain analysis to model and understand the behavior of finite population GAFOs observed while in transition to steady states. This approach appears to provide new insights into the circumstances under which GAFOs will (will not) perform well. Some preliminary results are presented and an initial evaluation of the merits of this approach is provided.

John Grefenstette and Alan Schultz (1994)
Evolutionary Approach to Learning in Robots. In Machine Learning Workshop on Robot Learning.
[GZipped PostScript

I. Imam and Haleh Vafaie (1994)
An Empirical Comparison Between Global And Greedy-like Search For Feature Selection. In Proceedings of the Florida AI Research Symposium (FLAIRS-94).  Pages 66–70.
[PDF]  [PostScript]  [GZipped PostScript

Mitchell A. Potter and Kenneth A. De Jong (1994)
A Cooperative Coevolutionary Approach to Function Optimization. In Proceedings of the Third Conference on Parallel Problem Solving from Nature (PPSN III).  Pages 249–257.  (c) Springer.
[PostScript

Alan C. Schultz (1994)
Learning Robot Behaviors Using Genetic Algorithms. In Intelligent Automation and Soft Computing: Trends in Research, Development, and Applications, v1, Proceedings of the First World Automation Congress.  Pages 607–612.  TSI Press.
[GZipped PostScript

Alan Schultz and John Grefenstette (1994)
Evolving Robot Behaviors. In Proceedings of the 1994 Artificial Life Conference.
[GZipped PostScript

William M. Spears (1994)
Simple Subpopulation Schemes. In Proceedings of the Third Annual Conference on Evolutionary Programming.  Pages 296–307.  World Scientific.
[GZipped PostScript

Haleh Vafaie and Kenneth A. De Jong (1994)
Improving a Rule Learning System Using Genetic Algorithms. In Machine Learning: A Multistrategy Approach.  Pages 453–470.  Morgan Kaufmann.
[PDF]  [PostScript]  [GZipped PostScript

Haleh Vafaie and I. Imam (1994)
Feature Selection Methods: Genetic Algorithms vs. Greedy-like Search. In Proceedings of the International Conference on Fuzzy and Intelligent Control Systems.
[PDF]  [PostScript]  [GZipped PostScript

Kenneth A. De Jong and William M. Spears (1993)
On the State of Evolutionary Computation. In Proceedings of the 1993 International Conference on Genetic Algorithms.  Pages 618–623.
[PDF
Abstract:
In the past few years the evolutionary computation landscape has been rapidly changing as a result of increased levels of interaction between various research groups and the injection of new ideas which challenge old tenets. The effect has been simultaneously exciting, invigorating, annoying, and bewildering to the old-timers as well as the new-comers to the field. Emerging out of all of this activity are the beginnings of some structure, some common themes, and some agreement on important open issues. We attempt to summarize these emergent properties in this paper.

Kenneth A. De Jong, William M. Spears, and Diana F. Gordon (1993)
Using Genetic Algorithms for Concept Learning. Machine Learning, 13 : 161–188.   J. Grefenstette editor(s).   Kluwer Academic
[GZipped PostScript
Abstract:
In this paper, we explore the use of genetic algorithms (GAs) as a key element in the design and implementation of robust concept learning systems. We describe and evaluate a GA-based system called GABIL that continually learns and refines concept classification rules from its interaction with the environment. The use of GAs is motivated by recent studies showing the effects of various forms of bias built into different concept learning systems, resulting in systems that perform well on certain concept classes (generally, those well matched to the biases) and poorly on others. By incorporating a GA as the underlying adaptive search mechanism, we are able to construct a concept learning system that has a simple, unified architecture with several important features. First, the system is surprisingly robust even with minimal bias. Second, the system can be easily extended to incorporate traditional forms of bias found in other concept learning systems. Finally, the architecture of the system encourages explicit representation of such biases and, as a result, provides for an important additional feature: the ability to dynamically adjust system bias. The viability of this approach is illustrated by comparing the performance of GABIL with that of four other more traditional concept learners (AQ14, C4.5, ID5R, and IACL) on a variety of target concepts. We conclude with some observations about the merits of this approach and about possible extensions.

Alan C. Schultz and John J. Grefenstette (1993)
Learning Action Models as Reactive Behaviors. In Proceeding of the Workshop on Learning Action Models, AAAI-93.

Alan C. Schultz, John J. Grefenstette, and Kenneth A. De Jong (1993)
Test and Evaluation by Genetic Algorithms. IEEE Expert : 9–14.

Haleh Vafaie and Kenneth A. De Jong (1993)
Robust Feature Selection Algorithms. In Proceedings of the International Conference on Tools with AI.  Pages 356–364.  IEEE Computer Society Press.
[PDF]  [PostScript]  [GZipped PostScript

DeJong William M. Spears, T. Baeck, D. Fogel, and Hugo de Garis (1993)
An Overview of Evolutionary Computation. In Proceedings of European Conference on Machine Learning.  Pages 442–459.
[PDF
Abstract:
Evolutionary computation uses computational models of evolutionary processes as key elements in the design and implementation of computer based problem solving systems. In this paper we provide an overview of evolutionary computation, and describe several evolutionary algorithms that are currently of interest. Important similarities and differences are noted, which lead to a discussion of important issues that need to be resolved, and items for future research.

Kenneth A. De Jong and Jayshree Sarma (1992)
Generation Gaps Revisited. In Foundations of Genetic Algorithms - 2.   Darrell Whitley editor(s).  Pages 19–28.  Morgan Kaufmann.
[PDF]  [PostScript]  [GZipped PostScript

Kenneth A. De Jong and William M. Spears (1992)
A Formal Analysis of the Role of Multi-Point Crossover in Genetic Algorithms. Annals of Mathematics and Artificial Intelligence Journal : 1–26.
[PDF
Abstract:
On the basis of early theoretical and empirical studies, genetic algorithms have typically used 1 and 2-point crossover operators as the standard mechanisms for implementing recombination. However, there have been a number of recent studies, primarily empirical in nature, which have shown the benefits of crossover operators involving a higher number of crossover points. From a traditional theoretical point of view, the most surprising of these new results relate to uniform crossover, which involves on the average L / 2 crossover points for strings of length L. In this paper we extend the existing theoretical results in an attempt to provide a broader explanatory and predictive theory of the role of multi-point crossover in genetic algorithms. In particular, we extend the traditional disruption analysis to include two general forms of multi-point crossover: n-point crossover and uniform crossover. We also analyze two other aspects of multi-point crossover operators, namely, their recombination potential and exploratory power. The results of this analysis provide a much clearer view of the role of multi-point crossover in genetic algorithms. The implications of these results on implementation issues and performance are discussed, and several directions for further research are suggested.

Mitchell A. Potter (1992)
A Genetic Cascade-Correlation Learning Algorithm. In Proceedings of COGANN-92 International Workshop on Combinations of Genetic Algorithms and Neural Networks.  Pages 123–133.  IEEE Computer Society Press.
[PostScript]  [GZipped PostScript

Alan C. Schultz and John J. Grefenstette (1992)
Using a Genetic Algorithm to Learn Behaviors for Autonomous Vehicles. In Proceedings of the American Institute of Aeronautics and Astronautics Guidance, Navigation and Control Conference.  Pages 739–749.
[Zipped PostScript

Alan C. Schultz, John J. Grefenstette, and Kenneth A. De Jong (1992)
Adaptive Testing of Controllers for Autonomous Vehicles. In Proceedings of the Symposium on Autonomous Underwater Vehicles Technology.  Pages 158–164.  IEEE Press.
[Zipped PostScript

William M. Spears (1992)
Crossover or Mutation?. In Proceedings of the Foundations of Genetic Algorithms Workshop.   D. Whitley editor(s).  Pages 221–237.  Morgan Kaufmann.
[GZipped PostScript

William M. Spears and Kenneth A. De Jong (1992)
Using Genetic Algorithms for Supervised Concept Learning. Chapter in Artificial Intelligence Methods and Applications.   N.G. Bourbakis editor(s).  World Scientific.
[GZipped PostScript

William M. Spears and Diana F. Gordon (1992)
Is Consistency Harmful?. In Proceedings of the Biases in Inductive Learning Workshop for the Machine Learning Conference.
[GZipped PostScript

Haleh Vafaie and Kenneth A. De Jong (1992)
Genetic Algorithms as a Tool for Feature Selection in Machine Learning. In Proceedings of the International Conference on Tools with AI.  Pages 200–204.  IEEE Computer Society Press.
[PDF]  [PostScript]  [GZipped PostScript

Kenneth A. De Jong and William M. Spears (1991)
Learning Concept Classification Rules Using Genetic Algorithms. In Proceedings of the International Joint Conference on Artificial Intelligence.  Pages 651–656.
[PDF
Abstract:
In this paper we explore the use of an adaptive search technique (genetic algorithms) to construct a system GABIL which continually learns and refines concept classification rules from its interaction with the environment. The performance of the system is measured on a set of concept learning problems and compared with the performance of two existing systems: ID5R and C4.5. Preliminary results support that, despite minimal system bias, GABIL is an effective concept learner and is quite competitive with ID5R and C4.5 as the target concept increases in complexity.

Alan C. Schultz (1991)
Using a Genetic Algorithm to Learn Strategies for Collision Avoidance and Local Navigation. In Proceedings of the Seventh International Symposium on Unmanned Untethered Submersible Technology.  Pages 213–225.
[Zipped PostScript

Alan C. Schultz (1991)
Adapting the Evaluation Space to Improve Global Learning. In Proceedings of the Fourth International Conference on Genetic Algorithms.  Pages 158–164.  Morgan Kaufmann.
[Zipped PostScript

William M. Spears and V. Anand (1991)
A Study of Crossover Operators in Genetic Programming. In Proceedings of the Sixth International Symposium on Methodologies for Intelligent Systems.  Pages 409–418.
[GZipped PostScript

William M. Spears and Kenneth A. De Jong (1991)
On the Virtues of Parameterized Uniform Crossover. In Proceedings of the 4th International Conference on Genetic Algorithms.  Pages 230–236.  Morgan Kaufman.
[PDF
Abstract:
Traditionally, genetic algorithms have relied upon 1 and 2-point crossover operators. Many recent empirical studies, however, have shown the benefits of higher numbers of crossover points. Some of the most intriguing recent work has focused on uniform crossover, which involves on the average L/2 crossover points for strings of length L. Theoretical results suggest that, from the view of hyperplane sampling disruption, uniform crossover has few redeeming features. However, a growing body of experimental evidence suggests otherwise. In this paper, we attempt to reconcile these opposing views of uniform crossover and present a framework for understanding its virtues.

William M. Spears and D. Gordon (1991)
Adaptive Strategy Selection for Concept Learning. In Multistrategy Learning (MSL-91) Workshop.  Pages 231–246.
[GZipped PostScript

Haleh Vafaie and Kenneth A. De Jong (1991)
Improving the Performance of a Rule Induction System Using Genetic Algorithms. In Proceedings of the First International Workshop on Multistrategy Learning.  Pages 305–316.
[PDF]  [PostScript]  [GZipped PostScript

Jim Antonisse (1990)
A Grammar-Based Genetic Algorithm. In Foundations of the Genetic Algorithm Workshop.

Jim Antonisse (1990)
Unsupervised Sensor Credit Assignment in Knowledge-Based Sensor-Fusion Systems. In IEEE Systems, Man and Cybernetics.

Kenneth A. De Jong and William M. Spears (1990)
An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms. In International Workshop Parallel Problem Solving from Nature.  Pages 38–47.
[PDF
Abstract:
In this paper we present some theoretical and empirical results on the interacting roles of population size and crossover in genetic algorithms. We summarize recent theoretical results on the disruptive effect of two forms of multi-point crossover: npoint crossover and uniform crossover. We then show empirically that disruption analysis alone is not sufficient for selecting appropriate forms of crossover. However, by taking into account the interacting effects of population size and crossover, a general picture begins to emerge. The implications of these results on implementation issues and performance are discussed, and several directions for further research are suggested.

John J. Grefenstette, Connie L. Ramsey, and Alan C. Schultz (1990)
Learning sequential decision rules using simulation models and competition. Machine Learning : 355–381.   Kluwer Academic Publishers
[Zipped PostScript

Alan C. Schultz and John J. Grefenstette (1990)
Improving tactical plans with genetic algorithms. In Proceedings of IEEE Conference on Tools for Artificial Intelligence.  Pages 328–334.  IEEE Society Press.
[Zipped PostScript

Alan C. Schultz, Connie L. Ramsey, and John J. Grefenstette (1990)
Simulation-assisted learning by competition: Effects of noise differences between training model and target environment. In Proceedings of the Seventh International Conference on Machine Learning.  Pages 211–215.  Morgan Kaufmann.
[Zipped PostScript

William M. Spears and Kenneth A. De Jong (1990)
Using Genetic Algorithms for Supervised Concept Learning. In IEEE 1990 Second International Conference on Tools for Artificial Intelligence.  Pages 335–341.
[PDF
Abstract:
Genetic Algorithms (GAs) have traditionally been used for non-symbolic learning tasks. In this paper we consider the application of a GA to a symbolic learning task, supervised concept learning from examples. A GA concept learner (GABL) is implemented that learns a concept from a set of positive and negative examples. GABL is run in a batch incremental mode to facilitate comparison with an incremental concept learner, ID5R. Preliminary results support that, despite minimal system bias, GABL is an effective concept learner and is quite competitive with ID5R as the target concept increases in complexity.

William M. Spears and Kenneth A. De Jong (1990)
An Analysis of Multi-Point Crossover. In Proceedings of the Foundations of Genetic Algorithms Workshop.
[PDF
Abstract:
In this paper we present some theoretical results on two forms of multi-point crossover: n-point crossover and uniform crossover. This analysis extends the work from De Jong's thesis, which dealt with disruption of n-point crossover on 2nd order hyperplanes. We present various extensions to this theory, including 1) an analysis of the disruption of n-point crossover on kth order hyperplanes; 2) the computation of tighter bounds on the disruption caused by n-point crossover, by handling cases where parents share critical allele values; and 3) an analysis of the disruption caused by uniform crossover on kth order hyperplanes. The implications of these results on implementation issues and performance are discussed, and several directions for further research are suggested.

William M. Spears and Kenneth A. De Jong (1990)
Using Neural Networks and Genetic Algorithms as Heuristics for NP-Complete Problems. In Proceedings of the International Joint Conference on Neural Networks.  Pages 118–121.
[PDF
Abstract:
Paradigms for using neural networks (NNs) and genetic algorithms (GAs) to heuristically solve boolean satisfiability (SAT) problems are presented. Since SAT is NP-Complete, any other NP-Complete problem can be transformed into an equivalent SAT problem in polynomial time, and solved via either paradigm. This technique is illustrated for Hamiltonian circuit (HC) problems.

Jim Antonisse (1989)
A New Interpretation of Schema Notation that Overturns the Binary Encoding Constraint. In Proceedings of the Third International Conference on Genetic Algorithms.

Kenneth A. De Jong and William M. Spears (1989)
Using Genetic Algorithms to Solve NP-Complete Problems. In Proceedings of the Third International Conference on Genetic Algorithms.  Pages 124–132.
[PDF
Abstract:
A strategy for using Genetic Algorithms (GAs) to solve NP-complete problems is presented. The key aspect of the approach taken is to exploit the observation that, although all NP-complete problems are equally difficult in a general computational sense, some have much better GA representations than others, leading to much more successful use of GAs on some NP-complete problems than on others. Since any NP-complete problem can be mapped into any other one in polynomial time, the strategy described here consists of identifying a canonical NP-complete problem on which GAs work well, and solving other NP-complete problems indirectly by mapping them onto the canonical problem. Initial empirical results are presented which support the claim that the Boolean Satisfiability Problem (SAT) is a GA effective canonical problem, and that other NP complete problems with poor GA representations can be solved efficiently by mapping them first onto SAT problems.

Jim Antonisse and K. S. Keller (1988)
Dynamic Evaluation of Sources in Rule-Based Sensor Fusion Systems. In Proceedings of the 1988 Data Fusion Symposium.

Kenneth A. De Jong and Alan C. Schultz (1988)
Using Experience-Based Learning in Game Playing. In Proceedings of the Fifth International Machine Learning Conference.  Pages 284–290.
[GZipped PostScript

Jim Antonisse and K. S. Keller (1987)
Genetic Operations for High-Level Knowledge Representations. In Proceedings of the Second International Conference on Genetic Algorithms.

K. S. Keller and Jim Antonisse (1987)
Prediction-based Competitive Learning in the M2 System. In Proceedings of the 3rd Annual Expert Systems in Government Conference.

Jim Antonisse and K. S. Keller (1986)
Dynamic Evaluation of Imprecisely Specified Knowledge. In Proceedings of the 7th Annual Digital Avionics Systems Conference.

 
2009   2008   2007   2006   2005   2004   2003   2002   2001   2000   1999   1998   1997   Pre-1997  



 
  home     people     publications     tools     research     activities     community  




Last updated:    Thursday April 9, 2009 webmaster