Category: Evolutionary Intelligence

A two-objective evolutionary approach to design lossy compression algorithms for tiny nodes of wireless sensor networks

Abstract  Since tiny nodes of a wireless sensor network (WSN) are typically powered by batteries with, due to miniaturization and costs,
a limited capacity, with the aim of extending the lifetime of WSNs and making the exploitation of WSNs a…

Abstract  

Since tiny nodes of a wireless sensor network (WSN) are typically powered by batteries with, due to miniaturization and costs,
a limited capacity, with the aim of extending the lifetime of WSNs and making the exploitation of WSNs appealing, a lot of
research has been devoted to save energy. Although a number of factors contribute to power consumption, radio communication
has been generally considered its main cause and thus most of the techniques proposed for energy saving have mainly focused
on limiting transmission/reception of data, for instance, through data compression. As sensor nodes are equipped with limited
computational and storage resources, enabling compression requires to develop purposely-designed algorithms. To this aim,
we propose an approach to generate lossy compressors to be deployed on single nodes based on a differential pulse code modulation
scheme with quantization of the differences between consecutive samples. The quantization levels and thresholds, which allow
achieving different trade-offs between compression performance and information loss, are determined by a two-objective evolutionary
algorithm. We tested our approach on four datasets collected by real WSN deployments. We show that the lossy compressors generated
by our approach can achieve significant compression ratios despite negligible reconstruction errors and outperform LTC, a
lossy compression algorithm purposely designed to be embedded in sensor nodes.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0044-x
  • Authors
    • Francesco Marcelloni, Dipartimento di Ingegneria dell’Informazione, University of Pisa, Via Diotisalvi 2, 56122 Pisa, Italy
    • Massimo Vecchio, Signal Theory and Communications Department, University of Vigo, Vigo, Spain

GPU implementation of a road sign detector based on particle swarm optimization

Abstract  Road Sign Detection is a major goal of the Advanced Driving Assistance Systems. Most published work on this problem share
the same approach by which signs are first detected and then classified in video sequences, even if different…

Abstract  

Road Sign Detection is a major goal of the Advanced Driving Assistance Systems. Most published work on this problem share
the same approach by which signs are first detected and then classified in video sequences, even if different techniques are
used. While detection is usually performed using classical computer vision techniques based on color and/or shape matching,
most often classification is performed by neural networks. In this work we present a novel modular and scalable approach to
road sign detection based on Particle Swarm Optimization, which takes into account both shape and color to detect signs. In
our approach, in particular, the optimization of a single fitness function allows both to detect a sign belonging to a certain
category and, at the same time, to estimate its position with respect to the camera reference frame. To speed up processing,
the algorithm implementation exploits the parallel computing capabilities offered by modern graphics cards and, in particular,
by the Compute Unified Device Architecture by nVIDIA. The effectiveness of the approach has been assessed on both synthetic
and real video sequences, which have been successfully processed at, or close to, full frame rate.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0043-y
  • Authors
    • Luca Mussi, Dipartimento di Ingegneria dell’Informazione, University of Parma, Viale G. Usberti 181a, 43124 Parma, Italy
    • Stefano Cagnoni, Dipartimento di Ingegneria dell’Informazione, University of Parma, Viale G. Usberti 181a, 43124 Parma, Italy
    • Elena Cardarelli, Dipartimento di Ingegneria dell’Informazione, University of Parma, Viale G. Usberti 181a, 43124 Parma, Italy
    • Fabio Daolio, Information Systems Institute (ISI) – HEC, University of Lausanne, Internef 135, CH-1015 Lausanne, Switzerland
    • Paolo Medici, Dipartimento di Ingegneria dell’Informazione, University of Parma, Viale G. Usberti 181a, 43124 Parma, Italy
    • Pier Paolo Porta, Dipartimento di Ingegneria dell’Informazione, University of Parma, Viale G. Usberti 181a, 43124 Parma, Italy

Composition of web services through genetic programming

Abstract  Web Services are interfaces that describe a collection of operations that are network-accessible through standardized web
protocols. When a required operation is not found, several services can be compounded to get a composite serv…

Abstract  

