Algorithme génétique

Qu'est-ce que c'est ?

L'évolution naturelle peut être modélisée comme un jeu, dans lequel les récompenses pour un organisme qui joue un bon jeu de la vie sont la transmission de son matériel génétique à ses successeurs et sa survie continue. Dans l'évolution naturelle, les performances d'un individu dépendent de ses partenaires et de ses concurrents, ainsi que de l'environnement. Les algorithmes génétiques sont une simulation de la sélection naturelle sur une population de solutions candidates à un problème d'optimisation (chromosomes, individus, créatures ou phénotypes).

Les candidats sont évalués et croisés pour tenter de trouver de bonnes solutions. Ces solutions peuvent prendre beaucoup de temps et ne sont pas évidentes pour un être humain. Une phase d'évolution est lancée avec une population d'êtres générés au hasard. À chaque génération, l'aptitude de chaque individu de la population est évaluée. Certains sont choisis au hasard dans la population actuelle (en fonction de leur aptitude) et modifiés (recombinés et éventuellement mutés au hasard) pour former une nouvelle population. Le cycle se répète avec cette nouvelle population. L'algorithme se termine soit après qu'un certain nombre de générations se soient écoulées, soit après qu'un bon niveau d'aptitude ait été atteint pour la population. Si l'algorithme s'est terminé parce qu'un nombre maximum de générations a été atteint, cela ne signifie pas nécessairement qu'un bon niveau d'aptitude a été obtenu.

Programmation sur ordinateur

Le pseudo-code est :

1. Initialisation : Certaines solutions possibles sont créées ; très souvent, elles auront des valeurs aléatoires
2. Évaluation : Une fonction d'évaluation de la condition physique note chaque solution ; le score sera un nombre qui indique dans quelle mesure cette solution résout le problème.
3. Les étapes suivantes sont exécutées jusqu'à ce que l'exigence d'arrêt soit satisfaite :
1. Sélection : Choisissez les solutions/individus pour la prochaine itération
2. Recombinaison : Combiner les solutions retenues
3. Mutation : Changer au hasard les solutions nouvellement créées
4. Évaluation : Appliquer la fonction de mise en forme, voir étape 2.
5. Si la condition d'arrêt n'est pas remplie, recommencez l'étape de sélection.

Exemple

La description ci-dessus est abstraite. Un exemple concret aide.

Demandes

En général

Les algorithmes génétiques permettent de résoudre des problèmes de planification et d'ordonnancement. Ils ont également été appliqués à l'ingénierie. Ils sont souvent utilisés pour résoudre des problèmes d'optimisation globale.

En règle générale, les algorithmes génétiques peuvent être utiles dans les domaines qui posent des problèmes de condition physique complexes, car le mélange est conçu pour éloigner la population de l'optima local dans lequel un algorithme traditionnel d'ascension de colline pourrait se trouver bloqué. Les opérateurs de croisement couramment utilisés ne peuvent pas changer une population uniforme. La mutation seule peut assurer l'ergodicité du processus global de l'algorithme génétique (vu comme une chaîne de Markov).

Exemples de problèmes résolus par des algorithmes génétiques : miroirs conçus pour canaliser la lumière du soleil vers un collecteur solaire, antennes conçues pour capter des signaux radio dans l'espace, méthodes de marche pour les figures informatiques, conception optimale de corps aérodynamiques dans des champs d'écoulement complexes

Dans son manuel de conception d'algorithmes, Skiena déconseille les algorithmes génétiques pour toute tâche : "Il est assez peu naturel de modéliser les applications en termes d'opérateurs génétiques comme la mutation et le croisement sur des chaînes de bits. La pseudobiologie ajoute un autre niveau de complexité entre vous et votre problème. Deuxièmement, les algorithmes génétiques prennent beaucoup de temps sur des problèmes non triviaux. L'analogie avec l'évolution - où des progrès significatifs nécessitent des millions d'années - peut être tout à fait appropriée. [...] Je n'ai jamais rencontré de problème où les algorithmes génétiques me semblaient être la bonne façon de l'attaquer. De plus, je n'ai jamais vu de résultats de calcul utilisant des algorithmes génétiques qui m'ont favorablement impressionné. Tenez-vous en au recuit simulé pour vos besoins de recherche heuristique vaudou".

