Category: Genetic Programming and Evolvable Machines

Melanie Mitchell: Complexity a guided tour

Melanie Mitchell: Complexity a guided tour
Content Type Journal ArticlePages 127-128DOI 10.1007/s10710-009-9097-yAuthors
Felix Streichert, Eberhard Karls Universität Tübingen Wilhelm-Schickard-Institut für Informatik Tübingen Germany

Jour…

Melanie Mitchell: Complexity a guided tour

  • Content Type Journal Article
  • Pages 127-128
  • DOI 10.1007/s10710-009-9097-y
  • Authors
    • Felix Streichert, Eberhard Karls Universität Tübingen Wilhelm-Schickard-Institut für Informatik Tübingen Germany

Acknowledgment

Acknowledgment
Content Type Journal ArticlePages 3-4DOI 10.1007/s10710-009-9099-9Authors
Lee Spector, Hampshire College School of Cognitive Science Amherst MA 01002 USA

Journal Genetic Programming and Evolvable MachinesOnline ISSN 1573-7632Pr…

Acknowledgment

  • Content Type Journal Article
  • Pages 3-4
  • DOI 10.1007/s10710-009-9099-9
  • Authors
    • Lee Spector, Hampshire College School of Cognitive Science Amherst MA 01002 USA

Editorial introduction

Editorial introduction
Content Type Journal ArticlePages 1-2DOI 10.1007/s10710-009-9098-xAuthors
Lee Spector, Hampshire College School of Cognitive Science Amherst MA 01002 USA

Journal Genetic Programming and Evolvable MachinesOnline ISSN 157…

Editorial introduction

  • Content Type Journal Article
  • Pages 1-2
  • DOI 10.1007/s10710-009-9098-x
  • Authors
    • Lee Spector, Hampshire College School of Cognitive Science Amherst MA 01002 USA

Michael Affenzeller, Stefan Wagner, Stephan Winkler and Andreas Beham: Genetic algorithms and genetic programming modern concepts and practical applications

Michael Affenzeller, Stefan Wagner, Stephan Winkler and Andreas Beham: Genetic algorithms and genetic programming modern concepts and practical applications
Content Type Journal ArticlePages 123-125DOI 10.1007/s10710-009-9095-0Authors
Gisele L. Papp…

Michael Affenzeller, Stefan Wagner, Stephan Winkler and Andreas Beham: Genetic algorithms and genetic programming modern concepts and practical applications

  • Content Type Journal Article
  • Pages 123-125
  • DOI 10.1007/s10710-009-9095-0
  • Authors
    • Gisele L. Pappa, Federal University of Minas Gerais (UFMG) Computer Science Department Av. Antônio Carlos, 6627, Pampulha Belo Horizonte MG Brazil

EvAg: a scalable peer-to-peer evolutionary algorithm

Abstract  This paper studies the scalability of an Evolutionary Algorithm (EA) whose population is structured by means of a gossiping
protocol and where the evolutionary operators act exclusively within the local neighborhoods. This makes th…

Abstract  

This paper studies the scalability of an Evolutionary Algorithm (EA) whose population is structured by means of a gossiping
protocol and where the evolutionary operators act exclusively within the local neighborhoods. This makes the algorithm inherently
suited for parallel execution in a peer-to-peer fashion which, in turn, offers great advantages when dealing with computationally
expensive problems because distributed execution implies massive scalability. In this paper we show another advantage of this
algorithm: We experimentally demonstrate that it scales up better than traditional alternatives even when executed in a sequential
fashion. In particular, we analyze the behavior of several EAs on well-known deceptive trap functions with varying sizes and
levels of deceptiveness. The results show that the new EA requires smaller optimal population sizes and fewer fitness evaluations
to reach solutions. The relative advantage of the new EA is more outstanding as problem hardness and size increase. In some
cases the new algorithm reduces the computational efforts of the traditional EAs by several orders of magnitude.

  • Content Type Journal Article
  • Pages 227-246
  • DOI 10.1007/s10710-009-9096-z
  • Authors
    • J. L. J. Laredo, University of Granada, ATC-ETSIT C. Periodista Daniel Saucedo Aranda 18071 Granada Spain
    • A. E. Eiben, Vrije Universiteit Amsterdam Department of Computer Science Amsterdam The Netherlands
    • M. van Steen, Vrije Universiteit Amsterdam Department of Computer Science Amsterdam The Netherlands
    • J. J. Merelo, University of Granada, ATC-ETSIT C. Periodista Daniel Saucedo Aranda 18071 Granada Spain