Web Services are interfaces that describe a collection of operations that are network-accessible through standardized web
protocols. When a required operation is not found, several services can be compounded to get a composite service that performs
the desired task. To find this composite service a search process in a, generally, huge search space must be performed. The
algorithm that composes the services must select the adequate atomic processes and, also, must choose the correct way to combine
them using the different available control structures. In this paper a genetic programming algorithm for web services composition
is presented. The algorithm has a context-free grammar to generate the valid structures of the composite services and, also,
it includes a method to update the attributes of each node. Moreover, the proposal tries to minimize the number of services,
and looks for compositions with the minimum execution path. A full experimental validation with four different repositories
with up to 1,090 web services has been done, showing a great performance in all the tests as the algorithm finds a valid solution
with a short execution path.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0042-z
  • Authors
    • Pablo Rodríguez-Mier, Department of Electronics and Computer Science, University of Santiago de Compostela, E-15782 Galicia, Spain
    • Manuel Mucientes, Department of Electronics and Computer Science, University of Santiago de Compostela, E-15782 Galicia, Spain
    • Manuel Lama, Department of Electronics and Computer Science, University of Santiago de Compostela, E-15782 Galicia, Spain
    • Miguel I. Couto, Department of Electronics and Computer Science, University of Santiago de Compostela, E-15782 Galicia, Spain

Use of symmetry and stability for data clustering

Abstract  An important consideration in clustering is the determination of an algorithm appropriate for partitioning a given data set.
Thereafter identification of the correct model order and determining the corresponding partitioning need t…

Abstract  

An important consideration in clustering is the determination of an algorithm appropriate for partitioning a given data set.
Thereafter identification of the correct model order and determining the corresponding partitioning need to be performed.
In this paper, at first the effectiveness of the recently developed symmetry based cluster validity index named Sym-index which provides a measure of “symmetricity” of the different partitionings of a data set is shown to address all the
above mentioned issues, viz., identifying the appropriate clustering algorithm, determining the proper model order and evolving
the proper partitioning as long as the clusters possess the property of symmetry. Results demonstrating the superiority of
the proposed cluster validity measure in appropriately determining the proper clustering technique as well as appropriate
model order as compared to five other recently proposed measures, namely PS-index, I-index, CS-index, well-known XB-index, and stability based index, are provided for several clustering methods viz., two recently
developed genetic algorithm based clustering techniques, the average linkage clustering algorithm, self organizing map and
the expectation maximization clustering algorithm. Five artificial data sets and three real life data sets, are considered
for this purpose. In the second part of the paper, a new measure of stability of clustering solutions over different bootstrap
samples of a data set is proposed. Thereafter a multiobjective optimization based clustering technique is developed which
optimizes both Sym-index and the measure of stability simultaneously to automatically determine the appropriate number of clusters and the appropriate
partitioning of the data sets having symmetrical shaped clusters. Results on five artificial and five real-life data sets
show that the proposed technique is well-suited to detect the number of clusters from data sets having point symmetric clusters.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0041-0
  • Authors
    • Sriparna Saha, Image Processing and Modeling, Interdisciplinary Center for Scientific Computing (IWR), University of Heidelberg, Heidelberg, Germany
    • Ujjwal Maulik, Department of Theoretical Bioinformatics, DKFZ (Deutsches Krebsforschungszentrum, German Cancer Research Center), Heidelberg, Germany

Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms

Abstract  
Markov Chain Monte Carlo (MCMC) methods are often used to sample from intractable target distributions. Some MCMC variants aim to improve the performance
by running a population of MCMC chains. In this paper, we investigate the u…

Abstract  

