Available papers Chronological order

Back to EEAAX home page - 2000 - 1999 - 1998 - 1997 - 1996 - 1995 - 1994 - 1993

• Polar IFS + Parisian GP = Efficient IFS inverse problem solving
Pierre Collet, Evelyne Lutton, Frédéric Raynal and Marc Schoenauer - GPEM Journal 2000
• Genetic Programming and Domain Knowledge: Beyond the Limitations of Grammar-Guided Machine Discovery
Alain Ratle, Michèle Sebag - PPSN 2000
• A New Genetic Algorithm Working on State Domain Order Statistics
Daniel Delahaye and Stépahen Puechmorel- PPSN 2000
• An Adaptive Algorithm for constrained optimization problems
Sana Ben Hamida and Marc Schoenauer - PPSN 2000
• Flight Alternative Routes Generation by Genetic Algorithms
S. Oussedik and D. Delahaye and M. Schoenauer - CEC'2000
• Représentations non structurées en optimisation topologique de formes par algorithmes évolutionnaires
Hatem Hamda, François Jouve, Evelyne Lutton, Marc Schoenauer et Michèle Sebag - ESAIM Proceedings, 2000
• Adaptive techniques for Evolutionary Topological Optimum Design
Hatem Hamda and Marc Schoenauer - ACDM 2000
• Rigorous hitting times for binary mutations
J. Garnier, L. Kallel and M. Schoenauer - Evolutionary Computation 1999
• How to detect all maxima of a function ?
J. Garnier and L. Kallel - Evonet Summer School, 1999
• Dynamic Air Traffic Planning by Genetic Algorithms
S. Oussedik and D. Delahaye and M. Schoenauer - CEC99
• On functions with a given fitness--distance relation
Leila Kallel, Bart Naudts and Marc Schoenauer - CEC99
• Evolutionary Algorithms as Fitness Function Debuggers
F. Mansanne, F. Carrère, A . Ehinger, and M. Schoenauer ISMIS'99
• Inside GA Dynamics: Ground Basis for Comparison
Leila Kallel PPSN 1998
• Revisiting the Memory of Evolution
Michèle Sebag, Marc Schoenauer and Mathieu Peyral - Fundamenta Informaticae 1998
• Non-parametric identification of geological models
Marc Schoenauer, A. Ehinger and B. Braunschweig - ICEC'98
• Sphere Operators and Their Applicability for Constrained Parameter Optimization Problems
Marc Schoenauer and Zbigniew Michalewicz - EP98
• Evolutionary Computation: an Introduction
Marc Schoenauer and Zbigniew Michalewicz - Control and Cybernetics 97
• A priori comparison of binary crossover operators: No universal statistical measure, but a set of hints
Leila Kallel and Marc Schoenauer - EA97.
• Parametric and non-parametric identification of macro-mechanical models
Michèle Sebag, Marc Schoenauer and Habibou Maitournam - Eurogen97.
• Tractable Induction and Classification in First Order Logic Via Stochastic Matching
Michèle Sebag and Céline Rouveirol - IJCAI97.
• Toward Civilized Evolution: Developing Inhibitions.
Michèle Sebag and Marc Schoenauer - ICGA97.
• Alternative Random Initialization in Genetic Algorithms.
Leila Kallel and Marc Schoenauer - ICGA97.
• Boundary Operators for Constrained Parameter Optimization Problems
Marc Schoenauer and Zbigniew Michalewicz - ICGA97.
• Identification of Mechanical Inclusions.
Marc Schoenauer, Francois Jouve and Leila Kallel - D. Dasgupta and Z. Michalewicz Ed., Evolutionary Algorithms in Engineering Applications. Springer 1997.
• A Society of Hill-Climbers
Michèle Sebag and Marc Schoenauer - ICEC97.
• Optimisation topologique de formes par algorithmes génétiques (in French)
Couro Kane et Marc Schoenauer - Revue Française de Mécanique 1997
• Inductive Learning of Mutation Step-size in Evolutionary Parameter Optimization
Michèle Sebag, Marc Schoenauer, and Caroline Ravisé - EP97.
• Mechanical Inclusions Identification by Evolutionary Computation.
Marc Schoenauer, Leila Kallel and Francois Jouve - Revue européenne des éléments finis. Vol 5(5-6) - 1996.
• Evolutionary Algorithms for Constrained Parameter Optimization Problems.
Zbigniew Michalewicz and Marc Schoenauer - Evolutionary Computation Vol 4(1), 1996.
• Topological Optimum Design using Genetic Algorithms
C. Kane and M. Schoenauer - Control and Cybernetics - 25(5) - 1996.
• Mutation by Imitation in Boolean Evolution Strategies
M. Sebag and M. Schoenauer - PPSN 96.
• Evolutionary Computation at the Edge of Feasibility
M. Schoenauer and Z. Michalewicz - PPSN 96.
• Delaying the Choice of Bias: A Disjunctive Version Space Approach
M. Sebag - ICML 96.
• An Advanced Evolution Should Not Repeat Its Past Errors
Caroline Ravisé and Michele Sebag - ICML96
• Evolutionary Algorithms for Industrial Engineering Problems
Z. Michalewicz, D. Dasgupta, R. Leriche and M. Schoenauer - Comp. & Indus. Eng. J. (1996)
• Evolutionary Identification of Macro-Mechanical Models
M. Schoenauer, M. Sebag, F. Jouve, B. Lamy, and H. Maitournam, in P. J. Angeline and K. E. Kinnear, Jr, Editors, Advances in Genetic Programming II MIT Press, Cambridge, MA, 1996.
• Shape Representations and Evolution Schemes
Marc Schoenauer - EP 96
• Representations for Evolutionary Optimization and Identification in Structural Mechanics
Marc Schoenauer - EUROGEN 95
• Optimization of direction finders by Genetic Algorithms
Lionel Taieb and Marc Schoenauer - GALESIA 95
• Structural topology optimization in linear and nonlinear elasticity using genetic algorithms
Couro Kane, François Jouve and Marc Schoenauer - ASME-DAC95
• A Segregated Genetic Algorithm for Constrained Structural Optimization
Rodolphe G. Le Riche, Catherine Knopf-Lenoir and Raphael T. Haftka - ICGA95
• Evolutionary Chromatographic Law Identification by Recurrent Neural Nets
Alessandro Fadda and Marc Schoenauer - EP95
• Genetic Lander: An Experiment in Accurate Neuro-Genetic Control
Edmund Ronald and Marc Schoenauer - PPSN94
• Controlling Crossover through Inductive Learning
Michele Sebag and Marc Schoenauer - PPSN94
• Genetic Extensions of Neural Net Learning: Transfer Functions and Renormalisation Coefficients
Marc Schoenauer and Edmund Ronald - EA94
• A Rule-Based Similarity Measure
Michele Sebag and Marc Schoenauer - CBR94
• A Constraint-Based Induction Algorithm in FOL
Michele Sebag - ICML94
• Neuro-Genetic Truck Backer-Upper Controller
Marc Schoenauer and Edmund Ronald - ICEC94
• Using Constraints to Building Version Spaces
Michele Sebag and Marc Schoenauer - ECML94
• Inductive Learning of Membership Functions and Fuzzy Rules
Michele Sebag and Marc Schoenauer - Uncertainty Modelling
• Constrained GA optimization
Marc Schoenauer and Spyros Xanthakis - ICGA93

