Category: Genetic Programming and Evolvable Machines

Semantically-based crossover in genetic programming: application to real-valued symbolic regression

Abstract  We investigate the effects of semantically-based crossover operators in genetic programming, applied to real-valued symbolic
regression problems. We propose two new relations derived from the semantic distance between subtrees, kno…

Abstract  

We investigate the effects of semantically-based crossover operators in genetic programming, applied to real-valued symbolic
regression problems. We propose two new relations derived from the semantic distance between subtrees, known as semantic equivalence
and semantic similarity. These relations are used to guide variants of the crossover operator, resulting in two new crossover
operators—semantics aware crossover (SAC) and semantic similarity-based crossover (SSC). SAC, was introduced and previously
studied, is added here for the purpose of comparison and analysis. SSC extends SAC by more closely controlling the semantic
distance between subtrees to which crossover may be applied. The new operators were tested on some real-valued symbolic regression
problems and compared with standard crossover (SC), context aware crossover (CAC), Soft Brood Selection (SBS), and No Same
Mate (NSM) selection. The experimental results show on the problems examined that, with computational effort measured by the
number of function node evaluations, only SSC and SBS were significantly better than SC, and SSC was often better than SBS.
Further experiments were also conducted to analyse the perfomance sensitivity to the parameter settings for SSC. This analysis
leads to a conclusion that SSC is more constructive and has higher locality than SAC, NSM and SC; we believe these are the
main reasons for the improved performance of SSC.

  • Content Type Journal Article
  • Pages 91-119
  • DOI 10.1007/s10710-010-9121-2
  • Authors
    • Nguyen Quang Uy, Complex & Adaptive Systems Lab, School of Computer Science & Informatics, University College Dublin, Dublin, Ireland
    • Nguyen Xuan Hoai, Department of Computer Science, Le Quy Don University, Hanoi, Vietnam
    • Michael O’Neill, Complex & Adaptive Systems Lab, School of Computer Science & Informatics, University College Dublin, Dublin, Ireland
    • R. I. McKay, School of Computer Science and Engineering, Seoul National University, Seoul, Korea
    • Edgar Galván-López, Complex & Adaptive Systems Lab, School of Computer Science & Informatics, University College Dublin, Dublin, Ireland

GPEM special issue Progress in Genetic Programming and Evolvable Machines

The tenth anniversary special issue of the journal Genetic Programming and Evolvable Hardware (GPEM) looks back at past progress and future possibilities in this amazing area of computer science and machine intelligence. The issue includes a review of human-competitive results obtained via genetic programming and many other interesting articles. The special issue can be downloaded […]

The tenth anniversary special issue of the journal Genetic Programming and Evolvable Hardware (GPEM) looks back at past progress and future possibilities in this amazing area of computer science and machine intelligence. The issue includes a review of human-competitive results obtained via genetic programming and many other interesting articles. The special issue can be downloaded for free here until the end of July.

Share on Facebook

Redundancies in linear GP, canonical transformation, and its exploitation: a demonstration on image feature synthesis

Abstract  This paper concerns redundancies in representation of linear genetic programming (GP). We identify the causes of redundancies
in linear GP and propose a canonical transformation that converts original linear representations into a …

Abstract  

This paper concerns redundancies in representation of linear genetic programming (GP). We identify the causes of redundancies
in linear GP and propose a canonical transformation that converts original linear representations into a canonical form in
which structural redundancies are removed. In canonical form, we can easily verify whether two representations represent an
identical program. We then discuss exploitation of the proposed canonical transformation, and demonstrate a way to improve
search performance of linear GP by avoiding redundant individuals. Experiments were conducted with an image feature synthesis
problem. Firstly, we have verified that there are really a lot of redundancies in conventional linear GP. We then investigate
the effect of avoiding redundant individuals. The results yield that linear GP with avoidance of redundant individuals obviously
outperforms conventional linear GP.

  • Content Type Journal Article
  • Pages 49-77
  • DOI 10.1007/s10710-010-9118-x
  • Authors
    • Ukrit Watchareeruetai, Department of Media Science, Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japan
    • Yoshinori Takeuchi, Department of Media Science, Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japan
    • Tetsuya Matsumoto, Department of Media Science, Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japan
    • Hiroaki Kudo, Department of Media Science, Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japan
    • Noboru Ohnishi, Department of Media Science, Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japan

