Category: Genetic Programming and Evolvable Machines

Distributed differential evolution with explorative–exploitative population families

Abstract  This paper proposes a novel distributed differential evolution algorithm, namely Distributed Differential Evolution with Explorative–Exploitative
Population Families (DDE-EEPF). In DDE-EEPF the sub-populations are grouped into tw…

Abstract  This paper proposes a novel distributed differential evolution algorithm, namely Distributed Differential Evolution with Explorative–Exploitative
Population Families (DDE-EEPF). In DDE-EEPF the sub-populations are grouped into two families. Sub-populations belonging to
the first family have constant population size, are arranged according to a ring topology and employ a migration mechanism
acting on the individuals with the best performance. This first family of sub-populations has the role of exploring the decision
space and constituting an external evolutionary framework. The second family is composed of sub-populations with a dynamic
population size: the size is progressively reduced. The sub-populations belonging to the second family are highly exploitative
and are supposed to quickly detect solutions with a high performance. The solutions generated by the second family then migrate
to the first family. In order to verify its viability and effectiveness, the DDE-EEPF has been run on a set of various test
problems and compared to four distributed differential evolution algorithms. Numerical results show that the proposed algorithm
is efficient for most of the analyzed problems, and outperforms, on average, all the other algorithms considered in this study.

  • Content Type Journal Article
  • Pages 343-371
  • DOI 10.1007/s10710-009-9089-y
  • Authors
    • Matthieu Weber, University of Jyväskylä Department of Mathematical Information Technology P.O. Box 35 (Agora) 40014 Jyväskylä Finland
    • Ferrante Neri, University of Jyväskylä Department of Mathematical Information Technology P.O. Box 35 (Agora) 40014 Jyväskylä Finland
    • Ville Tirronen, University of Jyväskylä Department of Mathematical Information Technology P.O. Box 35 (Agora) 40014 Jyväskylä Finland

GP challenge: evolving energy function for protein structure prediction

Abstract  One of the key elements in protein structure prediction is the ability to distinguish between good and bad candidate structures.
This distinction is made by estimation of the structure energy. The energy function used in the best s…

Abstract  One of the key elements in protein structure prediction is the ability to distinguish between good and bad candidate structures.
This distinction is made by estimation of the structure energy. The energy function used in the best state-of-the-art automatic
predictors competing in the most recent CASP (Critical Assessment of Techniques for Protein Structure Prediction) experiment
is defined as a weighted sum of a set of energy terms designed by experts. We hypothesised that combining these terms more
freely will improve the prediction quality. To test this hypothesis, we designed a genetic programming algorithm to evolve
the protein energy function. We compared the predictive power of the best evolved function and a linear combination of energy
terms featuring weights optimised by the Nelder–Mead algorithm. The GP based optimisation outperformed the optimised linear
function. We have made the data used in our experiments publicly available in order to encourage others to further investigate
this challenging problem by using GP and other methods, and to attempt to improve on the results presented here.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9087-0
  • Authors
    • Paweł Widera, University of Nottingham School of Computer Science Nottingham NG8 1BB UK
    • Jonathan M. Garibaldi, University of Nottingham School of Computer Science Nottingham NG8 1BB UK
    • Natalio Krasnogor, University of Nottingham School of Computer Science Nottingham NG8 1BB UK

Natalio Krasnogor, Steve Gustafson, David A. Pelta, and Jose L. Verdegay (eds): Systems self-assembly: multidisciplinary snapshots

Natalio Krasnogor, Steve Gustafson, David A. Pelta, and Jose L. Verdegay (eds): Systems self-assembly: multidisciplinary snapshots
Content Type Journal ArticleCategory Book ReviewDOI 10.1007/s10710-009-9088-zAuthors
Navneet Bhalla, University of Cal…

Natalio Krasnogor, Steve Gustafson, David A. Pelta, and Jose L. Verdegay (eds): Systems self-assembly: multidisciplinary snapshots

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-009-9088-z
  • Authors
    • Navneet Bhalla, University of Calgary Department of Computer Science Calgary AB Canada

The identification and exploitation of dormancy in genetic programming

Abstract  In genetic programming, introns—fragments of code which do not contribute to the fitness of individuals—are usually viewed
negatively, and much research has been undertaken into ways of minimising their occurrence or effects. H…