Polar IFS + Parisian GP = Efficient IFS inverse problem solving.

Pierre Collet, Evelyne Lutton, Frédéric Raynal and M. Schoenauer

The inverse problem for Iterated Functions Systems (finding an IFS whose attractor is a target 2D shape) with non-affine IFS is a very complex task. Successful approaches have been made using Genetic Programming, but there is still room for improvement in both the IFS and the GP parts. This paper introduces Polar IFS: a specific representation of IFS functions which shrinks the search space to mostly contractive functions and gives direct access to the fixed points of the functions. On the evolutionary side, the Parisian'' approach is presented. It is similar to the Michigan'' approach of Classifier Systems: each individual of the population only represents a part of the global solution. The solution to the inverse problem for IFS is then built from a set of individuals. Both improvements show a drastic cut-down on CPU-time: good results are obtained with small populations in few generations.

Genetic Programming and Evolvable Machines, 1(4), pp 339-361, 2000

Gzipped Postscript A New Genetic Algorithm Working on State Domain Order Statistics
Daniel Delahaye and Stépahen Puechmorel- PPSN 2000

A New Genetic Algorithm Working on State Domain Order Statistics

Daniel Delahaye, Stépahen Puechmorel

This paper presents a new concept of Genetic Algorithm in which an individual is coded as a domain of the state space and is evaluated with the help of order statistics. For this first version only continuous criteria has been investigated. An hypercube domain of the state space is associated with each individual and is randomly sampled according to a distribution for which asymptotic extremes are known. Regular fitnesses are computed for all the samples in each domain and are combined to produce a prospectiveness criterion. A regular GA and this new GA are compared on classical N dimensional functions such as Sphere, Step, Ackley , Griewank for different values of N. A final comparison is given on the classical Lennard-Jones Molecular Conformation problem with 30 atoms. For both versions, a regular GA has been used; the first one works on state points and the other one on state domains. For all tests, and for the same number of criterion evaluations, this new algorithm performs much better than the classical one.

Genetic Programming and Domain Knowledge: Beyond the Limitations of Grammar-Guided Machine Discovery

Alain Ratle, Michèle Sebag

Application of Genetic Programming to the discovery of empirical laws is often impaired by the huge size of the domains involved. In physical applications, dimensional analysis is a powerful way to trim out the size of these spaces This paper presents a way of enforcing dimensional constraints through formal grammars in the GP framework. As one major limitation for grammar-guided GP comes from the initialization procedure (how to ,nd admissible and sufficiently diverse trees with a limited depth), an initialization procedure based on dynamic grammar pruning is proposed. The approach is validated on the problem of identification of a materials response to a mechanical test.

An Adaptive Algorithm for constrained optimization problems

Sana Ben Hamida and Marc Schoenauer

Several methods have been proposed for handling nonlinear constraints by evolutionary algorithms for numerical optimization problems. The most widely used are those based on penalty function, thanks to their simplicity. In this paper, we propose a new adaptative penalty approach for solving constrained optimization problems, based on the amount of feasible individuals in the population. This method uses specific selection and recombination operators adapted to the penalisation strategy. We demonstrate the power of this approach on the eleven test cases presented in the litterature.

Flight Alternative Routes Generation by Genetic Algorithms

S. Oussedik and D. Delahaye and M. Schoenauer

This paper present a new Air Traffic routes generator based on Genetic Algorithms. Due to the traffic growth, direct (and near direct) routes are more and more congested and there is a real need for spreading the traffic on new alternative routes. Those routes have to be different from several operational criteria and must not generate too much extra-distance compared with the direct route. To reach this goal, a GA has been implemented with an efficient sharing which automatically allows the emergence of different alternative routes. This algorithm has been tried on the French airspace and gives realistic operational results.

Représentations non structurées en optimisation topologique de formes par algorithmes évolutionnaires

Hatem Hamda, François Jouve, Evelyne Lutton, Marc Schoenauer et Michèle Sebag

Les algorithmes évolutionnaires sont des méthodes d'optimisation stochastiques inspirées -- grossièrement -- de l'évolution naturelle des populations. Méthodes globales d'ordre 0, leur robustesse et leur souplesse leur permettent d'attaquer la résolution numérique de problèmes difficiles à résoudre autrement. Mais c'est leur capacité à travailler sur des espaces de recherche non standards qui leur offre les perspectives les plus originales.
Dans le domaine de l'optimisation topologique de formes, les résultats obtenus il y a quelques années montraient la faisabilité de l'approche évolutionnaire, mais étaient limités par le fait que la complexité de l'espace de recherche était liée à celle du maillage utilisé lors de la simulation numérique. Ce papier introduit un ensemble de représentations compactes et non structurées dont la complexité n'est pas fixe, mais est ajustée par l'algorithme lui-même. Les résultats présentés dans cet article montrent que leur utilisation permet de repousser les limites de l'optimisation topologique de formes évolutionnaire. Des résultats sur des problèmes test simples tentent ensuite de comparer les mérites des diverses approches proposées.

Adaptive techniques for Evolutionary Topological Optimum Design

Hatem Hamda and Marc Schoenauer