Developments in Cartesian Genetic Programming: self-modifying CGP

Abstract  Self-modifying Cartesian Genetic Programming (SMCGP) is a general purpose, graph-based, developmental form of Genetic Programming
founded on Cartesian Genetic Programming. In addition to the usual computational functions, it includ…

Abstract  

Self-modifying Cartesian Genetic Programming (SMCGP) is a general purpose, graph-based, developmental form of Genetic Programming
founded on Cartesian Genetic Programming. In addition to the usual computational functions, it includes functions that can
modify the program encoded in the genotype. This means that programs can be iterated to produce an infinite sequence of programs
(phenotypes) from a single evolved genotype. It also allows programs to acquire more inputs and produce more outputs during
this iteration. We discuss how SMCGP can be used and the results obtained in several different problem domains, including
digital circuits, generation of patterns and sequences, and mathematical problems. We find that SMCGP can efficiently solve
all the problems studied. In addition, we prove mathematically that evolved programs can provide general solutions to a number
of problems: n-input even-parity, n-input adder, and sequence approximation to π.

  • Content Type Journal Article
  • Pages 397-439
  • DOI 10.1007/s10710-010-9114-1
  • Authors
    • Simon Harding, Memorial University of Newfoundland Department of Computer Science St. John’s NL A1B3X5 Canada
    • Julian F. Miller, University of York Department of Electronics York YO10 5DD UK
    • Wolfgang Banzhaf, Memorial University of Newfoundland Department of Computer Science St. John’s NL A1B3X5 Canada

Erratum to: Stochastic optimization of a biologically plausible spino-neuromuscular system model

Erratum to: Stochastic optimization of a biologically plausible spino-neuromuscular system model
Content Type Journal ArticlePages 87-88DOI 10.1007/s10710-010-9108-zAuthors
Stanley Gotshall, Department of Computer Science, University of Idaho, Mosco…

Erratum to: Stochastic optimization of a biologically plausible spino-neuromuscular system model

  • Content Type Journal Article
  • Pages 87-88
  • DOI 10.1007/s10710-010-9108-z
  • Authors
    • Stanley Gotshall, Department of Computer Science, University of Idaho, Moscow, ID USA
    • Kathy Browder, Department of Health, Physical Education, Recreation, and Dance, University of Idaho, Moscow, ID USA
    • Jessica Sampson, Department of Mechanical Engineering, University of Idaho, Moscow, ID USA
    • Terence Soule, Department of Computer Science, University of Idaho, Moscow, ID USA
    • Richard Wells, Department of Electrical and Computer Engineering, University of Idaho, Moscow, ID USA

Justin Lee: Morphogenetic Evolvable Hardware

Justin Lee: Morphogenetic Evolvable Hardware
Content Type Journal ArticlePages 79-80DOI 10.1007/s10710-010-9116-zAuthors
Martin A. Trefzer, University of York, York, UK

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

Justin Lee: Morphogenetic Evolvable Hardware

  • Content Type Journal Article
  • Pages 79-80
  • DOI 10.1007/s10710-010-9116-z
  • Authors
    • Martin A. Trefzer, University of York, York, UK

Genetic Programming and Evolvable Machines: ten years of reviews

