ALGORITHMES GÉNÉTIQUES



MÉTHODES NUMÉRIQUES

1. Complexité

1.1. NP-Complétude

2. Partie entière

3. Algorithme d'Héron

4. Algorithme d'Archimède

5. Calcul du nombre d'Euler

6. Systèmes d'équations linéaires

6.1. Une équation à une inconnue

6.2. Deux équations à deux inconnues

6.3. Trois équations à trois inconnues

6.4. N équations à n inconnues

7. Polynômes

8. Régressions et interpolations

8.1. Régression linéaire à une variable explicative

8.1.1. Droite de régression

8.1.2. Méthodes des moindres carrés

8.1.3. Analyse de la variance de la régression

8.2. Régression logistique

8.3. Interpolation polynômiale

8.3.1. Courbes de Bézier

8.3.2. Méthodes d'Euler

8.3.3. Polynôme de collocation

9. Recherche de racines

9.1. Méthodes des parties proportionnelles

9.2. Méthode de la bissection

9.3. Méthode de la sécante (Regula Falsi)

9.4. Méthode de Newton

10. Aires et sommes de riemann

10.1. Méthode des rectangles

10.2. Méthode des trapèzes

11. Programmation linéaire

11.1. Algorithme du simplexe

12. Méthode de Monte-Carlo

12.1. Calcul d'une intégrale

12.2. Calcul de PI

12.3. Dichotomie

13. Analyse en composantes principales (A.C.P.)

14. Analyse factorielle des correspondances (A.F.C.)

15. Khi-2

16. Méthode des différences finies

17. Réseaux de neurones formels

17.1. Modèle de neurone

17.2. Fonctions de transfert

17.3. Architecture de réseau

18. Algorithmes génétiques

18.1. Codage et population initiale

18.2. Les opérateurs

18.2.1. Opérateur de sélection

18.2.2. Opérateur de croisement

18.2.3. Opérateur de mutation

Les algorithmes génétiques (AGs) sont des algorithmes d'optimisation stochastiques itérés fondés sur les mécanismes de la sélection naturelle et de la génétique.

Leur fonctionnement est relativement simple :

1. Nous partons avec une population de solutions potentielles (chromosomes) initiales arbitrairement choisies

2. Nous évaluons leur performance (fitness) relative

3. Sur la base de ces performances, nous créons une nouvelle population de solutions potentielles en utilisant des opérateurs évolutionnaires simples : la sélection, le croisement et la mutation.

4. Nous recommençons ce cycle jusqu'à ce que nous trouvions une solution satisfaisante.

Les AGs ont été initialement développés par John Holland (1975). C'est au livre de Goldberg (1989) que nous devons leur popularisation. Leurs champs d'application sont très vastes. Outre l'économie (minimisation du risque des portefeuilles), ils sont utilisés pour l'optimisation de fonctions, en finance, en théorie du contrôle optimal (recherche opérationnelle), ou encore en théorie des jeux répétés et différentiels (en l'occurence dans les jeux évolutionnaires et le dilemme du prisonnier) et la recherche d'information (Google) ainsi que la recherche des plus courts chemins en théorie des graphes (routages Internet ou GPS). La raison de ce grand nombre d'applications est claire : simplicité et efficacité. Bien sûr, d'autres techniques d'exploration stochastiques existent, la méthode de Monte-Carlo peut-être considéré comme un concept similaire.

Pour résumer, Lerman et Ngouent (1995) distinguent quatre principales propriétés qui font la différence fondamentale entre ces algorithmes et les autres méthodes :

P1. Les algorithmes génétiques utilisent un codage des paramètres, et non les paramètres eux-mêmes.

P2. Les algorithmes génétiques travaillent sur une population de points, au lieu d'un point unique.

P3. Les algorithmes génétiques n'utilisent que les valeurs de la fonction étudiée, pas sa dérivée, ou une autre connaissance auxiliaire.

P4. Les algorithmes utilisent des règles de transition probabilistes, et non déterministes.

La simplicité de leurs mécanismes, la facilité de leur mise en application et leur efficacité même pour des problèmes complexes ont conduit à un nombre croissants de travaux ces dernières années.

Définitions:

D1. Un "algorithme génétique" est défini par un individu/chromosome/séquence et une solution potentielle au problème donné.

D2. Une "population" est un ensemble de chromosomes ou de points de l'espace de recherche

D3. "L'environnement" est assimilé à l'espace de recherche

D4. La fonction que nous cherchons à optimiser est appelée "fonction de fitness"

Avant d'aller plus loin, il faut définir de manière plus formelle les concepts précédents (mais sous l'hypothèse particulière ! de codage binaire).