Abstract  In genetic programming, introns—fragments of code which do not contribute to the fitness of individuals—are usually viewed
negatively, and much research has been undertaken into ways of minimising their occurrence or effects. However, identification
and removal of introns is often computationally expensive and sometimes intractable. We have therefore focused our attention
on one particular class of intron, which we refer to as dormant nodes. Mechanisms for locating such nodes are cheap to implement,
and reveal that the presence of dormancy can be extensive. Once identified, dormancy can be exploited in at least three ways:
improving execution efficiency, improving solution-finding performance, and simplifying program code. Experimentation shows
that the gains to be had in all three cases can be significant.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9086-1
  • Authors
    • David Jackson, University of Liverpool Department of Computer Science Liverpool L69 3BX UK

Automated synthesis of resilient and tamper-evident analog circuits without a single point of failure

Abstract  This study focuses on the use of genetic programming to automate the design of robust analog circuits. We define two complementary
types of failure modes: partial short-circuit and partial disconnect, and demonstrated novel circuit…

Abstract  This study focuses on the use of genetic programming to automate the design of robust analog circuits. We define two complementary
types of failure modes: partial short-circuit and partial disconnect, and demonstrated novel circuits that are resilient across
a spectrum of fault levels. In particular, we focus on designs that are uniformly robust, and unlike designs based on redundancy,
do not have any single point of failure. We also explore the complementary problem of designing tamper-proof circuits that
are highly sensitive to any change or variation in their operating conditions. We find that the number of components remains
similar both for robust and standard circuits, suggesting that the robustness does not necessarily come at significant increased
circuit complexity. A number of fitness criteria, including surrogate models and co-evolution were used to accelerate the
evolutionary process. A variety of circuit types were tested, and the practicality of the generated solutions was verified
by physically constructing the circuits and testing their physical robustness.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9085-2
  • Authors
    • Kyung-Joong Kim, Cornell University Mechanical and Aerospace Engineering Ithaca NY 14853 USA
    • Adrian Wong, Cornell University Electrical and Computer Engineering Ithaca NY 14853 USA
    • Hod Lipson, Cornell University Computing and Information Science 216 Upson Hall Ithaca NY 14853-7501 USA

The influence of mutation on population dynamics in multiobjective genetic programming

Abstract  Using multiobjective genetic programming with a complexity objective to overcome tree bloat is usually very successful but
can sometimes lead to undesirable collapse of the population to all single-node trees. In this paper we repo…

Abstract  Using multiobjective genetic programming with a complexity objective to overcome tree bloat is usually very successful but
can sometimes lead to undesirable collapse of the population to all single-node trees. In this paper we report a detailed
examination of why and when collapse occurs. We have used different types of crossover and mutation operators (depth-fair
and sub-tree), different evolutionary approaches (generational and steady-state), and different datasets (6-parity Boolean
and a range of benchmark machine learning problems) to strengthen our conclusion. We conclude that mutation has a vital role
in preventing population collapse by counterbalancing parsimony pressure and preserving population diversity. Also, mutation
controls the size of the generated individuals which tends to dominate the time needed for fitness evaluation and therefore
the whole evolutionary process. Further, the average size of the individuals in a GP population depends on the evolutionary
approach employed. We also demonstrate that mutation has a wider role than merely culling single-node individuals from the
population; even within a diversity-preserving algorithm such as SPEA2 mutation has a role in preserving diversity.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9084-3
  • Authors
    • Khaled Badran, University of Sheffield Laboratory for Image and Vision Engineering, Department of Electronic and Electrical Engineering Mappin Street Sheffield S1 3JD UK
    • Peter I. Rockett, University of Sheffield Laboratory for Image and Vision Engineering, Department of Electronic and Electrical Engineering Mappin Street Sheffield S1 3JD UK

A three-step decomposition method for the evolutionary design of sequential logic circuits

Abstract  Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate
the configurations of the programmable devices. The scalability is one of the main obstacles preventin…

