Déclarations prouvables sur les algorithmes génétiques

56

Les algorithmes génétiques n'ont pas beaucoup de poids dans le monde théorique, mais ils constituent une méthode métaheuristique assez bien utilisée (par métaheuristique, je veux dire une technique qui s'applique de manière générique à de nombreux problèmes, tels que l'annelage, la descente de gradient, etc.). En fait, une technique similaire à celle de l'AG est assez efficace pour le traitement des TSP euclidiennes .

Certaines métaheuristiques sont assez bien étudiées théoriquement: il existe des travaux sur la recherche locale et le recuit. Nous avons une assez bonne idée du fonctionnement de l'optimisation alternative ( comme k-means ). Mais pour autant que je sache, il n’ya rien de vraiment utile sur les algorithmes génétiques.

Existe-t-il une théorie algorithmique / de complexité solide sur le comportement des algorithmes génétiques, sous quelque forme que ce soit? Bien que j'aie entendu parler de choses comme la théorie des schémas , je l'exclurais de la discussion en fonction de ma compréhension actuelle du domaine pour ne pas être particulièrement algorithmique (mais je pourrais me tromper ici).

Suresh Venkat
la source
5
Pour plus d’inspiration, voir aussi p. 25 à 29 des diapositives FCRC 2007 de Papadimitriou .
Jukka Suomela
1
@Suresh: Je préférerais y voir une question plutôt qu'une réponse . Je serais ravi si quelqu'un d'autre avait la peine d'expliquer plus précisément le résultat auquel Papadimitriou fait référence dans les diapositives. :)
Jukka Suomela
1
voici une interprétation pop-sci de cette œuvre: tinyurl.com/2f39jrb
Suresh Venkat
1
J'ai récemment suivi un cours en Géorgie et mon battage médiatique à propos de celle-ci a diminué lorsque j'ai appris le théorème du No Free Lunch: en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
Alexandru
1
Alexandru, pourquoi ça? Il devrait être assez évident que presque toutes les techniques seront meilleures que d'autres dans certains cas et pires dans d'autres. Pensiez-vous vraiment que GA serait uniformément supérieur?
Raphaël

Réponses:

29

Y. Rabinovich, A. Wigderson. Techniques permettant de limiter le taux de convergence des algorithmes génétiques. Algorithmes de structures aléatoires, vol. 14, non. 2, 111-138, 1999. (également disponible sur la page d'accueil d'Avi Wigderson )

Joshua Grochow
la source
Il semble que le premier lien est disparu.
Jeremy Kun
@JeremyKun: Je viens de l'essayer et tout a bien fonctionné ... (Cela me rendrait triste qu'un lien de doi devienne caduque, annulant ainsi l'un des principaux objectifs du système de doi ...)
Joshua Grochow le
Je reçois toujours une erreur "Page Not Found" de la bibliothèque Wiley. Pourrait-il s'agir d'un problème de formatage / navigateur?
Jeremy Kun
@ JeremyKun: Pourrait être. Si vous avez accès à MathSciNet, essayez plutôt ce lien: ams.org/mathscinet-getitem?mr=1667317
Joshua Grochow
Ce n'est pas un problème parce que le lien vers sa page d'accueil fonctionne. J'essayais seulement d'aider à améliorer cette réponse :)
Jeremy Kun
13

Jetez un coup d'œil au travail de Benjamin Doerr du groupe Algorithms chez Max Planck (MPI). Il s’agit d’essayer de faire des contributions prouvables aux algorithmes évolutifs.

Doerr a notamment co-édité un ouvrage récent, Theory of Randomized Search Heuristics

Alex Lopez-Ortiz
la source
1
Ajouter un lien améliorerait cette réponse.
Dave Clarke
10

En plus de travailler sur le recuit simulé, Ingo Wegener avait quelques résultats théoriques sur les algorithmes évolutifs. La thèse de son doctorant Dirk Sudholt mérite également un coup d'oeil.

Rahul Savani
la source
10

Au cours de la dernière décennie, l'analyse à la volée des algorithmes évolutifs, de l'optimisation des colonies de fourmis et d'autres métaheuristiques a considérablement progressé. Pour une enquête, veuillez vous reporter à Oliveto et al. (2007) .