Définition: Les organismes en compétitions sont appelées "individus". Soit un alphabet equation, nous supposerons que chaque individu peut être représenté par un mot de longueur fixe l pris dans equation. Le mot A associé à un individu de la population sera appelé "chromosome" ou "séquence" (le terme n'est pas tout à fait équivalent à son homonyme biologique, cependant c'est une pratique courant que d'utiliser ce terme ici aussi) et donné donc par A de longueur l(A) avec equation (cause : hypothèse du codage binaire).

Dans la mesure où il n'y aura pas de risque de confusion, nous identifierons les termes individus et chromosome.

Les individus forment une population P de taille N, notée :

equation   (57.104)

Nous allons faire une autre assertion importante, c'est-à-dire, qu'il existe une fonction f d'une séquence à valeurs positives que nous noterons equation, dite "fonction de fitness" qui à tout equation associe un réel tel que :

equation   (57.105)

si et seulement si equation est mieux adapté au milieu queequation.

Remarquons que le terme "adapté" n'est pas défini. Pour cela, il faudrait caractériser le milieu dans lequel évoluent les individus, ce que nous ne ferons pas. En fait, puisque nous supposons l'existence d'une telle fonction et que nous posons l'équivalence avec le degré d'adaptation, celui-ci est automatiquement défini par la donnée de f.

Nous nommerons "génération" une population à un instant t, ce qu'il faut mettre en relation avec la notion de durée de vie ou d'âge. Cependant, nous nous placerons ici dans le cas particulier où chaque individu a une durée de vie égale à 1, donc la génération (t+1) est constituée d'individus différents de la génération t, nous les appellerons les "descendants". Réciproquement, les individus de la génération t seront les "ancêtres" des individus de la génération (t+1). Nous désignerons la génération t par P(t) soit la population à l'instant t.

Ainsi, un chromosome est vu comme une suite de bits en codage binaire appelé aussi "chaîne binaire". Dans le cas d'un codage non binaire, tel que le codage réel par exemple, alors la suite A ne contient qu'un point, nous avons equation avec equation

Remarque: La fitness (efficacité) est donc donnée par une fonction à valeurs positives réelles. Dans le cas d'un codage binaire, nous utiliserons souvent une fonction de décodage d qui permettra de passer d'une chaîne binaire à un chiffre à valeur réelle :

equation   (57.106)

La fonction de fitness est alors choisie telle qu'elle transforme cette valeur en valeur positive soit :

equation   (57.107)

Le but d'un algorithme génétique est alors simplement de trouver la chaîne qui maximise cette fonction f. Bien évidemment, chaque problème particulier nécessitera ses propres fonctions d et f.

Les AGs sont alors basés sur les phases suivantes :

1. Initialisation : une population initiale de N chromosomes est tirée aléatoirement

2. Évaluation : chaque chromosome est décodé puis évalué

3. Sélection : création d'une nouvelle population de N chromosomes par l'utilisation d'une méthode de sélection appropriée.

4. Reproduction : possibilité de croisement et mutation au sein de la nouvelle population

5. Retour à la phase d'évaluation jusqu'à l'arrêt de l'algorithme

CODAGE ET POPULATION INITIALE

Il existerait trois principaux type de codage : (1) Binaire, (2) Gray, (3) Réel. Nous pouvons facilement passer d'un codage à l'autre. Certains auteurs n'hésitent pas, par ailleurs, à faire le parallèle avec la biologie en parlent de génotype (cf. chapitre de Dynamique Des Populations) en ce qui concerne la représentation binaire d'un individu, et de phénotype (cf. chapitre de Dynamique Des Populations) pour ce est de sa valeur réelle correspondante dans l'espace de recherche.

Rappelons que la transformation la plus simple (fonction de décodage d) d'une chaîne binaire A en nombre entier x s'opère par la règle suivante (cf. chapitre sur les Nombres) :

equation   (57.108)

Ainsi le chromosome equation vaut trivialement :

equation  (57.109)

Evidemment, la fonction d sera modifiée (par tâtonnements!) selon le problème. Ainsi, si nous cherchons à maximiser une fonction equation une méthode possible serait la suivante (la taille du chromosome dépendant bien évidemment de la précision voulue) :

equation   (57.110)

ce qui peut s'assimiler à une série harmonique. Pour une précision au cinquième chiffre après la virgule nous imposerons equation puisque :

equation   (57.111)

Une autre façon de faire serait de choisir d telle que :

equation   (57.112)

Petite explication :

equation   (57.113)

Posons equation :

equation   (57.114)

Ainsi, avec equation nous avons equation et :

equation   (57.115)

La précision demandée y étant toujours vérifiée puisque :

equation   (57.116)

Cette dernière règle peut se généraliser. Ainsi, admettons que nous cherchons à maximiser (normaliser serait un terme peut-être plus correct) f en fonction d'une variable réelle x. Soit equation, avec equation, l'espace de recherche permis avec equation et equation les bornes inférieures et supérieures. Soit prec la précision (chiffre après la virgule) avec laquelle nous cherchons x. Soit equation la longueur de l'intervalle D. Nous devons alors diviser cet intervalle au pire en :

equation   (57.117)

sous-intervalles égaux afin de respecter la précision. Par exemple, soit equation nous avons donc equation si nous voulions une précision equation, alors il nous faut diviser cet intervalle en equation sous intervalles.

Avec s l'entier naturel tel que equation (dans notre exemple, equation car equation), la transformation d'une chaîne binaire equation en un nombre réel x peut alors s'exécuter en trois étapes :

1. Conversion (base 2 en base 10) :

equation   (57.118)

2. Normalisation :

equation   (57.119)

3. Maximisation :

equation   (57.120)

ou ce qui revient au même directement en une seule étape par :

equation   (57.121)

Ainsi pour equation, et equation nous retrouvons bien :

equation   (57.122)

Pour ce qui est de la phase d'initialisation, la procédure est assez simple. Elle consiste en un tirage aléatoire de N individus dans l'espace des individus permis. En codage binaire, selon la taille l de la chaîne, nous effectuons pour un chromosome l tirages dans equation avec équiprobabilité.

LES OPÉRATEURS

Les opérateurs jouent un rôle prépondérant dans la possible réussite d'un AG. Nous en dénombrons trois principaux : l'opérateur de sélection, de croisement et de mutation. Si le principe de chacun de ces opérateurs est facilement compréhensible, il est toutefois difficile d'expliquer l'importance isolée de chacun de ces opérateurs dans la réussite de l'AG. Cela tient pour partie au fait que chacun de ces opérateurs agit selon divers critères qui lui sont propres (valeur sélective des individus, probabilité d'activation de l'opérateur, etc.).

OPÉRATEUR DE SÉLECTION

Cet opérateur est peut-être le plus important puisqu'il permet aux individus d'une population de survivre, de se reproduire ou de mourir. En règle générale, la probabilité de survie d'un individu sera directement reliée à son efficacité relative au sein de la population.

Il existe plusieurs méthodes pour la reproduction .La méthode la plus connue et utilisée est sans nul doute, la roue de loterie biaisée (roulette wheel) de Goldberg (1989). Selon cette méthode, chaque chromosome sera dupliqué dans une nouvelle population proportionnellement à sa valeur d'adaptation. Nous effectuons, en quelque sorte, autant de tirages avec remises qu'il y a d'éléments dans la population. Ainsi, dans le cas d'un codage binaire, la fitness d'un chromosome particulier étant f(d(A)), la probabilité avec laquelle il sera réintroduit dans la nouvelle population de taille N est:

equation   (57.123)

Les individus ayant une grande fitness ont donc plus de chance d'être sélectionnées. Nous parlons alors de "sélection proportionnelle".

L'inconvénient majeur de cette méthode repose sur le fait qu'un individu n'état pas le meilleur pourrait tout de même dominer la sélection (imaginez la recherche du maxima d'une fonction dans equation, il peut y en a avoir plusieurs - de maxima - et donc mauvaise sélection...), nous parlerons alors à juste titre de "convergence prématurée" et c'est l'un des problèmes les plus fréquents lors de l'utilisation des algorithmes génétiques. Elle peut aussi donc engendrer une perte de diversité par la domination d'un super individu. Un autre inconvénient est sa faible performance vers la fin quand l'ensemble des individus se ressemblent.

