nach oben

2008 | Buch

Kapitel lesen Erstes Kapitel lesen

Artificial Evolution

8th International Conference, Evolution Artificielle, EA 2007, Tours, France, October 29-31, 2007, Revised Selected Papers

herausgegeben von: Nicolas Monmarché, El-Ghazali Talbi, Pierre Collet, Marc Schoenauer, Evelyne Lutton

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Inhaltsverzeichnis

Frontmatter

Genetic Programming

Treating Noisy Data Sets with Relaxed Genetic Programming

Abstract

In earlier papers we presented a technique (“RelaxGP”) for improving the performance of the solutions generated by Genetic Programming (GP) applied to regression and approximation of symbolic functions. RelaxGP changes the definition of a perfect solution: in standard symbolic regression, a perfect solution provides exact values for each point in the training set. RelaxGP allows a perfect solution to belong to a certain interval around the desired values.

We applied RelaxGP to regression problems where the input data is noisy. This is indeed the case in several “real-world” problems, where the noise comes, for example, from the imperfection of sensors. We compare the performance of solutions generated by GP and by RelaxGP in the regression of 5 noisy sets. We show that RelaxGP with relaxation values of 10% to 100% of the gaussian noise found in the data can outperform standard GP, both in terms of generalization error reached and in resources required to reach a given test error.

Luis Da Costa, Jacques-André Landry, Yan Levasseur

Cost-Benefit Investigation of a Genetic-Programming Hyperheuristic

Abstract

In previous work, we have introduced an effective, grammar-based, linear Genetic-Programming hyperheuristic, i.e., a search heuristic on the space of heuristics. Here we further investigate this approach in the context of search performance and resource utilisation. For the chosen realistic travelling salesperson problems it shows that the hyperheuristic routinely produces metaheuristics that find tours whose lengths are highly competitive with the best results from literature, while population size, genotype size, and run time can be kept very moderate.

Robert E. Keller, Riccardo Poli

Automatic Design of Vision-Based Obstacle Avoidance Controllers Using Genetic Programming

Abstract

The work presented in this paper is part of the development of a robotic system able to learn context dependent visual clues to navigate in its environment. We focus on the obstacle avoidance problem as it is a necessary function for a mobile robot. As a first step, we use an off-line procedure to automatically design algorithms adapted to the visual context. This procedure is based on genetic programming and the candidate algorithms are evaluated in a simulation environment. The evolutionary process selects meaningful visual primitives in the given context and an adapted strategy to use them. The results show the emergence of several different behaviors outperforming hand-designed controllers.

Renaud Barate, Antoine Manzanera

Generating SAT Local-Search Heuristics Using a GP Hyper-Heuristic Framework

Abstract

We present GP-HH, a framework for evolving local-search 3-SAT heuristics based on GP. The aim is to obtain “disposable” heuristics which are evolved and used for a specific subset of instances of a problem. We test the heuristics evolved by GP-HH against well-known local-search heuristics on a variety of benchmark SAT problems. Results are very encouraging.

Mohamed Bader-El-Den, Riccardo Poli

Swarm Intelligence

Magnetic Resonance Image Segmentation Based on Two-Dimensional Exponential Entropy and a Parameter Free PSO

Abstract

In this paper, a magnetic resonance image (MRI) segmentation method based on two-dimensional exponential entropy (2DEE) and parameter free particle swarm optimization (PSO) is proposed. The 2DEE technique does not consider only the distribution of the gray level information but also takes advantage of the spatial information using the 2D-histogram. The problem with this method is its time-consuming computation that is an obstacle in real time applications for instance. We propose to use a parameter free PSO algorithm called TRIBES, that was proved efficient for combinatorial and non convex optimization. The experiments on segmentation of MRI images proved that the proposed method can achieve a satisfactory segmentation with a low computation cost.

Amir Nakib, Yann Cooren, Hamouche Oulhadj, Patrick Siarry

Mimetic Variations on Stigmergic Swarm Paintings

Abstract

