Category: Genetic Programming and Evolvable Machines

Sean Luke: essentials of metaheuristics

Sean Luke: essentials of metaheuristics
Content Type Journal ArticlePages 333-334DOI 10.1007/s10710-011-9139-0Authors
Michael Lones, University of York, York, UK

Journal Genetic Programming and Evolvable MachinesOnline ISSN 1573-7632Print ISS…

Sean Luke: essentials of metaheuristics

  • Content Type Journal Article
  • Pages 333-334
  • DOI 10.1007/s10710-011-9139-0
  • Authors
    • Michael Lones, University of York, York, UK

Introduction: special issue on evolvable hardware challenges

Introduction: special issue on evolvable hardware challenges
Content Type Journal ArticlePages 181-182DOI 10.1007/s10710-011-9138-1Authors
Pauline C. Haddow, CRAB Lab, Department of Computer Science and Informatics, The Norwegian University of Scien…

Introduction: special issue on evolvable hardware challenges

  • Content Type Journal Article
  • Pages 181-182
  • DOI 10.1007/s10710-011-9138-1
  • Authors
    • Pauline C. Haddow, CRAB Lab, Department of Computer Science and Informatics, The Norwegian University of Science and Technology (NTNU), Trondheim, Norway

The evolution of standard cell libraries for future technology nodes

Abstract  Evolvable Hardware has been a discipline for over 15 years. Its application has ranged from simple circuit design to antenna
design. However, research in the field has often been criticised for not addressing real world proble…

Abstract  

Evolvable Hardware has been a discipline for over 15 years. Its application has ranged from simple circuit design to antenna
design. However, research in the field has often been criticised for not addressing real world problems. Intrinsic variability
has been recognised as one of the major challenges facing the semiconductor industry. This paper describes an approach that
optimises designs within a standard cell library by altering the transistor dimensions. The proposed approach uses a Multi-objective
Genetic Algorithm to optimise the device widths within a standard cell. The designs are analysed using statistically enhanced
transistor models (based on 3D-atomistic simulations) and statistical Spice simulations. The goal is to extract high-speed and low-power designs, which are more tolerant to the random fluctuations
present in current and future technology nodes. The results show improvements in both the speed and power of the optimised
standard cells and that the impact of threshold voltage variation is reduced.

  • Content Type Journal Article
  • Pages 235-256
  • DOI 10.1007/s10710-011-9131-8
  • Authors
    • James Alfred Walker, Intelligent Systems Group, Department of Electronics, University of York, Heslington, York, YO10 5DD UK
    • James A. Hilder, Intelligent Systems Group, Department of Electronics, University of York, Heslington, York, YO10 5DD UK
    • Dave Reid, Device Modelling Group, Department of Electronics and Electrical Engineering, University of Glasgow, Rankine Building, Oakfield Avenue, Glasgow, G12 8LT UK
    • Asen Asenov, Device Modelling Group, Department of Electronics and Electrical Engineering, University of Glasgow, Rankine Building, Oakfield Avenue, Glasgow, G12 8LT UK
    • Scott Roy, Device Modelling Group, Department of Electronics and Electrical Engineering, University of Glasgow, Rankine Building, Oakfield Avenue, Glasgow, G12 8LT UK
    • Campbell Millar, Device Modelling Group, Department of Electronics and Electrical Engineering, University of Glasgow, Rankine Building, Oakfield Avenue, Glasgow, G12 8LT UK
    • Andy M. Tyrrell, Intelligent Systems Group, Department of Electronics, University of York, Heslington, York, YO10 5DD UK

Accelerating floating-point fitness functions in evolutionary algorithms: a FPGA-CPU-GPU performance comparison

Abstract  Many large combinatorial optimization problems tackled with evolutionary algorithms often require very high computational
times, usually due to the fitness evaluation. This fact forces programmers to use clusters of computers, a co…

Abstract  

Many large combinatorial optimization problems tackled with evolutionary algorithms often require very high computational
times, usually due to the fitness evaluation. This fact forces programmers to use clusters of computers, a computational solution
very useful for running applications of intensive calculus but having a high acquisition price and operation cost, mainly
due to the Central Processing Unit (CPU) power consumption and refrigeration devices. A low-cost and high-performance alternative
comes from reconfigurable computing, a hardware technology based on Field Programmable Gate Array devices (FPGAs). The main
objective of the work presented in this paper is to compare implementations on FPGAs and CPUs of different fitness functions
in evolutionary algorithms in order to study the performance of the floating-point arithmetic in FPGAs and CPUs that is often
present in the optimization problems tackled by these algorithms. We have taken advantage of the parallelism at chip-level
of FPGAs pursuing the acceleration of the fitness functions (and consequently, of the evolutionary algorithms) and showing
the parallel scalability to reach low cost, low power and high performance computational solutions based on FPGA. Finally,
the recent popularity of GPUs as computational units has moved us to introduce these devices in our performance comparisons.
We analyze performance in terms of computation times and economic cost.

  • Content Type Journal Article
  • Pages 403-427
  • DOI 10.1007/s10710-011-9137-2
  • Authors
    • Juan A. Gomez-Pulido, Department of Technologies of Computers and Communications, University of Extremadura, 10003 Caceres, Spain
    • Miguel A. Vega-Rodriguez, Department of Technologies of Computers and Communications, University of Extremadura, 10003 Caceres, Spain
    • Juan M. Sanchez-Perez, Department of Technologies of Computers and Communications, University of Extremadura, 10003 Caceres, Spain
    • Silvio Priem-Mendes, Department of Computer Science, School of Technology and Management, Polytechnic Institute of Leiria, 2410 Leiria, Portugal
    • Vitor Carreira, Department of Computer Science, School of Technology and Management, Polytechnic Institute of Leiria, 2410 Leiria, Portugal