Abstract  The journal and in particular the resource reviews have been running for 10 years. There are a number of activities being
planned to celebrate. However it is a good time to revisit our original and updated goals again [(Langdo…

Abstract  

The journal and in particular the resource reviews have been running for 10 years. There are a number of activities being
planned to celebrate. However it is a good time to revisit our original and updated goals again [(Langdon, Genet Progrm Evolvable
Mach 1(1/2):165–169 (2000); Langdon and Gustafson, Genet Program Evolvable Mach 6(2):221–228 (2005)], compare them with what the journal has achieved and make new plans. “Books” section onwards gives up to date statistics
on the genetic programming and evolvable hardware literature and electronic resources.

  • Content Type Journal Article
  • Pages 321-338
  • DOI 10.1007/s10710-010-9111-4
  • Authors
    • W. B. Langdon, King’s College London Department of Computer Science London WC2R 2LS UK
    • S. M. Gustafson, GE Global Research Niskayuna NY 12309 USA

Editorial to tenth anniversary issue on progress in genetic programming and evolvable machines

Editorial to tenth anniversary issue on progress in genetic programming and evolvable machines
Content Type Journal ArticlePages 247-250DOI 10.1007/s10710-010-9115-0Authors
Julian F. Miller, University of York Department of Electronics York YO10 5DD…

Editorial to tenth anniversary issue on progress in genetic programming and evolvable machines

  • Content Type Journal Article
  • Pages 247-250
  • DOI 10.1007/s10710-010-9115-0
  • Authors
    • Julian F. Miller, University of York Department of Electronics York YO10 5DD UK
    • Riccardo Poli, University of Essex School of Computer Science and Electronic Engineering Colchester CO4 3SQ UK

Human-competitive results produced by genetic programming

Abstract  Genetic programming has now been used to produce at least 76 instances of results that are competitive with human-produced
results. These human-competitive results come from a wide variety of fields, including quantum computing cir…

Abstract  

Genetic programming has now been used to produce at least 76 instances of results that are competitive with human-produced
results. These human-competitive results come from a wide variety of fields, including quantum computing circuits, analog
electrical circuits, antennas, mechanical systems, controllers, game playing, finite algebras, photonic systems, image recognition,
optical lens systems, mathematical algorithms, cellular automata rules, bioinformatics, sorting networks, robotics, assembly
code generation, software repair, scheduling, communication protocols, symbolic regression, reverse engineering, and empirical
model discovery. This paper observes that, despite considerable variation in the techniques employed by the various researchers
and research groups that produced these human-competitive results, many of the results share several common features. Many
of the results were achieved by using a developmental process and by using native representations regularly used by engineers
in the fields involved. The best individual in the initial generation of the run of genetic programming often contains only
a small number of operative parts. Most of the results that duplicated the functionality of previously issued patents were
novel solutions, not infringing solutions. In addition, the production of human-competitive results, as well as the increased
intricacy of the results, are broadly correlated to increased availability of computing power tracked by Moore’s law. The
paper ends by predicting that the increased availability of computing power (through both parallel computing and Moore’s law)
should result in the production, in the future, of an increasing flow of human-competitive results, as well as more intricate
and impressive results.

  • Content Type Journal Article
  • Pages 251-284
  • DOI 10.1007/s10710-010-9112-3
  • Authors
    • John R. Koza, Stanford University Department of Electrical Engineering Stanford CA 94305 USA

Theoretical results in genetic programming: the next ten years?

Abstract  We consider the theoretical results in GP so far and prospective areas for the future. We begin by reviewing the state of
the art in genetic programming (GP) theory including: schema theories, Markov chain models, the distribution …

Abstract  

We consider the theoretical results in GP so far and prospective areas for the future. We begin by reviewing the state of
the art in genetic programming (GP) theory including: schema theories, Markov chain models, the distribution of functionality
in program search spaces, the problem of bloat, the applicability of the no-free-lunch theory to GP, and how we can estimate
the difficulty of problems before actually running the system. We then look at how each of these areas might develop in the
next decade, considering also new possible avenues for theory, the challenges ahead and the open issues.

  • Content Type Journal Article
  • Pages 285-320
  • DOI 10.1007/s10710-010-9110-5
  • Authors
    • Riccardo Poli, University of Essex School of Computer Science and Electronic Engineering Colchester CO4 3SQ UK
    • Leonardo Vanneschi, University of Milano-Bicocca Department of Informatics, Systems and Communication (D.I.S.Co.) viale Sarca 336-U14 Milan Italy
    • William B. Langdon, King’s College London Department of Computer Science London WC2R 2LS UK
    • Nicholas Freitag McPhee, University of Minnesota Morris Division of Science and Mathematics Morris MN 56267 USA