This paper explores artificial collective artistic work inspired by natural phenomena, namely the use of pheromone substances for mass recruitment in ants. Our goal is to look for innovative patterns using techniques derived from Artificial Life. We will play 2 variations, based on imitation, on a society of anonymous and homogeneous artificial micro-painters (the Colombines). In the Colombines model the virtual canvas, besides being a computational space for depositing paint, is also a pheromone medium, mirroring the painting patterns and influencing the painters’ behaviour. More, the micro-painters do not exchange information directly with each other, they are simply attracted towards non-painting areas of the canvas—the non-painted “tableaux” patches diffuse an “environmental produced” chemical and the painters prefer to follow the chemical gradient. Thus, this form of stigmergic communication simply influences the artistic agents movements. We will expand the Colombines basic model adding direct communication between the micro-artists: they will imitate the colour of others. In the first variation, they will imitate the colour of who ever they interact with and in the second one they will have a force attribute and colour imitation will depend on the force relationship between them.

Paulo Urbano

Minimal and Necessary Conditions for the Emergence of Species-Specific Recognition Patterns

Abstract

A simple mechanism is presented for the emergence of recognition patterns that are used by individuals to find each other and mate. The genetic component determines the brain of an individual, a machine learning architecture which is then used to transmit knowledge. Thanks to the interactions between the genetic and the knowledge parts the agents get to use species-specific recognition patterns, starting from an initial condition where the species are not distinguishable. Several machine learning architectures are investigated, as well as the influence of space and asynchronous genetic algorithm operations. Agents selecting each other for mating based on their limited recognition capacities is all that is needed for the emergence of species-specific recognition patterns: the transition between symbols to sequences with an intrinsic role within the species.

Nicolas Brodu

Artificial Ants for the Optimization of Virtual Keyboard Arrangement for Disabled People

Abstract

Many physically impaired people can meet difficulties when using a computer and particularly with the keyboard. Often, a virtual keyboard can improve the usability of the computer system by handicapped people and can be adapted to their disabilities. From a combinatorial point of view, artificial ants have been studied to improve classical keyboard arrangements. This paper present how this method can fit the first problem and then become a tool to build new “tailor-made” keyboards. Then, the artificial ants meta-heuristic can be used as often as needed as an optimizer that take into account user’s activities of writing.

Sonia Colas, Nicolas Monmarché, Pierre Gaucher, Mohamed Slimane

Combinational and Multi-objective Optimization

Self-organization and Evolution Combined to Address the Vehicle Routing Problem

Abstract

The paper deals with a self-organizing system in a evolutionary framework applied to the Euclidean Vehicle Routing Problem (VRP). Theoretically, self-organization is intended to allow adaptation to noisy data as well as to confer robustness according to demand fluctuation. Evolution through selection is intended to guide a population based search toward near-optimal solutions. To implement such principles to address the VRP, the approach uses the standard self-organizing map algorithm as a main operator embedded in a evolutionary loop. We evaluate the approach on standard benchmark problems and show that it performs better, with respect to solution quality and/or computation time, than other self-organizing neural networks to the VRP presented in the literature. As well, it substantially reduces the gap to some classical Operations Research heuristics.

Jean-Charles Créput, Abderrafiaâ Koukam

An Evolutionary Algorithm for the Block Stacking Problem

Abstract

How has a stack of n blocks to be arranged in order to maximize its overhang over a table edge while being stable? This question can be seen as an example application for applied statics and at the same time leads to a challenging optimization problem that was discussed recently in two theoretical studies.

Here, we address this problem by designing an evolutionary algorithm; the proposed method is applied to two instances of the block stacking problem, maximizing the overhang for 20 and 50 block stacks. The study demonstrates that the stacking problem is worthwhile to be investigated in the context of randomized search algorithms: it represents an abstract, but still demanding instance of many real-world applications. Furthermore, the proposed algorithm may become useful in empirically testing the tightness of theoretical upper bounds proposed for this problem.

Tim Hohm, Matthias Egli, Samuel Gaehwiler, Stefan Bleuler, Jonathan Feller, Damian Frick, Richard Huber, Mathias Karlsson, Reto Lingenhag, Thomas Ruetimann, Tom Sasse, Thomas Steiner, Janine Stocker, Eckart Zitzler