Jeux de société

Les jeux de société constituent une partie très importante du domaine des algorithmes génétiques appliqués aux problèmes de la théorie des jeux. Une grande partie des premiers travaux sur l'intelligence artificielle et les jeux était orientée vers les jeux de société classiques, tels que le tic-tac-toe^[3], les échecs et les dames. Les jeux de société peuvent maintenant, dans la plupart des cas, être joués par un ordinateur à un niveau supérieur à celui des meilleurs humains, même avec des techniques de recherche exhaustive aveugle. Le go est une exception notable à cette tendance, et a jusqu'à présent résisté aux attaques des machines. Les meilleurs joueurs de Go sur ordinateur jouent maintenant au niveau d'un bon novice. On dit que la stratégie du Go repose largement sur la reconnaissance des formes, et pas seulement sur l'analyse logique comme aux échecs et autres jeux plus indépendants des pièces^. L'énorme facteur de ramification efficace requis pour trouver des solutions de haute qualité restreint fortement le regard qui peut être utilisé dans une recherche de séquence de coups.

Jeux d'ordinateur

L'algorithme génétique peut être utilisé dans les jeux informatiques pour créer une intelligence artificielle (l'ordinateur joue contre vous). Cela permet une expérience de jeu plus réaliste ; si un joueur humain peut trouver une séquence d'étapes qui mène toujours au succès, même lorsqu'elles sont répétées dans différents jeux, il ne peut plus y avoir de défi. À l'inverse, si une technique d'apprentissage telle qu'un algorithme génétique pour un stratège peut éviter de répéter les erreurs passées, le jeu sera plus facile à jouer.

Les algorithmes génétiques nécessitent les parties suivantes :

• Une méthode pour représenter le défi en termes de solution (par exemple, mettre en déroute des soldats lors d'une attaque dans un jeu de stratégie)
• Une fonction d'aptitude ou d'évaluation afin de déterminer la qualité d'une instance (par exemple, une mesure des dommages causés à un adversaire lors d'une telle attaque).

La fonction de fitness accepte une instanciation mutée d'une entité et mesure sa qualité. Cette fonction est personnalisée en fonction du domaine du problème. Dans de nombreux cas, en particulier ceux impliquant une optimisation du code, la fonction d'adaptation peut être simplement une fonction de synchronisation du système. Une fois qu'une représentation génétique et une fonction d'adaptation sont définies, un algorithme génétique instancie les candidats initiaux comme décrit précédemment, puis s'améliore par l'application répétitive d'opérateurs de mutation, de croisement, d'inversion et de sélection (comme défini selon le domaine du problème).

Limitations

L'utilisation d'un algorithme génétique présente des limites par rapport aux autres algorithmes d'optimisation :

