Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2013 | Book

On the Foundations and the Applications of Evolutionary Computing Read chapter Read first chapter

EVOLVE- A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation

Editors: Emilia Tantar, Alexandru-Adrian Tantar, Pascal Bouvry, Pierre Del Moral, Pierrick Legrand, Carlos A. Coello Coello, Oliver Schütze

Publisher: Springer Berlin Heidelberg

Book Series : Studies in Computational Intelligence

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

The aim of this book is to provide a strong theoretical support for understanding and analyzing the behavior of evolutionary algorithms, as well as for creating a bridge between probability, set-oriented numerics and evolutionary computation.

The volume encloses a collection of contributions that were presented at the EVOLVE 2011 international workshop, held in Luxembourg, May 25-27, 2011, coming from invited speakers and also from selected regular submissions. The aim of EVOLVE is to unify the perspectives offered by probability, set oriented numerics and evolutionary computation. EVOLVE focuses on challenging aspects that arise at the passage from theory to new paradigms and practice, elaborating on the foundations of evolutionary algorithms and theory-inspired methods merged with cutting-edge techniques that ensure performance guarantee factors. EVOLVE is also intended to foster a growing interest for robust and efficient methods with a sound theoretical background.

The chapters enclose challenging theoretical findings, concrete optimization problems as well as new perspectives. By gathering contributions from researchers with different backgrounds, the book is expected to set the basis for a unified view and vocabulary where theoretical advancements may echo in different domains.

Table of Contents

Frontmatter

Foundations, Probability and Evolutionary Computation

Frontmatter
On the Foundations and the Applications of Evolutionary Computing
Abstract
Genetic type particle methods are increasingly used to sample from complex high-dimensional distributions. They have found a wide range of applications in applied probability, Bayesian statistics, information theory, and engineering sciences. Understanding rigorously these new Monte Carlo simulation tools leads to fascinating mathematics related to Feynman-Kac path integral theory and their interacting particle interpretations. In this chapter, we provide an introduction to the stochastic modeling and the theoretical analysis of these particle algorithms. We also illustrate these methods through several applications.
Pierre Del Moral, Alexandru-Adrian Tantar, Emilia Tantar
Incorporating Regular Vines in Estimation of Distribution Algorithms
Abstract
This chapter presents the incorporation and use of regular vines into Estimation of Distribution Algorithms for solving numerical optimization problems. Several kinds of statistical dependencies among continuous variables can be taken into account by using regular vines. This work presents a procedure for selecting the most important dependencies in EDAs by truncating regular vines. Moreover, this chapter also shows how the use of mutual information in the learning of graphical models implies a natural way of employing copula functions.
Rogelio Salinas-Gutiérrez, Arturo Hernández-Aguirre, Enrique R. Villa-Diharce
The Gaussian Polytree EDA with Copula Functions and Mutations
Abstract
This chapter introduces the Gaussian Poly-Tree Estimation Distribution Algorithm, and two extensions: i) with Gaussian copula functions, and ii) with local optimizers. The new construction and simulation algorithms, and its application to estimation of distribution algorithms with continuous Gaussian variables are also introduced. The algorithm for the construction of the structure and for edge orientation is based on information theoretic concepts such as mutual information and conditional mutual information. The three models are tested on a benchmark of 20 unimodal and multimodal functions. The version with copula function and mutations excels in most problems achieving near optimal success rate.
Ignacio Segovia Domínguez, Arturo Hernández Aguirre, Enrique Villa Diharce

Set Oriented Numerics