Introduction: special issue on parallel and distributed evolutionary algorithms, part I

Introduction: special issue on parallel and distributed evolutionary algorithms, part I
Content Type Journal ArticlePages 339-341DOI 10.1007/s10710-009-9094-1Authors
Marco Tomassini, University of Lausanne Information Systems Department, HEC Lausann…

Introduction: special issue on parallel and distributed evolutionary algorithms, part I

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

Hybrid of genetic algorithm and local search to solve MAX-SAT problem using nVidia CUDA framework

Abstract  General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that
promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in al…

Abstract  General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that
promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design
and software development. In this paper we describe the challenges and design choices involved in parallelizing a hybrid of
Genetic Algorithm (GA) and Local Search (LS) to solve MAXimum SATisfiability (MAX-SAT) problem on a state-of-the-art nVidia
Tesla GPU using nVidia Compute Unified Device Architecture (CUDA). MAX-SAT is a problem of practical importance and is often
solved by employing metaheuristics based search methods like GAs and hybrid of GA with LS. Almost all the parallel GAs (pGAs)
designed in the last two decades were designed for either clusters or MPPs. Unfortunately, very little research is done on
the implementation of such algorithms over commodity graphics hardware. GAs in their simple form are not suitable for implementation
over the Single Instruction Multiple Thread (SIMT) architecture of a GPU, and the same is the case with conventional LS algorithms.
In this paper we explore different genetic operators that can be used for an efficient implementation of GAs over nVidia GPUs.
We also design and introduce new techniques/operators for an efficient implementation of GAs and LS over such architectures.
We use nVidia Tesla C1060 to perform several numerical tests and performance measurements and show that in the best case we
obtain a speedup of 25×. We also discuss the effects of different optimization techniques on the overall execution time.

  • Content Type Journal Article
  • Pages 391-415
  • DOI 10.1007/s10710-009-9091-4
  • Authors
    • Asim Munawar, Hokkaido University Graduate School of Information Science & Technology Sapporo Japan
    • Mohamed Wahib, Hokkaido University Graduate School of Information Science & Technology Sapporo Japan
    • Masaharu Munetomo, Hokkaido University Information Initiative Center Sapporo Japan
    • Kiyoshi Akama, Hokkaido University Information Initiative Center Sapporo Japan

Parallel evolution using multi-chromosome cartesian genetic programming

Abstract  Parallel and distributed methods for evolutionary algorithms have concentrated on maintaining multiple populations of genotypes,
where each genotype in a population encodes a potential solution to the problem. In this paper, we inv…

Abstract  Parallel and distributed methods for evolutionary algorithms have concentrated on maintaining multiple populations of genotypes,
where each genotype in a population encodes a potential solution to the problem. In this paper, we investigate the parallelisation
of the genotype itself into a collection of independent chromosomes which can be evaluated in parallel. We call this multi-chromosomal evolution
(MCE). We test this approach using Cartesian Genetic Programming and apply MCE to a series of digital circuit design problems
to compare the efficacy of MCE with a conventional single chromosome approach (SCE). MCE can be readily used for many digital
circuits because they have multiple outputs. In MCE, an independent chromosome is assigned to each output. When we compare
MCE with SCE we find that MCE allows us to evolve solutions much faster. In addition, in some cases we were able to evolve
solutions with MCE that we unable to with SCE. In a case-study, we investigate how MCE can be applied to to a single objective
problem in the domain of image classification, namely, the classification of breast X-rays for cancer. To apply MCE to this
problem, we identify regions of interest (RoI) from the mammograms, divide the RoI into a collection of sub-images and use
a chromosome to classify each sub-image. This problem allows us to evaluate various evolutionary mutation operators which
can pairwise swap chromosomes either randomly or topographically or reuse chromosomes in place of other chromosomes.

  • Content Type Journal Article
  • Pages 417-445
  • DOI 10.1007/s10710-009-9093-2
  • Authors
    • James Alfred Walker, University of York Intelligent Systems Group, Department of Electronics Heslington York YO10 5DD UK
    • Katharina Völk, University of York Intelligent Systems Group, Department of Electronics Heslington York YO10 5DD UK
    • Stephen L. Smith, University of York Intelligent Systems Group, Department of Electronics Heslington York YO10 5DD UK
    • Julian Francis Miller, University of York Intelligent Systems Group, Department of Electronics Heslington York YO10 5DD UK

