Quand les algorithmes génétiques sont-ils un bon choix pour l'optimisation?

20

Les algorithmes génétiques sont une forme de méthode d'optimisation. Souvent, la descente de gradient stochastique et ses dérivés sont le meilleur choix pour l'optimisation des fonctions, mais des algorithmes génétiques sont encore parfois utilisés. Par exemple, l'antenne du vaisseau spatial ST5 de la NASA a été créée avec un algorithme génétique:

Antenne ST5

Quand les méthodes d'optimisation génétique sont-elles un meilleur choix que les méthodes de descente de gradient plus courantes?

Gus
la source
7
+1 pour l'exemple, j'ai trouvé l'article original: alglobus.net/NASAwork/papers/Space2006Antenna.pdf
Tim

Réponses:

19

Les algorithmes génétiques (GA) sont une famille d'heuristiques qui sont empiriquement bonnes pour fournir une réponse décente dans de nombreux cas, bien qu'elles soient rarement la meilleure option pour un domaine donné.

Vous mentionnez des algorithmes basés sur les dérivés, mais même en l'absence de dérivés, il existe de nombreux algorithmes d'optimisation sans dérivés qui fonctionnent bien mieux que les GA. Voir ceci et cette réponse pour quelques idées.

Ce que de nombreux algorithmes d'optimisation standard ont en commun (même les méthodes sans dérivé) est l'hypothèse que l'espace sous-jacent est une variété lisse (peut-être avec quelques dimensions discrètes), et que la fonction à optimiser se comporte quelque peu bien.

Cependant, toutes les fonctions ne sont pas définies sur un collecteur lisse. Parfois, vous souhaitez optimiser sur un graphique ou d'autres structures discrètes (optimisation combinatoire) - ici, il existe des algorithmes dédiés, mais les GA fonctionnent également.

Plus vous allez vers des fonctions définies sur des structures complexes et discrètes, plus les AG peuvent être utiles, surtout si vous pouvez trouver une représentation dans laquelle les opérateurs génétiques fonctionnent au mieux (ce qui nécessite beaucoup de réglages manuels et de connaissances de domaine).

Bien sûr, l'avenir pourrait conduire à oublier complètement les AG et à développer des méthodes pour mapper des espaces discrets à un espace continu , et utiliser la machinerie d'optimisation que nous avons sur la représentation continue.

lacerbi
la source
2

Les méthodes génétiques sont bien adaptées à l'optimisation multicritères lorsque la descente de gradient est dédiée à l'optimisation des monocritères. La descente en gradient permet de trouver un minimum de fonctions lorsqu'il existe des dérivées et qu'il n'y a qu'une seule solution optimale (si l'on excepte les minimas locaux). Un algorithme génétique peut être utilisé dans des problèmes multicritères et conduire à un continuum de solutions, chacune étant des individus d'une population, ayant évolué à partir d'une population initiale. Les valeurs à optimiser sont les phénotypes des individus et il peut y avoir plusieurs phénotypes. Généralement, aucun individu n'a simultanément la meilleure valeur de chaque phénotype, il n'y a donc pas qu'une seule solution. Les individus de la population finale, qui sont tous des solutions de l'optimisation, font partie du "front de Pareto" et sont marqués comme étant "Pareto rang un" personnes. Cela signifie que par rapport à tous les autres individus ayant les mêmes performances pour chaque phénotype, ils sont au moins meilleurs pour un phénotype que les autres.

manu190466
la source
Ok pour un downvote, mais pourriez-vous expliquer où je me trompe?
manu190466
5
Ce site valorise les réponses qui fournissent le contexte et le contexte. Consultez cette page d'aide pour savoir comment fournir des réponses qui s'ajouteront à notre référentiel de réponses utiles à des questions intéressantes. Expliquer votre réponse est également un bon moyen de tester votre propre compréhension. Par exemple, dans ce cas, vous souhaiterez peut-être développer la façon dont les algorithmes génétiques «sont bien adaptés à l'optimisation multicritères», car la page Wikipedia semble impliquer des fonctions de fitness à valeur unique comme objectifs des algorithmes génétiques.
EdM
0

Meilleur dans quel sens?

D'après mon expérience, les AG sont l'un des optimiseurs les plus pragmatiques. Alors que de nombreux algorithmes plus précis nécessitent du temps et des efforts pour formaliser des problèmes réels dans le monde mathématique, les GA peuvent gérer n'importe quelle fonction de coût avec des règles et des contraintes complexes (les GA sont liés par une approche d'exécution après tout et non par un calcul spécifique). Ce processus est simple et vous pouvez essayer de nombreuses approches pour les travaux exploratoires.

J'apprécie également la possibilité de réinjecter des solutions passées à l'algorithme pour de futures exécutions, ce qui est bon pour les tâches répétées.

Conceptuellement, un algorithme génétique peut être représenté par une table de hachage des fonctions et convient donc aux langages fonctionnels comme Clojure qui est également un langage où vous pouvez obtenir de gros résultats très rapidement.

Les algorithmes génétiques peuvent également être imbriqués: la fonction de coût d'un GA peut être un GA! Ces algorithmes tirent parti du matériel et de l'infrastructure modernes qui leur permettent de calculer une très grande population de sorte que, même avec de simples opérations de mutation / sélection, vous pouvez toujours obtenir de bons résultats.

Même pour des problèmes simples comme trouver le minimum d'une fonction d'onde, les AG ne sont pas si mauvais et peuvent atteindre une précision décente dans un délai acceptable.

Alors oui, les solutions analytiques peuvent avoir un temps d'exécution et une précision plus rapides, mais le temps requis pour les produire surpondère souvent des avantages attendus! Donc quand ? Presque à chaque fois pour moi, du moins pour la méta-optimisation.

Joseph Yourine
la source
L'idée maîtresse de cet argument semble être que les algorithmes génétiques sont des optimiseurs de boîte noire. Mais il existe de nombreux optimiseurs de boîte noire. Pourquoi serait-ce mieux que d'autres choix? De plus, je ne pense pas que ce soit vraiment le cas que les GA peuvent facilement gérer les contraintes. Par exemple, si la fonction n'est pas définie à l'exception d'un sous-espace 3D dans un monde 4D, une GA vanilla échouerait certainement.
Cliff AB
@CliffAB En fait, je n'ai rien dit à ce sujet et peut-être plus au contraire. Dans GA, vous avez beaucoup de contrôle sur le calcul de base, le GA en lui-même est une séquence d'étapes et un ordre léger. Lorsque vous définissez des fonctions de coût, vous pouvez gérer n'importe quoi dans la fonction, même les contraintes externes que vous pouvez interroger. Mes principaux arguments sont les suivants: gérer de nombreux problèmes, vous ne devez pas vous soucier de la compatibilité avec le cadre (il vous suffit de renvoyer un coût), trouver une solution réelle et décente dans la plupart des études de cas, MÊME si ce n'est pas toujours le meilleur
Joseph Yourine