Defining locality as a problem difficulty measure in genetic programming

Abstract  A mapping is local if it preserves neighbourhood. In Evolutionary Computation, locality is generally described as the property
that neighbouring genotypes correspond to neighbouring phenotypes. A representation has high locality if…

Abstract  

A mapping is local if it preserves neighbourhood. In Evolutionary Computation, locality is generally described as the property
that neighbouring genotypes correspond to neighbouring phenotypes. A representation has high locality if most genotypic neighbours
are mapped to phenotypic neighbours. Locality is seen as a key element in performing effective evolutionary search. It is
believed that a representation that has high locality will perform better in evolutionary search and the contrary is true
for a representation that has low locality. When locality was introduced, it was the genotype-phenotype mapping in bitstring-based
Genetic Algorithms which was of interest; more recently, it has also been used to study the same mapping in Grammatical Evolution.
To our knowledge, there are few explicit studies of locality in Genetic Programming (GP). The goal of this paper is to shed
some light on locality in GP and use it as an indicator of problem difficulty. Strictly speaking, in GP the genotype and the
phenotype are not distinct. We attempt to extend the standard quantitative definition of genotype-phenotype locality to the
genotype-fitness mapping by considering three possible definitions. We consider the effects of these definitions in both continuous-
and discrete-valued fitness functions. We compare three different GP representations (two of them induced by using different
function sets and the other using a slightly different GP encoding) and six different mutation operators. Results indicate
that one definition of locality is better in predicting performance.

  • Content Type Journal Article
  • Pages 365-401
  • DOI 10.1007/s10710-011-9136-3
  • Authors
    • Edgar Galván-López, Natural Computing Research and Applications Group, University College Dublin, Dublin, Ireland
    • James McDermott, Natural Computing Research and Applications Group, University College Dublin, Dublin, Ireland
    • Michael O’Neill, Natural Computing Research and Applications Group, University College Dublin, Dublin, Ireland
    • Anthony Brabazon, Natural Computing Research and Applications Group, University College Dublin, Dublin, Ireland

Hardware spiking neural network prototyping and application

Abstract  EMBRACE has been proposed as a scalable, reconfigurable, mixed signal, embedded hardware Spiking Neural Network (SNN) device.
EMBRACE, which is yet to be realised, targets the issues of area, power and scalability through the use o…

Abstract  

EMBRACE has been proposed as a scalable, reconfigurable, mixed signal, embedded hardware Spiking Neural Network (SNN) device.
EMBRACE, which is yet to be realised, targets the issues of area, power and scalability through the use of a low area, low
power analogue neuron/synapse cell, and a digital packet-based Network on Chip (NoC) communication architecture. The paper
describes the implementation and testing of EMBRACE-FPGA, an FPGA-based hardware SNN prototype. The operation of the NoC inter-neuron
communication approach and its ability to support large scale, reconfigurable, highly interconnected SNNs is illustrated.
The paper describes an integrated training and configuration platform and an on-chip fitness function, which supports GA-based
evolution of SNN parameters. The practicalities of using the SNN development platform and SNN configuration toolset are described.
The paper considers the impact of latency jitter noise introduced by the NoC router and the EMBRACE-FPGA processor-based neuron/synapse
model on SNN accuracy and evolution time. Benchmark SNN applications are described and results demonstrate the evolution of
high quality and robust solutions in the presence of noise. The reconfigurable EMBRACE architecture enables future investigation
of adaptive hardware applications and self repair in evolvable hardware.

  • Content Type Journal Article
  • Pages 257-280
  • DOI 10.1007/s10710-011-9130-9
  • Authors
    • Seamus Cawley, Bio-Inspired and Reconfigurable Computing Research Group, National University of Ireland, Galway, Galway, Ireland
    • Fearghal Morgan, Bio-Inspired and Reconfigurable Computing Research Group, National University of Ireland, Galway, Galway, Ireland
    • Brian McGinley, Bio-Inspired and Reconfigurable Computing Research Group, National University of Ireland, Galway, Galway, Ireland
    • Sandeep Pande, Bio-Inspired and Reconfigurable Computing Research Group, National University of Ireland, Galway, Galway, Ireland
    • Liam McDaid, Intelligent Systems Research Centre, University of Ulster, Magee Campus, Derry, Northern Ireland,UK
    • Snaider Carrillo, Intelligent Systems Research Centre, University of Ulster, Magee Campus, Derry, Northern Ireland,UK
    • Jim Harkin, Intelligent Systems Research Centre, University of Ulster, Magee Campus, Derry, Northern Ireland,UK

