JOURNEES EVOLUTIONNAIRES TRIMESTRIELLES 4
le 3 mai 1999
Université de Paris 5
45, rue des St Pères - Paris 6ème (Plan d'accès)
Salle Leduc (RdC à dte)
Merci à Claude Lattaud

Programme

9h30 - 10h45 Overview of evolutionary multi-objective optimisation
              résumé
             Kalyanmoy Deb

10h45 - 11h00 Pause café

11h00 - 11h45 Du neurone humain à l'algorithmique génétique et décisionnelle: un défi pour l'analyse multicritère,
              résumé
             Silvére Massebeuf, Christian Fonteix, Laszlo N. Kiss et Ivan Marc

11h45 - 12h30 Taxonomie des Méta-heuristiques hybrides
              résumé
             El-ghazali Talbi

12h30 - 14h00 Déjeuner

14h00 - 14h45 Algorithmes évolutifs appliqués à l'analyse d'images - un survol
              résumé
             Cyril Fonlupt

14h45 - 15h30 A Genetic Algorithm for the Brain Image Recognition Problem modeled by Correspondence between Graphs
              résumé
             Claudia Boeres, Aymeric Perchant, Isabelle Bloch, Michel Roux

15h30 - 16h00 Pause café et discussion ouverte

16h00 - 16h45 Une nouvelle technique d'optimisation de forme d'électrodes utilisant des algorithmes génétiques,
              résumé
             Bruno Sareni

16h45 - 17h30 Identification des constantes mécaniques d'un composite à partir de mesures ultra-sonores,
              résumé
             Catherine Potel et Catherine Vayssade

17h30 - 18h15 Optimisation paramétrique vs programmation génétique
              résumé
             Sana Ben Hamida et Alain Racine

Overview of evolutionary multi-objective optimisation
Kalyanmoy Deb,
Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur, India,
Currently visiting Department of Computer Science, University of Dortmund, Germany
Many real-world search and optimization problems are naturally posed as non-linear programming problems having multiple objectives. However, due to the lack of suitable solution techniques, such problems are artificially converted into a single-objective problem and solved. The difficulty arises because such problems give rise to a set of Pareto-optimal solutions, instead of a single optimum solution. It then becomes important to find not just one Pareto-optimal solution but as many of them as possible. Classical methods are not efficient because they require repetitive applications to find multiple Pareto-optimal solutions and in some occasions repetitive applications do not guarantee finding distinct Pareto-optimal solutions. The population approach of evolutionary algorithms (EAs) allows an efficient way to find multiple Pareto-optimal solutions simultaneously in a single run.
In this talk, the concept of multi-objective optimization will be reviewed. Thereafter, three popular classical optimization methods will be discussed to show the deficiencies in them. One implementation of a EA which uses non-domination concept will be discussed in details. Simulation results on a number of test problems and on a couple of engineering design problems will show the efficacy of the method. Clearly, EAs have a niche in solving multi-objective optimization problems compared to classical methods. This is why multi-objective optimization using EAs is getting a growing attention in the recent past. In this talk, a number of future challenges in the research of multi-objective optimization, including test problem development and solving goal programming problems will also be discussed.

Du neurone humain à l'algorithmique génétique et décisionnelle: un défi pour l'analyse multicritère,
Silvére Massebeuf, Christian Fonteix, Laszlo N. Kiss et Ivan Marc, LSGC, Nancy
Dans la fabrication d'un produit, de nombreux paramètres entrent en ligne de compte pour optimiser le procédé. L'expérience humaine est un atout considérable pour la connaissance qu'elle peut apporter au problème. Mais le décideur est souvent amené à prendre une décision de compromis parmi tous les objectifs fixés. En effet, la qualité, la productivité et les coûts de production devront toujours être optimisés. Une procédure est proposée, basée sur l'adaptation d'algorithmes génétiques diploïdes, pour reculer la prise de décision. Le concept de la domination de Pareto est utilisé pour obtenir une zone optimale multicritère la plus précise et la plus proche possible de la zone de Pareto théorique. Ensuite, une méthode de partition permet de découper cette zone en sous-parties d'intérêt similaire en terme de critère et de déterminer par conséquent des seuils de préférence pour un choix ultérieur. Enfin, un algorithme d'aide à la décision permet de faire un classement de toutes les solutions non dominées et de choisir le meilleur compromis de production. Cette démarche est appliquée à un exemple de fabrication d'aliments granulés pour bétail.

Taxonomie des Méta-heuristiques hybrides
El-ghazali Talbi, Laboratoire d'Informatique Fondamentale de Lille
Hybrid metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. A wide variety of hybrid approaches have been proposed in the literature. In this talk, a taxonomy of hybrid metaheuristics is presented in an attempt to provide a common terminology and classification mechanisms. The taxonomy, while presented in terms of metaheuristics, is also applicable to most types of heuristics and exact optimization algorithms.

Algorithmes évolutifs appliqués à l'analyse d'images - un survol
Cyril Fontlupt, Laboratoire d'informatique du Littoral, Calais
L'analyse et le traitement d'images ont des applications multiples et importantes dans des domaines aussi divers que la surveillance aérienne et satellitaire, l'analyse d'images médicales, la reconnaissance automatique d'images...
Un des objectifs principaux réalisés lors d'un processus traitement d'images est la localisation ou la reconnaissance d'un type particulier d'objet à l'intérieur de cette image. Ce processus est fort complexe car même si l'objet est défini de manière très précise, il est rare qu'il apparaisse tel quel dans l'image (image bruité ou de faible qualité) ou encore objet partiellement dissimilé.
Les techniques évolutives se prêtent bien à l'analyse d'images car ces méthodes sont particulièrement adaptées au travail dans un milieu bruité, où les critères de recherche sont soit difficiles à déterminer soit difficiles à qualifier. De plus, les techniques évolutives ne demandent qu'une très faibles connaissance a priori du problème.
Durant cet exposé, nous présenterons quelques applications du traitement d'images par les algorithmes évolutifs : amélioration d'images, reconnaissance de segments et reconnaissance de modèles.

Résolution par algorithmes génétiques de la recherche d'homomorphismes flous de graphes pour la reconnaissance de scène à partir d'un modéle.
Claudia Boeres, Aymeric Perchant, Isabelle Bloch, Michel Roux, ENST, Paris
Le domaine de l'analyse d'image médicale avec des techniques informatiques a beaucoup contribué pour une analyse plus fine des effets thérapeutiques sur des tumeurs du cerveau. Le department TSI (E.N.S.T.) a entrepris un projet avec l'hôpital Saint Vincent de Paul (Paris) dont l'objectif principal est l'analyse des images de cerveau avec des tumeurs. Le but consiste a identifier les structures anatomiques autour de la tumeur, structures qui peuvent être par la suite déformées par elle. Avec cette information, les radiologistes analyseraient mieux les images, en utilisant des mesures quantitatives. La méthode de reconnaissance prend en compte des structures de graphe pour représenter l'image à reconnaître et l'atlas anatomique qui sert de modèle à la reconnaissance.
L'idée de l'isomorphisme de graphes (ou même de l'isomorphisme de sous-graphes) est souvent utilisé dans la littérature. Néanmoins, dans les situations pratiques, quelques variantes de cette idée sont utilisées, en raison de la présence fréquente des imperfections ou du "bruit " dans les images, d'où le besoin des modèles de correspondance plus souple. Pour cette raison une variante du problème d'isomorphisme (homomorphism de graphes d'attrib uts flous ou simplement morphism de graphes d'attributs flous) a été considerée.
L'objectif de cette presentation est de se concentrer sur l'utilisation de meta-heuristiques, particulierment les algorithmes génétiques, pour régler le probleme de mise en correspondance des graphes d'attributs flous. Cette famille d'algorithmes a des développements récents dans la littérature.
Notre première approche utilise un un algorithme génétique canonique qui a été developpé et bien étudié par Holland et souvent utilisé dans plusieurs applications. Pour guider l'évolution génétique, nous avons proposé une function "fitness" fondée sur les degrés de similitudes calculés à partir des attributs des sommets et des arcs, qui représentent respectivement l'information concernant les régions (d'image a reconnaitre et du modèle) et des relations entre eux.
Dans une deuxième formulation, une nouvelle function "fitness" avec un compromis plus fort entre l'information obtenue à partir des noeuds et des arcs des graphes comparés a été proposé. Également, un nouvel opérateur de "crossover" a été défini, prenant en compte une heuristique qui inclus la connaissance du problème dans le processus de reproduction: nous essayons d'utiliser les bonnes characteristiques des chromosomes-parents pour mieux créer chromosomes-fils, quand c'est possible. De cette façon, on veut améliorer la recherche réalisé dans l'espace de solution.
Nous évaluons actuellement les résultats de ces approches sur un exemple construit à partir de vraies images de cerveau, afin d'analyser la qualité de cette méthode en considérant un problème difficile.

Une nouvelle technique d'optimisation de forme d'electrodes utilisant des algorithmes genetiques.
Bruno Sareni, Centre de Genie Electrique, Ecole Centrale de Lyon

La reduction des contraintes en champ electrique sur les profils d'electrodes est un des objectifs de l'optimisation de forme en electrostatique. Avec des methodes de C.A.O. traditionnelles, des formes d'electrodes optimales peuvent etre deduites a partir d'un profil parametre directement a l'aide de rayons et de centres de courbures.
Nous proposons une methode originale qui differe fondamentalement de l'approche precedente. Le procede que nous avons developpe pour des systemes 2D-plan et axisymetriques consiste a identifier la forme de l'electrode a une ligne equipotentielle obtenue par un systeme de charges fictives.
La conception d'une forme d'electrode se resume alors a la resolution d'un probleme d'optimisation sous contraintes ou les parametres sont les valeurs et les positions des charges. Ces parametres doivent etre optimises d'une part, de facon a ce que les formes generees respectent un gabarit geometrique donne (sous forme de limites a ne pas franchir) et d'autre part, pour qu'un objectif dependant de la solution en champ electrique soit atteint. Cette approche nouvelle permet par ailleurs de constituer des problemes contraints de difficulte variables pour tester et faire progresser les algorithmes d'optimisation.
Trois exemples d'application sont proposes et traites a l'aide d'algorithmes genetiques de nichage.

Identification des constantes mécaniques d'un composite à partir de mesures ultra-sonores,
Catherine Potel, Catherine Vayssade et Jean-François de Belleval, MNM/GSM/LG2mS, Compiègne

L'évaluation et le contrôle non destructif d'un matériau par ultrasons consiste à envoyer des ondes ultrasonores générées par un transducteur et à étudier les échos réfléchis ou transmis en vue de détecter un défaut ou de connaître les propriétés du matériau utilisé. Le contrôle se fait généralement dans l'eau, un milieu de couplage étant nécessaire entre le matériau étudié et le transducteur ultrasonore. Le problème direct de la propagation des ultrasons dans une plaque consiste, connaissant les caractéristiques d'une onde incidente (fréquence, angle) et les caractéristiques du milieu étudié (épaisseur, constantes viscoélastiques), à déduire les coefficients de réflexion ou de transmission et la vitesse de propagation de chaque onde se propageant dans le milieu. Le problème inverse consiste donc à utiliser le coefficient de réflexion ou de transmission en monochromatique (une seule fréquence) pour en déduire les constantes viscoélastiques du matériau, par algorithmes de minimisation d'erreur. C'est une méthode non classique d'inversion du problème direct, car elle permet de s'affranchir de conditions de séparation des échos des divers modes générés dans la plaque.
L'étude a commencé par un matériau isotrope, dépendant de deux constantes viscoélastiques complexes, donc de quatre variables à optimiser, chaque constante pouvant être mise sous la forme . La fonction coût choisie présentant beaucoup de minima locaux, une méthode de type gradient telle que la méthode BFGS n'est pas employable. Le passage aux algorithmes génétiques a en revanche donné de bons résultats.
Le cas d'un matériau transversalement isotrope, dépendant pour la configuration choisie de quatre constantes élastique complexes, donc de huit variables à optimiser a ensuite été étudié. L'optimisation des parties réelles seules, les parties imaginaires étant fixées, est assez bonne. En revanche, la faible variation de la fonction coût en fonction des parties imaginaires des constantes viscoélastiques entraîne une très mauvaise détermination de ces dernières.

Optimisation paramétrique vs programmation génétique
Sana BenHamida et Alain Racine, CMAP, Ecole Polytechnique
Dans le but d'ameliorer le processus de fusion nucleaire, les physiciens cherchent aujourd'hui a concevoir un systeme laser efficace produisant un faisceau d'energie optimal pour la procedure de fusion. Leur principal but est de concentrer l'energie sur la capsule elementaire a irradier avec une distribution uniforme de l'intensite et une perte d'energie minimale. Ceci revient a controler la forme du champ d'irradiance sur le plan focal du systeme optique.
Pour atteindre cet objectif, la lame de phase, un element optique fondamental traverse directement par le faisceau laser, doit etre faconnee de maniere precise. La forme de ce composant est a la fois complexe et doit respecter d'evidentes contraintes de fabrication.
Le but de cette application est donc de trouver une forme optimale pour la lame de phase permettant de rapprocher le profil d'intensite genere au plan focal d'une super gaussienne d'ordre eleve.
Ce probleme est traite avec deux approches evolutionnaires differentes: Strategies d'Evolution et Programmation Genetique. La premiere approche manipule des solutions sous forme de matrices numeriques representant le masque de phase sur un domaine carre. La seconde utilise une representation fonctionnelle (sous forme arborescente) de la surface de la lame.
Dans cet expose, nous presenterons la problematique ainsi que les resultats fournis par chacune des deux approches. Nous montrerons comment les interpretations de ces resultats ont debouche sur la mise au point d'un algorithme hybride reduisant la complexite temporelle du traitement.