guill.net - La page des réseaux

1 - Introduction

Depuis Euclid (450 ans avant J.C) les mathématiques n’ont pas cessé de modéliser les phénomènes naturels en mettant au point des concepts de plus en plus raffinés pour prendre en compte les multiples aspects de ces derniers. Ainsi naquirent alors des théories toujours plus complexes et plus abstraites pour cerner le monde qui nous entoure. Mais voilà qu’en observant le détail microscopique de ‘’mère nature ‘’, elle nous suggère des modèles mathématiques…

En effet, l’observation du système immunitaire, de la solidification des métaux, des principes de la génétique (pour ne citer que ceux-là) a conduit vers le fondement des théories telles que le recuit simulé et les algorithmes génétiques. Ces derniers qui nous intéressent particulièrement ont résolu de façon très élégante une gamme de problèmes allant des questions de mathématiques pures aux applications concrètes de finances, de distribution, d’électronique et autres…

Cet exposé est un survol des algorithmes (AG). Nous relatons, d’abord, un bref historique de l’évolution des AG. Nous présentons, ensuite, les principes de fonctionnement de ces algorithmes ainsi que leurs champs d’application et des exemples simples qui faciliteront leur compréhension
 

2 - Historique

Charles Darwin, biologiste, montre en 1859 (origin of species), que l’apparition d’espèces distinctes est le résultat de la sélection naturelle de variations individuelles.

Cette sélection naturelle est l’exercice d’une population qui lutte pour la vie et tente de s’étendre en faisant face aux multiples contraintes de l’environnement (conditions
extérieures et les autres individus) et en disposant d’un espace et de ressources limités.

Les individus les plus adaptés (fitest en anglais) auront une meilleure longévité ainsi qu’une meilleure progéniture. Mendel explique, plus tard, les lois sur le principes du
Croisement et de la mutation génétiques [1].

J.H. Holland, professeur à l’université du Michigan, entreprit  avec ses étudiants, en 1975, une vaste étude qui permit de poser les fondements des AG en calquant les principes de Darwin (sélection, croisement, mutation ,chromosome, gènes). Il parvint alors, à mettre au point les étapes de l’algorithme et ses principes de codage [2]. Il
Esquissa aussi les grandes perspectives d’application des algorithmes génétiques (AG). Ces travaux ont suscité un intérêt sans cesse croissant pour les mathématiciens
dont Koza qui validé rigoureusement leurs mécanismes [3].
 

3 - Fonctionnement général

31 - Analogie avec le fonctionnement biologie

Un algorithme génétique recherche les extrêmas d’une fonction définie sur un espace de données appelé population initiale. Par analogie avec la génétique, chaque individu de cette population est un chromosome et chaque caractéristique de l’individu est un gène[4].

Dans un cas simple, un gène sera représenté par un bit (0 ou 1), un chromosome par une chaîne de bits et un individu par un ensemble de chaîne de bits.

Pour commencer, l’AG  génère aléatoirement une population initiale (comme solutions Possibles). Il opère, ensuite à un croisement des meilleurs chromosomes (les meilleurs sont choisis par une fonction d’évaluation propre au problème à résoudre) . Ce croisement (hybridation) ou crossover, en anglais, consiste en l’échange d’un certain nombre de bits (gènes) entre les deux parents. Les meilleurs enfants obtenus seront croisés, à leur tour, pour obtenir encore une meilleure génération .

L’algorithme  crée des mutation (change la valeur de quelques bits aléatoirement) pour bien imiter le processus naturel. On répète ces étapes jusqu’à ce qu’à ce qu’un enfant soit estimé proche de la solution recherchée [5]. Ces opérateurs génétiques seront définis rigoureusement plus loin.

32 - Champ d’application [6]

L’AG permet d’obtenir des solutions à un problème n’ayant pas de méthode de résolution décrite précisément, ou dont la solution exacte, si elle est connue, est trop compliquée pour être calculée en un temps raisonnable. Dans ce cadre, on peut citer quelques problèmes complexes bien connus :
- Constitution des équipes de travail
- Voyageur de commerce
- Implémentation optimale de points de ventes
- Problème du sac à dos
- Mise au point d’un emploi du temps
- Gestion de portefeuille (placements)
- Optimisation dans les réseaux
- …………………

33 - Avantage des AG [6]

