www.marmakoide.org

The homepage of Alexandre Devert

Publications

As a goodie: a bibtex file that reference all my publications.

2012

A Study on Scalable Representations for Evolutionary Optimization of Ground Structures

Accepted for publication in Evolutionary Computation, to appear.

Authors:Alexandre Devert Thomas Weise Ke Tang
Abstract:This paper presents a comparative study of two indirect solution representations, a generative and an ontogenic one, on a set of well-known 2D truss design problems. The generative representation encodes the parameters of a trusses design as a mapping from a 2D space. The ontogenic representation encodes truss design parameters as a local truss transformation iterated several times, starting from a trivial initial truss. Both representations are tested with a naive Evolution Strategy based optimization scheme, as well as the state-of-the-art HyperNEAT approach. We focus both on the best objective value obtained and the computational cost to reach a given level of optimality. The study shows that the two solutions representations behave very differently. For experimental settings with equal complexity, with the same optimization scheme and settings, the generative representation provides results which are far from optimal, whereas the ontogenic representation delivers near-optimal solutions. The ontogenic representation is also much less computationally expensive than a direct representation until very close to the global optimum. The study questions the scalability of the generative representations, while the results for the ontogenic representation display a much better scalability.
Download:PDF

2011

Robustness and the Halting Problem for Multi-Cellular Artificial Ontogeny

Accepted for publication in IEEE Transactions on Evolutionary Computation, June 2011.

Authors:Alexandre Devert Nicolas Bredeche Marc Schoenauer
Abstract:Most works in Multi-Cellular Artificial Ontogeny solve the halting problem by arbitrarily limiting the number of iterations of the developmental process. Hence, the trajectory of the developing organism in the phenotypic space is only required to come close to an accurate solution during a very short developmental period. Because of the well-known opportunism of evolution, there is indeed no reason for the organism to remain close to a good solution in other situations: if the development is continued after the limiting bound; if the environment is perturbed by some noise during the development; if the development takes place in different physical conditions. In order to increase the robustness of the solution against such hazards, a new stopping criterion for the developmental process is proposed, based on the stability of some internal energy of the organism during its development. Such adaptive stopping criterion biases evolution toward solutions in which robustness is an intrinsic property. Experimental results on different French flag problems demonstrate that enforcing stable developmental process makes it possible to produce solutions that not only accurately approximate the target shape, but also demonstrate near-perfect self-healing properties, as well as excellent generalization capabilities.
Download:PDF

2009

When and why development is needed: generative and developmental systems

Accepted for publication at GECCO 2009, Montreal, Québec, Canada, 2009.

Authors:Alexandre Devert
Abstract:Within the evolutionary computation community, there is a strong consensus to agreed on the need of indirect representations to achieve scalability. But no such consensus has been yet found on how to design an indirect representation. An idea to build a scalable representation, is to see the phenotype to genotype mapping as an iterative transformation process: an explicit development stage. But such an approach is computationally expensive and then it relevance might be questionable. Through a simple, accessible example, optimization of a block stack overhang, it is shown that, indeed, an explicit development stage can be the only way if one wants a scalable representation and/or scalable solutions to a problem.
Download:PDF Poster PDF

2008

Artificial Ontogeny for Truss Structure Design

Accepted for publication at Workshop on Spatial Computing (SCW), at the second IEEE International Conference on Self-Adaptive and Self-Organizing Systems, Venice, Italy, 2008.

Authors:Alexandre Devert Nicolas Bredeche Marc Schoenauer
Abstract:This paper introduces an approach based on Artificial Embryogeny for truss design to address the problem of finding the best truss structure for a given loading. In this setup, the basic idea is to optimize the size and length of beams in a truss through the actions of a set of cells that are distributed over the very truss structure. Given information at the mechanical level (beam strain), each cell controller is able to modify the local truss structure (beam size and length) during a developmental process. The advantage of such a method relies on the idea that a template cell controller is duplicated over all cells, keeping the optimization search space very low, while each cell may act in a different manner depending on local information. This approach is demonstrated on a classical benchmark, the cantilever: resulting organisms are shown to provide very interesting and unique properties regarding reuse of optimized genotypes in noisy or higher-dimension settings.
Download:PDF

2007

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

Accepted for publication at EA 2007, Tour, France, October 29-31th 2007.

Authors:Alexandre Devert Nicolas Bredeche Marc Schoenauer
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.
Download:PDF

Robust Multi-Cellular Developmental Design

Accepted for publication at GECCO 2007, London, England, July 7-11th 2007.

Authors:Alexandre Devert Nicolas Bredeche Marc Schoenauer
Abstract:This paper introduces a continuous model for Multi-cellular Developmental Design. The cells are fixed on a 2D grid and exchange "chemicals" with their neighbors during the growth process. The quantity of chemicals that a cell produces, as well as the differentiation value of the cell in the phenotype, are control led by a Neural Network (the genotype) that takes as inputs the chemicals produced by the neighboring cells at the previous time step. In the proposed model, the number of iterations of the growth process is not pre-determined, but emerges during evolution: only organisms for which the growth process stabilizes give a phenotype (the stable state), others are declared nonviable. The optimization of the controller is done using the NEAT algorithm, that optimizes both the topology and the weights of the Neural Networks. Though each cell only receives local information from its neighbors, the experimental results of the proposed approach on the 'flags' problems (the phenotype must match a given 2D pattern) are almost as good as those of a direct regression approach using the same model with global information. Moreover, the resulting multi-cellular organisms exhibit almost perfect self-healing characteristics.
Download:PDF

2006

Evolutionary Design of Buildable Objects with BlindBuilder : an Empirical Study

Accepted for publication at ASPGP 2006, Hanoi, Vietnam, October 12-14th 2006.

Authors:Alexandre Devert Nicolas Bredeche Marc Schoenauer
Abstract:In a previous paper, we presented BlindBuilder, a new representation formalism for Evolutionary Design based on construction plans. As for other indirect encoding approaches in the literature, BlindBuilder makes it possible to easily represent possible solutions but makes it difficult to perform structural optimization. While satisfying results are provided, it becomes more and more difficult to build larger structures during the course of evolution. This is due to the high disruptive rate of variation operators as construction plans grow. In this paper, we provide an analysis of such a problem and propose new construction operators to avoid this. Then, we perform extensive experiments so as to identify the key parameters and discuss the advantages, limitations and possible perspectives of the indirect enconding approach.
Download:PDF

Blindbuilder : A new encoding to evolve Lego-like structures

Accepted for publication at EUROGP 2006, Budapest, Hungary, April 10-12th 2006.

Authors:Alexandre Devert Nicolas Bredeche Marc Schoenauer
Abstract:This paper introduces a new representation for assemblies of small Lego-like elements: structures are indirectly encoded as construction plans. This representation shows some interesting properties such as hierarchy, modularity and easy constructibility checking by definition. Together with this representation, efficient GP operators are introduced that allow efficient and fast evolution, as witnessed by the results on two construction problems that demonstrate that the proposed approach is able to achieve both compactness and reusability of evolved components.
Download:PDF