Chapter 8 Algorithmes évolutionnaires et problèmes inverses

Ce chapitre présente succintement les algorithmes évolutionnaires ¹ , méthodes stochastiques d'optimisation globale qui s'inspirent (librement) de l'évolution darwinienne des populations biologiques, et dont font partie les algorithmes génétiques. Un des intérêts d'étudier ici ces algorithmes tient dans les nombreuses variantes de parallélisation possibles -- sachant que le temps calcul important nécessaire à l'obtention de résultats sur des problèmes réels rend indispensable l'utilisation de ressources distribuées. Quelques techniques de parallélisation seront donc décrites dans la section 8.2. Enfin, une approche générique de l'application de ces algorithmes à la résolution de problèmes inverses sera proposée, illustrée par un problème d'identification de sous-sol recherche pétrolière.

8.1 Les algorithmes

Les phénomènes physiques ou biologiques ont été à la source de nombreux algorithmes s'en inspirant plus ou moins librement. Ainsi les réseaux de neurones artificiels s'inspirent du fonctionnement du cerveau humain, l'algorithme de recuit simulé de la thermodynamique, et les algorithmes évolutionnaires (AEs) (dont les plus connus sont les algorithmes génétiques) de l'évolution darwinienne des populations biologiques.

Avant de décrire plus avant les algorithmes évolutionnaires précisons toutefois que le paradigme darwinien qui sous-tend ces algorithmes est une grossière caricature du phénomène naturel qu'il imite, et qu'en tout état de cause, il ne saurait être une justification de l'emploi de ces techniques -- pas plus que le vol des oiseaux ne peut justifier l'invention de l'avion!² .

8.1.1 Définitions et notations

Soit à optimiser une fonction F à valeurs réelles definie sur un espace W, supposé muni d'une distance d. Le parallèle avec l'évolution naturelle a entrainé l'apparition d'un vocabulaire spécifique :

La fonction objectif F est appelée fonction performance, ou fonction d'adaptation (fitness en anglais) ;
Les points de l'espace de recherche W sont appelés des individus ;
Les P-uplets d'individus sont appelés des populations ;
On parlera d'une génération pour la boucle principale de l'algorithme ;

8.1.2 Le squelette

La pression de l'``environement'' est simulée à l'aide de la fonction d'adaptation F, et le principe darwinien Les plus adaptés survivent et se reproduisent, est implanté de la manière suivante :

Initialisation de la population P₀ en choisissant P individus dans W, généralement par tirage aléatoire avec une probabilité uniforme sur W ;
Evaluation des individus de P₀ (i.e. calcul des valeurs de F pour tous les individus) ;
La génération i construit la population P_i à partir de la population P_i-1 :
- Sélection des individus les plus performants (au sens de F) de P_i-1 ;
- Application (avec une probabilité donnée) des opérateurs génétiques aux parents sélectionnés, ce qui génère de nouveaux individus, les enfants ; on parlera de mutation pour les opérateurs unaires, et de croisement pour les opérateurs binaires (ou n-aires) ;
- Evaluation des enfants ;
- Remplacement des parents au moyen d'une sélection darwinienne parmi les enfants, avec participation éventuelle des parents.
L'évolution stoppe quand le niveau de performance souhaité est atteint, ou qu'un nombre fixé de générations s'est écoulé sans améliorer l'individu le plus performant.

Figure 8.1: Squelette d'un algorithme évolutionaire

Il est important de noter que le coût CPU essentiel de ces algorithmes provient de l'étape d'évaluation (calcul des performances) : les tailles de populations sont de l'ordre de quelques dizaines, le nombre de générations de quelques centaines, ce qui donne lieu à quelques dizaines de milliers de calculs de F.

8.1.3 Les composants

Nous allons maintenant détailler les principaux composants d'un algorithme évolutionnaire, en donnant des exemples concrets.

On notera tout d'abord que l'on peut répartir les diverses étapes de l'algorithme de la section précédente en deux groupes : celles qui dépendent de l'espace de recherche (initialisation, opérateurs génétiques et évaluation) et celles qui n'en dépendent pas (sélection et remplacement).

L'étape d'évaluation, totalement spécifique au problème traité, et objet des sections sur la parallélistion, ne sera plus mentionnée ici.

L'espaces de recherche

Il s'agit de la composante principale de l'algorithme -- qui est même en fait préalable aux autres. Dans de nombreux cas, l'espace de recherche est totalement déterminé par le problème (la fonction objectif). Mais il est toujours possible de transporter son problème dans un espace habilement choisi (changement de ``variables'') où sa résolution sera plus aisée. Cet espace, où seront appliqués les opérateurs génétiques, est alors appelé espace génotypique, et l'espace de recherche initial, dans lequel est calculée la performance des individus, est appelé espace phénotypique.

