Samuel BERNARD
Année 2003
V1.0.0.1

Algorithmes Evolutionnaires

Plan de l'exposé:

• Introduction aux méthodes d'optimisations

• Un problème concret: optimisation d'un commutateur optique

• Présentation d'un commutateur TIR

• Variables d'optimisation

• Une manière pour le résoudre, les algorithmes évolutionnaires

• Description

• Algorithmes Génétiques

• Initialisation

• Evaluation

• Sélection

• Croisement

• Mutation

• Mise à jour

• Les limitations

• Adaptation au problème posé

• Codage

• Espace de recherche

• Fonctions objectif

• Fonction d'adaptation

• Paramètres de l'algorithme

• Résultats

• Conclusion

• Bibliographie

Introduction aux différentes méthodes d'optimisation

L'optimisation d'une fonction est un problème très important pour les ingénieurs. Et ce dans tous les domaines. Pour cela, différentes méthodes sont utilisées:

• Méthodes déterministes
  Revient à la résolution de systèmes de n eq à n inconnues, linéaires ou non, donc on peut utiliser la méthode du gradient ou de Gauss-Seidel (que l'on ne détaillera pas dans cet exposé)

• Méthodes non déterministes
  Font appel à des tirages aléatoires pour mieux explorer l'espace de recherche

• Monte carlo: évaluation de la fonction en des points choisit aléatoirement.* Hybride: gradients a partir de points choisis aléatoirement

• Recuit simulé: A partir d'un point initial, on se déplace aléatoirement. Si la valeur est plus grande, on l'accepte sinon on la refuse avec une certaine probabilité.

• Algorithme évolutionnaire: Simulation d'évolution de populations de solutions. Les meilleurs individus sont sélectionnés et croisés entre eux pour donner d'autres individus. C'est le thème de cet exposé.

Optimisation d'un commutateur optique

Présentation d'un commutateur TIR

Nous allons chercher à optimiser les paramètres qui régissent un commutateur à réflexion interne total (ou commutateur TIR). Un commutateur directionnel permet d'aiguiller la lumière dans un guide ou dans un autre en faisant varier l'indice de réfraction au niveau de l'embranchement. Ces composants servent à la réalisation de matrices de commutation pour la génération de retards temporels, afin de commander des antennes actives. Ils sont constitués de deux guides sécants et d'une électrode surplombant l'intersection. Une injection forte de courant peut entraîner une diminution d'indice de réfraction suffisante pour induire une réflexion totale.

Principe d'un commutateur TIR.

Variables d'optimisation

Schéma d'un commutateur TIR et ses principales variables.

Les sept variables prises en compte dans l'optimisation sont:
- l’angle entre les deux guides q
- la largeur des guides l
- la largeur du miroir e
- la longueur du miroir l_m
- le décalage de l’axe du miroir d_m
- la largeur de la zone intermédiaire e₂
- la consommation du miroir I_s (fonction de la variation d’indice dn).

Algorithmes Evolutionnaires

Description

L'evolution naturelle a permis de créer des systèmes biologiques très complexes adaptés à de nombreuses conditions. Ses mécanismes reposent sur le principe de compétition entre les individus. Les individus les mieux adaptés aux conditions survivent et peuvent laisser une descendance qui répandront leurs gènes.
Devant ces possibilités, quelques chercheurs des années 50 ont tenté d'en adapter le principe a l'ingénierie. Mais la faible puissance des machines de l'époque et des connaissances de la génétique naturelle n'a pas permis d'avoir de résultats concluants. Plus tard, dans les années 60 et 70, trois écoles utilisant le principe de l'évolution de façon différente apparurent:

• Les algorithmes génétiques (GA) développés par J.H.Holland

• La programmation évolutionnaire (EP) de L.J.Fogel

• Les stratégie d'évolution (ES) de H.P.Shwefel

Plus tard, une autre classe d'algorithmes évolutionnaires vit le jour, la programmation génétique (GP) de J.Koza qui était auparavant un sous groupe des GA.

Ces différentes classes d'algorithmes évolutionnaires ne différent que sur les détails d'implantation des opérateurs et sur les procédures de sélection et remplacement de la population. Malgré que leur but soient différent à l'origine, ils sont maintenant surtout utilisés pour résoudre des problèmes d'optimisations. Dans la suite de cet exposé, nous verrons plus en détail les algorithmes génétiques qui sont les plus connus des algorithmes évolutionnaires.

Algorithmes Génétiques

Les algorithmes génétiques suivent tous le même schéma de fonctionnement:

- Initialisation
*boucle
- Evaluation
- Sélection
- Croisement
- Mutation
- Mise à jour
recommencer a boucle

Initialisation:

Tout d'abord, on fixe l'espace de recherche; la plupart du temps, il s'agit de {0,1}^N pour des raisons de simplicité. On crée ensuite des fonctions de codage et de décodage entre le génotype d'un individu qui est inclus dans l'espace de recherche et son phénotype qui est la valeur de la fonction pour cet individu. L'efficacité de l'algorithme dépendra grandement du choix de ce codage ce qui présente deux difficultés: limiter l'espace de recherche et fournir des solutions valides pour le problème.
Puis on crée la première population qui sera amenée a évoluer. On définit ainsi à cette étape la taille des populations N qui ne doit pas être trop élevée pour que le temps de calcul soit raisonnable ni trop faible pour que la solution trouvée soit intéressante. Pour composer cette première population, on fixe aléatoirement la valeur des gènes d'un individu selon une distribution uniforme.

Evaluation:

On définit au préalable la fonction d'adaptation qui associe a chaque phénotype une valeur dite d'adaptation, c'est la note de l'individu, plus elle est élevée, plus la solution donnée par ce phénotype est optimale.
La construction de cette fonction doit être particulièrement optimisée car elle sera executé un grand nombre de fois, jusqu'à N fois à toutes les générations, ce qui fait que la rapidité de l'algorithme depend essentiellement d'elle.
Elle doit aussi pouvoir tenir compte des phénotypes invalides si le problème doit satisfaire des contraintes que les opérateurs de mutation et croisement ne respectent pas.

Sélection:

Notons que les étapes de sélection et de remplacement sont indépendantes de l'espace de recherche. Nous appelerons sélection l'ensemble des deux procédures.
On distingue deux types de sélection:
- la sélection déterministe:
On sélectionne toujours les meilleurs individus et on écarte totalement les plus mauvais. Cela suppose un tri de l'ensemble de la population. On parle alors d'élitisme.
- la sélection stochatique
On favorise toujours les meilleurs individus mais de manière stochatique ce qui laisse une chance aux individus moins performants. Il se peut que le meilleur individu ne soit pas sélectionné au depens du plus faible et qu'aucun des enfants ne soit au niveau du meilleur parent.

Différentes techniques de sélection:

• Tirage de roulette (RWS)
  Chaque individu a une chance d'être selectionné proportionnelle à sa performance. Pour utiliser l'image de la roulette, chaque individu possède une case de la roulette dont la taille dépend de son adaptation. On lance la boule dans la roulette et on sélectionne l'individu qui possède la case où elle est tombé. Cette méthode est très classique mais a une forte variance: avec un peu de malchance, un individu très mauvais peut être choisi autant de fois qu'il y a de place pour la génération suivante et de même, il se peut qu'aucun des 'bons' individus ne soit sélectionné.

• Sélection universelle stochastique (SUS)
  On prend l'image d'un segment decoupé en autant de sous segment qu'il y a d'individus. Les individus sélectionnés sont désignés par un ensemble de points équidistants. Cela garantit alors une variance faible.

• Sélection par tournois
  On choisit n individus et on sélectionne le meilleur qui pourra encore participer à un tournoi. On organise aurant de tournois qu'il y a d'individus a repêcher. La variance de cette méthode est élevée. Le nombre n permet de donner plus ou moins de chance aux individus peu adaptés. Avec un nombre élevé de participants, un individu faible sera presque toujours sûr de perdre. Une variante est d'accepter le gagnant qu'avec une certaine probabilité comprise entre 0.5 et 1.

• Elitisme
  On trie l'ensemble de la population suivant leur adaptation et on sélectionne les premiers. La variance est nulle et la pression de sélection très élevée. (les faibles n'ont aucune chance au contraire des forts qui sont toujours sélectionnés)