Une solution à ce problème ne tient pas dans l'utilisation d'une autre méthode de sélection mais dans l'utilisation d'une fonction de fitness modifiée. Ainsi, nous pouvons utiliser un changement d'échelle (scaling) afin de diminuer ou accroître de manière artificielle l'écart relatif entre les fitness des individus.

Brièvement, il existe d'autres méthodes, la plus connue étant celle du tournoi (tournament selection) : nous tirons deux individus aléatoirement dans la population et nous reproduisons le meilleur des deux dans la nouvelle population. Nous refaisons cette procédure jusqu'à ce que la nouvelle population soit complète. Cette méthode donne de bons résultats. Toutefois, aussi important que soit la phase de sélection, elle ne crée pas de nouveau individus dans la population. Ceci est le rôle des opérateurs de croisement et de mutation.

OPÉRATEUR DE CROISEMENT

L'opérateur de croisement permet la création de nouveaux individus selon un processus fort simple. Il permet donc l'échange d'information entre les chromosomes (individus). Tout d'abord, deux individus, qui forment alors un couple, sont tirés au sein de la nouvelle population issue de la reproduction. Puis un (potentiellement plusieurs) site de croisement est tiré aléatoirement (chiffre entre 1 et l-1). Enfin, selon une probabilité equation que le croisement s'effectue, les segments finaux (dans le cas d'un seul site de croisement) des deux parents sont alors échangés autour de ce site :

