Category: Genetic Programming and Evolvable Machines

Open issues in genetic programming

Abstract  It is approximately 50 years since the first computational experiments were conducted in what has become known today as the
field of Genetic Programming (GP), twenty years since John Koza named and popularised the method, and …

Abstract  

It is approximately 50 years since the first computational experiments were conducted in what has become known today as the
field of Genetic Programming (GP), twenty years since John Koza named and popularised the method, and ten years since the
first issue appeared of the Genetic Programming & Evolvable Machines journal. In particular, during the past two decades there has been a significant range and volume of development in the theory
and application of GP, and in recent years the field has become increasingly applied. There remain a number of significant
open issues despite the successful application of GP to a number of challenging real-world problem domains and progress in
the development of a theory explaining the behavior and dynamics of GP. These issues must be addressed for GP to realise its
full potential and to become a trusted mainstream member of the computational problem solving toolkit. In this paper we outline
some of the challenges and open issues that face researchers and practitioners of GP. We hope this overview will stimulate
debate, focus the direction of future research to deepen our understanding of GP, and further the development of more powerful
problem solving algorithms.

  • Content Type Journal Article
  • Pages 339-363
  • DOI 10.1007/s10710-010-9113-2
  • Authors
    • Michael O’Neill, University College Dublin Complex & Adaptive Systems Lab, School of Computer Science & Informatics Dublin Ireland
    • Leonardo Vanneschi, University of Milano-Bicocca Milan Italy
    • Steven Gustafson, GE Global Research Niskayuna NY USA
    • Wolfgang Banzhaf, Memorial University of Newfoundland St. John’s NL Canada

Grammar-based Genetic Programming: a survey

Abstract  Grammar formalisms are one of the key representation structures in Computer Science. So it is not surprising that they have
also become important as a method for formalizing constraints in Genetic Programming (GP). Practical gramma…

Abstract  

Grammar formalisms are one of the key representation structures in Computer Science. So it is not surprising that they have
also become important as a method for formalizing constraints in Genetic Programming (GP). Practical grammar-based GP systems
first appeared in the mid 1990s, and have subsequently become an important strand in GP research and applications. We trace
their subsequent rise, surveying the various grammar-based formalisms that have been used in GP and discussing the contributions
they have made to the progress of GP. We illustrate these contributions with a range of applications of grammar-based GP,
showing how grammar formalisms contributed to the solutions of these problems. We briefly discuss the likely future development
of grammar-based GP systems, and conclude with a brief summary of the field.

  • Content Type Journal Article
  • Pages 365-396
  • DOI 10.1007/s10710-010-9109-y
  • Authors
    • Robert I. McKay, Seoul National University Structural Complexity Lab, School of Computer Science and Engineering Seoul Korea
    • Nguyen Xuan Hoai, Le Quy Don University Department of Computer Science Hanoi Vietnam
    • Peter Alexander Whigham, University of Otago Department of Information Science Dunedin NZ New Zealand
    • Yin Shan, Medicare Australia Canberra Australia
    • Michael O’Neill, University College Dublin Complex and Adaptive Systems Lab, School of Computer Science and Informatics Dublin Ireland

Autonomous experimental design optimization of a flapping wing

Abstract  Applying evolutionary computation to the optimization of aerodynamic properties of shapes and structures usually involves
computational fluid dynamics simulations. The simulation of the physical properties of a possible solution ha…

Abstract  

Applying evolutionary computation to the optimization of aerodynamic properties of shapes and structures usually involves
computational fluid dynamics simulations. The simulation of the physical properties of a possible solution has various advantages.
However, like in all simulations various restrictions and simplifications exist even for the most advanced simulation methods.
Furthermore, the high computational demand very often does not allow high fidelity simulations together with numerical optimization
methods. In this paper, we present an approach to combine evolutionary algorithms with physical measurements in order to allow
an experiment-based evaluation of solutions. In this way, we can overcome the limitations connected to simulations of physical
environments. We present the approach for a set-up in which the geometry of a flapping wing is optimized in order to find
optimal configurations for various quality criteria.

  • Content Type Journal Article
  • Pages 23-47
  • DOI 10.1007/s10710-010-9107-0
  • Authors
    • Markus Olhofer, Honda Research Institute Europe GmbH, Offenbach/Main, Germany
    • Dilyana Yankulova, Control Theory and Robotics Lab, Technical University of Darmstadt, Darmstadt, Germany
    • Bernhard Sendhoff, Honda Research Institute Europe GmbH, Offenbach/Main, Germany