Abstract  Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate
the configurations of the programmable devices. The scalability is one of the main obstacles preventing EHW from being applied
to real-world applications. Several techniques have been proposed to overcome the scalability problem. One of them is to decompose
the whole circuit into several small evolvable sub-circuits. However, current techniques for scalability are mainly used to
evolve combinational logic circuits. In this paper, in order to decompose a sequential logic circuit, the state decomposition,
output decomposition and input decomposition are united as a three-step decomposition method (3SD). A novel extrinsic EHW
system, namely 3SD–ES, which combines the 3SD method with the (μ, λ) ES (evolution strategy), is proposed, and is used for the evolutionary designing of larger sequential logic circuits. The
proposed extrinsic EHW system is tested extensively on sequential logic circuits taken from the Microelectronics Center of
North Carolina (MCNC) benchmark library. The results demonstrate that 3SD–ES has much better performance in terms of scalability.
It enables the evolutionary designing of larger sequential circuits than have ever been evolved before.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9083-4
  • Authors
    • Houjun Liang, University of Science and Technology of China Nature Inspired Computation and Applications Laboratory (NICAL), Department of Computer Science and Technology 230027 Hefei Anhui China
    • Wenjian Luo, University of Science and Technology of China Nature Inspired Computation and Applications Laboratory (NICAL), Department of Computer Science and Technology 230027 Hefei Anhui China
    • Xufa Wang, University of Science and Technology of China Nature Inspired Computation and Applications Laboratory (NICAL), Department of Computer Science and Technology 230027 Hefei Anhui China

Evolutionary design of Evolutionary Algorithms

Abstract  Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult
task. This is why we have to find other manners to construct algorithms that perform very well on some proble…

Abstract  Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult
task. This is why we have to find other manners to construct algorithms that perform very well on some problems. One possibility
(which is explored in this paper) is to let the evolution discover the optimal structure and parameters of the EA used for
solving a specific problem. To this end a new model for automatic generation of EAs by evolutionary means is proposed here.
The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular
problem. Several Evolutionary Algorithms for function optimization are generated by using the considered model. Numerical
experiments show that the EAs perform similarly and sometimes even better than standard approaches for several well-known
benchmarking problems.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9081-6
  • Authors
    • Laura Dioşan, Babeş-Bolyai University Department of Computer Science, Faculty of Mathematics and Computer Science Kogalniceanu 1 Cluj-Napoca 400084 Romania
    • Mihai Oltean, Babeş-Bolyai University Department of Computer Science, Faculty of Mathematics and Computer Science Kogalniceanu 1 Cluj-Napoca 400084 Romania

Semantic analysis of program initialisation in genetic programming

Abstract  Population initialisation in genetic programming is both easy, because random combinations of syntax can be generated straightforwardly,
and hard, because these random combinations of syntax do not always produce random and diverse…

Abstract  Population initialisation in genetic programming is both easy, because random combinations of syntax can be generated straightforwardly,
and hard, because these random combinations of syntax do not always produce random and diverse program behaviours. In this
paper we perform analyses of behavioural diversity, the size and shape of starting populations, the effects of purely semantic
program initialisation and the importance of tree shape in the context of program initialisation. To achieve this, we create
four different algorithms, in addition to using the traditional ramped half and half technique, applied to seven genetic programming
problems. We present results to show that varying the choice and design of program initialisation can dramatically influence
the performance of genetic programming. In particular, program behaviour and evolvable tree shape can have dramatic effects
on the performance of genetic programming. The four algorithms we present have different rates of success on different problems.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9082-5
  • Authors
    • Lawrence Beadle, University of Kent Computing Laboratory Canterbury CT2 7NF UK
    • Colin G. Johnson, University of Kent Computing Laboratory Canterbury CT2 7NF UK

A review of procedures to evolve quantum algorithms

Abstract  There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by
Shor in 1994 and then Grover in 1996. A lack of invention since Grover’s algorithm has been commonly attri…

Abstract  There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by
Shor in 1994 and then Grover in 1996. A lack of invention since Grover’s algorithm has been commonly attributed to the non-intuitive
nature of quantum algorithms to the classically trained person. Thus, the idea of using computers to automatically generate
quantum algorithms based on an evolutionary model emerged. A limitation of this approach is that quantum computers do not
yet exist and quantum simulation on a classical machine has an exponential order overhead. Nevertheless, early research into
evolving quantum algorithms has shown promise. This paper provides an introduction into quantum and evolutionary algorithms
for the computer scientist not familiar with these fields. The exciting field of using evolutionary algorithms to evolve quantum
algorithms is then reviewed.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9080-7
  • Authors
    • Adrian Gepp, Bond University School of Information Technology Robina QLD Australia
    • Phil Stocks, Bond University School of Information Technology Robina QLD Australia