Nous allons maintenant donner deux exemples d'espaces de recherche parmi les plus utilisés -- et détaillerons les composantes de l'algorithmes dans ces deux cas particulier.
Les chaînes de bits (bitstring en anglais).
L'espace de recherche est ici W = {0,1}^N. Historiquement (voir section 8.1.4) il s'agit de l'école des algorithmes génétiques, et la jsutification de l'utilisation intensive de cet espace de recherche particulier était fondé à la fois sur un parallèle encore plus precis avec la biologie (une chaîne de bits étant assimilée à un chromosome) et sur des considérations théoriques qui ne seront pas détaillées ici (voir les références de la section 8.1.4 à ce sujet). Ce contexte reste toutefois très utilisé, et permet également une présentation aisée des divers composants de l'algorithme.
Les vecteurs de réels:
C'est bien sûr le cas le plus fréquent en calcul numérique : W est un sous-ensemble de IRⁿ, borné ou non. On parle alors aussi d'optimisation paramétrique.

Initialisation

Le principe général de l'initialisation est d'échantilloner le plus uniformément possible l'espace de recherche W.

Dans le cas des chaînes de bits, chaque bit de chaque individu est tiré égal à 0 ou à 1 avec un probabilité 0.5.

Dans le cas de l'optimisation paramétrique, si W = P[a_i,b_i] (cas borné), on tire uniformément chaque coordonnée dans l'intervalle correspondant. Par contre, si W n'est pas borné, il faut faire des choix. On pourra par exemple tirer mantisses et exposants uniformément.

Opérateurs génétiques

C'est durant cette étape que de nouveaux individus sont crées à partir des individus préalablement sélectionnés. On distingue les opérateurs de croisement (binaires, ou plus généralement n-aires) et les opérateurs de mutation, unaires. A noter que cette étape est toujours stochastique, c'est à dire que le résultat de l'application d'un opérateur dépend de tirages aléatoires.
Le croisement
L'idée générale du croisement est l'échange de matériel génétique entre les parents : si deux parents sont plus performants que la moyenne, on peut espérer que cela est du à certaines parties de leur génotype, et que certains des enfants, recevant les''bonnes'' parties de leurs deux parents, n'en seront que plus performants. Ce raisonnement, trivialement valable pour des fonctions performance linéaires, est extrapolé (et expérimentalement vérifié) à une classe plus étendue de fonctions, sans que les résultats théoriques aujourd'hui disponibles ne permettent de délimiter précisément la classe de fonctions pour lesquelles le croisement est utile.

Signalons enfin que tous les individus sélectionnés ne sont pas forcément croisés. Le croisement -- comme tous les opérateurs génétiques, est appliqué avec une certaine probabilité notée P_c.
Dans le cadre des chaînes de bits, les divers opérateurs de croisement échangent des bits (à position fixée) entre les parents. La figure 8.2 donne l'exemple du croisement à point. Un autre croisement consiste à tirer au sort pour chaque position (avec probabilité 0.5) de quel parent proviendra le bit correspondant chez chaque enfant.

(b₁, ..., b_N)

(c₁, ..., c_N)
ü
ý
þ

P_c

¾®

ì
í
î

(b₁, ..., b_l, c_l+1, ..., c_N)

(c₁, ..., c_l, b_l+1, ..., b_N)

Figure 8.2:

Dans le cadre de l'optimisation paramétrique, on peut bien entendu appliquer les mêmes opérateurs d'échange de coordonnées. On peut également -- et c'est en général bien plus efficace -- ``mélanger'' les deux parents par une combinaison linéaire. On parle alors de croisement arithmétique :

(X,Y)

p_c

¾®

a X + (1 - a) Y , a = U[0,1]

(X,Y)

p_c

¾®

a_i X_i + (1 - a_i) Y_i , a_i = U[0,1]

La première version revient à choisir l'enfant uniformément sur le segment [X Y] alors que la deuxième revient à tirer l'enfant uniformément sur l'hypercube dont [X Y] est une diagonale. Remarquons que l'échange de coordonnées revient à choisir comme enfant un des sommets de cet hypercube.
La mutation L'idée directrice de la mutation est de permettre de visiter tout l'espace. Les quelques résultats théoriques de convergence des algorithmes évolutionnaires ont d'ailleurs tous comme condition l'ergodicité de la mutation, c'est-à-dire le fait que tout point de l'espace de recherche peut être atteint en un nombre fini de mutations.
Dans le cadre des chaînes de bits, on modifie aléatoirement certains bits. Par exemple, pour chaque parent (ou enfant du croisement), et pour chaque position l,