A Study of Evaluation Functions for the Graph K-Coloring Problem

Abstract

The evaluation or fitness function is a key component of any heuristic search algorithm. This paper introduces a new evaluation function for the well-known graph K-coloring problem. This function takes into account not only the number of conflicting vertices, but also inherent information related to the structure of the graph. To assess the effectiveness of this new evaluation function, we carry out a number of experiments using a set of DIMACS benchmark graphs. Based on statistic data obtained with a parameter free steepest descent, we show an improvement of the new evaluation function over the classical one.

Daniel Cosmin Porumbel, Jin-Kao Hao, Pascale Kuntz

Genetic Branch-and-Bound or Exact Genetic Algorithm?

Abstract

Production resettings is a vital element of production flexibility and optimizing the setup tasks scheduling within a production channel is required to improve production rate. This paper deals with a NP-Hard production resetting optimization problem based on an industrial case. In this paper we present how to hybrid a Branch-and-Bound method for this problem with a genetic algorithm. The idea is to use the genetic algorithm to improve the upper bound and thus speeding up the Branch-and-Bound while the genetic algorithm uses the content of the Branch-and-Bound stack to reduce its search space. Both methods are running in parallel and are therefore collaborating together.

Cédric Pessan, Jean-Louis Bouquard, Emmanuel Néron

Aerodynamic Topology Optimisation Using an Implicit Representation and a Multiobjective Genetic Algorithm

Abstract

Given the focus on incremental change in existing empirical aerodynamic design methods, radical, unintuitive, new optimal solutions in previously unexplored regions of design space are very unlikely to be found using them. We present a framework based on an implicit shape representation and a multiobjective evolutionary algorithm that aims to produce a variety of optimal flow topologies for a given requirement, providing designers with insights into possibly radical solutions. A revolutionary integrated flow simulation system developed specifically for design work is used to evaluate candidate designs.

Windo Hutabarat, Geoffrey T. Parks, Jerome P. Jarrett, William N. Dawes, P. John Clarkson

Direct and Indirect Representations for Evolutionary Design of Objects

Abstract

We follow up on the work of Ebner[1] in studying representations for evolutionary design of objects. We adopt both the method and the simulation framework, and perform more thorough experiments. We design new representations, both direct and indirect, and compare their performance to the original work. We design and make use of a specialised system for distributed computing that integrates smoothly with the EO library[5]. First, we confirm the results of Ebner with VRML scene graphs representation. Next, we demonstrate how both of the new representations based on triangular mesh perform significantly better. Finally, we study and improve the performance of the distributed system that we utilised to run our experiments on tens of computing nodes.

Juraj Plavcan, Pavel Petrovic

Adaptive and Assortative Mating Scheme for Evolutionary Multi-Objective Algorithms

Abstract

We are interested in the role of restricted mating schemes in the context of evolutionary multi-objective algorithms. In this paper, we propose an adaptive assortative mating scheme that uses similarity in the decision space (genotypic assortative mating) and adapts the mating pressure as the search progresses. We show that this mechanism improves the performance of the simple evolutionary algorithm for multi-objective optimisation (SEAMO2) on the multiple knapsack problem.

Khoi Le, Dario Landa-Silva

Theory in GA and ES

The Cooperative Royal Road: Avoiding Hitchhiking

Abstract

We propose using the so called Royal Road functions as test functions for cooperative co-evolutionary algorithms (CCEAs). The Royal Road functions were created in the early 90’s with the aim of demonstrating the superiority of genetic algorithms over local search methods. Unexpectedly, the opposite was found to be true. The research deepened our understanding of the phenomenon of hitchhiking where unfavorable alleles may become established in the population following an early association with an instance of a highly fit schema. Here, we take advantage of the modular and hierarchical structure of the Royal Road functions to adapt them to a co-evolutionary setting. Using a multiple population approach, we show that a CCEA easily outperforms a standard genetic algorithm on the Royal Road functions, by naturally overcoming the hitchhiking effect. Moreover, we found that the optimal number of sub-populations for the CCEA is not the same as the number of components that the function can be linearly separated into, and propose an explanation for this behavior. We argue that this class of functions may serve in foundational studies of cooperative co-evolution.

