Tag: Genetic Programming and Evolvable Machines

An eigen analysis of the GP community

Abstract  The coauthorship and coeditorship relations as recorded in the genetic programming bibliography provide a quantitative view
of the GP community. Eigen analysis is used to find the principle components of the community. It shows the major eigenvalues
and eigenvectors are responsible for 70% of the connection graph. Top eigen authors are given.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9060-3
  • Authors
    • W. B. Langdon, University of Essex Departments of Biological and Mathematical Sciences Colchester UK
    • R. Poli, University of Essex Department of Computing and Electronic Systems Colchester UK
    • W. Banzhaf, Memorial University of Newfoundland Department of Computer Science St.John’s Canada

Abstract  The coauthorship and coeditorship relations as recorded in the genetic programming bibliography provide a quantitative view
of the GP community. Eigen analysis is used to find the principle components of the community. It shows the major eigenvalues
and eigenvectors are responsible for 70% of the connection graph. Top eigen authors are given.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9060-3
  • Authors
    • W. B. Langdon, University of Essex Departments of Biological and Mathematical Sciences Colchester UK
    • R. Poli, University of Essex Department of Computing and Electronic Systems Colchester UK
    • W. Banzhaf, Memorial University of Newfoundland Department of Computer Science St.John’s Canada

Cyclic metamorphic memory for cellular bio-inspired electronic systems

Abstract  In nature the DNA contained in each cell of an organism, is in fact a memory map that, through the transcription of its genes,
describes the unique characteristics of the individual. Similarly in an artificial embryonic cell, used to construct electronic
systems, a memory map and its relevant gene also describes and determines the functionality of each cell and, collectively,
the entire system. This paper proposes a new variable size memory map based on a novel and efficient gene selection algorithm
that no longer uses the hitherto common address decoding approach to access some fixed memory space. Instead, it applies the
principle of cyclic metamorphic gene selection of the artificial DNA memory. A further benefit of the approach is that the
functionality of the system can also be easily altered through genetic operators or variable memory space environment for
enhanced behaviour. It is suitable therefore for the implementation of GA processes.

  • Content Type Journal Article
  • Category Originall Paper
  • DOI 10.1007/s10710-008-9056-z
  • Authors
    • M. Samie, Shiraz University Department of EE Engineering Shiraz Iran
    • E. Farjah, Shiraz University Department of EE Engineering Shiraz Iran
    • G. Dragffy, University of the West of England Bristol UK

Abstract  In nature the DNA contained in each cell of an organism, is in fact a memory map that, through the transcription of its genes,
describes the unique characteristics of the individual. Similarly in an artificial embryonic cell, used to construct electronic
systems, a memory map and its relevant gene also describes and determines the functionality of each cell and, collectively,
the entire system. This paper proposes a new variable size memory map based on a novel and efficient gene selection algorithm
that no longer uses the hitherto common address decoding approach to access some fixed memory space. Instead, it applies the
principle of cyclic metamorphic gene selection of the artificial DNA memory. A further benefit of the approach is that the
functionality of the system can also be easily altered through genetic operators or variable memory space environment for
enhanced behaviour. It is suitable therefore for the implementation of GA processes.

  • Content Type Journal Article
  • Category Originall Paper
  • DOI 10.1007/s10710-008-9056-z
  • Authors
    • M. Samie, Shiraz University Department of EE Engineering Shiraz Iran
    • E. Farjah, Shiraz University Department of EE Engineering Shiraz Iran
    • G. Dragffy, University of the West of England Bristol UK

Analysis of mass spectrometry data of cerebral stroke samples: an evolutionary computation approach to resolve and quantify peptide peaks

Abstract  A preliminary investigation of cerebral stroke samples injected into a mass spectrometer is performed from an evolutionary
computation perspective. The detection and resolution of peptide peaks is pursued for the purpose of automatically and accurately
determining unlabeled peptide quantities. A theoretical peptide peak model is proposed and a series of experiments are then
pursued (most within a distributed computing environment) along with a data preprocessing strategy that includes (i) a deisotoping
step followed by (ii) a peak picking procedure, followed by (iii) a series of evolutionary computation experiments oriented
towards the investigation of their capability for achieving the aforementioned goal. Results from four different genetic algorithms
(GA) and one differential evolution (DE) algorithm are reported with respect to their ability to find solutions that fit within
the framework of the presented theoretical peptide peak model. Both unconstrained and constrained (as determined by a course
grained preprocessing stage) solution space experiments are performed for both types of evolutionary algorithms. Good preliminary
results are obtained.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9057-y
  • Authors
    • Julio J. Valdés, National Research Council Canada Institute for Information Technology Bldg. M-50, 1200 Montreal Rd. Ottawa ON Canada K1A 0R6
    • Alan J. Barton, National Research Council Canada Institute for Information Technology Bldg. M-50, 1200 Montreal Rd. Ottawa ON Canada K1A 0R6
    • Arsalan S. Haqqani, National Research Council Canada Institute for Biological Sciences 100 Sussex Dr. Ottawa ON Canada K1A 0R6

