Category: Genetic Programming and Evolvable Machines

Tina Yu, David Davis, Cem Baydar, Rajkumar Roy (eds): Evolutionary Computation in Practice: Studies in Computational Intelligence

Tina Yu, David Davis, Cem Baydar, Rajkumar Roy (eds): Evolutionary Computation in Practice: Studies in Computational Intelligence
Content Type Journal ArticleCategory Book ReviewDOI 10.1007/s10710-008-9068-8Authors
Larry M. Deschaine, Science Applic…

Tina Yu, David Davis, Cem Baydar, Rajkumar Roy (eds): Evolutionary Computation in Practice: Studies in Computational Intelligence

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-008-9068-8
  • Authors
    • Larry M. Deschaine, Science Applications International Corporation Aiken SC USA

Scaling of program functionality

Abstract  The distribution of fitness values (landscapes) of programs tends to a limit as the programs get bigger. We use Markov chain
convergence theorems to give general upper bounds on the length of programs needed for convergence. How bi…

Abstract  The distribution of fitness values (landscapes) of programs tends to a limit as the programs get bigger. We use Markov chain
convergence theorems to give general upper bounds on the length of programs needed for convergence. How big programs need
to be to approach the limit depends on the type of the computer they run on. We give bounds (exponential in N, N log N and smaller) for five computer models: any, average or amorphous or random, cyclic, bit flip and four functions (AND, NAND,
OR and NOR). Programs can be treated as lookup tables which map between their inputs and their outputs. Using this we prove
similar convergence results for the distribution of functions implemented by linear computer programs. We show most functions
are constants and the remainder are mostly parsimonious. The effect of ad-hoc rules on genetic programming (GP) are described
and new heuristics are proposed. We give bounds on how long programs need to be before the distribution of their functionality
is close to its limiting distribution, both in general and for average computers. The computational importance of destroying
information is discussed with respect to reversible and quantum computers. Mutation randomizes a genetic algorithm population
in


\frac14(l+1)(log (l)+4)

generations. Results for average computers and a model like genetic programming are confirmed experimentally.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9065-y
  • Authors
    • W. B. Langdon, University of Essex Mathematical and Biological Sciences and Computing and Electronic Systems Essex CO4 3SQ UK

Coevolutionary bid-based genetic programming for problem decomposition in classification

Abstract  In this work a cooperative, bid-based, model for problem decomposition is proposed with application to discrete action domains
such as classification. This represents a significant departure from models where each individual constr…

Abstract  In this work a cooperative, bid-based, model for problem decomposition is proposed with application to discrete action domains
such as classification. This represents a significant departure from models where each individual constructs a direct input-outcome
map, for example, from the set of exemplars to the set of class labels as is typical under the classification domain. In contrast,
the proposed model focuses on learning a bidding strategy based on the exemplar feature vectors; each individual is associated
with a single discrete action and the individual with the maximum bid ‘wins’ the right to suggest its action. Thus, the number
of individuals associated with each action is a function of the intra-action bidding behaviour. Credit assignment is designed
to reward correct but unique bidding strategies relative to the target actions. An advantage of the model over other teaming
methods is its ability to automatically determine the number of and interaction between cooperative team members. The resulting model shares several traits with
learning classifier systems and as such both approaches are benchmarked on nine large classification problems. Moreover, both
of the evolutionary models are compared against the deterministic Support Vector Machine classification algorithm. Performance
assessment considers the computational, classification, and complexity characteristics of the resulting solutions. The bid-based
model is found to provide simple yet effective solutions that are robust to wide variations in the class representation. Support
Vector Machines and classifier systems tend to perform better under balanced datasets albeit resulting in black-box solutions.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9067-9
  • Authors
    • Peter Lichodzijewski, Dalhousie University Faculty of Computer Science 6050 University Ave. Halifax NS Canada B3H 1W5
    • Malcolm I. Heywood, Dalhousie University Faculty of Computer Science 6050 University Ave. Halifax NS Canada B3H 1W5

Introduction to Special Section on Evolutionary Computation in Games

Introduction to Special Section on Evolutionary Computation in Games
Content Type Journal ArticleCategory EditorialDOI 10.1007/s10710-008-9066-xAuthors
Moshe Sipper, Ben-Gurion University Department of Computer Science Beer-Sheva 84105 IsraelMario G…

Introduction to Special Section on Evolutionary Computation in Games

  • Content Type Journal Article
  • Category Editorial
  • DOI 10.1007/s10710-008-9066-x
  • Authors
    • Moshe Sipper, Ben-Gurion University Department of Computer Science Beer-Sheva 84105 Israel
    • Mario Giacobini, University of Torino Department of Animal Production, Epidemiology and Ecology, Faculty of Veterinary Medicine Torino Italy