Gabriela Ochoa, Evelyne Lutton, Edmund Burke

Conditioning, Halting Criteria and Choosing λ

Abstract

We show the convergence of 1 + λ-ES with standard step-size update-rules on a large family of fitness functions without any convexity assumption or quasi-convexity assumptions ([3,6]). The result provides a rule for choosing λ and shows the consistency of halting criteria based on thresholds on the step-size.

The family of functions under work is defined through a condition-number that generalizes usual condition-numbers in a manner that only depends on level-sets. We consider that the definition of this condition-number is the relevant one for evolutionary algorithms; in particular, global convergence results without convexity or quasi-convexity assumptions are proved when this condition-number is finite.

Olivier Teytaud

Log-Linear Convergence and Optimal Bounds for the (1 + 1)-ES

Abstract

The (1 + 1)-ES is modeled by a general stochastic process whose asymptotic behavior is investigated. Under general assumptions, it is shown that the convergence of the related algorithm is sub-log-linear, bounded below by an explicit log-linear rate. For the specific case of spherical functions and scale-invariant algorithm, it is proved using the Law of Large Numbers for orthogonal variables, that the linear convergence holds almost surely and that the best convergence rate is reached. Experimental simulations illustrate the theoretical results.

Mohamed Jebalia, Anne Auger, Pierre Liardet

Applications of EAs

Evolution Strategies for Laser Pulse Compression

Abstract

This study describes first steps taken to bring evolutionary optimization technology from computer simulations to real world experimentation in physics laboratories. The approach taken considers a well understood Laser Pulse Compression problem accessible both to simulation and laboratory experimentation as a test function for variants of Evolution Strategies. The main focus lies on coping with the unavoidable noise present in laboratory experimentation. Results from simulations are compared to previous studies and to laboratory experiments.

Riccardo Fanciulli, Lars Willmes, Janne Savolainen, Peter van der Walle, Thomas Bäck, Jennifer L. Herek

Fully Three-Dimensional Tomographic Evolutionary Reconstruction in Nuclear Medicine

Abstract

3-D reconstruction in Nuclear Medicine imaging using complete Monte-Carlo simulation of trajectories usually requires high computing power. We are currently developing a Parisian Evolution Strategy in order to reduce the computing cost of reconstruction without degrading the quality of results. Our approach derives from the Fly algorithm which proved successful on real-time stereo image sequence processing. Flies are considered here as photon emitters. We developed the marginal fitness technique to calculate the fitness function, an approach usable in Parisian Evolution whenever each individual’s fitness cannot be calculated independently of the rest of the population.

Aurélie Bousquet, Jean Louchet, Jean-Marie Rocchisani

A Study of Crossover Operators for Gene Selection of Microarray Data

Abstract

Classification of microarray data requires the selection of a subset of relevant genes in order to achieve good classification performance. Several genetic algorithms have been devised to perform this search task. In this paper, we carry out a study on the role of crossover operator and in particular investigate the usefulness of a highly specialized crossover operator called GeSeX (GEne SElection crossover) that takes into account gene ranking information provided by a Support Vector Machine classifier. We present experimental evidences about its performance compared with two other conventional crossover operators. Comparisons are also carried out with several recently reported genetic algorithms on four well-known benchmark data sets.

Jose Crispin Hernandez Hernandez, Béatrice Duval, Jin-Kao Hao

Searching for Glider Guns in Cellular Automata: Exploring Evolutionary and Other Techniques

Abstract

We aim to construct an automatic system for the discovery of collision-based universal cellular automata that simulate Turing machines in their space-time dynamics using gliders and glider guns.

In this paper, an evolutionary search for glider guns with different parameters is described and other search techniques are also presented as benchmark. We demonstrate the spontaneous emergence of an important number of novel glider guns discovered by genetic algorithms.

Emmanuel Sapin, Larry Bull

A Genetic Algorithm for Generating Improvised Music

Abstract