Contrairement à la recherche opérationnelle, l’AG n’exige aucune connaissance de la manière dont résoudre le problème . Il est seulement nécessaire de pouvoir évaluer la qualité de la solution. Également, dans le cas de recherche d’optimum de fonctions analytiques, on n’a besoin ni de dérivabilité ni de continuité.

La mise en œuvre d’un AG est aisée : le ‘’moteur’’ est commun; il y a donc peu de programmation spécifique au problème. Aussi, plus le problème est complexe, plus l’AG montre sa supériorité. Nous comparons, dans le tableau1, l’efficacité de l’approche classique et de l’approche génétique.

34 - Les opérateurs génétiques

L’algorithme génétique réalise l’optimisation par la manipulation d’une population de chromosomes. À chaque génération, l’AG  crée un ensemble de nouveaux chromosomes au de diverses opérations appelées opérateurs génétiques [7] :

• La sélection qui consiste à élire des individus pour la reproduction. Les meilleurs peuvent être choisis plusieurs fois pour la prochaine génération, alors que les moins aptes auront moins de chance de l’être.
• L’hybridation ou croisement (crossover) qui consiste à générer de nouveaux chromosomes par l’échange d’une partie de la chaîne entre des paires de chromosomes existant.

Exemple : 
• La mutation qui consiste à changer la parité d’un chromosome pris au hasard.

Exemple : 

4 - Éléments méthodologiques d’application des AG [8]

Pour appliquer adéquatement l’AG, il est nécessaire d’identifier clairement les différentes étapes préalables à la programmation.

41 - Procédé

Pour utiliser l’AG , on doit disposer de six éléments :

• Un principe de codage de l’élément de population. Cette étape associe à chacun des points de l’espace considéré une structure de données. Elle se place après la phase  de modélisation mathématique du problème traité. Les codages binaires ont été les premiers à être utilisés. Actuellement, on se sert de plus en plus de codages réels notamment pour l’optimisation des problèmes à variables réelles.
• Un mécanisme capable de générer une population initiale non homogène qui servira de base pour les générations futures. Ce choix conditionne la rapidité de la convergence vers l’optimum. Dans le cas où l’on ne connaît rien du problème à résoudre, il est essentiel que la population initiale soit répartie sur tout le domaine de recherche.
• Une fonction à optimiser. Celle-ci retourne un réel positif appelé fonction d’évaluation (fitness).
• Un mécanisme de sélection des individus candidats à l’évolution. On utilise généralement la ‘’roulette’’ du casino pour sélectionner les individus au hasard. Chaque individu occupe sur la roulette un secteur proportionnel à sa fonction d’évaluation : cela fait que le hasard est biaisé envers les éléments les plus justes (aptes) qui ont plus de chances d’être sélectionnés que les autres.
• Des opérateurs permettant de diversifier la population au cours des générations et d’explorer l’espace d’état. L’opérateur de croisement recompose les gènes d’individus existant. L’opérateur de mutation a pour but de garantir l’exploration de l’espace.
• Des paramètres de dimensionnement : taille de la population, critère d’arrêt, probabilité d’application des opérateurs génétiques.

• Taille de la population : entre 30 et 50 individus
• Taux de croisement : entre 70% et 95%
• Taux de mutation : 0,5% à1%.

43 - Codage [10]

Dans ce qui suit x **y signifiera x à la puissance y ; Pc probabilité de croisement et Pm probabilité de mutation.
Pour chercher le maximum d’une fonction f(x), dans l’intervalle [a , b] , avec une précision de n chiffres significatifs, on procédera de la façon suivante :

L’intervalle [a , b] sera subdivisé en (b - a)(10**n) petits intervalles qui représenteront chacun un chromosome.

Chaque chromosome sera codé à l’aide de  k bits, avec k vérifiant les inéquations suivantes :
avec  a = 0000….00   et b = 1111….11.

Le code de chaque chromosome correspond à sa valeur binaire x’.

Le nombre réel correspondant au chromosome est déterminé par : x = a + x’(2/( (2**k)) – 1)

Un exemple numérique simple est donné à la fin du chapitre.

44 - Calculs effectué pour chaque génération :