An evolved anti-jamming adaptive beamforming network

Abstract  Interference in wireless networks is undesirable, whether it is due to unintentional or malicious causes. Adaptive beamforming
is a spatial filtering technique that can prevent jammers from disrupting wireless networks. This paper …

Abstract  

Interference in wireless networks is undesirable, whether it is due to unintentional or malicious causes. Adaptive beamforming
is a spatial filtering technique that can prevent jammers from disrupting wireless networks. This paper presents an evolvable
hardware (EH) application in which an evolutionary algorithm (EA) is used to configure an adaptive beamformer to achieve two
goals: (1) steering nulls towards jamming signals and (2) directing gain in the direction of the desired signal. This is the
first demonstration of an EA-configured adaptive beamformer to counter a jamming system. Simulation results show that the
EA is able to thwart up to three jamming signals. The results suggest that EH is a promising approach towards wireless network
security.

  • Content Type Journal Article
  • Pages 217-234
  • DOI 10.1007/s10710-011-9134-5
  • Authors
    • Jason D. Lohn, Department of Electrical and Computer Engineering, Carnegie Mellon University, Silicon Valley Campus, Mountain View, CA, USA
    • Jonathan M. Becker, Department of Electrical and Computer Engineering, Carnegie Mellon University, Silicon Valley Campus, Mountain View, CA, USA
    • Derek S. Linden, X5 Systems Inc, Ashburn, VA, USA

Open BEAGLE: a generic framework for evolutionary computations

Open BEAGLE: a generic framework for evolutionary computations
Content Type Journal ArticlePages 329-331DOI 10.1007/s10710-011-9135-4Authors
Dmitry Batenkov, Weizmann Institute of Science, Rehovot, Israel

Journal Genetic Programming and Evolv…

Open BEAGLE: a generic framework for evolutionary computations

  • Content Type Journal Article
  • Pages 329-331
  • DOI 10.1007/s10710-011-9135-4
  • Authors
    • Dmitry Batenkov, Weizmann Institute of Science, Rehovot, Israel

Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware

Abstract  We propose to utilize a formal verification algorithm to reduce the fitness evaluation time for evolutionary post-synthesis
optimization in evolvable hardware. The proposed method assumes that a fully functional digital circuit is …

Abstract  

We propose to utilize a formal verification algorithm to reduce the fitness evaluation time for evolutionary post-synthesis
optimization in evolvable hardware. The proposed method assumes that a fully functional digital circuit is available. A post-synthesis
optimization is then conducted using Cartesian Genetic Programming (CGP) which utilizes a satisfiability problem solver to
decide whether a candidate solution is functionally correct or not. It is demonstrated that the method can optimize digital
circuits of tens of inputs and thousands of gates. Furthermore, the number of gates was reduced for the LGSynth93 benchmark
circuits by 37.8% on average with respect to results of the conventional SIS tool.

  • Content Type Journal Article
  • Pages 305-327
  • DOI 10.1007/s10710-011-9132-7
  • Authors
    • Zdenek Vasicek, Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic
    • Lukas Sekanina, Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic

Evolution of human-competitive lossless compression algorithms with GP-zip2

Abstract  We propose GP-zip2, a new approach to lossless data compression based on Genetic Programming (GP). GP is used to optimally
combine well-known lossless compression algorithms to maximise data compression. GP-zip2 evolves programs wi…

Abstract  

We propose GP-zip2, a new approach to lossless data compression based on Genetic Programming (GP). GP is used to optimally
combine well-known lossless compression algorithms to maximise data compression. GP-zip2 evolves programs with multiple components.
One component analyses statistical features extracted by sequentially scanning the data to be compressed and divides the data
into blocks. These blocks are projected onto a two-dimensional Euclidean space via two further (evolved) program components.
K-means clustering is then applied to group similar data blocks. Each cluster is labelled with the optimal compression algorithm
for its member blocks. After evolution, evolved programs can be used to compress unseen data. The compression algorithms available
to GP-zip2 are: Arithmetic coding, Lempel-Ziv-Welch, Unbounded Prediction by Partial Matching, Run Length Encoding, and Bzip2.
Experimentation shows that the results produced by GP-zip2 are human-competitive, being typically superior to well-established
human-designed compression algorithms in terms of the compression ratios achieved in heterogeneous archive files.

  • Content Type Journal Article
  • Pages 335-364
  • DOI 10.1007/s10710-011-9133-6
  • Authors
    • Ahmed Kattan, School of Computer Science and Electronic Engineering, University of Essex, Colchester, CO4 3SQ UK
    • Riccardo Poli, School of Computer Science and Electronic Engineering, University of Essex, Colchester, CO4 3SQ UK