Genetic art is a recent art form generated by computers based on the genetic algorithms (GAs). In this paper, the components of a GA embedded into a genetic art tool named AMUSE are introduced. AMUSE is used to generate improvised melodies over a musical piece given a harmonic context. Population of melodies is evolved towards a better musical form based on a fitness function that evaluates ten different melodic and rhythmic features. Performance analysis of the GA based on a public evaluation shows that the objectives used by the fitness function are assembled properly and it is a successful artificial intelligence application.

Ender Özcan, Türker Erçal

Unsupervised Learning of Echo State Networks: A Case Study in Artificial Embryogeny

Abstract

Echo State Networks (ESN) have demonstrated their efficiency in supervised learning of time series: a ”reservoir” of neurons provide a set of dynamical systems that can be linearly combined to match the target dynamics, using a simple quadratic optimisation algorithm to tune the few free parameters. In an unsupervised learning context, however, another optimiser is needed. In this paper, an adaptive (1+1)-Evolution Strategy is used to optimise an ESN to tackle the ”flag” problem, a classical benchmark from multi-cellular artificial embryogeny: the genotype is the cell controller of a Continuous Cellular Automata, and the phenotype, the image that corresponds to the fixed-point of the resulting dynamical system, must match a given 2D pattern. This approach is able to provide excellent results with few evaluations, and favourably compares to that using the NEAT algorithm (a state-of-the-art neuro-evolution method) to evolve the cell controllers. Some characteristics of the fitness landscape of the ESN-based method are also investigated.

Alexandre Devert, Nicolas Bredeche, Marc Schoenauer

Enhanced Genetic Algorithm with Guarantee of Feasibility for the Unit Commitment Problem

Abstract

In this paper, an enhanced genetic algorithm for the Unit Commitment problem is presented. This problem is known to be a large scale, mixed integer programming problem for which exact solution is highly intractable. Thus, a metaheuristic based method has to be used to compute a very often suitable solution. The main idea of the proposed enhanced genetic algorithm is to use a priori knowledge of the system to design new genetic operators so as to increase the convergence rate. Further, a suitable penalty criterion is defined to explicitly deal with numerous constraints of the problem and to guarantee the feasibility of the solution. The method is also hybridized with an exact solution algorithm, which aims to compute real variables from integer variables. Finally, results show that the enhanced genetic algorithm leads to the tractable computation of a satisfying solution for large scale Unit Commitment problems.

Guillaume Sandou, Stéphane Font, Sihem Tebbani, Arnaud Hiret, Christian Mondon

On the Design of Adaptive Control Strategies for Evolutionary Algorithms

Abstract

This paper focuses on the design of control strategies for Evolutionary Algorithms. We propose a method to encapsulate multiple parameters, reducing control to only one criterion. This method allows to define generic control strategies independently from both the algorithm’s operators and the problem to be solved. Three strategies are proposed and compared on a classical optimization problem, considering their generality and performance.

Jorge Maturana, Frédéric Saubion

Improvement of Intelligent Optimization by an Experience Feedback Approach

Abstract

Intelligent optimization is a domain of evolutionary computation that emerges since a few years. All the methods within this discipline are based on mechanisms for maintaining a set of individuals and, separately, a space of knowledge linked to the individuals. The aim is to make the individuals evolve to reach better solutions generation after generation using the knowledge linked to them. The idea proposed in this paper consists in using previous experiences in order to build the knowledge referential and then accelerate the search process. A method which allows reusing knowledge gained from experience feedback is proposed. This approach has been applied to the problem of selection of project scenario in a multi-objective context. An evolutionary algorithm has been modified in order to allow the reuse of capitalized knowledge. This knowledge is gathered in an influence diagram allowing its reuse by the algorithm.

Paul Pitiot, Thierry Coudert, Laurent Geneste, Claude Baron

Backmatter

Titel: Artificial Evolution
herausgegeben von: Nicolas Monmarché
El-Ghazali Talbi
Pierre Collet
Marc Schoenauer
Evelyne Lutton
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-79305-2
Print ISBN: 978-3-540-79304-5
DOI: https://doi.org/10.1007/978-3-540-79305-2