Algorithmes génétiques - Introduction

L'algorithme génétique (GA) est une technique d'optimisation basée sur la recherche basée sur les principes de Genetics and Natural Selection. Il est fréquemment utilisé pour trouver des solutions optimales ou quasi optimales à des problèmes difficiles qui, autrement, prendraient une vie entière à résoudre. Il est fréquemment utilisé pour résoudre des problèmes d'optimisation, dans la recherche et dans l'apprentissage automatique.

Introduction à l'optimisation

L'optimisation est le processus de making something better. Dans tout processus, nous avons un ensemble d'entrées et un ensemble de sorties comme indiqué dans la figure suivante.

L'optimisation fait référence à la recherche des valeurs des entrées de manière à obtenir les «meilleures» valeurs de sortie. La définition du «meilleur» varie d'un problème à l'autre, mais en termes mathématiques, elle se réfère à la maximisation ou à la minimisation d'une ou plusieurs fonctions objectives, en faisant varier les paramètres d'entrée.

L'ensemble de toutes les solutions ou valeurs possibles que les entrées peuvent prendre constitue l'espace de recherche. Dans cet espace de recherche, se trouve un point ou un ensemble de points qui donne la solution optimale. Le but de l'optimisation est de trouver ce point ou cet ensemble de points dans l'espace de recherche.

Que sont les algorithmes génétiques?

La nature a toujours été une grande source d'inspiration pour toute l'humanité. Les algorithmes génétiques (AG) sont des algorithmes basés sur la recherche basés sur les concepts de sélection naturelle et de génétique. Les GA sont un sous-ensemble d'une branche beaucoup plus vaste du calcul connue sous le nom deEvolutionary Computation.

Les GA ont été développés par John Holland et ses étudiants et collègues de l'Université du Michigan, notamment David E. Goldberg, et ont depuis été essayés sur divers problèmes d'optimisation avec un haut degré de succès.

Dans les GA, nous avons un pool or a population of possible solutionsau problème donné. Ces solutions subissent ensuite une recombinaison et une mutation (comme dans la génétique naturelle), produisant de nouveaux enfants, et le processus se répète sur différentes générations. Chaque individu (ou solution candidate) se voit attribuer une valeur de fitness (basée sur sa valeur de fonction objective) et les individus en meilleure forme ont une plus grande chance de s'accoupler et de produire des individus plus «en forme». Ceci est conforme à la théorie darwinienne de la «survie du plus apte».

De cette façon, nous continuons à «faire évoluer» de meilleurs individus ou solutions au fil des générations, jusqu'à ce que nous atteignions un critère d'arrêt.

Les algorithmes génétiques sont de nature suffisamment aléatoire, mais ils fonctionnent bien mieux que la recherche locale aléatoire (dans laquelle nous essayons simplement diverses solutions aléatoires, en gardant une trace des meilleures à ce jour), car ils exploitent également les informations historiques.

Avantages des AG

Les AG présentent divers avantages qui les ont rendus extrêmement populaires. Ceux-ci comprennent -

  • Ne nécessite aucune information dérivée (qui peut ne pas être disponible pour de nombreux problèmes du monde réel).

  • Est plus rapide et plus efficace par rapport aux méthodes traditionnelles.

  • Possède de très bonnes capacités parallèles.

  • Optimise les fonctions continues et discrètes ainsi que les problèmes multi-objectifs.

  • Fournit une liste de «bonnes» solutions et pas seulement une solution unique.

  • Obtient toujours une réponse au problème, qui s'améliore avec le temps.

  • Utile lorsque l'espace de recherche est très grand et qu'un grand nombre de paramètres sont impliqués.

Limitations des GA

Comme toute technique, les GA souffrent également de quelques limitations. Ceux-ci comprennent -

  • Les GA ne conviennent pas à tous les problèmes, en particulier aux problèmes simples et pour lesquels des informations dérivées sont disponibles.

  • La valeur de la forme physique est calculée à plusieurs reprises, ce qui peut être coûteux en calcul pour certains problèmes.

  • Étant stochastique, il n'y a aucune garantie sur l'optimalité ou la qualité de la solution.

  • S'il n'est pas mis en œuvre correctement, l'AG peut ne pas converger vers la solution optimale.

GA - Motivation

Les algorithmes génétiques ont la capacité de fournir une solution «assez bonne» «assez rapide». Cela rend les algorithmes génétiques intéressants à utiliser pour résoudre des problèmes d'optimisation. Les raisons pour lesquelles les AG sont nécessaires sont les suivantes:

Résolution de problèmes difficiles

En informatique, il existe un grand nombre de problèmes, qui sont NP-Hard. Cela signifie essentiellement que même les systèmes informatiques les plus puissants prennent beaucoup de temps (voire des années!) Pour résoudre ce problème. Dans un tel scénario, les AG se révèlent être un outil efficace pour fournirusable near-optimal solutions dans un court laps de temps.

Échec des méthodes basées sur le gradient

Les méthodes traditionnelles basées sur le calcul fonctionnent en commençant à un point aléatoire et en se déplaçant dans la direction du gradient, jusqu'à ce que nous atteignions le sommet de la colline. Cette technique est efficace et fonctionne très bien pour les fonctions d'objectif à pic unique comme la fonction de coût dans la régression linéaire. Mais, dans la plupart des situations du monde réel, nous avons un problème très complexe appelé paysages, qui sont constitués de nombreux sommets et de nombreuses vallées, ce qui entraîne l'échec de ces méthodes, car elles souffrent d'une tendance inhérente à se coincer dans les optima locaux. comme indiqué dans la figure suivante.

Obtenir rapidement une bonne solution

Certains problèmes difficiles comme le problème du voyageur de commerce (TSP), ont des applications dans le monde réel comme la recherche de chemin et la conception VLSI. Imaginez maintenant que vous utilisez votre système de navigation GPS, et qu'il faut quelques minutes (voire quelques heures) pour calculer le chemin «optimal» de la source à la destination. Le retard dans de telles applications du monde réel n'est pas acceptable et donc une solution «assez bonne», qui est livrée «rapidement» est ce qui est nécessaire.