(b₁, b₂, ..., b_N)

p_m

¾®

(b₁, b₂, ..., 1-b_l, b_l+1, ..., b_N)

Attention, la probabilité p_m est ici une probabilité par bit et non par individu.

Une autre possibilité est de prédéfinir un nombre de bits à modifier (généralement 1) et de choisir ensuite au hasard une position dans chaque individu et de modifier le bit correspondant. Cet opérateur est lui appliqué avec un probabilité P_m par individu, bien sûr.

Dans le cadre de l'optimisation paramétrique, la mutation la plus employée est la mutation gaussienne, qui consiste à rajouter un bruit gaussien à chaque variable (l'opérateur étant appliqué avec une certaine probabilité par individu P_m).

X_i := X_i + N(0,s²)

Tout l'art est alors dans le choix de la variance s du bruit gaussien utilisé. On peut évidemment demander à l'utilisateur de fixer cette valeur. Mais des études théoriques sur des fonctions simples ont démontré que cette valeur devrait décroitre au fil des générations -- et il devient difficile de fixer une suite de valeurs décroissante qui soit synchrone avec l'éventuelle convergence de l'algorithme pour des fonctions quelconques.

L'idée originale pour résoudre ce problème est due aux pères des stratégies d'évolution (I. Rechenberg et H.-P. Schwefel, voir section 8.1.4). Elle consiste à considérer ces s comme des variables supplémentaires, et à les faire également évoluer (via croisement et mutation!).

Si l'espace phénotypique initial est, par exemple, P[a_i,b_i], l'espace génotypique sera P[a_i,b_i] × IR⁺, chaque individu se voyant muni de sa propre variance s. La mutation devient alors

s := s exp(t N(0,1))

X_i := X_i + N(0,s)

La variance s est modifiée par une perturbation log-normale -- elle doit rester positive, et son évolution doit ètre symétrique par rapport à un puisqu'elle intervient ensuite de manière multiplicative.

L'idée est qu'un individu ayant de bonnes performances après plusieurs mutations n'est pas arrivé où il est par hasard, et doit avoir une valeur de s adaptée à la zone de l'espace de recherche où il se trouve. Signalons qu'il existe une variante dans laquelle une variance est attachée à chaque variable. Enfin, dans la variante la plus générale, une matrice de corrélation complète évolue avec chaque individu.

Procédures de sélection

La partie darwinienne de l'algorithme comprend les deux étapes de sélection et de remplacement. Répétons que ces étapes sont totalement indépendantes de l'espace de recherche.

On distingue deux catégories de procédures de sélection ou de remplacement (par abus de langage, nous appellerons sélection les deux types de procédures) : les procédures déterministes et les procédures stochatiques.
Sélection déterministes
On sélectionne les meilleurs individus (au sens de la fonction performance). Si plus de quelques individus doivent être selectionnés, cela suppose un tri de l'ensemble de la population -- mais cela ne pose un problème de temps calcul que pour des très grosses tailles de population.

Les individus les moins performants sont totalement éliminés de la population, et le meilleur individu est toujours sélectionné -- on parle alors d'élitisme.
Sélection stochastiques
Il s'agit toujours de favoriser les meilleurs individus, mais ici de manière stochastique, ce qui laisse une chance aux individus moins performants. Par contre, il peut arriver que le meilleur individu ne soit pas sélectionné, et qu'aucun des enfants n'atteigne un performance aussi bonne que celle du meilleur parent ...

Le tirage de roulette est la plus célèbre des sélections stochastiques. Supposant un problème de maximisation avec uniquement des performances positives, elle consiste à donner à chaque individu une probabilité d'être sélectionné proportionnelle à sa performance. Une illustration de la roulette est donnée figure 8.3 : on lance la boule dans la roulette, et on choisit l'individu dans le secteur duquel la boule a fini sa course.

Figure 8.3: Sélection par tirage de roulette : cas de 4 individus de performances respectives 50, 25, 15 et 10. Une boule est ``lancée'' dans cette roulette, et l'individu dnas le secteur duquel elle s'arrête est sélectionné.

Le tirage de roulette présente toutefois de nombreux inconvénients, en particulier reliés à l'échelle de la fonction performance : alors qu'il est théoriquement équivalent d'optimiser a F + b et F pour tout a > 0, il est clair que le comportement de la sélection par roulette va fortement dépendre de a dans ce cas. C'est pourquoi cette sélection est presque totalement abandonnée aujourd'hui.

