EC lab Publications (long)

Kenneth A. De Jong's Dissertation

2007   2006   2005   2004   2003   2002   2001   2000   1999   1998   1997   1996   1995   Pre-1995

2007 Publications

Liviu Panait, Sean Luke, and R. Paul Wiegand (2007)

Biasing Coevolutionary Search for Optimal Multiagent Behaviors. IEEE Transactions on Evolutionary Computation : (in press).
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.

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.

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)

Emperical Study on the Effects of Synthetic Social Structures on Teams of Autonomous Vehiles. 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.

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] 

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 Cooevolutionary 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 .
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 Congnition. In Proceedings of World Congress on Computational Intelligence`.

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.

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 Fundaments. 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 technologycapable of adaptation, self-assembly, and self-repair hasfuelled renewed interest in using approaches inspired by developmentalbiology. To meet this need, a new eld, calledComputational Development (CD), has emerged. Its focus ison adapting processes and mechanisms from developmentalbiology so as to help us build scalable, complex technology.Due to the embryonic nature of the eld, however, researchinvestigating the potential of such approaches for di erentproblem domains is crucial to its success. In this paper, theplausibility of applying a developmental biology-inspired approachto the demanding problem domain of reactive robotcontrol is explored. Using developmental genetics as a sourceof inspiration, a model of genetic regulatory networks is usedin conjunction with a spatially distributed evolutionary algorithmto evolve real-time robot controllers for tasks suchas 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 ta ke advantage of more information. We introduce a variant of the cooperative target observation domain w hich is free of such constraints. We propose two algorithms, inspired by K-means clustering and hill-cl imbing respectively, which are scalable in degree of decentralization. Neither algorithm consistently o utperforms 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 combinatio 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 algorithmand the external objectivemetricmeasuring 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 BiasWhen 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 learningexperience 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.

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 behaviour 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 Colective 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] 

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) .   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, discreteevent 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] 

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 di erent 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 di cult 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 re ective 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 di cult multi-modal test functions, the multi-representation island model does no worse than a standard EA on all of the functions, and produces signi cant 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.

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] 

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.

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] 

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] 

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)

Ant Foraging Revisited. In Proceedings of the Second International Workshop on the Mathematics and Algorithms of Social Insects.

Liviu Panait and Sean Luke (2003)

Evolving Foraging Behaviors. In Proceedings of the Second International Workshop on the Mathematics and Algorithms of Social Insects.

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 algorithmfails 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 formany 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-ofmind 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 eversmaller 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, behaviorbased 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.

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 coevol