Per Kristian Lehre
la source
Kristian Lehre, je viens juste de vous regarder et de voir votre domaine d’intérêt. Je voudrais donc poser la question suivante: pensez-vous que des outils similaires pourraient être utilisés pour analyser le temps d’exécution des algorithmes d’optimisation des colonies de fourmis, ainsi que des questions de type "Algorithme naturel" de Chazelle ( taux de convergence des oiseaux s'assemblant)? Pour le moment, les techniques de Chazelle semblent être une île à elles seules, et je me demande s’il existe une image plus grande.
Aaron Sterling
2
Oui, ces techniques peuvent être adaptées pour analyser le temps d'exécution des ACO. J'ai récemment co-écrit un article sur les ACO pour le problème MinCut. Veuillez également consulter l'enquête de Witt (2009): springerlink.com/content/3727x3255r1816g4 Je ne suis au courant d'aucun lien entre cette recherche et les travaux de Chazelle, mais elle mérite certainement d'être explorée.
Per Kristian Lehre
7

Lovasz et Vempala (numéro spécial de FOCS 2003 de J. Comp. System Sci.) Utilisent une variante du recuit simulé pour obtenir un meilleur algorithme ( ) permettant de calculer le volume d'un corps convexe. De toute évidence, ils peuvent prouver quelque chose sur la variante qu'ils utilisent, afin d'obtenir la borne supérieure prouvable de leur algorithme global.O(n4)

Joshua Grochow
la source
1
hé, il est de retour :)
Suresh Venkat le
6

Vérifiez ces références:

Lothar Schmitt, Théorie des algorithmes génétiques II: modèles d'opérateurs génétiques sur la représentation des populations de tenseur de cordes et convergence vers des optima globaux pour une fonction de fitness arbitraire sous mise à l'échelle

Shiu Yin Yuen; BKS Cheung, Limites de probabilité de succès d'un algorithme génétique classique basé sur la distance de Hamming

Chang CY Dorea; Judinor A. Guerra Jr .; Rafael Morgado; Andre GC Pereira, Modélisation de la chaîne de Markov en plusieurs étapes de l'algorithme génétique et résultats de la convergence

C. Dombry, Un modèle de marche aléatoire pondéré. Application à un algorithme génétique

Mohammad Al-Turkistany
la source
6

Il existe également un article de D. BHANDARI, CA MURTHY et SK PAL (malheureusement indisponible en ligne) qui fournit une preuve de convergence fondée sur deux hypothèses:

  • Sélection élitiste: la meilleure solution de la génération doit être dans la générationt + 1tt+1
  • L'opérateur de mutation permet de passer d'une solution à une autre en un nombre fini d'étapes

La preuve de convergence utilise un modèle de chaîne de Markov.

Voici la référence: Dinabandhu Bhandari, CA Murthy: Algorithme génétique avec modèle élitiste et sa convergence. IJPRAI 10 (6): 731-747 (1996)

Lamine
la source
6

Les modèles mathématiques d'algorithmes génétiques avec des populations finies mais non unitaires sont difficiles à manier et se sont révélés jusqu'ici inanimables à l'analyse pour toutes les fonctions de fitness, sauf la plus triviale. Il est intéressant de noter que si vous êtes prêt à accepter un argument de symétrie , un argument, en d’autres termes, qui n’est pas formulé dans les limites d’un système axiomatique formel, il existe un résultat intéressant et magnifique sur le pouvoir de calcul des algorithmes génétiques.

Plus précisément, un algorithme génétique à croisement uniforme est capable d’évaluer de manière implicite et parallèle un grand nombre de partitions de schéma grossières et peut identifier efficacement les partitions dont les schémas constitutifs ont des valeurs d’aptitude moyenne différentes. Cette forme de parallélisme implicite est en réalité plus puissante que celle décrite par John Holland et ses étudiants et, contrairement au parallélisme implicite décrit par Holland, elle peut être vérifiée expérimentalement. (Voir cet article de blog.)

Le document suivant explique comment des algorithmes génétiques avec filtrage croisé uniforme impliquent un parallélisme implicite dans une heuristique d’optimisation globale polyvalente appelée hyper - escalade :

Explication de l'optimisation dans les algorithmes génétiques avec croisement uniforme . Apparaître dans les actes de la conférence Foundations of Genetic Algorithms 2013.

(Avertissement: je suis l'auteur du journal)

kburjorj
la source
il est intelligent / novateur d’utiliser la SAT aléatoire comme référence pour l’AG et montre une idée qui semble avoir été explorée par peu de documents. Supposons que l’AG puisse travailler sur n’importe quelle classe de complexité arbitraire et constitue peut-être vraiment un moyen de construire des algorithmes dans une classe de complexité "supérieure" sur la base des résultats d’algorithmes dans une classe de complexité "inférieure" .... alors dans un certain sens, cela logique d'analyser la "complexité" des GA car ils pourraient transcender la classification par classe de complexité ....
vzn
5

Raphael Cerf a réalisé sa thèse de doctorat sur les algorithmes génétiques à Montpellier sous la direction d'Alain Berlinet, d'un point de vue mathématique. Il est assez ancien, mais ferait probablement partie de toute bibliographie sur les algorithmes génétiques.

Jeremy
la source