Frontmatter
On Quality Indicators for Black-Box Level Set Approximation
Abstract
This chapter reviews indicators that can be used to compute the quality of approximations to level sets for black-box functions. Such problems occur, for instance, when finding sets of solutions to optimization problems or in solving nonlinear equation systems. After defining and motivating level set problems from a decision theoretic perspective, we discuss quality indicators that could be used to measure how well a set of points approximates a level set. We review simple indicators based on distance, indicators from biodiversity, and propose novel indicators based on the concept of Hausdorff distance. We study properties of these indicators with respect to continuity, spread, and monotonicity and also discuss computational complexity. Moreover, we study the use of these indicators in a simple indicatorbased evolutionary algorithm for level set approximation.
Michael T. M. Emmerich, André H. Deutz, Johannes W. Kruisselbrink
Set Oriented Methods for the Numerical Treatment of Multiobjective Optimization Problems
Abstract
In many applications, it is required to optimize several conflicting objectives concurrently leading to a multobjective optimization problem (MOP). The solution set of a MOP, the Pareto set, typically forms a (k-1)-dimensional object, where k is the number of objectives involved in the optimization problem. The purpose of this chapter is to give an overview of recently developed set oriented techniques - subdivision and continuation methods - for the computation of Pareto sets \(\mathcal{P}\) of a givenMOP. All these methods have in common that they create sequences of box collections which aim for a tight covering of \(\mathcal{P}\). Further, we present a class of multiobjective optimal control problems which can be efficiently handled by the set oriented continuation methods using a transformation into high-dimensionalMOPs. We illustrate all the methods on both academic and real world examples.
Oliver Schütze, Katrin Witting, Sina Ober-Blöbaum, Michael Dellnitz

Landscape, Coevolution and Cooperation

Frontmatter
A Complex-Networks View of Hard Combinatorial Search Spaces
Abstract
According to worst-case complexity analysis, difficult combinatorial problems are those for which no polynomial-time algorithms are known (see, for instance, [15]). Thus, according to this point of view, large enough instances of these problems cannot be solved in reasonable time. The mathematical analysis is primarily based on decision problems, i.e. those that require a yes/no answer [7, 15], but the theory can readily be extended to optimization problems [16], roughly speaking, those in which we seek a solution with an associated minimum or maximum cost, which are the ones that will be dealt with here.
Marco Tomassini, Fabio Daolio
Cooperative Coevolution for Agrifood Process Modeling
Abstract
On the contrary to classical schemes of evolutionary optimisations algorithms, single population Cooperative Co-evolution techniques (CCEAs, also called “Parisian” approaches) make it possible to represent the evolved solution as an aggregation of several individuals (or even as a whole population). In other words, each individual represents only a part of the solution. This scheme allows simulating the principles of Darwinian evolution in a more economic way, which results in gain in robustness and efficiency. The counterpart however is a more complex design phase. In this chapter, we detail the design of efficient CCEAs schemes on two applications related to the modeling of an industrial agri-food process. The experiments correspond to complex optimisations encountered in the modeling of a Camembert-cheese ripening process. Two problems are considered:
  • A deterministic modeling problem, phase prediction, for which a search for a closed form tree expression is performed using genetic programming (GP).
  • A Bayesian network structure estimation problem. The novelty of the proposed approach is based on the use of a two step process based on an intermediate representation called independence model. The search for an independence model is formulated as a complex optimisation problem, for which the CCEA scheme is particularly well suited. A Bayesian network is finally deduced using a deterministic algorithm, as a representative of the equivalence class figured by the independence model.
Olivier Barrière, Evelyne Lutton, Pierre-Henri Wuillemin, Cédric Baudrit, Mariette Sicard, Nathalie Perrot
Hybridizing cGAs with PSO-like Mutation
Abstract
Over the last years, interest in hybrid metaheuristics has risen considerably in the field of optimization. Combinations of operators andmetaheuristics have provided very powerful search techniques. In this chapter we incorporate active components of Particle Swarm Optimization (PSO) into the Cellular Genetic Algorithm(cGA).We replace themutation operator by amutation based on concepts of PSO. We present two hybrid algorithms and analyze their performance using a set of different problems. The results obtained are quite satisfactory in efficacy and efficiency, outperforming in most cases existing algorithms for a set of problems.
E. Alba, A. Villagra

Multi-objective Optimization, Heuristic Conversion Algorithms