This paper introduces some advances in Evolutionary Topological Optimum Design, thanks to extensive use of adaptive techniques. On the genotypic side, a variable length representation is used: the complexity of the representation of each individual is evolved by the algorithm rather than being prescribed by some fixed mesh of the design domain, resulting in self-adaptive complexity. On the phenotypic side, an original adaptive mechanism is proposed that maintains both feasible and infeasible individuals, thus exploring both sides of the boundary of the feasible region, where the optimum structure is known to lie. Not only does this improves the results of past work in on Evolutionary Topological Optimum Design on standard benchmark bidimensional cantilever problems, but it also allows to address three-dimensional problems who had up to now stayed beyond reach for evolutionary algorithms.

I. Parmee, Ed., Evolutionary Design and Manufacture, Springer Verlag, 2000

Rigorous hitting times for binary mutations

J. Garnier, L. Kallel and M. Schoenauer

In the binary evolutionary optimization framework, two mutation operators are theoretically investigated. For both the standard mutation, in which all bits are flipped independently with the same probability, and the 1-bit-flip mutation, which flips exactly one bit per bitstring, the statistical distribution of the first hitting times of the target are thoroughly computed (expectation and variance) up to terms of order l (the size of the bitstrings) in two distinct situations: without any selection, or with the deterministic (1+1)-ES selection on the OneMax problem. In both cases, the 1-bit-flip mutation convergence time is smaller by a constant (in terms of l) multiplicative factor. These results extend to the case of multiple independent optimizers.

Evolutionary Computation 7(2) pp 167-203, 1999

Dynamic Air Traffic Planning by Genetic Algorithms

S. Oussedik and D. Delahaye and M. Schoenauer

In the past, the first way to reduce the congestion of the Air Traffic Control System was to modify the structure of the airspace in order to increase the capacity (increasing the number of runways, increasing the number of sectors by reducing their size). This method has a limit due to the cost involved by new runways and the way to manage traffic in too small sectors (a controller needs a minimum amount of airspace to solve conflicts). The other way to reduce congestion is to modify the flight plans in order to adapt the demand to the available capacity. So, to reduce congestion, demand has to be spread in spatial and time dimension (route-slot allocation). Our research addresses the general time-route assignment problem using a static and a dynamic approach. A state of the art of the existing methods shows that this general bi-allocation problem is usually partially treated and the whole problem remains unsolved due to the induced complexity. GAs are then adapted to the problem. A sector congestion measure has been developed which gather the major control workload indicators. This measure is then computed for each proposed planning by referring to an off-line simulation. New problem-based stochastic operators have been developed and successfully applied on real instances of the problem.

On functions with a given fitness--distance relation

Leila Kallel, Bart Naudts and Marc Schoenauer

Recent work stresses the limitations of fitness distance correlation (FDC) as an indicator of landscape difficulty for genetic algorithms (GAs). Realizing that the fitness distance correlation (FDC) value cannot be reliably related to landscape difficulty, we investigate whether an interpretation of the whole correlation plot can yield reliable information about the behavior of the GA. Our approach is as follows. We present a generic method for constructing fitness functions which share the same fitness versus distance-to-optimum relation (FD relation). Special attention is given to FD relations which show no local optimum in the correlation plot, as is the case for the relation induced by Horn's longpath. We give an inventory of different types of GA behavior found within a class of fitness functions with a common correlation plot. We finally show that GA behavior can be very sensitive to small modifications of the fitness--distance relation.

How to detect all maxima of a function ?

J. Garnier and L. Kallel

This paper starts by a theoretical investigation of a family of landscapes characterized by the number of their local optima N and the distribution of the sizes alphaj of their attraction basins. We then propose a practical methodology for identifying these quantities (N and alphaj distribution) for an unknown landscape, given a random sample on that landscape and a local steepest ascent search. This methodology applies to any landscape specified with a modification operator and provides bounds on search complexity (to detect all local optima) when using the modification operator at hand. Experiments demonstrate the efficiency of this methodology for guiding the choice of modification operators, leading to the design of problem-dependent optimization heuristics.

Evonet Summer School 1999

Evolutionary Algorithms as Fitness Function Debuggers

F. Mansanne, F. Carrère, A . Ehinger, and M. Schoenauer

All Evolutionary Algorithms experienced practitioners emphasize the need for a careful design of the fitness function. It is commonly heard, for instance, that {\em If there is a bug in your fitness function, the EA will find it''.} This paper presents a case study of such a situation in the domain of geophysical underground identification: some weird solutions are found by the Evolutionary Algorithm, obviously physically absurd, but fulfilling almost perfectly the geophysical criterion.

Z. Ras and A. Skowron editors, Proceedings of ISMIS'99, Foundation of Intelligent Systems 11th International Symposium LNAI 1609, Springer Verlag, pp 639-647, 1999

Inside GA Dynamics: Ground Basis for Comparison

Leila Kallel

This paper reviews some of the commonly used methods to compare GA performance on different problems or to compare the adequation of GA parameters and operators. This points out the scaling issue when differently distributed fitness functions are compared. Hamming fitness functions are then proposed as a basis to relax the dependence of GA-performance-measures on fitness scale or distribution, and to account for any GA parameters bias. Different measures are also proposed, distinguishing convergence time from GA radial and effective trajectory in Hamming space.

Proceedings of PPSN'98 Springer Verlag, LNCS 1498, pp 57-66, 1998.

Revisiting the Memory of Evolution

Michèle Sebag, Marc Schoenauer and Mathieu Peyral

A new evolution scheme is presented, memorizing the extreme (best and worse) past individuals through distributions over the binary search space. These distributions are used to bias the mutation operator in a ($\mu+\lambda$) Evolution Strategy, guiding the generation of newborn offspring: different {\em mimetic strategies} are defined, combining either attraction, indifference or repulsion with respect to the two distributions. These distributions are then updated from the best and the worse individuals in the current population. Experiments on large size binary problems allow one to delineate the niche of each of these mimetic strategies.

Fundamenta Informaticae 38 pp 1-39, 1998.

Non-parametric identification of geological models

M. Schoenauer, A. Ehinger and B. Braunschweig