Markov Chain Monte Carlo (MCMC) methods are often used to sample from intractable target distributions. Some MCMC variants aim to improve the performance
by running a population of MCMC chains. In this paper, we investigate the use of techniques from Evolutionary Computation
(EC) to design population-based MCMC algorithms that exchange useful information between the individual chains. We investigate
how one can ensure that the resulting class of algorithms, called Evolutionary MCMC (EMCMC), samples from the target distribution as expected from any MCMC algorithm. We analytically and experimentally show—using
examples from discrete search spaces—that the proposed EMCMCs can outperform standard MCMCs by exploiting common partial structures
between the more likely individual states. The MCMC chains in the population interact through recombination and selection.
We analyze the required properties of recombination operators and acceptance (or selection) rules in EMCMCs. An important
issue is how to preserve the detailed balance property which is a sufficient condition for an irreducible and aperiodic EMCMC
to converge to a given target distribution. Transferring EC techniques to population-based MCMCs should be done with care.
For instance, we prove that EMCMC algorithms with an elitist acceptance rule do not sample the target distribution correctly.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0040-1
  • Authors
    • Madalina M. Drugan, Utrecht University Department of Information and Computing Sciences PO. Box 80.089 3508 TB Utrecht The Netherlands
    • Dirk Thierens, Utrecht University Department of Information and Computing Sciences PO. Box 80.089 3508 TB Utrecht The Netherlands

Real-world transfer of evolved artificial immune system behaviours between small and large scale robotic platforms

Abstract  In mobile robotics, a solid test for adaptation is the ability of a control system to function not only in a diverse number
of physical environments, but also on a number of different robotic platforms. This paper demonstrates that…

Abstract  

In mobile robotics, a solid test for adaptation is the ability of a control system to function not only in a diverse number
of physical environments, but also on a number of different robotic platforms. This paper demonstrates that a set of behaviours
evolved in simulation on a miniature robot (epuck) can be transferred to a much larger-scale platform (Pioneer), both in simulation
and in the real world. The chosen architecture uses artificial evolution of epuck behaviours to obtain a genetic sequence,
which is then employed to seed an idiotypic, artificial immune system (AIS) on the Pioneers. Despite numerous hardware and
software differences between the platforms, navigation and target-finding experiments show that the evolved behaviours transfer
very well to the larger robot when the idiotypic AIS technique is used. In contrast, transferability is poor when reinforcement
learning alone is used, which validates the adaptability of the chosen architecture.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0039-7
  • Authors
    • Amanda M. Whitbrook, Intelligent Modelling and Analysis Research Group (IMA), School of Computer Science, University of Nottingham, Nottingham, NG8 1BB UK
    • Uwe Aickelin, Intelligent Modelling and Analysis Research Group (IMA), School of Computer Science, University of Nottingham, Nottingham, NG8 1BB UK
    • Jonathan M. Garibaldi, Intelligent Modelling and Analysis Research Group (IMA), School of Computer Science, University of Nottingham, Nottingham, NG8 1BB UK

Multi-stage fuzzy evaluation in evolutionary robot vision for face detection

Abstract  This paper proposes a method of evolutionary robot vision based on a local genetic algorithm based on clustering (LGAC) and
multi-stage fuzzy evaluation. In order to improve the communication capability of human-friendly partner ro…

Abstract  

This paper proposes a method of evolutionary robot vision based on a local genetic algorithm based on clustering (LGAC) and
multi-stage fuzzy evaluation. In order to improve the communication capability of human-friendly partner robots, the human
face should be extracted as correctly as possible. First, we discuss the concept of evolutionary robot vision in dynamic environments.
Next, we propose growing neural gas for preprocessing as a bottom–up processing, and local genetic algorithm based on clustering
for template matching in human face detection as a top–down processing. In order to improve the performance of the human face
detection, we use multi-stage fuzzy evaluation for evaluating the degree of human face. Finally, we show several experimental
results and discuss the effectiveness of the proposed method.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0038-8
  • Authors
    • Akihiro Yorita, Tokyo Metropolitan University Graduate School of System Design Tokyo Japan
    • Naoyuki Kubota, Tokyo Metropolitan University Graduate School of System Design Tokyo Japan

A learning classifier system with mutual-information-based fitness

Abstract  This paper introduces a new variety of learning classifier system (LCS), called MILCS, which utilizes mutual information as
fitness feedback. Unlike most LCSs, MILCS is specifically designed for supervised learning. We present expe…

Abstract  