Dario Floreano and Claudio Mattiussi (eds): Bio-inspired artificial intelligence: theories, methods, and technologies

Dario Floreano and Claudio Mattiussi (eds): Bio-inspired artificial intelligence: theories, methods, and technologies
Content Type Journal ArticlePages 441-443DOI 10.1007/s10710-010-9104-3Authors
Ivan Garibay, University of Central Florida, Orlando,…

Dario Floreano and Claudio Mattiussi (eds): Bio-inspired artificial intelligence: theories, methods, and technologies

  • Content Type Journal Article
  • Pages 441-443
  • DOI 10.1007/s10710-010-9104-3
  • Authors
    • Ivan Garibay, University of Central Florida, Orlando, FL USA

Guest editorial: special issue on parallel and distributed evolutionary algorithms, part two

Guest editorial: special issue on parallel and distributed evolutionary algorithms, part two
Content Type Journal ArticlePages 129-130DOI 10.1007/s10710-010-9106-1Authors
Marco Tomassini, HEC, University of Lausanne Information Systems Department La…

Guest editorial: special issue on parallel and distributed evolutionary algorithms, part two

  • Content Type Journal Article
  • Pages 129-130
  • DOI 10.1007/s10710-010-9106-1
  • Authors
    • Marco Tomassini, HEC, University of Lausanne Information Systems Department Lausanne Switzerland
    • Leonardo Vanneschi, Systems and Communication (D.I.S.Co.), University of Milano-Bicocca Department of Informatics Milan Italy

Variable population size and evolution acceleration: a case study with a parallel evolutionary algorithm

Abstract  With current developments of parallel and distributed computing, evolutionary algorithms have benefited considerably from
parallelization techniques. Besides improved computation efficiency, parallelization may bring about innovati…

Abstract  

With current developments of parallel and distributed computing, evolutionary algorithms have benefited considerably from
parallelization techniques. Besides improved computation efficiency, parallelization may bring about innovation to many aspects
of evolutionary algorithms. In this article, we focus on the effect of variable population size on accelerating evolution
in the context of a parallel evolutionary algorithm. In nature it is observed that dramatic variations of population size
have considerable impact on evolution. Interestingly, the property of variable population size here arises implicitly and
naturally from the algorithm rather than through intentional design. To investigate the effect of variable population size
in such a parallel algorithm, evolution dynamics, including fitness progression and population diversity variation, are analyzed.
Further, this parallel algorithm is compared to a conventional fixed-population-size genetic algorithm. We observe that the
dramatic changes in population size allow evolution to accelerate.

  • Content Type Journal Article
  • Pages 205-225
  • DOI 10.1007/s10710-010-9105-2
  • Authors
    • Ting Hu, Memorial University Department of Computer Science St. John’s NL Canada
    • Simon Harding, Memorial University Department of Computer Science St. John’s NL Canada
    • Wolfgang Banzhaf, Memorial University Department of Computer Science St. John’s NL Canada

Expert-driven genetic algorithms for simulating evaluation functions

Abstract  In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function’s parameters for
computer chess. Our results show that using an appropriate expert (or mentor), we can evolve a program th…

Abstract  

In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function’s parameters for
computer chess. Our results show that using an appropriate expert (or mentor), we can evolve a program that is on par with
top tournament-playing chess programs, outperforming a two-time World Computer Chess Champion. This performance gain is achieved
by evolving a program that mimics the behavior of a superior expert. The resulting evaluation function of the evolved program
consists of a much smaller number of parameters than the expert’s. The extended experimental results provided in this paper
include a report on our successful participation in the 2008 World Computer Chess Championship. In principle, our expert-driven
approach could be used in a wide range of problems for which appropriate experts are available.

  • Content Type Journal Article
  • Pages 5-22
  • DOI 10.1007/s10710-010-9103-4
  • Authors
    • Omid David-Tabibi, Department of Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel
    • Moshe Koppel, Department of Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel
    • Nathan S. Netanyahu, Department of Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel

Deployment of parallel linear genetic programming using GPUs on PC and video game console platforms

