A la découverte des algorithmes génétiques – Wikipedia – Origines
Les algorithmes genetiques
Wikipedia
“Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle et l'appliquent à une population de solutions potentielles au problème donné. La solution est approchée par « bonds » successifs.”Origines
- 1860 : Charles Darwin publie son livre intitulé "L'origine des espèces au moyen de la sélection naturelle ou la lutte pour l'existence dans la nature" et expose sa théorie de l'évolution des espèces.
- 1960 : John Holland ainsi que ses collègues et élèves de l'Université du Michigan débutent des travaux de recherche sur les algorithmes génétiques.
- 1966 : Le Docteur Lawrence J. Fogel présente sa thèse sur la programmation évolutionnaire.
- 1973 : Ingo Rechenberg travaille sur des méthodes d'optimisation connu sous le nom de "Stratégie d'évolution".
- 1975 : John Holland introduit le premier modèle formel des algorithmes génétiques avec la prise en compte de l'opérateur d'enjambement en complément des mutations. Ce modèle servira de base aux recherches ultèrieures.
Principe
Générer une population de n individus initiaux. La population d'individus doit être non homogène et servira de base pour les générations futures. Par analogie avec la génétique, chaque individu est codé par un chromosome (comportant donc plusieurs gènes).
On évalue les différentes solutions proposées, afin de les "classer" en fonction de leur pertinence. Pour cela, on utilise une fonction d’évaluation qui permettra ensuite de faire la sélection.
La population sélectionnée est divisée en couples, formés aléatoirement. L’algorithme sélectionne un ou plusieurs gène(s) sur chacun des deux individus.
On applique ensuite un algorithme qui aura pour role de modifier un gêne au hasard.
On effectue ces opérations un maximum de fois de façon à augmenter la justesse du résultat.
Le codage ou modelisation
codage binaire codage à caractères multiples codage sous forme d'arbreLa population initiale
La taille de la population initiales est laissée à l'appéciation du programmeur. Il n'est souvent pas nécessaire d'utiliser des populations démesurées. Une taille de 100 ou 150 individus s'avèrera souvent amplement suffisante, tant pour la qualité des solutions trouvées que pour le temps d'exécution de notre algorithme.
La fonction d'évaluation ou fonction fitness
La fonction d'évalation sera utilisée pour calculer le score d'un individu (point dans l'espace de recherche). L'évaluation d'un individu ne dépendant pas de celle des autres individus, le résultat fournit par la fonction d'évaluation va permettre de sélectionner ou de refuser un individu.
La selection
la selection par roulette la selection par rang la selection steady-state la selection par tournoi l'élitismeLa selection par roulette
La selection par rang
Chromosomes 1 2 3 4 5 6 Total Evaluation 89 5 1 4 3 2 100 Rang 6 5 1 4 3 2 21 Probabilité 29% 24% 5% 19% 14% 9% 100%
La selection steady-state
A chaque génération sont sélectionnés quelques chromosomes parmi ceux qui ont le meilleur résultat pour créer des chromosomes fils. Ensuite les chromosomes les plus mauvais sont retirés et remplacés par les nouveaux. Le reste de la population survie à la nouvelle génération.
La sélection par tournoi
Un tournoi consiste en une rencontre entre plusieurs individus pris au hasard dans la population. Le vainqueur du tournoi est l'individu de meilleure qualité. Il est possible de ne conserver que le vainqueur comme de conserver les 2 meilleurs individus ou les 3 meilleurs. Cela dépend du choix développeur, selon qu'il souhaite créer beaucoup de tournois, ou bien créer des tournois avec beaucoup de participants.
Il est possible faire participer un même individu à plusieurs tournois.
Le principe de la sélection par tournoi augmente les chances pour les individus de piètre qualité de participer à l'amélioration de la population.
L'élitisme
Elle consiste à copier un ou plusieurs des meilleurs chromosomes dans la nouvelle génération. Ensuite, on génère le reste de la population selon l'algorithme de reproduction usuel. Cette méthode améliore considérablement les algorithmes génétiques, car elle permet de ne pas perdre les meilleurs solutions.
Le croisement ou hybridation ou enjambement ou crossover
A partir de deux individus, on obtient deux nouveaux individus (enfants) qui héritent de certaines caractéristiques de leurs parents. L'hybridation sélectionnne des gènes parmis deux individus appelés parents. A partir de ces gènes sont générés les enfants.
L'hybridation est mis en place pour que les nouveaux chromosomes gardent une partie des chromosomes anciens. Ceci dans le but d'obtenir, peut-être, de meilleurs chromosomes.
Il n'est pas nécessaire et surtout pas recommandé de croiser tous les individus d'une population, car rien ne nous dit si le résultat d'un croisement sera meilleur ou moins bon que les individus parents.
La mutation
Au sein d’un chromosome, un gène est substitué à un autre de manière aléatoire. Ceci permet d’éviter à l’algorithme de s'enliser dans un optimum local.
Cependant, le taux de mutation ne doit pas être trop important, afin de ne pas tomber dans une recherche aléatoire. Un taux aux alentours de 1% est généralement utillisé.
Insertion des nouveaux individus dans la population
Une fois que les nouveaux individus sont créés que ce soit par croisements ou par mutations, il faut sélectionner ceux qui vont continuer à participer à l'amélioration de la population. Ce choix est totalement libre.
Il est possible de refaire une étape d'évaluation des individus nouvellement créés afin de ne conserver que les N meilleurs individus.
Itérations
Il ne reste plus qu'à éffectuer ces opérations un maximum de fois de façon à augmenter la justesse du résultat. On peut choisir d’arrêter l’algorithme lorsqu’un individu obtient un score jugé suffisamment satisfaisant, ou après un certain nombre de générations.Conditions d'utilisation
Les algorithmes génétiques peuvent être une bonne solution pour résoudre un problème. Néanmoins, leur utilisation doit être conditionnée par certaines caractéristiques du problème :
- Le temps de calcul de la fonction d'évalutation doit être relativement court.
- L'espace de recherches doit être important. En effet, pour un espace dont la taille est faible, il peut être plus sûr de parcourir cet espace de manière exhaustive afin d'obtenir la solution optimale.
- Il n'existe pas d'algorithmes déterministes adaptés et raisonnables.
- Lorsque l'on préfère avoir une solution relativement bonne rapidement plutôt qu'avoir la solution optimale en une durée indéfinie (programmation de machines qui doivent être très réactives aux conditions environnantes).
Applications
- Les algorithmes génétiques ont été mis à contribution en économie et en finance.
- Certaines industries utilisent les algorithmes génétiques pour la programmation des robots d'assemblage, dans l'industrie automobile par exemple, ou dans le domaine de l'aérodynamique dans un souci d'optimisation structurelle.
- Mise en place de logiciels d’optimisation comme Evolver pour Microsoft Excel.
- La NASA a adopté ces algorithmes dans le cadre de l’exploration de Mars pour les déplacements du robot Pathfinder.
Limites
- La difficulté de la mise en place de la fonction d'évaluation ainsi que certains paramètres comme le taux de mutation ou la taille de la population.
- L'impossibilité d'être assuré, même après un nombre important de générations, que la solution trouvée soit la meilleure. On peut seulement être sûr que l'on s'est approché de la solution optimale, sans la certitude de l'avoir atteinte.
"La vie trouve toujours son chemin."
Dr Ian Malcolm , Jurassic Park- http://pro.cleamax.fr/info-bioinspiree/?p=gene
- http://khayyam.developpez.com/articles/algo/genetic/
- http://sis.univ-tln.fr/~tollari/TER/AlgoGen1/node5.html
- http://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n%C3%A9tique
Genetic car
http://boxcar2d.com/about.htmlDéfinition d'une voiture
un chassi défini par
- [float] une densité comprise entre 30 et 300
- [float,float] 8 vecteurs (paires de coordonnées) ou chaque valeur absolue non nulle d'une coordonnée est comprise entre 0.1 et 1.1
(X,0) (X,Y) (0,Y) (-X,Y) (-X,0) (-X,-Y) (0,-Y) (X, -Y)
2 roues définies par
- [float] un rayon compris entre 0.2 et 0.5
- [float] une densité comprise entre 40 et 100
- [int] un sommet compris entre 0 et 7