Many problems to be solved in geophysical processing can be expressed in terms of identification of spatial geological models : given a function Phi applied to a geological model Gamma, producing a result R, the problem is to find Gamma* such that Phi(Gamma*) = R*, where R}* is the expected result : a seismogram, a pressure curve, a seismic cross-section etc. The presented research deals with the joint use of evolutionary algorithms and Voronoi diagrams to address some non-parametric instances of identification problems in geophysics, i.e. without a priori hypothesis about the geometrical layout of possible solutions. In this paper, a first application in velocity determination for seismic imaging demonstrates the ability of this approach to identify both the geometry and the velocities of the underground from experimental seismograms.

Proceedings of ICEC'98, IEEE International conference on Evolutionary Computation LNAI 1609, Springer Verlag, pp 639-647, 1999

Sphere Operators and Their Applicability for Constrained Parameter Optimization Problems

Marc Schoenauer and Zbigniew Michalewicz

In this paper we continue our earlier studies on boundary operators for constrained parameter optimization problems. We discuss thoroughly one particular class of boundary operators --- sphere operators --- and argue about their applicability to general constrained problems through a mapping between the boundary of the feasible region of the search space and a sphere. We provide with some experimental evaluation of these transformations, on some problems from our earlier studies, as well as on problems with convex search space.

Presented at the Seventh Annual Conference on Evolutionary Programming - EP'98

Evolutionary Computation: An Introduction

Marc Schoenauer and Zbigniew Michalewicz

Evolutionary computation techniques have received a lot of attention regarding their potential as optimization techniques for complex real-world problems. These techniques, based on the powerful principle of survival of the fittest'', model some natural phenomena of genetic inheritance and Darwinian strife for survival; they also constitute an interesting category of modern heuristic search. This introductory article presents the main paradigms of evolutionary algorithms (genetic algorithms, evolution strategies, evolutionary programming, genetic programming) as well as other (hybrid) methods of evolutionary computation. Two particular research directions (parallel evolutionary techniques and self-adaptation) are discussed further in the last part of this paper.

Control and Cybernetics Special Issue on Evolutionary Computation 26(3) pp 307-338, 1997

A priori comparison of binary crossover operators: No universal statistical measure, but a set of hints

Leila Kallel and Marc Schoenauer

The choice of an operator in Evolutionary Computation is generally based on comparative runs of the algorithms. However, some statistical a priori measures, based on samples of (parents-offspring), have been proposed to avoid such brute comparisons. In this paper we survey some of these works in the context of binary crossover operators. We first extend these measures to overcome some of their limitations. Unfortunately, experimental results on well known binary problems suggest that any of the measures used here can give false indications. Being all defined as averages, they can miss the important parts: none of the tested measures can pretend to be a good indicator alone. However, considering together the Expected Mean Improvement to a target value and the Fitness Operator Correlation gives the best predictive results. Moreover, detailed insights on the samples, based on some graphical layouts of the offspring fitnesses, seem to allow more accurate predictions on the respective performances of binary crossover operators.

Artificial Evolution'97 pp 287-299, LNCS 1363, Springer Verlag 1997

Parametric and non-parametric identification of macro-mechanical models

Michèle Sebag, Marc Schoenauer and Habibou Maitournam

This chapter presents evolutionary identification of a particular form of behavioral laws for elasto-visco-plastic materials termed rheological models. First, rheological models with known graph of connections are used, and the identification amounts to identifying real-valued parameters. But the more challenging task of identifying also the topology of the rheological model can be tackled using Genetic Programming, after turning those models into parse-trees. Both approaches are compared and discussed on a simple artificial example.

Genetic Algorithms and Evolution Strategies in Engineering and Computer Sciences pp 327-340, John Wiley 1997

Tractable Induction and Classification in First Order Logic Via Stochastic Matching.

Michèle Sebag and Céline Rouveirol

Learning in first-order logic (FOL) languages suffers from a specific difficult y: both induction and classification are potentially exponential in the size of hypotheses. This difficulty is usually dealt with by limiting the size of hypotheses, via either syntactic restrictions or search strategies. This paper is concerned with polynomial induction and use of FOL hypotheses with no size restrictions. This is done via stochastic matching: instead of exhaustively exploring the set of matchings between any example and any short candidate hypothesis, one stochastically explores the set of matchings between any example and any candidate hypothesis. The user sets the number of matching samples to consider and thereby controls the cost of induction and classification. One advantage of this heuristic is to allow for resource-bounded learning, without any a priori knowledge about the problem domain. Experiments on a real-world problem pertaining to organic chemistry fully demonstrate the potentialities of the approach regarding both predictive accuracy and computational cost.

Proceedings of IJCAI97, pp 888-896, 1997.

Toward Civilized Evolution: Developing Inhibitions.

Michèle Sebag and Marc Schoenauer

Most evolutionary algorithms concerned with a memory of evolution aim at memorizing and reusing the recipes of past successes (e.g. fruitful operators or fruitful mutation directions). \\ The scheme proposed here follows the opposite track, and memorizes the past failures of evolution (unfit offspring) through a virtual individual termed the {\em virtual loser}. The underlying metaphor is that offspring should attempt to get further away from the virtual loser than their parents. This is done by a new evolution operator, termed {\em flee-mutation}, as an alternative to standard recombination and mutation. Special attention is paid to adjusting the flee-mutation step size. Experiments on large sized problems validate this approach, and unexpectedly show that a constant flee-mutation step size over a population is desirable.

Proceedings of the Seventh International Conference on Genetic Algorithms, Morgan Kaufmannm pp 291-298, 1997.

Alternative Random Initialization in Genetic Algorithms.

Leila Kallel and Marc Schoenauer

Though unanimously recognized as a crucial step in Evolutionary Algorithms, initialization procedures have not been paid much attention so far. In bitstring Genetic Algorithms, for instance, the standard 0/1 equiprobable choice for every bit is rarely discussed, as the resulting distribution probability over the whole bitstring space is uniform. However, uniformity is relative to a measure on the search space. First, considering the measure given by the density of 1's, the {\em Uniform Covering} initialization procedure is naturally designed. Second, taking into account the probability of appearance of sequences of identical bits leads to design another alternative initialization procedure, the {\em Homogeneous Block} procedure. These procedures are compared with the standard initialization procedure on several problems. A priori comparison is achieved using Fitness-Distance Correlation. Actual experiments demonstrate the accuracy of these FDC-based comparisons, and emphasize the usefulness of the two proposed procedure.