Abstract  We present a general method for deploying parallel linear genetic programming (LGP) to the PC and Xbox 360 video game console
by using a publicly available common framework for the devices called XNA (for “XNA’s Not Acronymed

Abstract  

We present a general method for deploying parallel linear genetic programming (LGP) to the PC and Xbox 360 video game console
by using a publicly available common framework for the devices called XNA (for “XNA’s Not Acronymed”). By constructing the
LGP within this framework, we effectively produce an LGP “game” for PC and XBox 360 that displays results as they evolve.
We use the GPU of each device to parallelize fitness evaluation and the mutation operator of the LGP algorithm, thus providing
a general LGP implementation suitable for parallel computation on heterogeneous devices. While parallel GP implementations
on PCs are now common, both the implementation of GP on a video game console using GPU and the construction of a GP around
a framework for heterogeneous devices are novel contributions. The objective of this work is to describe how to implement
the parallel execution of LGP in order to use the underlying hardware (especially GPU) on the different platforms while still
maintaining loyalty to the general methodology of the LGP algorithm built for the common framework. We discuss the implementation
of texture-based data structures and the sequential and parallel algorithms built for their use on both CPU and GPU. Following
the description of the general algorithm, the particular tailoring of the implementations for each hardware platform is described.
Sequential (CPU) and parallel (GPU-based) algorithm performance is compared on both PC and video game platforms using the
metrics of GP operations per second, actual time elapsed, speedup of parallel over sequential implementation, and percentage
of execution time used by the GPU versus CPU.

  • Content Type Journal Article
  • Pages 147-184
  • DOI 10.1007/s10710-010-9102-5
  • Authors
    • Garnett Wilson, Memorial University of Newfoundland Department of Computer Science St. John’s NL A1B 3X5 Canada
    • Wolfgang Banzhaf, Memorial University of Newfoundland Department of Computer Science St. John’s NL A1B 3X5 Canada

An ensemble-based evolutionary framework for coping with distributed intrusion detection

Abstract  A distributed data mining algorithm to improve the detection accuracy when classifying malicious or unauthorized network activity
is presented. The algorithm is based on genetic programming (GP) extended with the ensemble paradigm….

Abstract  

A distributed data mining algorithm to improve the detection accuracy when classifying malicious or unauthorized network activity
is presented. The algorithm is based on genetic programming (GP) extended with the ensemble paradigm. GP ensemble is particularly
suitable for distributed intrusion detection because it allows to build a network profile by combining different classifiers that together provide complementary information. The main novelty of the algorithm is
that data is distributed across multiple autonomous sites and the learner component acquires useful knowledge from this data
in a cooperative way. The network profile is then used to predict abnormal behavior. Experiments on the KDD Cup 1999 Data
show the capability of genetic programming in successfully dealing with the problem of intrusion detection on distributed
data.

  • Content Type Journal Article
  • Pages 131-146
  • DOI 10.1007/s10710-010-9101-6
  • Authors
    • Gianluigi Folino, Institute for High Performance Computing and Networking (ICAR) National Research Council (CNR) Via P. Bucci 41C 87036 Rende CS Italy
    • Clara Pizzuti, Institute for High Performance Computing and Networking (ICAR) National Research Council (CNR) Via P. Bucci 41C 87036 Rende CS Italy
    • Giandomenico Spezzano, Institute for High Performance Computing and Networking (ICAR) National Research Council (CNR) Via P. Bucci 41C 87036 Rende CS Italy

Simdist: a distribution system for easy parallelization of evolutionary computation

Abstract  This article introduces Simdist, a software tool for parallel execution of evolutionary algorithms (EAs) in a master-slave configuration on cluster architectures.
Clusters have become a cost-effective parallel solution, and the pot…

Abstract  

This article introduces Simdist, a software tool for parallel execution of evolutionary algorithms (EAs) in a master-slave configuration on cluster architectures.
Clusters have become a cost-effective parallel solution, and the potential computational capabilities are phenomenal. However,
the transition from traditional R&D on a personal computer to parallel development and deployment can be a major step. Simdist
simplifies this transition considerably, by separating the task of distributing data across the cluster network from the actual
EA-related processing performed on the master and slave nodes. Simdist is constructed in the vein of traditional Unix command
line tools; it runs in a separate process and communicates with EA child processes via standard input and output. As a result,
Simdist is oblivious to the programming language(s) used in the EA, and the EA is similarly oblivious to the internals of
Simdist.

  • Content Type Journal Article
  • Pages 185-203
  • DOI 10.1007/s10710-009-9100-7
  • Authors
    • Boye Annfelt Høverstad, Norwegian University of Science and Technology (NTNU) Department of Computer and Information Science Trondheim Norway