Evolving strategy for a probabilistic game of imperfect information using genetic programming

Abstract  We provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. Ant Wars contestants are virtual ants collecting food on a grid board in the presence
of a competing ant. BrilliAnt has…

Abstract  We provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. Ant Wars contestants are virtual ants collecting food on a grid board in the presence
of a competing ant. BrilliAnt has been evolved through a competitive one-population coevolution using genetic programming
and fitnessless selection. In this paper, we detail the evolutionary setup that lead to BrilliAnt’s emergence, assess its
direct and indirect human-competitiveness, and describe the behavioral patterns observed in its strategy.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9062-1
  • Authors
    • Wojciech Jaśkowski, Poznan University of Technology Institute of Computing Science Poznan Poland
    • Krzysztof Krawiec, Poznan University of Technology Institute of Computing Science Poznan Poland
    • Bartosz Wieloch, Poznan University of Technology Institute of Computing Science Poznan Poland

The 2007 IEEE CEC simulated car racing competition

Abstract  This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary
Computation. Both the game that was used as the domain for the competition, the controllers submitted as …

Abstract  This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary
Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition
and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational
intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process,
we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9063-0
  • Authors
    • Julian Togelius, Dalle Molle Institute for Artificial Intelligence (IDSIA) Galleria 2 6928 Manno-Lugano Switzerland
    • Simon Lucas, University of Essex Department of Computing and Electronic Systems Colchester CO4 3SQ UK
    • Ho Duc Thang, University of Nottingham Department of Computer Science Nottingham UK
    • Jonathan M. Garibaldi, University of Nottingham Department of Computer Science Nottingham UK
    • Tomoharu Nakashima, Osaka Prefecture University Graduate School of Engineering Gakuen-cho 1-1 Naka-ku Sakai 599-8531 Japan
    • Chin Hiong Tan, National University of Singapore Singapore Singapore
    • Itamar Elhanany, University of Tennessee Department of Electrical Engineering and Computer Science Knoxville TN USA
    • Shay Berant, Binatix, Inc. Palo Alto CA USA
    • Philip Hingston, Edith Cowan University Joondalup Australia
    • Robert M. MacCallum, Imperial College London SW7 2AZ UK
    • Thomas Haferlach, Imperial College London SW7 2AZ UK
    • Aravind Gowrisankar, University of Texas Department of Computer Sciences Austin TX USA
    • Pete Burrow, University of Essex Department of Computing and Electronic Systems Colchester CO4 3SQ UK

Russel C. Eberhart, Yuhui Shi: Computational Intelligence: Concepts to Implementation

Russel C. Eberhart, Yuhui Shi: Computational Intelligence: Concepts to Implementation
Content Type Journal ArticleCategory Book ReviewDOI 10.1007/s10710-008-9064-zAuthors
Pablo A. Estévez, University of Chile Faculty of Physical and Mathematical Sc…

Russel C. Eberhart, Yuhui Shi: Computational Intelligence: Concepts to Implementation

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-008-9064-z
  • Authors
    • Pablo A. Estévez, University of Chile Faculty of Physical and Mathematical Sciences, Department of Electrical Engineering Avenida Tupper 2007 P.O. Box 412-3 Santiago Chile

Evolving encapsulated programs as shared grammars

Abstract  Facilitating the discovery and reuse of modular building blocks is generally regarded as the key to achieving better scalability
in genetic programming (GP). A precedent for this exists in biology, where complex designs are the pro…

Abstract  Facilitating the discovery and reuse of modular building blocks is generally regarded as the key to achieving better scalability
in genetic programming (GP). A precedent for this exists in biology, where complex designs are the product of developmental
processes that can also be abstractly modeled as generative grammars. We introduce shared grammar evolution (SGE), which aligns
grammatical development with the common application of grammars in GP as a means of establishing declarative bias. Programs
are derived from and represented by a global context-free grammar that is transformed and extended according to another, user-defined
grammar. Grammatical productions and the subroutines they encapsulate are shared between programs, which enables their reuse
without reevaluation and can significantly reduce total evaluation time for large programs and populations. Several variants
of SGE employing different strategies for controlling solution size and diversity are tested on classic GP problems. Results
compare favorably against GP and newer techniques, with the best results obtained by promoting diversity between derived programs.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9061-2
  • Authors
    • Martin H. Luerssen, Flinders University of South Australia School of Informatics and Engineering GPO Box 2100 Adelaide 5001 Australia
    • David M. W. Powers, Flinders University of South Australia School of Informatics and Engineering GPO Box 2100 Adelaide 5001 Australia