Proceedings of the Seventh International Conference on Genetic Algorithms, Morgan Kaufmann, pp 268-275, 1997.

Boundary Operators for Constrained Parameter Optimization Problems.

Marc Schoenauer and Zbigniew Michalewicz

In this paper we continue our earlier study [in PPSN96] on boundary operators for constrained parameter optimization problems. The significance of this line of research is based on the observation that usually the global solution for many optimization problems lies on the boundary of the feasible region. Thus, for many constrained numerical optimization problems it might be beneficial to search just the boundary of the search space defined by a set of constraints (some other algorithm might be used for searching the interior of the search space, if activity of a constraint is not certain). We present a few boundary operators for a sphere and provide with their experimental evaluation.

Proceedings of the Seventh International Conference on Genetic Algorithms, Morgan Kaufmann, pp 322-329, 1997.

Identification of Mechanical Inclusions

Marc Schoenauer, Francois Jouve and Leila Kallel

Evolutionary Algorithms provide a general approach to inverse problem solving: As optimization methods, they only require the computation of values of the function to optimize. Thus, the only prerequisite to efficiently handle inverse problems is a good numerical model of the direct problem, and a representation for potential solutions. The identification of mechanical inclusion, even in the linear elasticity framework, is a difficult problem, theoretically ill-posed: Evolutionary Algorithms are in that context a good tentative choice for a robust numerical method, as standard deterministic algorithms have proven inaccurate and unstable. However, great attention must be given to the implementation. The representation, which determines the search space, is critical for a successful application of Evolutionary Algorithms to any problem. Two original representations are presented for the inclusion identification problem, together with the associated evolution operators (crossover and mutation). Both provide outstanding results on simple instances of the identification problem, including experimental robustness in presence of noise.

in D. Dasgupta and Z. Michalewicz Ed., Evolutionary Algorithms in Engineering Applications. pp 479-496, Springer Verlag 1997.

A Society of Hill-Climbers

Michèle Sebag and Marc Schoenauer

This paper is concerned with function optimization in binary search spaces. It focuses on how hill-climbers can work together and/or use their past trials in order to speed up the search. A hill-climber is viewed as a set of mutations. The challenge is twofold: one must determine how many bits should be mutated, and which bits should preferably be mutated, or in other words, which climbing directions are to be preferred.

The latter question is addressed by recording the last worst trials of the hill-climbers within an individual termed {\em repoussoir}. The hill-climbe rs further explore the neighborhood of their current point as to get away from the repoussoir. As to the former question, no definite answer is proposed. Nevertheless, we experimentally show that hill-climbers behave quite differently depending on whether one sets a mutation rate per bit, or sets the exact number of bits to mutate per individual.
Two algorithms describing societies of hill-climbers, with or without memory of the past trials, are described. These are experimented on several 900-bits problems, and significantly outperform standard Genetic Algorithms and Evolution Strategies.

Proceedings of 1997 IEEE International Conference on Evolutionary Computation, pp 319-324, Indianapolis, April 1997.

Optimisation topologique de formes par algorithmes génétiques

Couro Kane et Marc Schoenauer

Le travail présenté dans ce papier est centré sur le problème de l'optimisation topologique des formes, et utilise la méthode des algorithmes génétiques. Une population de formes évolue selon le principe darwinien Les plus adaptés survivent, la fonction d'adaptation poussant les individus de cette population vers les structures optimales. Nous montrons la flexibilité de cette approche, qui permet d'obtenir des résultats hors de portée des algorithmes standard du domaine ; le prix à payer est un coût de calcul important. Ainsi, plusieurs solutions quasi-optimales peuvent être obtenues pour le même problème ; l'optimisation peut être faite en respectant des contraintes sur plus d'un chargement ; le chargement peut être appliqué sur la frontière inconnue de la structure finale (comme par exemple pour l'optimisation d'un dôme sous-marin) ; enfin, cette méthode peut être appliquée à tout type de matériau et à tout modèle mécanique, ainsi qu'en attestent les résultats en élasticité non-linéaire, les premiers du genre à notre connaissance. Les clés de ces succès sont des adaptations de la méthode générale des algorithmes génétiques au problème posé. Tout d'abord, des opérateurs génétiques spécialisés ont été utilisés à la place des opérateurs standard. Ensuite, la fonction d'adaptation a du être modifiée après que les premiers résultats utilisant le modèle de l'élasticité en grands déplacements eurent conduit à des résultats non-viables : une contrainte sur le champ de contraintes mécaniques a été incorporée à la fonction d'adaptation.

Revue Française de Mécanique 4 pp 237-246, 1997

Inductive Learning of Mutation Step-size in Evolutionary Parameter Optimization

Michèle Sebag, Marc Schoenauer, and Caroline Ravisé

The problem of setting the mutation step-size for real-coded evolutionary algorithms has received different answers: exogenous rules like the $1/5$ rule, or endogenous factor like the self-adaptation of the step-size in the Gaussian mutation of modern Evolution Strategies. On the other hand, in the bitstring framework, the control of both crossover and mutation by means of Inductive Leaning has proven beneficial to evolution, mostly by recognizing -- and forbidding -- past errors (i.e. crossover or mutations leading to offspring that will not survive next selection step). This Inductive Learning-based control is transposed to the control of mutation step-size in evolutionary parameter optimization, and the resulting algorithm is experimentally compared to the self-adaptive step-size of Evolution Strategies.

Proceedings of the Sixth Annual Conference on Evolutionary Programming, LNCS 1213, pp 247-261, Indianapolis, April 1997.

Mechanical Inclusions Identification by Evolutionary Computation.

Marc Schoenauer, Leila Kallel and Francois Jouve

The problem of the identification of mechanical inclusion is theoretically ill-posed, and to-date numerical algorithms have demonstrated to be inaccurate and unstable. On the other hand, Evolutionary Algorithms provide a general approach to inverse problem solving. However, great care must be taken during the implementation: The choice of the representation, which determines the search space, is critical. Three representations are presented and discussed. Whereas the straightforward mesh-dependent representation suffers strong limitations, both mesh-independent representation provide outstanding results on simple instances of the identification problem, including experimental robustness in presence of noise.