Croisement

Une fois certains individus sélectionnés, on les fait se reproduire entre eux, pour cela on utilise l'opérateur croisement. C'est l'opérateur essentiel de recherche d'un algorithme génétique. Il combine les génotype de deux individus pour en obtenir deux nouveaux. Avec cet opérateur, les génotypes sont vus comme une chaîne de nombres binaires. Plusieurs méthodes de croisement sont utilisées:

• Croisement en un point:
  On choisit au hasard un point de coupure identique sur les deux génotypes et on échange les fragments situés après le point de coupure pour donner les deux nouveaux génotypes.

• Croisement en deux points:
  On choisit au hasard deux points de croisement et on échange les fragments situés entre ces deux points.

• Croisement en k points:
  Généralisation à k points de coupure des méthodes précédentes.

• Croisement uniforme:
  Il peut être vu comme un croisement multi-points dont le nombre de points de coupure n'est pas connu a priori. En pratique on utilise un masque binaire de la même longueur que les génotypes. Si à la n-ième position, il y a un 0, on conserve les symboles sinon on les échanges. Le masque est généré aléatoirement pour chaque couple.

Il existe d'autres sortes de croisement qui peuvent améliorer les précédents sous selon divers aspects ou alors ce sont des opérateurs crées spécifiquement pour un problème donné (pour respecter certaines conditions des génotypes par exemple).