• L'évaluation répétée de la fonction de fitness pour des problèmes complexes est souvent le segment le plus limitant des algorithmes évolutifs artificiels. Trouver la solution optimale à des problèmes complexes nécessite souvent des évaluations de la fonction d'aptitude très coûteuses. Dans les problèmes du monde réel tels que les problèmes d'optimisation structurelle, une seule évaluation de fonction peut nécessiter plusieurs heures à plusieurs jours de simulation complète. Les méthodes d'optimisation classiques ne peuvent pas traiter de tels types de problèmes. Il est souvent nécessaire d'utiliser une approximation, car le calcul de la solution exacte prend trop de temps. Les algorithmes génétiques combinent parfois différents modèles d'approximation pour résoudre des problèmes complexes de la vie réelle.
• Les algorithmes génétiques ne s'adaptent pas bien à l'échelle. En d'autres termes, lorsque le nombre d'éléments exposés à une mutation est important, il y a souvent une augmentation exponentielle de la taille de l'espace de recherche. Cela rend extrêmement difficile l'utilisation de la technique sur des problèmes tels que la conception d'un moteur, d'une maison ou d'un avion. Pour utiliser des algorithmes génétiques avec de tels problèmes, il faut les décomposer en une représentation la plus simple possible. Pour cette raison, nous voyons des algorithmes évolutifs codant des conceptions de pales de soufflante au lieu de moteurs, des formes de bâtiments au lieu de plans de construction détaillés, et des profils d'ailes au lieu de conceptions d'avions entiers. Le deuxième problème de complexité est la question de savoir comment protéger les pièces qui ont évolué pour représenter de bonnes solutions contre de nouvelles mutations destructrices, en particulier lorsque leur évaluation d'aptitude exige qu'elles se combinent bien avec d'autres pièces.
• La "meilleure" solution n'est qu'en comparaison avec d'autres solutions. Par conséquent, le critère d'arrêt n'est pas clair pour chaque problème.
• Dans de nombreux problèmes, les algorithmes génétiques ont tendance à converger vers des optima locaux ou même des points arbitraires plutôt que vers l'optimum global du problème. Cela signifie que l'algorithme ne "sait pas comment" sacrifier l'aptitude à court terme pour acquérir une aptitude à long terme. La probabilité que cela se produise dépend de la forme de la fonction d'aptitude : certains problèmes facilitent la recherche de l'optimum global, d'autres peuvent permettre à la fonction de trouver plus facilement l'optimum local. Ce problème peut être atténué en utilisant une fonction de fitness différente, en augmentant le taux de mutation, ou en utilisant des techniques de sélection qui maintiennent une population de solutions diversifiées. Une technique courante pour maintenir la diversité consiste à utiliser une "pénalité de niche" : tout groupe d'individus présentant une similarité suffisante (rayon de niche) se voit ajouter une pénalité, qui réduira la représentation de ce groupe dans les générations suivantes, permettant ainsi de maintenir d'autres individus (moins similaires) dans la population. Cette astuce peut toutefois ne pas être efficace, selon le paysage du problème. Une autre technique possible consisterait à remplacer simplement une partie de la population par des individus générés de manière aléatoire, lorsque la majorité de la population est trop semblable aux autres. La diversité est importante dans les algorithmes génétiques (et la programmation génétique) car le croisement d'une population homogène ne donne pas de nouvelles solutions. Dans les stratégies d'évolution et la programmation évolutionniste, la diversité n'est pas essentielle en raison d'une plus grande dépendance à l'égard de la mutation.
• Il est difficile d'opérer sur des ensembles de données dynamiques, car les génomes commencent à converger très tôt vers des solutions qui peuvent ne plus être valables pour des données ultérieures. Plusieurs méthodes ont été proposées pour résoudre ce problème en augmentant d'une manière ou d'une autre la diversité génétique et en empêchant une convergence précoce, soit en augmentant la probabilité de mutation lorsque la qualité de la solution baisse (appelée hypermutation déclenchée), soit en introduisant occasionnellement dans le pool génétique des éléments entièrement nouveaux générés de manière aléatoire (appelés immigrants aléatoires). Là encore, les stratégies d'évolution et la programmation évolutionniste peuvent être mises en œuvre avec une stratégie dite "de la virgule" dans laquelle les parents ne sont pas maintenus et les nouveaux parents sont sélectionnés uniquement parmi la progéniture. Cela peut être plus efficace pour les problèmes dynamiques.
• Les algorithmes génétiques ne peuvent pas résoudre efficacement les problèmes dans lesquels la seule mesure d'aptitude est une seule bonne/neutre mesure (comme les problèmes de décision), car il n'y a aucun moyen de converger vers la solution (pas de colline à gravir). Dans ces cas, une recherche aléatoire peut trouver une solution aussi rapidement qu'une AG. Cependant, si la situation permet de répéter l'essai de succès/échecs en donnant (éventuellement) des résultats différents, alors le rapport entre les succès et les échecs fournit une mesure d'aptitude appropriée.
• Pour des problèmes d'optimisation spécifiques et des cas de problèmes, d'autres algorithmes d'optimisation peuvent être plus efficaces que les algorithmes génétiques en termes de vitesse de convergence. Les algorithmes alternatifs et complémentaires comprennent les stratégies d'évolution, la programmation évolutionnaire, le recuit simulé, l'adaptation gaussienne, l'ascension de collines et l'intelligence des essaims (par exemple : optimisation des colonies de fourmis, optimisation des essaims de particules) et les méthodes basées sur la programmation linéaire en nombres entiers. L'adéquation des algorithmes génétiques dépend de la quantité de connaissances du problème ; les problèmes bien connus ont souvent des approches meilleures et plus spécialisées.