Revue européenne des éléments finis. Vol 5(5-6), pp 619-648, 1996.

Evolutionary Algorithms for Constrained Parameter Optimization Problems.

Zbigniew Michalewicz and Marc Schoenauer

Evolutionary computation techniques have received a lot of attention regarding their potential as optimization techniques for complex numerical functions. However, they have not produced a significant breakthrough in the area of nonlinear programming due to the fact that they have not addressed the issue of constraints in a systematic way. Only recently several methods have been proposed for handling nonlinear constraints by evolutionary algorithms for numerical optimization problems; however, these methods have several drawbacks and the experimental results on many test cases have been disappointing.

In this paper we (1) discuss difficulties connected with solving the general nonlinear programming problem, (2) survey several approaches which have emerged in the evolutionary computation community, and (3) provide a set of eleven interesting test cases, which may serve as a handy reference for future methods.

Evolutionary Computation Vol 4(1), pp 1-32, 1996.

Topological Optimum Design using Genetic Algorithms

C. Kane and M. Schoenauer

Structural topology optimization is addressed through Genetic Algorithms: A set of designs is evolved following the Darwinian {\em survival-of-fittest} principle. The goal is to optimize the weight of the structure under displacement constraints.
This approach demonstrates high flexibility, and breaks many limits of standard optimization algorithms, in spite of the heavy requirements in term of computational effort: Alternate optimal solutions to the same problem can be found; Structures can be optimized with respect to multiple loadings; The prescribed loadings can be applied on the unknown boundary of the solution, rather than on the fixed boundary of the design domain; Different materials as well as different mechanical models can be used, as witnessed by the first results of Topological Optimum Design ever obtained in the large displacements model.
But these results could not have been obtained without careful specific handling of the specific aspects of topological genetic optimization: First, specific genetic operators (crossover, mutation) were introduced; Second, special attention was paid to the design of the objective function; The nonlinear geometrical effects of the large displacement model lead to non viable solutions, unless some constraints are imposed on the stress field..

Control and Cybernetics, Vol.25 No.5, pp 1059-1088, 1996.

Mutation by Imitation in Boolean Evolution Strategies

M. Sebag and M. Schoenauer

Adaptive heuristics have been developed in the Evolution Strategy frame regarding the mutation of real-valued variables. But these heuristics poorly extend to discrete variables: when the rate or variance of mutation gets too small, mutation has no effect any more. To overcome this problem, we propose two mutation operators, that use the worst individuals of the current population as beacons indicating the limits of the current promising region: Mutation by differentiation drives individuals away from the beacon-individuals. Mutation by imitation inversely assumes that beacon-individuals still contain relevant informations, and aims at moving the individual at hand nearer to the beacons. Mutation by imitation produces offspring that share the features of several parents''; but in contrast with classical crossover, it allows one to control the distance between the offspringand the main parent, by fixing the number of bits to mutate. Mutation by imitation thus permits a tunable exchange of informations among individuals. Both operators have been implemented in a boolean (mu + lambda)-ES framework, and experimented on four problems: the Royal Road problem, a GA-deceptive problem, the combinatorial multiple knapsack optimization problem and the Long Path problem. Comparative validation is presented and discussed.

Proceedings of Parallel Problems Solving from Nature, Berlin, Sept. 1996. LNCS 1141

Evolutionary Computation at the Edge of Feasibility

M. Schoenauer and Z. Michalewicz

Numerical optimization problems enjoy a significant popularity in evolutionary computation community; all major evolutionary techniques use such problems for various tests and experiments. However, many of these techniques (as well as other, classical optimization methods) encounter difficulties in solving some real-world problems which include non-trivial constraints. This paper discusses a new development which is based on the observation that very often the global solution lies on the boundary of the feasible region. Thus, for many constrained numerical optimization problems it might be beneficial to limit the search to that boundary, using problem-specific operators. Two test cases illustrate this approach: specific operators are designed from the simple analytical expression of the constraints. Some possible generalizations to larger classes of constraints are discussed as well.

Proceedings of Parallel Problems Solving from Nature, Berlin, Sept. 1996. LNCS 1141

Delaying the Choice of Bias: A Disjunctive Version Space Approach

M. Sebag

This paper is concerned with alleviating the choice of learning biases via a two-step process:

- The set of all hypotheses that are consistent with the data and cover at least one training example, is given an implicit characterization of polynomial complexity. The only bias governing this induction phase is that of the language of hypotheses.

- Classification of further examples is done via interpreting this implicit theory; the interpretation mechanism allows one to relax the consistency requirement and tune the specificity of the theory at no extra induction cost.

Experimental validations demonstrate very good results on both nominal and numerical datasets.

Proceedings of International Conference on Machine Learning, Bari, July 1996

An Advanced Evolution Should Not Repeat Its Past Errors

Caroline Ravisé and Michele Sebag

A safe control of genetic evolution consists in preventing past errors of evolution from being repeated. This could be done by keeping track of the history of evolution, but maintaining and exploiting the complete history is intractable.

This paper investigates the use of machine learning, in order to extract manageable information from this history. More precisely, induction from examples of past trials and errors provides rules discriminating errors from successful trials. Such rules allow to a priori estimate the desirability of future trials; this knowledge can support powerful control strategies.

Several strategies of ML-based control are applied to a genetic algorithm, and tested on the Royal Road, a GA-deceptive, and a combinatorial optimization problem. Comparing mutation control with crossover control yields unexpected results. Proceedings of International Conference on Machine Learning, Bari, July 1996

Evolutionary algorithms for Contrained Engineering Problems

Z. Michalewicz, D. Dasgupta, R. Leriche and M. Schoenauer

Evolutionary computation techniques receive an ever increasing attention regarding their potentialities as optimization techniques for complex problems. One of the recent areas of applications for these techniques is in the field of industrial engineering; these include scheduling and sequencing in manufacturing systems, computer-aided design, facility layout and location problems, distribution and transportation problems, and many others. In this paper we concentrate on the issue of constraint handling methods for evolutionary computation techniques. This general discussion is followed by three test case studies: truss structure optimization problem, design of a composite laminated plate, and the unit commitment problem.

Computers & Industrial Engineering Journal, vol 30(2), April 1996