Mutation

L'opérateur de mutation modifie aléatoirement la valeur de certains bits d'un génotype avec une faible probabilité, typiquement entre 0.01 et 0.001. Si ce dernier est trop élevé, on risque de ne pas voir une bonne convergence, et s'il est trop faible, ça réduit d'autant son effet.
L'interêt de cet opérateur est d'éviter une dérive génétique: certains gènes favorisés par le hasard peuvent se répandre au détriment des autres et sont ainsi présents au même endroit sur tout les génotypes. La mutation permet alors un maintien de la diversité génétique utile pour une bonne exploration de l'espace de recherche.
Un autre interêt est de permettre une meilleure recherche locale, notamment quand la plupart des individus ont convergé autour de l'optimum global. A ce moment, le croisement est assez inefficace car les individus sont souvent identiques. La mutation leur donne alors la chance de s'approcher du maximum globale d'autant que le permet la précision du codage.
On a alors principalement le croisement pour explorer globalement et entièrement l'espace de recherche et la mutation pour la recherche locale et l'optimisation de solutions déjà utilisables.

Mise à jour

On crée la nouvelle génération en sélectionnant des individus de la génération précédente et en les ayant croisés entre eux et mutés pour donner de nouveaux individus. On réapplique ce processus sur cette nouvelle génération.
L'algorithme s'arrête quand le meilleur individu d'une génération a dépassé un certain stade ou alors quand un certain nombre d'individus sont identiques à la solution locale optimale (convergence partielle).

Les limitations

• Nécessité de pré-traitement, post-traitement: il faut adapter les données du problème à l'algorithme, ie créer les fonctions de codage et de décodage.

• Difficile à programmer : chaque algorithme est très dépendant du problème donc il est difficile de réutiliser des programmes déjà créés. Résultats, les concepteurs ne sont souvent pas les utilisateurs, ce qui limite leur bonne utilisation.

• Temps de calcul pouvant être important, ce qui rend l'essai de plusieurs valeurs de paramètres plus ardu.

• Les paramètres: ils sont trop souvent déterminés à l'expérience de l'utilisateur. De plus, les paramètres sont très importants pour les performances de l'algorithme, les performances peuvent être désastreuses s'ils ont été mal choisis.

Adaptation au problème posé

Nous allons utiliser les algorithmes génétiques pour optimiser notre commutateur TIR. Tout d'abord, nous devons définir le codage utilisé, l'espace de recherche, les fonctions objectif et la fonction d'adaptation.

Codage

Pour notre algorithme, nous allons utiliser un codage binaire (le plus utilisé car plus simple informatiquement parlant). Chaque gène d'un individu sera codé par un entier (32 bits) et chaque individu sera vu comme un tableau de chromosomes qui sont des tableaux de gènes. Une population est ensuite un tableau d'individus.
Les fonctions de codage et décodage sont ici relativement aisées car les individus sont caractérisés par les 7 variables du problème qui sont des nombres donc aisément codables par des entiers.

Espace de recherche

Nous avons déjà définie les variables rentrant en compte dans l'optimisation, il nous reste maintenant à borner leur valeur avec des considérations physiques, technologiques ou numériques. Par exemple, l'angle q ne doit pas être trop petit pour éviter tout couplage entre guides adjacents et ne pas être trop grand pour que la variation d'indice et donc la consommation restent raisonnables. Pour ce qui est des dimensions du miroir, elles doivent permettre une bonne efficacité, une faible consommation et une fabrication aisée. Ainsi, nous avons défini l'espace de recherche suivant:

Fonctions objectif

Les objectifs sont une consommation, une diaphonie et des pertes faibles. Donc on définit 5 fonctions objectif parce que la diaphonie et les pertes dépendent de l'état du commutateur // ou X:

• f_{pertes //} = E_sortie/E_entrée

• f_{pertes X} = E_sortie/E_entrée

• f_{diaph //} = 1 – E_sortie/E_entrée

• f_{diaph X} = 1 – E_sortie/E_entrée

• f_conso = 1 – I_s / I_{s max}
  
  

On a trouvé la formule donnant la consommation I_s en fonction des paramètres d'optimisation à l'aide d'une étude du commutateur par un modèle physique électrique. I_{s max} représente le cas le plus défavorable possible dans l'espace de recherche donné.

Fonction d'adaptation

La fonction d'adaptation est tout simplement une somme pondérée des fonctions objectif: f = Σ α_i*f_i

Les coefficients α_i permettent de privilégier tel ou tel objectif en fonction des besoins. Ici, c'est surtout utile pour pondérer la consommation suivant que l'on veut un composant économe ou performant.

Paramètres de l'algorithme

Pour cette optimisation, il a été utilisé une sélection par tournois, un renouvellement de la moitié de la population, des croisements en un ou deux points et un taux de mutation variant selon le temps, codé pour chaque géne avec un second chromosome lui aussi soumit a l'évalution avec un taux de départ fixé a 0.1.

Résultats

On conclura cette partie par les résultats obtenus par cette méthode.

Auparant, une étude avait été réalisée à l'aide d'une BPM-2D (modèle physique de la propagation de la lumière dans les guides d'onde). Elle fut relativement longue et laborieuse du fait de la méthode "à la main" employée. Voici ses résultats:

Pour que l'on puisse voir l'influence de la consommation et choisir le composant répondant à ses besoins en terme consommation, on a prit comme fonction d'adaptation:
f = (f_{pertes //} + f_{diaph //} + f_{pertes X} + f_{diaph X} + α*f_conso ) / (4+α)

Ainsi en faisant varier α, on fait varier l'importance de la consommation du composant.Voici les résultats obtenus avec une population de 100 individus:

Les résultats sont sans appels, avec des consommations bien moindres, les perfomances des composants sont au moins aussi bonne que celui optimisé "à la main". Cela démontre l'efficacité des algorithmes évolutionnaires. On remarque aussi que, bien évidemment, plus le composant consomme et plus ses propriétés sont perfomantes. C'est ainsi à l'utilisateur de savoir ce dont il a besoin, performance ou economie.

Conclusion

Les algorithmes évolutionnaires utilise le même principe que l'évolution naturelle, la compétition entre individus, pour créer des systèmes complexes pouvant s'adapter à de nombreuses situations. Cela permet d'optimiser efficacement un dispositif physique ou une fonction mathématique en explorant complètement l'espace de recherche des solutions sans pour autant avoir un coût démesuré.
Cependant, même s'il semble que ce soit une solution miracle pour optimiser n'importe quel problème, il ne faut pas oublier que le développement d'un tel algorithme efficace n'est pas à la portée de tout le monde, surtout qu'il n'existe pas encore d'outils permettant d'en réaliser sans avoir de connaissances informatiques avancées.
C'est d'ailleurs pour cela que malgré que le principe des algorithmes évolutionnaires soit très ancien informatiquement parlant, ils soient relativement peu utilisées dans l'industrie, même si cela tend a changer. Des outils de développement sont du coup mis en chantier et l'on ne devrait pas attendre trop longtemps pour qu'ils soient pleinement utilisables par les ingénieurs cherchant à résoudre un problème d'optimisation.
Mais cela serait une erreur de dire que les algorithmes évolutionnaires ne soient utiles que pour des optimisations, ils peuvent aussi servir, par exemple, à developper des réseaux de neurones efficaces ou encore sont excellents dans l'identification d'objets comme par exemple sur des images RADAR. On ne pourrait d'ailleurs pas donner la liste complète des utilisations qui seraient faites des algorithmes évolutionnaires tant il reste à découvrir et à inventer à leur sujet surtout vu la puissance et les possibilités sans cesse croissantes des ordinateurs. Notons quand même, pour finir, l'émergence de la programmation génétique qui fait évoluer des populations de programme LISP pour réaliser au mieux une taché donnée. C'est tout simplement le vieux rêve du programmeur qui fait réaliser son programme par un autre programme.

Bibliographie

http://www.eudil.fr/~vmagnin/coursag/index.html

http://www.enseignement.polytechnique.fr/profs/informatique/Eric.Goubault/poly/cours009.html

http://www.ai.univ-paris8.fr/~renaud/publications/hthese/node3.html

http://automatesintelligents.com/interviews/2001/avr/p_collet.html

http://etna.int-evry.fr/~ap/EC-tutoriel/Tutoriel.html

http://www.damas.ift.ulaval.ca/projets/pomier/Spec/node1.html

http://www.rennard.org/alife/french/gavintr.html

Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer-Verlag, seconde édition, 1994. BU : 005.1 MIC