Réseau de neurones artificiels - Algorithme génétique

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.

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

Dans les AG, nous avons un pool ou une population de solutions possibles au 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 plus de chances 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, GA 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 Gas attrayant pour une utilisation dans la résolution de 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. Cependant, dans la plupart des situations du monde réel, nous avons un problème très complexe appelé paysages, composé de nombreux pics et de nombreuses vallées, ce qui entraîne l'échec de ces méthodes, car elles souffrent d'une tendance inhérente à rester bloquées aux 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. Les retards dans de telles applications du monde réel ne sont pas acceptables et donc une solution «assez bonne», qui est livrée «rapidement» est ce qui est nécessaire.

Comment utiliser GA pour les problèmes d'optimisation?

Nous savons déjà que l'optimisation consiste à rendre quelque chose comme la conception, la situation, la ressource et le système aussi efficace que possible. Le processus d'optimisation est illustré dans le diagramme suivant.

Étapes du mécanisme GA pour le processus d'optimisation

Les étapes suivantes sont les étapes du mécanisme GA lorsqu'il est utilisé pour l'optimisation des problèmes.

  • Générez la population initiale de manière aléatoire.

  • Sélectionnez la solution initiale avec les meilleures valeurs de fitness.

  • Recombinez les solutions sélectionnées à l'aide d'opérateurs de mutation et de croisement.

  • Insérez la progéniture dans la population.

  • Maintenant, si la condition d'arrêt est remplie, renvoyez la solution avec sa meilleure valeur de fitness. Sinon, passez à l'étape 2.