• Calculer la fonction d’évaluation eveal(vj) pour chaque chromosome vj.
• Calculer l’évaluation totale, F, de la population (somme des évaluations de chaque chromosome).
• Calculer la probabilité de sélection pj pour chaque chromosome vj : pj = eval(vj)/F.
• Calculer la probabilité cumulative qj pour chaque vj (qj = p1+p2+….+pj).
• Pour sélectionner, on fait tourner la roulette taille_population fois de la façon suivante : À chaque fois, on génère, au hasard, un nombre  r dans [0 , 1]  ,  Si r < q1 , sélectionner v,  Sinon, sélectionner vj , avec 2 =< j =<taille_population tel que q(j-1) < r <qj.
• Pour chaque chromosome de la nouvelle population, on génère , au hasard, r dans [0,1], Si  r < Pc, sélectionner le chromosome pour le croisement,
• Croiser les chromosomes ainsi obtenus deux à deux. Si le nombre de chromosomes obtenu est impaire, on peut décider d’élaguer un ou de prendre un autre.
• Générer, au hasard, r dans [0,1]  (autant de fois qu’il y a de bits dans toute la population). Si r =< Pm, muter le bit.

5 - Exemples simples

Les exemples suivants sont choisis très simples pour faciliter la compréhension de l’implémentation de l’approche génétique.

51-Maximum d’une fonction réelle d’une variable réelle

Cherchons le maximum de f(x) = -(x**2) + 4x dans l’intervalle [¨1 , 3] avec une précision de 1/10.
Analytiquement, on voit rapidement que f’(x) = -2x + 4 , que f’’(x) = -2 < 0 et que le maximum correspond à x = 2 et f(x) = 4.
Cherchons la longueur du chromosome (nombre de bits de la chaîne).
La longueur de l’intervalle est 3 – 1 = 2.

Chaque unité doit être subdivisée en 10 (précision souhaitée).
Donc, l’intervalle est subdivisé en 2 * 10 = 20 petits intervalles.
Le nombre de bits requis pour représenter tous les réels  considérés dans l’intervalle est k tel que 2**(k – 1) =< 20 =< 2**k.  k = 5.

Pour modéliser le problème, convenons de ce qui suit :
Une population de 4 individus (chromosomes), chaque individu codé sur 5 bits (gènes).
Pc = 0,75  et Pm = 0,01.

Construisons aléatoirement la génération initiale

La somme des évaluations est 12,7 ; la plus grande évaluation 3,3  et la valeur moyenne 3,2.
Formons la première génération.

Sélection :
En calculant les probabilités de sélection, on obtient :
P1 = 0,2444       Q1 = 0,244
P2 = 0,2333       Q2 = 0,437
P3 = 0,259         Q3 = 0,736
P4 = 0,262         Q4 = 1

On fait tourner 4 fois la roulette pour générer des nombres  r dans [0 , 1], on obtient :
0,512 0,710 0,216 0,773

r = 0,51        Q2 < 0,512 < Q3      V3 est sélectionné
r = 0,70        Q2 < 0,710 < Q3      V3  …………….
r = 0,282       0,216 < Q1              V1 …………….
R = 0,733     Q3 < 0,773 <Q4       V4 ……………..

La première génération devient :
V1’ 11011
V2’ 11011
V3’ 01100
V4’ 10100

Croisement :
Assumons qu’aléatoirement, on procède au croisement à partir de la deuxième position
On fait tourner la roulette pour générer des nombres  r dans [0 , 1].
Si r < 0,75 , le chromosome est sélectionné pour le croisement.
On obtient : 0,82    0,52    0,17    0,35
Alors  V2, V3, V4  sont sélectionnés. Comme le nombre est impaire, on laisse tomber le
dernier . Cela donne pour le croisement :

Après croisement on obtient :

 V1’’     11011
 V 2’’    11100
 V3’’     01011
 V4’’     10100

Mutation :
Il y a 4x5 = 20 bits  .
On tourne la roulette 20 fois pour générer r dans [0, 1]
Si r < 0,01, on mute le bit de ce rang.
Seulement, au 18ième tour, on obtient r = 0.008, on mute, alors le 18ième bit qui correspond au 3ième bit du 4ième vecteur.
Finalement, la première génération devient :
V1     11011
V2     11100
V3     01011
V4     01000
 
En évaluant la première génération , on obtient :
x1 = 2,6     eval(V1) = 3,6
x2 = 2,5     eval(V2) = 3,7
x3 = 1,7     eval(V3) = 3,8
x4 = !,5      evalV4) = 3,7