Frontmatter
On Gradient-Based Local Search to Hybridize Multi-objective Evolutionary Algorithms
Abstract
Using evolutionary algorithms when solving multi-objective optimization problems (MOPs) has shown remarkable results during the last decade. As a consolidated research area it counts with a number of guidelines and processes; even though, their efficiency is still a big issue which lets room for improvements. In this chapter we explore the use of gradient-based information to increase efficiency on evolutionary methods, when dealing with smooth real-valued MOPs. We show the main aspects to be considered when building local search operators using the objective function gradients, and when coupling them with evolutionary algorithms. We present an overview of our current methods with discussion about their convenience for particular kinds of problems.
Adriana Lara, Oliver Schütze, Carlos A. Coello Coello
On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems
Abstract
We present a modular and flexible algorithmic framework to enable a fusion of scheduling theory and evolutionary multi-objective combinatorial optimization. For single-objective scheduling problems, that is the optimization of task assignments to sparse resources over time, a variety of optimal algorithms or heuristic rules are available. However, in the multi-objective domain it is often impossible to provide specific and theoretically well founded algorithmic solutions. In that situation, multi-objective evolutionary algorithms are commonly used. Although several standard heuristics from this domain exist, most of them hardly allow the integration of available single-objective problem knowledge without complex redesign of the algorithms structure itself. The redesign and tuned application of common evolutionary multi-objective optimizers is far beyond the scope of scheduling research. We therefore describe a framework based on a cellular and agent-based approach which allows the straightforward construction of multi-objective optimizers by compositing single-objective scheduling heuristics. In a case study, we address strongly NP-hard parallel machine scheduling problems and compose optimizers combining the known single-objective results. We eventually show that this approach can bridge between scheduling theory and evolutionary multi-objective search.
Christian Grimme, Markus Kemmerling, Joachim Lepping
Analysing the Robustness of Multiobjectivisation Approaches Applied to Large Scale Optimisation Problems
Abstract
Multiobjectivisation transforms a mono-objective problem into a multiobjective one. The main aim of multiobjectivisation is to avoid stagnation in local optima, by changing the landscape of the original fitness function. In this contribution, an analysis of different multiobjectivisation approaches has been performed. It has been carried out with a set of scalable mono-objective benchmark problems. The experimental evaluation has demonstrated the advantages of multiobjectivisation, both in terms of quality and saved resources. However, it has been revealed that it produces a negative effect in some cases. Some multiobjectivisation schemes require the specification of additional parameters which must be adapted for dealing with different problems. Multiobjectivisation with parameters has been proposed as a method to improve the performance of the whole optimisation scheme. Nevertheless, the parameter setting of an optimisation scheme which considers multiobjectivisation with parameters is usually more complex. In this work, a new model based on the usage of hyperheuristics to facilitate the application of multiobjectivisation with parameters has been proposed. Experimental evaluation has shown that this model has increased the robustness of the whole optimisation scheme.
Carlos Segura, Eduardo Segredo, Coromoto León
A Comparative Study of Heuristic Conversion Algorithms, Genetic Programming and Return Predictability on the German Market
Abstract
This paper evaluates the predictability of the heuristic conversion algorithms Moving Average Crossover and Trading Range Breakout in the German stock market. Hypothesis testing and a bootstrap procedure are used to test for predictive ability. Results show that the algorithms considered do not have predictive ability. Further, Genetic Programming is used to adapt the buying and selling rules of the investigated algorithms resulting in a new algorithm. Results show that a genetic programming approach does not lead to good new algorithms. We extend former works by using the Sortino Ratio as a measure of risk, and by applying competitive analysis.
Esther Mohr, Günter Schmidt, Sebastian Jansen
Metadata
Title
EVOLVE- A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation
Editors
Emilia Tantar
Alexandru-Adrian Tantar
Pascal Bouvry
Pierre Del Moral
Pierrick Legrand
Carlos A. Coello Coello
Oliver Schütze
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-32726-1
Print ISBN
978-3-642-32725-4
DOI
https://doi.org/10.1007/978-3-642-32726-1

Premium Partner

    Image Credits