Histoire

En 1950, Alan Turing a proposé une "machine à apprendre" qui serait parallèle aux principes de l'évolution. La simulation informatique de l'évolution a commencé dès 1954 avec les travaux de Nils Aall Barricelli, qui utilisait l'ordinateur à l'Institute for Advanced Study de Princeton, dans le New Jersey. Sa publication de 1954 n'a pas été très remarquée. À partir de 1957, le généticien quantitatif australien Alex Fraser a publié une série d'articles sur la simulation de la sélection artificielle d'organismes à loci multiples contrôlant un trait mesurable. Dès ces débuts, la simulation informatique de l'évolution par les biologistes est devenue plus courante au début des années 1960, et les méthodes ont été décrites dans les livres de Fraser et Burnell (1970) et de Crosby (1973). Les simulations de Fraser comprenaient tous les éléments essentiels des algorithmes génétiques modernes. En outre, Hans-Joachim Bremermann a publié dans les années 1960 une série d'articles qui ont également adopté une population de solutions aux problèmes d'optimisation, en subissant des recombinaisons, des mutations et des sélections. Les recherches de Bremermann ont également porté sur les éléments des algorithmes génétiques modernes. Parmi les autres pionniers remarquables, citons Richard Friedberg, George Friedman et Michael Conrad. De nombreux articles sont réimprimés par Fogel (1998).

Bien que Barricelli, dans un travail qu'il a rapporté en 1963, ait simulé l'évolution de la capacité à jouer à un jeu simple, l'évolution artificielle est devenue une méthode d'optimisation largement reconnue grâce aux travaux d'Ingo Rechenberg et de Hans-Paul Schwefel dans les années 1960 et au début des années 1970 - le groupe de Rechenberg a pu résoudre des problèmes d'ingénierie complexes grâce à des stratégies d'évolution. Une autre approche était la technique de programmation évolutive de Lawrence J. Fogel, qui a été proposée pour générer de l'intelligence artificielle. La programmation évolutionniste utilisait à l'origine des machines à états finis pour prédire les environnements, et utilisait la variation et la sélection pour optimiser les logiques prédictives. Les algorithmes génétiques, en particulier, sont devenus populaires grâce aux travaux de John Holland au début des années 1970, et notamment à son livre Adaptation in Natural and Artificial Systems (1975). Ses travaux ont commencé par des études sur les automates cellulaires, menées par Holland et ses étudiants à l'université du Michigan. Holland a introduit un cadre formalisé pour prédire la qualité de la prochaine génération, connu sous le nom de "Holland's schema theorem". La recherche sur les AG est restée largement théorique jusqu'au milieu des années 1980, lorsque la première conférence internationale sur les algorithmes génétiques s'est tenue à Pittsburgh, en Pennsylvanie.