Evolutionary Identification of Macro-Mechanical Models

M. Schoenauer, M. Sebag, F. Jouve, B. Lamy, and H. Maitournam

This chapter illustrates the potential of genetic programming (GP) in the field of macro-mechanical modeling, addressing the problem of identification of a mechanical model for a material. Two kinds of models are considered. One-dimensional dynamic models are represented via symbolic formulations termed {\em rheological models}, which are directly evolved by GP. Three-dimensional static models of hyperelastic materials are expressed in terms of strain energy functions. A model is rated based on the distance between the behavior predicted by the model, and the actual behavior of the material given by a set of mechanical experiments. The choice of GP is motivated by strong arguments, relying on the tree-structure of rheological models in the first case, and on the need for first and second order derivatives in the second case. Key issues are the exploration of viable individuals only, and the use of Gaussian mutations to optimize numerical constants.

Shape Representations and Evolution Schemes

Marc Schoenauer

The choice of a representation i.e. the definition of the search space, is of vital importance in all Evolutionary Optimization processes. In the context of Topological Optimum Design (TOD) in Structural Mechanics, this paper investigates possible representations for evolutionary shape design. The goal is the identification of a shape in R2 having optimal mechanical properties. Evolutionary Computation has been demonstrated a valuable tool for TOD problems. However, all past results are based on the straightforward bitstring representation whose complexity increases with that of the underlying Mechanical model. To overcome this difficulty, different representations for shapes are introduced, and compared on the benchmark problem of TOD using various evolutionary schemes. The results are discussed with respect to the different degree of epistasis of the representations.

Presented at the Fifth Annual Conference on Evolutionary Programming, San Diego, March 1996

Representations for Evolutionary Optimization and Identification in Structural Mechanics

Marc Schoenauer

This paper presents an Evolutionary approach to problems of shape optimization and identification: the aim is to find a partition of a given design domain of the 2D-plane or the 3D-space into two subsets (e.g. material and void for the Optimal Design problems). The central issue of this paper is the representation of such repartition suitable for its evolutionary optimization. Three different representations are introduced and discussed, and comparative experimental results are presented.

In J. Périaux and G. Winter, editors, Genetic Algorithms in Engineering and Computer Sciences, John Wiley, 1995

Optimization of direction finders by Genetic Algorithms

Lionel Taieb and Marc Schoenauer

The relative positions of the antennas of a direction finder are critical regarding the efficiency and the robustness of the indications of the apparatus. The state of the art in direction finder optimization is limited with classical methods to the case of direction finders with 3 antennas, with naive trial-and-error methods for more complex cases. The use of Genetic Algorithms brings a tremendous increase to that domain, allowing the optimization of direction finders with up to 10 antennas in a reasonable computing time. Moreover, as GAs provide multiple optimal solutions on multi-modal problems, a thorough numerical investigation of all possible optima provides a new insight in the underlying optimization problem, finally leading to the derivation of a formula for the optimal direction finders.

Presented at GALESIA 95, First IEE/IEEE International Conference on Genetic ALgorithms in Engineering Systems: Innovations and Applications, Sheffield, September 1995

Structural topology optimization in linear and nonlinear elasticity using genetic algorithms

Couro Kane, François Jouve and Marc Schoenauer

In this paper, structural topology optimization is addressed through Genetic Algorithms. A set of designs is evolved following the Darwinian survival-of-fittest principle. The standard crossover and mutation operators are tailored for the needs of 2D topology optimization. The genetic algorithm based on these operators is experimented on plane stress problems of cantilever plates: the goal is to optimize the weight of the structure under displacement constraints. The main advantage of this approach is that it can both find out alternative optimal solutions, as experimentally demonstrated on a problem with multiple solutions, and handle different kinds of mechanical model: some results in elasticity with large displacements are presented. In that case, the nonlinear geometrical effects of the model lead to non viable solutions, unless some constraints are imposed on the stress field.

Presented at 21st ASME Design Automatic Conference, Boston MA, ASME Press, 1995

A Segregated Genetic Algorithm for Constrained Structural Optimization

Rodolphe G. Le Riche, Catherine Knopf-Lenoir and Raphael T. Haftka

The problem of minimizing by genetic algorithms the weight of a composite laminate subjected to various failure constraints is considered. Constraints are accounted for through penalty functions. The amount of penalty for each constraint violation is typically controlled by a penalty parameter that has a crucial influence on the performance of the genetic algorithm. An optimal value of each penalty parameter exists. It is larger than the smallest value of the penalty for which the global optimum is feasible. A generational elitist genetic algorithm is found to be less efficient for laminate optimization than a genetic algorithm with a more conservative selection procedure (a superelitist'' algorithm). A segregated genetic algorithm is proposed that uses a double penalty strategy and is superelitist. The segregated genetic algorithm performs as well as the superelitist genetic algorithm for optimal amounts of penalty. In addition, the segregated genetic algorithm is less sensitive to the choice of penalty parameters.

ICGA95, the sixth International Conference on Genetic Algorithms, Pittsburg, USA, Morgan Kaufmann, July 1995

Evolutionary Chromatographic Law Identification by Recurrent Neural Nets

Analytic chromatography is a physical process whose aim is the separation of the components of a chemical mixture, based on their different affinities for some porous medium through which they are percolated. This paper presents an application of evolutionary recurrent neural nets optimization to the identification of the internal law of chromatography. New mutation operators involving the parameters of a single neuron are introduced. Furthermore, the strategy for using the different kind of mutation takes into account the past history of the neural net at hand. The first results for one- and two-component mixtures demonstrate the basic feasibility of the recurrent neural net approach. A strategy to improve the robustness of the results is presented.

Presented at EP95, the fourth annual conference on Evolutionary Programming, San Diego, USA, MIT Press, March 1995

Genetic Lander: An Experiment in Accurate Neuro-Genetic Control

Edmund Ronald and Marc Schoenauer

The control problem of soft-landing a toy lunar module simulation is investigated in the context of neural nets. While traditional supervised back-propagation training is inappropriate for lack of training exemplars, genetic algorithms allow a controller to be evolved without difficulty: Evolution is a form of unsupervised learning. A novelty introduced in this paper is the presentation of additional renormalized inputs to the net; experiments indicate that the presence of such inputs allows precision of control to be attained faster, when learning time is measured by the number of generations for which the GA must run to attain a certain mean performance.