évaluation totale = 14,8 plus grande valeur = 3,8 valeur moyenne = 3.7

On vient de terminer une itération de la boucle ‘’Tant que’’.
 

Formons la deuxième génération :
En prenant maintenant comme population initiale  la première génération et en refaisant la boucle ‘’tant que’’ (on applique les opérateurs de sélection, de croisement et de mutation) on obtient la deuxième génération :
V1 01100      x1 = 1,7     eval(V1) = 3,9
V2 11011      x2 = 2,6     eval(V2) = 3,6
V3 01100      x3 = 1,7     eval(V3) = 3,9
V4 01011      x4 = 1,6     eval(V4) = 3,8
Somme des évaluations = 15,2
La plus grande valeur = 3,9 (revient 2 fois)
La moyenne = 3,8

En formant la troisième génération, à partir de la deuxième, on obtient :
Somme des évaluations = 15,5
La plus grande valeur = 3,9 (revient trois fois)
La  moyenne = 3,8
On remarque une certaine stagnation autour de x = 1,7 et x = 2,3 qui donnent tous les deux f(x) = 3,9.

Remarque :
Si on avait opté pour une précision de 1/1000, l’évolution aurait été plus rapide et le maximum encore plus proche de 4 (par exemple 3,986).
Dans ce cas, on aurait on aurait codé chaque nombre de l’intervalle [1 , 3] sur 11 bits car l’intervalle serait subdivisé en 2000 nombres réels (voir le début de la section pour ces calculs).

52 - Maximum d’une fonction réelle à deux variables réelles

Cherchons  Max f(x ,y) = x2 + y2 dans [-2 , +2]x[-2 , +2].
Soit une précision de 1/1000 pour x et y.
La longueur de l’intervalle est de 4.
L’intervalle sera subdivisé en 4000 nombres réels représentés sur 12 bits chacun (voir début de la section 51)
Au lieu de représenter  séparément  x et y, on peut les concaténer sur un seul vecteur de 24 bits où la partie codera x et la deuxième y.
On construit, alors une population initiale  de 30 chromosomes par exemple.

V1      110001100001111100101010
 .
 .
 .
V30     010100110001110101110111

On suivra exactement les mêmes étapes de sélection, croisement, mutation, évaluation que pour une fonction d’une seule variable.

6 - Conclusion

Cet exposé constitue une bonne introduction aux algorithmes génétiques et fournit les éléments nécessaires à leur programmation. Les exemples sont choisis très simples pour permettre à un débutant d’y mettre pied. Évidemment dans le cas des fonctions mathématiques usuelles, les méthodes analytiques sont, de loin, plus élégantes et plus précises. Mais, aussitôt que l’on s’approche d’une fonction H( ) complexe dont on ne connaît rien sur sa dérivée ou dont l’équation H’( ) = 0 est difficile à résoudre,  l’approche génétique deviendra incontournable.

Également, nous avons fait état d’une panoplie d’application dans différentes industries sans traiter d’exemples . Cela fera l’objet de notre prochain rapport.
Nous comptons présenter quelques exemples connus qui ont donné du fil à retordre à la recherche opérationnelle.
 

Bibliographie

[1] D.A.Goldbert. Genetic algorithms in search, optimisation and machine learning. Addison-Wesley, janvier 1999.

[2] J.H. Holland. Adaptation in natural and artificial system. Ann Arbor, university of Michigan Press, 1975.

[3] J.R. Koza. Genetic programming. MIT Press, 1992.

[4] Fractales Groupe- INRIA. What is genetic algorithm.2000. www.syntim.inria.fr

[5] Sophie Conte Que sont les algorithmes génétiques. Revue Cybersciences 2000.  www.cybersciences.com

[6] PMSI. Optimisation par algorithme génétique. 2000. www.geoticies.com

[7] René Leféburne et Christophe Lebret. Utilisation de  l’algorithme génétique dans la  détermination d’unréseau optimal de points de ventes. Revue Banque Paris 1996. www.geoticies.com

[8] Jean Marc Alliot. Algorithmes génétiques et applications. ENAC 2000. www.recherche.enac.fr

[9] Sylvain Barthélémy. Principe général des algorithmes génétiques. 2000.  www.barth.netliberte.org

[10] Zbignew Michalewicz. Gennetic algorithm + Data sturctures = evolution programs PP31-42 Springer-Verlag 1992.