La sélection par le rang consiste à faire une sélection en utilisant une roulette dont les secteurs sont proportionnels aux rangs des individus. La variante linéaire utilise directement le rang (P pour le meilleur, 1 pour le moins bon, pour une population de taille P), les variantes polynomiales remplaçant ces valeurs par i/ P^a, a>0. Seuls comptent alors les position srelatives des individus entre eux, et non les valeurs -- arbitraires -- de la fonction F.

La sélection par tournoi n'utilise aussi que des comparaisons entre individus -- et ne nécessite même pas de tri de la population. Elle possède un paramètre T, taille du tournoi. Pour sélectionner un individu, on en tire T uniformément dans la population, et on sélectionne le meilleur de ces T individus. Le choix de T permet de faire varier la pression sélective, c'est-à-dire les chances de sélection des plus performants par rapport aux plus faibles. A noter que le cas T=2 correspond, en espérance et au premier ordre en fonction de P, à la selection par le rang linéaire.

Les schémas d'évolution

On regroupe sous ce nom les ensemble sélection/remplacement, qui ne peuvent être dissociées lors des analyses du darwinisme au sein des algorithmes évolutionnaires. Un schéma d'évolution est donc la réunion d'une procédure de sélection et d'une procédure de remplacement. Toute combinaison des procédures présentées plus haut (et de bien d'autres encore) est licite. Toutefois, certaines combinaisons sont plus souvent utilisées, que ce soit pour des raisons historiques, théoriques ou expérimentales. Pour cette raison, les noms donnés sont souvent les noms des école historiques qui les ont popularisées -- mais gardons à l'esprit que ces schémas sont totalement indépendants de l'espace de recherche, alors que nous verrons que les écoles historiques travaillaient sur des esapces de recherche bien précis.
Schéma algorithme génétique générationel (GGA)
Ce schéma utilise une sélection stochastique pour sélectionner exactement P parents (certains parents peuvent donc être sélectionnés plusieurs fois, d'autres pas du tout). Ces P parents donnent ensuite P enfants par application des opérateurs génétiques (avec probabilité donnée). Enfin, ces P enfants remplacent purement et simplement les P parents pour la génération suivante.
Schéma algorithme génétique stationnaire (Steady-state GA -- SSGA)
Dans ce schéma, un individu est sélectionné, généralement par tournoi, un second si le croisement doit être appliqué, et l'enfant résultant (après croisement et mutation éventuels) est re-inséré dans la population en remplacement d'un ``vieux'' parent sélectionné par un tournoi inversé (le moins performant ``gagne'').
Schémas stratégies d'évolution ((µ ,⁺ l)-ES)
Deux schémas sont regroupés sous ces appellations. Dans les deux cas, l'étape de sélection est un tirage uniforme (on peut dire qu'il n'y a pas de sélection au sens darwinien). À partir d'une population de taille µ (notations historiques!), l enfants sont générés par application des opérateurs génétiques. L'étape de remplacement est alors totalement déterministe. Dans le schéma (µ ,l)-ES, les meilleurs µ enfants deviennent les parents de la génération suivante, alors que dans le schéma (µ +l)-ES, les meilleurs des µ + l parents plus enfants sont les parents de la génération suivante.

8.1.4 Les algorithmes historiques

On distingue quatre grandes familles historiques d'algorithme -- et les différences entre elles ont laissé des traces dans le paysage évolutionnaire actuel, en dépit d'une unification de nombreux concepts.

Algorithmes Génétiques (GA), J. Holland, 1975 et D.E. Goldberg, 1989, Michigan, USA.
Les GA ont été imaginés comme outils de modélisation de l'adaptation. Ils travaillent dans l'espace des chaînes de bits [0,1]ⁿ avec les schémas GGA et SSGA. Ce sont les plus connus des algorithmes évolutionnaires, et (malheureusement ?) souvent les seuls variantes connues des chercheurs des autres disciplines.
Stratégies d'évolution (ES), I. Rechenberg et H.P. Schwefel, 1965, Berlin.
Les ES ont été mises au points par deux jeunes ingénieurs travaillant sur des problèmes numériques. Le contexte était l'optimisation paramétrique, et les schémas d'évolution sont bien entendu les (µ ,⁺ l)-ES. Un énorme progrès a été apporté par les techniques adaptatives d'ajustement des paramètres de mutation, et ce sont sans contestation les meilleurs algorithmes pour les problèmes purement numériques.
Programmation évolutionnaire (EP), L.J. Fogel, 1966 et D.B. Fogel, 1991, 1995, Californie, USA.
Imaginée par Larry Fogel pour la découverte d'automates à états finis pour l'approximation de séries temporelles, EP a rapidement travaillé sur des espaces de recherche très variés. Le schéma utilisé ressemble à s'y méprendre à un (P+P)-ES -- quoique développé complètement indépendemment.
Programmation génétique (GP), J. Koza, 1990, Californie, USA.
Apparue initialement comme sous-domaine des GAs, GP est devenu une branche à part entière (conférence, journal, ...). La spécificité de GP est l'espace de recherche, fait d'arbres représentant des programmes complets. GP cherche à atteindre (et réussit souvent!) un des vieux rêves des programmeurs, faire écrire le programme par un autre programme. Les schémas d'évolution utilisés sont souvent de type SSGA, mais avec des tailles de population énormes. Et les tendance récentes sont pour GP ... la parallélisation systématique et sur de grosses grappes de stations. Ainsi, les résultats récents les plus spectaculaires obtenus par Koza l'ont été avec 64 populations de 10000 individus, ou encore avec 1000 populations de 500 individus, utilisant le modèle en îlots (voir section 8.2.3) sur des grappes Beowulf de stations Alpha ou Pentium sous Linux.

8.1.5 Les points-clé

La diversité génétique

Le terme diversité génétique désigne la variété des génotypes présents dans la population. Elle devient nulle lorsque tous les individus sont identiques -- on parle alors de convergence de l'algorithme (a posteriori!). Mais il est important de savoir que lorsque la diversité génétique devient très faible, il y a très peu de chances pour qu'elle augmente à nouveau. Et si cela se produit trop tôt, la convergence a lieu vers un optimum local -- on parle alors de convergence prématurée. Il faut donc préserver la diversité génétique, sans pour autant empécher la convergence. Un autre point de vue sur ce problème est le suivant.

Le dilemne exploration-exploitation

A chaque étape de l'algorithme, il faut effectuer le compromis entre explorer l'espace de recherche, afin d'éviter de stagner dans un optimum local, et exploiter les meilleurs individus obtenus, afin d'atteindre de meilleurs valeurs aux alentours. Trop d'exploitation entraîne une convergence vers un optimum local, alors que trop d'exploration entraîne la non-convergence de l'algorithme.

Typiquement, les opérations de sélection et de croisement sont des étapes d'exploitation, alors que l'initialisation et la mutation sont des étapes d'exploitation. On peut ainsi régler les parts respectives d'exploration et d'exploitation en jouant sur les divers paramètres de l'algorithme (probabilités d'application des opérateurs, pression de sélection, ...). Malheureusement, il n'existe pas de règles universelles de réglages et seuls des résultats expérimentaux donnent une idée du comportement des divers composantes des algorithmes.

8.2 Parallélisation des AEs

Les algorithmes évolutionnaires sont des algorithmes coûteux en temps calcul -- mais il est facile de voir que l'étape la plus coûteuse -- l'évaluation de la performance de toute une population -- est constituée de calculs totalement indépendants entre eux. Il semble donc facile de les paralléliser.

Cependant, la méthode naturelle de lancement en parallèle des calculs de performance n'est pas la seule manière d'envisager la parallélisation des algorithmes évolutionnaires. Il existe même une gamme complète de manière de paralléliser ces algorithmes, de la simple parallélisation du calcul de performance lui-même jusqu'à la distribution complète de la population sur les divers processeurs disponibles.

Une quantité clé pour le choix de la méthode de parallélisation comme pour le calcul du gain que celle-ci apporte est le ratio évaluation-évolution, rapport entre le temps moyen pour un calcul de performance et le temps moyen nécessaire pour la sélection, l'application des opérateurs génétiques et le remplacement d'un individu (temps moyen, car ces opérations sont généralement effectuées sur des groupes d'individus).

8.2.1 Parallélisation du calcul de performance

Cette technique est citée pour mémoire, car rien de général ne peut être dit a ce sujet : si l'on dispose déjà d'un algorithme de calcul de la fonction performance parallèle, on peut bien sûr l'utiliser au sein d'un algorithme évolutionnaire standard. Le gain espéré dépend alors totalement du problème.

8.2.2 Distribution du calcul de performance

Distribution synchrone

Il s'agit donc de paralléliser l'étape d'évaluation. Une station maître gère l'algorithme lui-même (sélection/remplacement et opérateurs génétiques), et envoie les calculs de performance à des stations esclaves. Le comportement de l'algorithme parallèle est alors exactement celui de l'algorithme séquentiel, et le facteur d'accélération devient rapidement très proche du nombre de processeurs lorsque le ratio évaluation-évolution augmente, pour des tailles de population ne dépassant pas quelques multiples du nombre de processeurs disponibles.

Figure 8.4: Distribution des calculs de performance, (c) Th. Bäck, ICD, Dortmund.

Lorsque la durée d'un calcul de performance varie d'un calcul à l'autre (que ce soit en raison de conditions de calcul différentes, ou de par l'hétérogénéité des processeurs utilisés), le gain apporté par ce schéma de parallélisation peut toutefois se dégrader, l'ensemble des processeurs devant alors attendre le plus lent d'entre eux. Une gestion plus fine de la distribution des calculs (à l'aide d'une liste de calculs à effectuer, un processeur recevant un nouveau calcul dés la fin du calcul précédent) permet de limiter ce phénomène sans complètement le suprimer en fin de génération. De plus, la tolérance aux pannes est nulle : si un processeur s'arrête pour une raison quelconque, l'ensemble de l'algorithme se mettra en attente du résultat manquant.

Distribution asynchrone

Une manière élégante de régler ces problèmes est d'utiliser un schéma d'évolution asynchrone : chaque processeur esclave effectue son calcul de performance, renvoie le résultat au maître et reçoit immédiatement un nouveau calcul. Cela suppose que les étapes de sélection/remplacement peuvent être effectuée individu par individu. Le schéma steady-state séquentiel permet déjà cela, et peut donc être utilisé sans modification : chaque fois qu'un esclave renvoie la performance d'un enfant, le maître effectue l'étape de remplacement pour cet enfant, immédiatement suivie d'une sélection de nouveaux parents et de l'appliation des opérateurs génétiques, avant de renvoyer l'enfant à évaluer à l'esclave en question, qui ainsi n'attend pas.

Un premier inconvénient est que certains individus dont le calcul de performance aura été plus long (convergence plus lente d'un algorithme numériques ou processeur moins rapide) seront insérés dans une population ayant évolué depuis leur apparition, et risquent d'être anachroniques -- et en particulier de d'être éliminés rapidement, avant d'avoir été sélectionnés pour reproduction. Mais il ne semble pas expérimentalement que ce phénomène soit très pénalisant.
Mais plus limitant pour les deux modèles précédents est l'engorgement de communications qui se produit au noeud maître dés que le nombre de processeurs augmente, et si le temps ratio évaluation-évolution n'est pas suffisant : les esclaves doivent alors attendre leur tour pour recevoir le calcul suivant.

Ni Dieu ni maître

Signalons pour mémoire une version totalement tolérante aux pannes -- en ce sens que tant qu'un processeur (et le serveur de fichiers) fonctionne, l'algorithme peut continuer -- est le modèle dans lequel la population, toujours centralisée, n'est plus maintenue physiquement sur un processeur, mais se trouve stockée dans un fichier auquel tous les processeurs ont accès. Chaque processeur effectue alors l'ensemble des opérations sélection - opérateurs - évaluation - remplacement en lisant et écrivant dans le fichier de la population.

L'inconvénient de ce schéma est bien sûr le temps important nécessaire aux ouvertures/lecture/fermeture du fichier, plus le fait qu'un seul processeur peut écrire en même temps. A n'utiliser qu'en environnement hostile, et si le temps d'un calcul de performance est important.

8.2.3 Modèle en îlots

Le modèle suivant de parallélisation des algorithmes évolutionnaires consiste à diviser la population en petites sous-population, chaque sous-population évoluant sur un processeur, suivant un schéma traditionnel auquel vient s'ajouter une étape de migration : chaque sous-population envoie ses meilleurs individus soit vers les populations voisines soit dans un ``pool'' commun -- ce choix dépend du coût relatifs des communications entre processeurs. Chaque sous-population reçoit ensuite des individus soit envoyés par ses voisins soit péchés dans le ``pool'' central.

Une des possibilités offerte par ce modèle en îlots est que chaque sous-population évolue en utilisant des paramètres différents (voir Figure 8.5) : le réglage des paramètres est un des talons d'Achille des algorithmes évolutionnaires, et c'est là une manière élégante de ne pas choisir ... D'aute part, les ``bons'' paramètres peuvent être différents à différentes étapes de l'évolution, et on peut espérer qu'une des sous-population au moins aura des paramètres bien réglés à tout moment. En envoyant ses meilleurs individus aux autres sous-populations, elle tirera l'ensemble des individus dans le bon sens.

Figure 8.5: Exemple de modéle en îlots -- le paramètre de mutation est différent à chaque noeud, (c) Th. Bäck, ICD, Dortmund.

Mais même lorsque les sous-populations utilisent exactement les mêmes paramètres, la dispersion topologique, fonction du mode de migration choisi (i.e. entre voisins uniquement, ou avec un échange généralisé), a pour effet de préserver la diversité génétique plus longtemps. En effet, il est important de noter qu'il ne s'agit pas ici de la simple parallélisation de l'algorithme séquentiel, mais d'un algorithme à la dynamique totalement différente. Ceci rend en particulier difficiles les comparaisons avec les versions séquentielles, et biaise les tentatives d'estimation du gain.

8.2.4 Population distribuée

Un dernier modèle de parallélisation consiste à distribuer une unique population sur l'ensemble des processeurs (en général sur des machines massivement parallèles). Sur chaque processeur ``vivent'' alors quelques individus (souvent un seul), et les opérations de sélection/remplacement et de croisement se font entre individus ``voisins'' pour la topologie du réseau de processeurs.

Ce modèle génère lui aussi une nouvelle dynamique de l'algorithme, différente des précédentes, avec, comme dans le modèle en îlots, l'apparition de ``niches écologiques'' distribuées par ``zones géographiques de processeurs'', et permettant donc également la découverte d'optima multiples.

A noter qu'il existe en général dans ce modèle un processeur superviseur (ou root), qui reçoit des informations de l'ensemble des processeurs et permet de suivre précisément l'évolution de l'ensemble en affichant diverses statistiques. C'est en particulier lui qui décidera de l'arrêt de l'algorithme.

Figure 8.6: Population totalement distribuée, répartie sur une grappe de stations arrangées en topologie torique. Sur chaque noeud se trouvent quelques individus, qui se reproduisent localement.

8.2.5 Quel modèle choisir?

Il reste certainement des modes de parallélisation des algorithmes évolutionnaires à inventer. Il faut cependant retenir pour le moment que les deux derniers modèles présentés ci-dessus se sont montrés souvent plus performants que l'algorithme séquentiel, au-delà du gain en vitesse du à l'accroissement de ressources (on a constaté des convergences supra-linéaires du modèle totalement distribué par exemple). Au point que ces variantes d'algorithmes sont maintenant quelquefois implantées ... sur des machines séquentielles!
Le choix d'un modèle particulier dépend et du problème et de la configuration matérielle, ... et bien sûr des outils et/ou du temps dont on dispose pour l'implantation.

Négligeant le cas où l'on dispose déjà d'une évaluation de performance parallèle, le modèle le plus simple à implanter est évidemment la distribution du calcul de performance. De plus, il n'y a pas de paramètre supplémentaire à ajuster -- une expérience du schéma steady-state séquentiel est suffisante. Le gain à espérer, en cas de réseau de processeurs homogènes, et de calculs équivalents en temps, est strictement linéaire en fonction du nombre de processeurs. Par contre le noeud maître peut rapidement être saturé si le nombre de processeurs est grand en fonction au temps d'un calcul de performance.

Lorsque le nombre de processeurs disponibles augmente, il faut passer au modèle en îlots. L'investissement en développement n'est pas aussi important qu'il y parait à première vue : il faut ajouter à la boucle de génération classique les étapes de migration. Par contre, l'algorithme étant totalement modifié, il faut prévoir un temps de prise en main non négligeable -- sans compter les choix de paramètres (stratégie et fréquence de migration). D'un autre côté, on peut espérer des gains plus importants, soit de par l'utilisation de différents jeux de paramètres d'évolution aux différents noeuds, soit de par la dynamique différente -- préservation d'une plus grande diversité génétique plus longtemps.

8.3 Résolution de problèmes inverses

Un problème inverse est défini par rapport à un problème direct. Le problème direct consiste à simuler un phénomène physique (ou mécanique, ou chimique), à partir de conditions expérimentales données, d'une loi modélisant le phénomène et d'un schéma numérique :

Entrées

Sortie

1in

Conditions
expérimentales

1in

Loi

1in

Comportement
simulé

Figure 1 : Un problème direct

Le problème inverse consiste, partant de conditions expérimentales et du comportement du phénomène physique observé dans ces conditions, à déterminer une loi modèlisant le phénomène physique de façon satisfaisante. La performance d'une loi est donnée par la différence entre le comportement simulé, obtenu par résolution du problème direct pour cette loi avec les conditions expérimentales données, et le comportement réellement observé avec les mêmes conditions expérimentales :

Entrées

Sortie

2in

1.5in

Conditions expérimentales

1.5in

Comportement observé

1in

Loi

Figure 2 : Un problème inverse du problème de la Figure 1.

Fréquemment, les problèmes inverses ne peuvent être traités par les approches classiques faute de disposer d'une fonction performance assez régulière et dont les dérivées soient connues. Au contraire, l'optimisation évolutionnaire requiert uniquement que la fonction performance soit calculable : elle est applicable à tout problème inverse correspondant à un problème direct numériquement résolu.
Reste à choisir l'espace dans lequel rechercher la loi inconnue, ce qui pose le dilemme suivant. Lorsque l'espace exploré est trop restreint, la qualité de la solution peut être compromise ; lorsque cet espace est trop vaste, la convergence de l'optimisation peut être trop lente.
La fin de ce chapitre décrit un exemple en acoustique, l'identification de sous-sol en prospection pétrolière.

8.3.1 Exemple en acoustique

On se propose de retrouver une anomalie dans le sous-sol en fonction d'enregistrements de sismogrammes réalisés en surface d'après des explosions artificielles. La propagation des explosions est simulée par la résolution numérique de l'équation des ondes (avec conditions aux limites absorbantes, voir [Bam98]). Plusieurs représentations sont possibles pour la cible de l'identification :

Si l'on suppose que l'on recherche une anomalie dans un sous-sol par ailleurs homogène, que les caractéristiques physiques du sous-sol et de l'anomalie sont connues, et que la forme de l'anomalie est une ellipse, on est ramené à l'identification ... de 2 paramètres, les deux axes de l'ellipse d₁ et d₂.
Il est possible également de chercher la valeur de la vitesse de propagation dans cette ellipse. Le problème reste un problème d'optimisation paramétrique, i.e. l'espace de recherche est un sous -ensemble de IRⁿ (ici, n=3).
On peut à loisir rajouter des inconnues, par exemple la position du centre de l'ellipse (espace de recherche = IR⁵).
Mais il est plus difficile de rechercher une forme inconnue - voire une distribution totalement arbitraire des vitesses de propagation dans le sous-sol. La première question à résoudre pour ce problème, tout de même plus réaliste, est alors celle du choix de l'espace de recherche.

A noter par contre que quelle que soit la représentation choisie, le calcul de la fonction performance est exactement le même, à savoir la résolution d'autant de problèmes directs qu'il y a de sources d'explosion. Par contre, le choix d'une représentation générale implique que la recherche peut être plus longue ...

Dans tous les cas, il suffit (!) de disposer d'opérateurs génétiques (croisement, mutation) en rapport avec le problème et la représentation.

8.3.2 Représentation paramétrique

Le problème est de trouver une représentation pour un champ scalaire (la vitesse de propagation des ondes dans le milieu considéré) dans un domaine 2d. La première approche est ``naturelle'' pour tout numéricien: On discrétise le domaine souterrain en éléments, étape de toute façon nécessaire à la résolution numérique du problème direct, et on considère une variable par élément.

Les opérateurs usuels pour l'évolution de vecteurs de variables réelles sont le croisement arithmétique et la mutation gaussienne adaptative (voir section 8.1.3).

L'inconvénient de cette méthode est le nombre élevé de variables dés que l'on souhaite une précision importante, ainsi que l'absence totale de toute corrélation entre les diverses variables : il est clair que des variations très rapides du sous-sol entre plusieurs éléments voisins ne sont pas possibles physiquement. Par contre, des individus présentant de telles anomalies ont la même probabilité d'apparition dans l'espace de recherche que des configurations de vitesse ``raisonnables''.

8.3.3 Diagrammes de Voronoï

Avec un peu d'imagination, on peut trouver d'autres représentations à la fois plus réalistes en terme de description du sous-sol, mais surtout dont la complexité (le nombre de ``variables'') ne dépend pas d'une quelconque discrétisation.

Figure 8.7: Exemple de représentation de Voronoï. Le génotype est la liste des sites de Voronoï munis chacun d'un scalaire (la vitesse en ce site). Le phénotype est obtenu par construction du diagramme de Voronoï correspondant : un point du domaine a la vitesse du site de Voronoï le plus proche de lui.

Une approche possible repose sur la notion de Diagrammes de Voronoî : l'espace de recherche est l'ensemble des listes de taille variable de sites de Voronoî auxquels est associé une vitesse de propagation. Le pavage du sous-sol par les cellules de Voronoî correspondantes réalise alors une disposition des vitesses de propagation ``constantes par gros morceaux'' dans le sous-sol -- ce qui est déjà plus réaliste (voir Figure 8.7. De plus, la complexité du maillage n'intervient pas sur la taille de l'espace de recherche. Les détails sur cette représentation et les opérateurs associés (qui se devinent aisément), ainsi que des exemples de résultats obtenus sur ce problème inverse (avec un algorithme séquentiel!) peuvent être trouvés dans l'article [SAB98].

1: On n'hésitera pas à consulter les livres ou articles [BFM97], [BNKF97], [SAB98] et [Mic96].
2: on peut même utiliser ce type d'algorithme en n'étant pas un convaincu du darwinisme, d'oú d'ailleurs l'emploi du néologisme ``évolutionnaire'', inspiré de l'anglais evolutionary.