Abstract  A preliminary investigation of cerebral stroke samples injected into a mass spectrometer is performed from an evolutionary
computation perspective. The detection and resolution of peptide peaks is pursued for the purpose of automatically and accurately
determining unlabeled peptide quantities. A theoretical peptide peak model is proposed and a series of experiments are then
pursued (most within a distributed computing environment) along with a data preprocessing strategy that includes (i) a deisotoping
step followed by (ii) a peak picking procedure, followed by (iii) a series of evolutionary computation experiments oriented
towards the investigation of their capability for achieving the aforementioned goal. Results from four different genetic algorithms
(GA) and one differential evolution (DE) algorithm are reported with respect to their ability to find solutions that fit within
the framework of the presented theoretical peptide peak model. Both unconstrained and constrained (as determined by a course
grained preprocessing stage) solution space experiments are performed for both types of evolutionary algorithms. Good preliminary
results are obtained.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9057-y
  • Authors
    • Julio J. Valdés, National Research Council Canada Institute for Information Technology Bldg. M-50, 1200 Montreal Rd. Ottawa ON Canada K1A 0R6
    • Alan J. Barton, National Research Council Canada Institute for Information Technology Bldg. M-50, 1200 Montreal Rd. Ottawa ON Canada K1A 0R6
    • Arsalan S. Haqqani, National Research Council Canada Institute for Biological Sciences 100 Sussex Dr. Ottawa ON Canada K1A 0R6

Introduction to Evolvable Hardware: A Practical Guide for Designing Self-Adaptive Systems

Introduction to Evolvable Hardware: A Practical Guide for Designing Self-Adaptive Systems

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-008-9058-x
  • Authors
    • Antonio Mesquita, Programa de Engenharia Eletrica, COPPE/UFRJ CP. 68504, Centro de Tecnologia Ilha do Fundao CEP 21945-970 Rio de Janeiro RJ Brazil

Introduction to Evolvable Hardware: A Practical Guide for Designing Self-Adaptive Systems

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-008-9058-x
  • Authors
    • Antonio Mesquita, Programa de Engenharia Eletrica, COPPE/UFRJ CP. 68504, Centro de Tecnologia Ilha do Fundao CEP 21945-970 Rio de Janeiro RJ Brazil

Genetic programming for medical classification: a program simplification approach

Abstract  This paper describes a genetic programming (GP) approach to medical data classification problems. In this approach, the evolved
genetic programs are simplified online during the evolutionary process using algebraic simplification rules, algebraic equivalence
and prime techniques. The new simplification GP approach is examined and compared to the standard GP approach on two medical
data classification problems. The results suggest that the new simplification GP approach can not only be more efficient with
slightly better classification performance than the basic GP system on these problems, but also significantly reduce the sizes
of evolved programs. Comparison with other methods including decision trees, naive Bayes, nearest neighbour, nearest centroid,
and neural networks suggests that the new GP approach achieved superior results to almost all of these methods on these problems.
The evolved genetic programs are also easier to interpret than the “hidden patterns” discovered by the other methods.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9059-9
  • Authors
    • Mengjie Zhang, Victoria University of Wellington School of Mathematics, Statistics and Computer Science P.O. Box 600 Wellington New Zealand
    • Phillip Wong, Victoria University of Wellington School of Mathematics, Statistics and Computer Science P.O. Box 600 Wellington New Zealand

Abstract  This paper describes a genetic programming (GP) approach to medical data classification problems. In this approach, the evolved
genetic programs are simplified online during the evolutionary process using algebraic simplification rules, algebraic equivalence
and prime techniques. The new simplification GP approach is examined and compared to the standard GP approach on two medical
data classification problems. The results suggest that the new simplification GP approach can not only be more efficient with
slightly better classification performance than the basic GP system on these problems, but also significantly reduce the sizes
of evolved programs. Comparison with other methods including decision trees, naive Bayes, nearest neighbour, nearest centroid,
and neural networks suggests that the new GP approach achieved superior results to almost all of these methods on these problems.
The evolved genetic programs are also easier to interpret than the “hidden patterns” discovered by the other methods.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-008-9059-9
  • Authors
    • Mengjie Zhang, Victoria University of Wellington School of Mathematics, Statistics and Computer Science P.O. Box 600 Wellington New Zealand
    • Phillip Wong, Victoria University of Wellington School of Mathematics, Statistics and Computer Science P.O. Box 600 Wellington New Zealand