Genetic programming on graphics processing units

Abstract  The availability of low cost powerful parallel graphics cards has stimulated the port of Genetic Programming (GP) on Graphics
Processing Units (GPUs). Our work focuses on the possibilities offered by Nvidia G80 GPUs when programmed…

Abstract  The availability of low cost powerful parallel graphics cards has stimulated the port of Genetic Programming (GP) on Graphics
Processing Units (GPUs). Our work focuses on the possibilities offered by Nvidia G80 GPUs when programmed in the CUDA language.
In a first work we have showed that this setup allows to develop fine grain parallelization schemes to evaluate several GP
programs in parallel, while obtaining speedups for usual training sets and program sizes. Here we present another parallelization
scheme and optimizations about program representation and use of GPU fast memory. This increases the computation speed about
three times faster, up to 4 billion GP operations per second. The code has been developed within the well known ECJ library
and is open source.

  • Content Type Journal Article
  • Pages 447-471
  • DOI 10.1007/s10710-009-9092-3
  • Authors
    • Denis Robilliard, Univ. Lille Nord de France, ULCO, LIL Maison de la Recherche Blaise Pascal, 50 rue Ferdinand Buisson BP 719 62228 CALAIS Cedex France
    • Virginie Marion-Poty, Univ. Lille Nord de France, ULCO, LIL Maison de la Recherche Blaise Pascal, 50 rue Ferdinand Buisson BP 719 62228 CALAIS Cedex France
    • Cyril Fonlupt, Univ. Lille Nord de France, ULCO, LIL Maison de la Recherche Blaise Pascal, 50 rue Ferdinand Buisson BP 719 62228 CALAIS Cedex France

A grid-enabled asynchronous metamodel-assisted evolutionary algorithm for aerodynamic optimization

Abstract  A Grid-enabled asynchronous metamodel-assisted evolutionary algorithm is presented and assessed on a number of aerodynamic
shape optimization problems. An efficient way of implementing surrogate evaluation models or metamodels (art…

Abstract  A Grid-enabled asynchronous metamodel-assisted evolutionary algorithm is presented and assessed on a number of aerodynamic
shape optimization problems. An efficient way of implementing surrogate evaluation models or metamodels (artificial neural
networks) in the context of an asynchronous evolutionary algorithm is proposed. The use of metamodels relies on the inexact
pre-evaluation technique already successfully applied to synchronous (i.e. generation-based) evolutionary algorithms, which
needs to be revisited so as to efficiently cooperate with the asynchronous search method. The so-created asynchronous metamodel-assisted
evolutionary algorithm is further enabled for Grid Computing. The Grid deployment of the algorithm relies on three middleware
layers: GridWay, Globus Toolkit and Condor. Single- and multi-objective CFD-based designs of isolated airfoils and compressor cascades are handled using the proposed algorithm and the gain in CPU cost is demonstrated.

  • Content Type Journal Article
  • Pages 373-389
  • DOI 10.1007/s10710-009-9090-5
  • Authors
    • V. G. Asouti, National Technical University of Athens Parallel CFD & Optimization Unit, Lab. of Thermal Turbomachines, School of Mechanical Engineering P.O. Box 64069 Athens 15710 Greece
    • I. C. Kampolis, National Technical University of Athens Parallel CFD & Optimization Unit, Lab. of Thermal Turbomachines, School of Mechanical Engineering P.O. Box 64069 Athens 15710 Greece
    • K. C. Giannakoglou, National Technical University of Athens Parallel CFD & Optimization Unit, Lab. of Thermal Turbomachines, School of Mechanical Engineering P.O. Box 64069 Athens 15710 Greece