This paper introduces a new variety of learning classifier system (LCS), called MILCS, which utilizes mutual information as
fitness feedback. Unlike most LCSs, MILCS is specifically designed for supervised learning. We present experimental results,
and contrast them to results from XCS, UCS, GAssist, BioHEL, C4.5 and Naïve Bayes. We discuss the explanatory power of the
resulting rule sets. MILCS is also shown to promote the discovery of default hierarchies, an important advantage of LCSs. Final comments include future directions for this research, including investigations in
neural networks and other systems.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0037-9
  • Authors
    • Robert Elliott Smith, University College London Department of Computer Science London UK
    • Max Kun Jiang, University College London Department of Computer Science London UK
    • Jaume Bacardit, University of Nottingham School of Computer Science Nottingham UK
    • Michael Stout, University of Nottingham School of Computer Science Nottingham UK
    • Natalio Krasnogor, University of Nottingham School of Computer Science Nottingham UK
    • Jonathan D. Hirst, University of Nottingham School of Chemistry Nottingham UK

LSGA: combining level-sets and genetic algorithms for segmentation

Abstract  A novel technique is presented to combine genetic algorithms (GAs) with level-set functions to segment objects with known
shapes and variabilities on images. The individuals of the GA, also known as chromosomes consist of a sequenc…

Abstract  

A novel technique is presented to combine genetic algorithms (GAs) with level-set functions to segment objects with known
shapes and variabilities on images. The individuals of the GA, also known as chromosomes consist of a sequence of parameters of a level-set function. Each chromosome represents a unique segmenting contour. An initial
population of segmenting contours is generated based on the learned variation of the level-set parameters from training images.
Each segmenting contour (an individual) is evaluated for its fitness based on the texture of the region it encloses. The fittest
individuals are allowed to propagate to future generations of the GA run using selection, crossover and mutation. The GA thus
provides a framework for combining texture and shape features for segmentation. Level-set-based segmentation methods typically
perform gradient descent minimization on an energy function to deform a segmenting contour. The computational complexity of
computing derivatives increases as the number of terms increases in the energy function. In contrast, here the level-set-based
curve evolution/deformation is performed derivative-free using a genetic algorithm. The algorithm has been tested for segmenting
thermographic images of hands and for segmenting the prostate in pelvic CT and MRI images. In this paper we describe the former;
the latter is described in [11, 12]. The LSGA successfully segments entire hands on images in which hands are only partially visible. At the end of the paper
we report experimental evaluation of the performance of LSGA and compare it with algorithms using single features: the Gabor
wavelet based textural segmentation method [1, 9], and the level-set based segmentation algorithm of Chan and Vese [6].

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0036-x
  • Authors
    • Payel Ghosh, Portland State University Department of ECE Portland OR USA
    • Melanie Mitchell, Portland State University Department of ECE Portland OR USA
    • Judith Gold, Temple University Department of Public Health Philadelphia PA USA

Evolutionary self-adaptation: a survey of operators and strategy parameters

Abstract  The success of evolutionary search depends on adequate parameter settings. Ill conditioned strategy parameters decrease the
success probabilities of genetic operators. Proper settings may change during the optimization process. The…

Abstract  

The success of evolutionary search depends on adequate parameter settings. Ill conditioned strategy parameters decrease the
success probabilities of genetic operators. Proper settings may change during the optimization process. The question arises
if adequate settings can be found automatically during the optimization process. Evolution strategies gave an answer to the
online parameter control problem decades ago: self-adaptation. Self-adaptation is the implicit search in the space of strategy
parameters. The self-adaptive control of mutation strengths in evolution strategies turned out to be exceptionally successful.
Nevertheless, for years self-adaptation has not achieved the attention it deserves. This paper is a survey of self-adaptive
parameter control in evolutionary computation. It classifies self-adaptation in the taxonomy of parameter setting techniques,
gives an overview of automatic online-controllable evolutionary operators and provides a coherent view on search techniques
in the space of strategy parameters. Beyer and Sendhoff’s covariance matrix self-adaptation evolution strategy is reviewed
as a successful example for self-adaptation and exemplarily tested for various concepts that are discussed.

  • Content Type Journal Article
  • DOI 10.1007/s12065-010-0035-y
  • Authors
    • Oliver Kramer, Technische Universität Dortmund Dortmund Germany