Editorial introduction

Editorial introduction

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9054-6
  • Authors
    • Wolfgang Banzhaf, Memorial University of Newfoundland Department of Computer Science St. John’s NL Canada AlB 3X5

Editorial introduction

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9054-6
  • Authors
    • Wolfgang Banzhaf, Memorial University of Newfoundland Department of Computer Science St. John’s NL Canada AlB 3X5

Acknowledgment

Acknowledgment

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9055-5

Acknowledgment

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9055-5

Sporadic model building for efficiency enhancement of the hierarchical BOA

Abstract  Efficiency enhancement techniques—such as parallelization and hybridization—are among the most important ingredients of practical
applications of genetic and evolutionary algorithms and that is why this research area represents an important niche of evolutionary
computation. This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation
of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure
of the probabilistic model is updated once in every few iterations (generations), whereas in the remaining iterations, only
model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters
is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time
complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization
problems, sporadic model building leads to a significant model-building speedup, which decreases the asymptotic time complexity of model building in hBOA by a factor of

\Uptheta(n0.26)

to

\Uptheta(n0.5),

where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence;
nonetheless, if model building is the bottleneck, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building. The paper also presents a dimensional
model to provide a heuristic for scaling the structure-building period, which is the only parameter of the proposed sporadic
model-building approach. The paper then tests the proposed method and the rule for setting the structure-building period on
the problem of finding ground states of 2D and 3D Ising spin glasses.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9052-8
  • Authors
    • Martin Pelikan, University of Missouri in St. Louis Missouri Estimation of Distribution Algorithms Laboratory, 321 CCB, Department of Mathematics and Computer Science One University Blvd. St. Louis MO 63121 USA
    • Kumara Sastry, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA
    • David E. Goldberg, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA

Abstract  Efficiency enhancement techniques—such as parallelization and hybridization—are among the most important ingredients of practical
applications of genetic and evolutionary algorithms and that is why this research area represents an important niche of evolutionary
computation. This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation
of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure
of the probabilistic model is updated once in every few iterations (generations), whereas in the remaining iterations, only
model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters
is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time
complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization
problems, sporadic model building leads to a significant model-building speedup, which decreases the asymptotic time complexity of model building in hBOA by a factor of


\Uptheta(n0.26)

to


\Uptheta(n0.5),

where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence;
nonetheless, if model building is the bottleneck, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building. The paper also presents a dimensional
model to provide a heuristic for scaling the structure-building period, which is the only parameter of the proposed sporadic
model-building approach. The paper then tests the proposed method and the rule for setting the structure-building period on
the problem of finding ground states of 2D and 3D Ising spin glasses.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9052-8
  • Authors
    • Martin Pelikan, University of Missouri in St. Louis Missouri Estimation of Distribution Algorithms Laboratory, 321 CCB, Department of Mathematics and Computer Science One University Blvd. St. Louis MO 63121 USA
    • Kumara Sastry, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA
    • David E. Goldberg, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA

A genetic algorithm for discrete tomography reconstruction

Abstract  The aim of this paper is the description of an experiment carried out to verify the robustness of two different approaches
for the reconstruction of convex polyominoes in discrete tomography. This is a new field of research, because it differs from
classic computerized tomography, and several problems are still open. In particular, the stability problem is tackled by using
both a modified version of a known algorithm and a new genetic approach. The effect of both, instrumental and quantization
noises has been considered too.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9051-9
  • Authors
    • Cesare Valenti, Università di Palermo Dipartimento di Matematica e Applicazioni Via Archirafi 34 90123 Palermo Italy

Abstract  The aim of this paper is the description of an experiment carried out to verify the robustness of two different approaches
for the reconstruction of convex polyominoes in discrete tomography. This is a new field of research, because it differs from
classic computerized tomography, and several problems are still open. In particular, the stability problem is tackled by using
both a modified version of a known algorithm and a new genetic approach. The effect of both, instrumental and quantization
noises has been considered too.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9051-9
  • Authors
    • Cesare Valenti, Università di Palermo Dipartimento di Matematica e Applicazioni Via Archirafi 34 90123 Palermo Italy

Maja J. Matarić: The Robotics Primer

Maja J. Matarić: The Robotics Primer

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-007-9053-7
  • Authors
    • Andrew Vardy, Memorial University of Newfoundland Computer Science/Engineering & Applied Science (Joint) St. John’s Canada

Maja J. Matarić: The Robotics Primer

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-007-9053-7
  • Authors
    • Andrew Vardy, Memorial University of Newfoundland Computer Science/Engineering & Applied Science (Joint) St. John’s Canada