Presented at PPSN94, the third Parallel Problem Solving from Nature conference, Jerusalem, Israel, Springer Verlag, October 1994

Controlling Crossover through Inductive Learning

Michele Sebag and Marc Schoenauer

Crossover may achieve the fast combination of performant building blocks ; but as a counterpart, if a crossover point arises in a newly discovered schema, this schema may just disappear. We propose to use inductive learning to control such destructive effects of crossover. The idea is to periodically gather some examples of crossovers, labelled as "good" or "bad" crossovers according to their effects given the current population. From these examples, inductive learning then builds rules discriminating good from bad crossovers. This ruleset allows to control further crossovers : only good crossovers --- according to the rule set --- are performed. Some experimentations on the Royal Road problem are discussed.

Presented at PPSN94, the third Parallel Problem Solving from Nature conference, Jerusalem, Israel, Springer Verlag, October 1994

Genetic Extensions of Neural Net Learning: Transfer Functions and Renormalisation Coefficients

Marc Schoenauer and Edmund Ronald

This paper deals with technical issues relevant to artificial neural net (ANN) training by genetic algorithms. Neural nets have applications ranging from perception to control; in the context of control, achieving great precision is more critical than in pattern recognition or classification tasks. In previous work, the authors have found that when employing genetic search to train a net, both precision and training speed can be greatly enhanced by an input renormalisation technique. In this paper we investigate the automatic tuning of such renormalisation coefficients, as well as the tuning of the slopes of the transfer functions of the individual neurons in the net. Waiting time analysis is presented as an alternative to the classical "mean perfomance" interpretation of GA experiments. It is felt that it provides a more realistic evaluation of the real-world usefulness of a GA.

Presented at EA94, the first Evolution Artificielle conference, Toulouse, France, Cepadues, September 1994

A Rule-Based Similarity Measure

Michele Sebag and Marc Schoenauer

An induction-based method for retrieving similar cases and/or easily adaptable cases is presented in a 3-steps process : first, a rule set is learned from a data set ; second, a reformulation of the problem domain is derived from this ruleset ; third, a surface similarity with respect to the reformulated problem appears to be a structural similarity with respect to the initial representation of the domain. This method achieves some integration between machine learning and case-based reasoning : it uses both compiled knowledge (through the similarity measure and the ruleset it is derived from) and instanciated knowledge (through the cases).

Presented at CBR94

A Constraint-Based Induction Algorithm in FOL

Michele Sebag

We present a bottom-up generalization which builds the maximally general terms covering a positive example and rejecting negative examples in first-order logic (FOL), i.e. in terms of Version Spaces, the set G. This algorithm is based on rewriting negative examples as constraints upon the generalization of the positive example at hand. The constraints space is partially ordered, inducing a partial order on negative examples ; the near-misses as defined by Winston can then be formalized in FOL as negative examples minimal with respect to this partial order. As expected, only near-misses are necessary to build the set G. Moreover, constraints can be used directly to classify further examples.

Presented at ICML94, the International Conference on Machine Learning, New Brunswick, USA, Morgan Kaufmann, July 1994

Neuro-Genetic Truck Backer-Upper Controller

Marc Schoenauer and Edmund Ronald

The precise docking of a truck at a loading dock has been proposed by (Nguyen & Widrow 90) as a benchmark problem for non-linear control by neural-nets. The main difficulty is that back-propagation is not a priori suitable as a learning paradigm, because no set of training vectors is available: It is non-trivial to find solution trajectories that dock the truck from anywhere in the loading yard.

In this paper we show how a genetic algorithm can evolve the weights of a feedforward 3-layer neural net that solves the control problem for a given starting state, achieving a short trajectory from starting point to goal. The fitness of a net in the population is a function of both the nearest position from the goal and the distance travelled. The influence of input data renormalisation on trajectory precision is also discussed.

Presented at ICEC94, the first International Conference on Evolutionary Computation, Orlando, USA, IEEE Press, June 1994

Using Constraints to Building Version Spaces

Michele Sebag and Marc Schoenauer

Our concern is building the set G of maximally general terms covering positive examples and rejecting negative examples in propositional logic. Negative examples are represented as constraints on the search space. This representation allows for defining a partial order on the negative examples and on attributes too. It is shown that only minimal negative examples and minimal attributes are to be considered when building the set G. These results hold in case of a non-convergent data set. Constraints can be directly used for a polynomial characterization of G. They also allow for detecting erroneous examples in a data set.

Presented at ECML94, the European Conference on Machine Learning, Catana, Italy, April 1994

Inductive Learning of Membership Functions and Fuzzy Rules

Michele Sebag and Marc Schoenauer

By means of membership functions, measurable informations (size expressed in inches, age expressed in years) are converted into linguistic qualifiers (tall, young). It is emphasized that the acception of linguistic qualifiers is context-dependant and may depend on several attributes. Therefore, the difference between membership functions and fuzzy rules vanishes. A method inspired from inductive learning is presented : it performs the extraction of membership functions and / or fuzzy rules from examples.

in Uncertainty Modelling, Theory and Applications, B. Ayyub and M.M. Gupta Eds, serie Machine Intelligence and Pattern Recognition, North Holland, 1994

Constrained GA optimization

Marc Schoenauer and Spyros Xanthakis

We present a general method of handling constraints in genetic optimization, based on the Behavioural Memory paradigm. Instead of requiring the problem-dependent design of either repair operators (projection on the feasible region) or penalty function (weighted sum of the constraints violations and the objective function), we sample the feasible region by evolving from an initially random population, successively applying a series of different fitness functions which embody constraint satisfaction. The final step is the optimization of the objective function restricted to the feasible region. The success of the whole process is highly dependent on the genetic diversity maintained during the first steps, ensuring a uniform sampling of the feasible region. This method succeeded on some truss structure optimization problems, where the other genetic techniques for handling the constraints failed to give good results. Moreover in some domains, as in automatic generation of software test data, no other technique can be easily applied, as some constraints are not even computable until others are satisfied.

Presented at ICGA93, the fourth International Conference on Genetic Algorithms, Urbana Champaign, USA, Morgan Kaufmann, July 1993