equation
  (57.124)

Cet opérateur permet la création de deux nouveaux individus. Toutefois, un individu sélectionné lors de la reproduction ne subit pas nécessairement l'action d'un croisement. Ce dernier ne s'effectue qu'avec une certaine probabilité. Plus cette probabilité est élevée et plus la population subira de changement.

Quoi qu'il en soit, il se peut que l'action conjointe de la reproduction et du croisement soit insuffisante pour assurer la réussite de l'AG. Ainsi, dans le cas du codage binaire que nous avons choisi jusqu'ici, certaines informations (in extenso : caractères de l'alphabet) peuvent disparaître de la population. Ainsi aucun individu de la population initiale ne contient de 1 en dernière position de la chaîne, et que ce 1 fasse partie de la chaîne optimale à trouver, tous les croisements possibles ne permettront pas de faire apparaître ce 1 initialement inconnu. En codage réel, une telle situation peut arriver si utilisant un opérateur simple de croisement, il se trouvait qu'initialement toute la population soit comprise entre 0 et 40 et que la valeur optimale était de 50. Toutes les combinaisons convexes possibles de chiffres appartenant à l'intervalle [0,40] ne permettront jamais d'aboutir à un chiffre de 50. C'est pour remédier entre autre à ce problème que l'opération de mutation est utilisée.

OPÉRATEUR DE MUTATION

Le rôle de cet opérateur est de modifier aléatoirement, avec une certaine probabilité, la valeur d'un composant de l'individu. Dans le cas du codage binaire, chaque bit equation est remplacé selon une probabilité equation par son inverse equation. C'est ce qu'il illustre la figure ci-dessous. Tout comme plusieurs lieux de croisement peuvent être possibles, nous pouvons très bien admettre qu'une même chaîne puisse subir plusieurs mutations.

equation
  (57.125)

La mutation est traditionnellement considérée comme un opérateur marginal bien qu'elle confère en quelque sorte aux algorithmes génétiques la propriété d'ergodicité (in extenso : tous les points de l'espace de recherche peuvent être atteints). Cet opérateur est d'une grande importance. Il a de fait un double rôle : celui d'effectuer une recherche locale et/ou de sortir d'une trappe (recherche éloignée).

Les opérateurs de l'algorithme génétique sont guidés par un certain nombre de paramètres fixés à l'avance. La valeur de ces paramètres influence la réussite ou non d'un algorithme génétique. Ces paramètres sont les suivants :

- La taille de la population N, et la longueur du codage de chaque individu l (dans le cas de codage binaire). Si N est trop grand, le temps de calcul de l'algorithme peut s'avérer très important, et si N est trop petit, il peut converger trop rapidement vers un mauvais chromosome.

- La probabilité de croisement equation. Elle dépend de la forme de la fonction de fitness. Son choix est en général heuristique (tout comme pour equation). Plus elle est élevée, plus la population subit évidemment de changements importants. Les valeurs généralement admises sont comprises entre 0.5 et 0.9.

- La probabilité de mutation equation. Ce taux est généralement faible puisqu'un taux élevé risque de conduire à une solution sous-optimale.

Plutôt que de réduite equation, une autre façon d'éviter que les meilleurs individus soient altérés est d'utiliser la reconduite explicite de l'élite dans une certaine proportion. Ainsi, bien souvent, les meilleurs 5%, par exemple, de la population sont directement reproduits à l'identique, l'opérateur de reproduction ne jouant alors que sur les 95% restant. Cela est appelé une "stratégie élitiste".

Parant du constat que les valeurs des paramètres des différents opérateurs sont eux-mêmes inconnus et ne peuvent être améliorés au fur et à mesure que de manière expérimentale, certains auteurs, tels que Novkovic et Sverko (1997), proposent d'utiliser une sorte de méta-AG : l'un pour trouver l'individu optimal et l'autre pour trouver la valeur optimale des paramètres. Ces deux algorithmes tourneraient alors simultanément ou séquentiellement. Toutefois, il est inévitable que le temps de calcul (la complexité algorithmique) s'alourdisse en conséquence.

Voyons maintenant un exemple d'AG (exemple de Goldberg - 1989). Il consiste à trouver le maximum de la fonction equation sur l'intervalle [0,31] où x est un entier. La première étape consiste à coder la fonction. Par exemple, nous utilisons un codage binaire de x, la séquence (chromosome) contenant au maximum 5 bits. Ainsi, nous avons equation, de même equation. Nous recherchons donc le maximum d'une fonction de fitness (nous choisirons equation lui-même dans cet exemple simple) dans un espace de 32 valeurs possible de x.

1. Tirage et évaluation de la population initiale

Nous fixons la traille de la population à equation. Nous tirons donc de façon aléatoire 4 chromosomes sachant qu'un chromosome est composé de 5 bits, et chaque bit dispose d'une probabilité ½ d'avoir une valeur 0 ou 1. Le maximum, (au hasard) 16 est atteint par la deuxième séquence. Voyons comment l'algorithme va tenter d'améliore ce résultat.

D'abord nous obtenons le tableau suivant :

Chromosome

Valeur

Fitness f(x)

Pi %

1

00101

5

5

14.3

2

10000

16

16

45.7

3

00010

2

2

5.7

4

01100

12

12

34.3

Total

   

35

100

Tableau: 57.10  - Évolution (mutation) des chromosomes

Nous tournons donc quatre fois cette roue pour obtenir la séquence suivante :

Tirage

Chromosome

1

10000

2

01100

3

00101

4

10000

Tableau: 57.11  - Séquence tirage des chromosomes

Nous voyons bien ici le risque que nous aurions à perdre la séquence N° 2 dès le départ... c'est le problème de cette méthode. Elle peut converger moins vite que d'autres. Cependant, le lecteur remarquera que nous avons perdu la séquence N° 3.

Nous passons maintenant à la partie du croisement : les parents sont sélectionnés au hasard. Nous tirons aléatoirement un lieu de croisement ("site" ou "locus") dans la séquence. Le croisement s'opère alors à ce lieu avec une probabilité equation. Le tableau ci-dessous donne les conséquences de cet opérateur en supposant que les chromosomes 1 et 3, puis 2 et 4 sont appariés et qu'à chaque fois le croisement s'opère (par exemple avec equation).

 

l=2

l=3

Séquences d'origine

100|00

01|100

001|01

10|000

Séquences croisées

10001

01000

00100

10100

Tableau: 57.12  - Croisement des chromosomes

Nous passons maintenant à la partie mutation : dans cet exemple à codage binaire, la mutation est la modification aléatoire occasionnelle (de faible probabilité) de la valeur d'un bit (inversion d'un bit). Nous tirons ainsi pour chaque bit un chiffre aléatoire entre 0 et 1 et si ce chiffre est inférieur à equation alors la mutation s'opère. Le tableau ci-dessous avec equation met en évidence ce processus :

Anc. Chr.

Tirage aléa.

Nouveau bit

Nouveau Chr.

10001

15 25 36 04 12

1

10011

00100

26 89 13 48 59

-

00100

01000

32 45 87 22 65

-

01000

10100

47 01 85 62 35

1

11100

Tableau: 57.13  - Mutation des chromosomes

Maintenant que la nouvelle population est entièrement créée, nous pouvons de nouveau l'évaluer :

Chromosome

Valeur

Fitness f(x)

Pi %

1

10011

19

19

32.2

2

00100

4

4

6.8

3

01000

8

8

13.5

4

11100

28

28

47.5

Total

   

59

100

Tableau: 57.14  - Évaluation de la mutation des chromosomes

Le maximum est maintenant 28 (N° 4). Nous sommes donc passés de 16 à 28 après une seule génération. Bien sûr, nous devons recommencer la procédure à partir de l'étape de sélection jusqu'à ce que le maximum global, 31, soit obtenu, ou bien qu'un critère d'arrêt ai été satisfait.

Remarque: Il est possible de démontrer mathématiquement, ce qui est remarquable !!!, que les portions de chromosomes qui se retrouvent chez les meilleurs individus vont avoir tendance à se reproduire...