Efficacité du croisement dans les algorithmes génétiques
J'ai implémenté un certain nombre d'algorithmes génétiques pour résoudre une variété de problèmes. Cependant, je suis toujours sceptique quant à l'utilité du croisement/recombinaison.
J'implémente habituellement d'abord la mutation avant d'implémenter le crossover. Et après avoir implémenté le crossover, Je ne vois généralement pas d'accélération significative dans la vitesse à laquelle une bonne solution candidate est générée par rapport à l'utilisation simple de la mutation et à l'introduction de quelques individus aléatoires dans chaque génération pour assurer la génétique .
Bien sûr, cela peut être attribué à de mauvais choix de la fonction de croisement et/ou des probabilités, mais j'aimerais obtenir une explication/preuve concrète pour savoir pourquoi/si le croisement améliore ou non le gaz. Il n'y a eu aucune étude sur cette question?
Je comprends le raisonnement derrière cela: crossover permet de combiner les forces de deux individus en un seul individu. Mais pour moi c'est comme dire que nous pouvons accoupler un scientifique et un jaguar pour obtenir un intelligent et rapide hybride.
EDIT: dans la réponse de mcdowella, il a mentionné comment trouver un cas où le cross-over peut améliorer l'escalade à partir de plusieurs points de départ n'est pas trivial. Quelqu'un pourrait-il élaborer sur ce point?
6 réponses
Vous avez raison d'être sceptique quant à l'opération de croisement. Il y a un papier appelé "Sur l'efficacité de crossover dans le cadre de simulations d'évolution de l'optimisation" (Fogel et Stayton, Biosystems 1994). Il est disponible gratuitement à 1 (une bonne source de beaucoup d'autres grands pubs par Fogel ainsi).
En passant, si vous ne l'avez pas déjà fait, je vous recommande de regarder dans une technique appelée "évolution différentielle". Il peut être très bon pour résoudre de nombreux problèmes d'optimisation.
Il fortement dépend de la souplesse de votre espace de recherche. Exemple pervers si chaque " geneome "était haché avant d'être utilisé pour générer des" phenomes " alors vous feriez simplement une recherche aléatoire.
Cas moins extrême, c'est pourquoi nous avons souvent des entiers de code gris dans GAs.
Vous devez adapter vos fonctions de croisement et de mutation à l'encodage. Le gaz se désintègre assez facilement si vous leur lancez des calculs antipathiques. Si le croisement de A et B ne donne pas quelque chose c'est à la fois A-like Et B-like alors c'est inutile.
Exemple:
Le génome est long de 3 bits, le bit 0 détermine s'il est terrestre ou Marin. Les Bits 1-2 décrivent les fonctions digestives des créatures terrestres et les capacités visuelles des créatures marines.
Considérez deux créatures terrestres.
| bit 0 | bit 1 | bit 2
----+-------+-------+-------
Mum | 0 | 0 | 1
Dad | 0 | 1 | 0
Ils pourraient se croiser entre les bits 1 et 2 donnant un enfant dont la fonction digestive est un compromis entre celle de maman et celle de Papa. Grand.
Ce crossover semble raisonnable à condition que le bit 0 n'ait pas changé . Si c'est le cas, votre fonction de croisement a transformé une sorte de tripes en une sorte d'yeux. Er... Wut? Il pourrait aussi bien avoir été une mutation aléatoire.
Pose la question de savoir comment L'ADN contourne ce problème. C'est à la fois modal et hiérarchique. Il y a de grandes sections qui peuvent changer beaucoup sans beaucoup d'effet, dans d'autres une seule mutation peut avoir des effets drastiques (comme le bit 0 ci-dessus). Parfois la valeur de X affecte le comportement tiggered par Y, et toutes les valeurs de X sont légales et peuvent être explorées alors qu'une modification de Y fait le segfault animal.
Analyses Théoriques de Gaz utilisent souvent extrêmement brut codages et ils souffrent davantage de numériques que sémantique proches.
Mon impression est que l'escalade de colline à partir de plusieurs départs aléatoires est très efficace, mais qu'essayer de trouver un cas où le cross-over peut améliorer cela n'est pas trivial. Une référence est "Crossover: The Divine Afflatus in Search" par David Iclanzan, qui déclare
La théorie traditionnelle de L'AG est basée sur l'hypothèse du bloc de construction (BBH) qui stipule que les Algorithmes génétiques (GAs) fonctionnent en découvrant, mise en valeur et recombinaison de schémas de faible ordre de haute qualité cordes, d'une manière fortement parallèle. Historiquement, les tentatives de capturez les caractéristiques topologiques du paysage de fitness qui illustrent ce processus intuitivement simple, ont été principalement infructueux. Les méthodes de recombinaison basées sur la Population ont été surperformé à plusieurs reprises sur les suites de tests abstraits conçus spéciaux, par différentes variantes d'algorithmes basés sur la mutation.
Un article connexe est " surmonter la difficulté hiérarchique en escaladant la colline constitutif Structure" par David Iclănzan et Dan Dumitrescu, qui déclare
L'hypothèse du bloc de construction suggère que les Algorithmes génétiques (GAs) sont bien adaptés aux problèmes hiérarchiques, où la résolution efficace nécessite la décomposition du problème et l'assemblage de la solution à partir sous-solution avec de fortes interdépendances non linéaires. Papier propose un grimpeur opérant sur l'espace building block (BB) cela peut résoudre efficacement les problèmes hiérarchiques.
Les deux œuvres séminales de John Holland "Adaptation in Natural and Artificial Systems" et "Hidden Order" (moins formel) discutent en profondeur de la théorie du croisement. IMO, "algorithmes génétiques dans la recherche, L'optimisation et L'apprentissage automatique" de Goldberg a un chapitre très accessible sur les fondements mathématiques qui comprend des conclusions telles que:
Avec crossover et reproduction....ces schémas avec des performances supérieures à la moyenne et des longueurs de définition courtes vont être échantillonnés à des taux de croissance exponentielle.
Une autre bonne référence pourrait être "an Extension to the Theory of Convergence and a Proof of the time Complexity of Genetic Algorithms "D'Ankenbrandt (dans" Foundations of Genetic Algorithms " de Rawlins).
Je suis surpris que le pouvoir du crossover ne vous ait pas été apparent dans votre travail; quand j'ai commencé à utiliser des algorithmes génétiques et que j'ai vu à quel point le crossover semblait puissamment "dirigé", j'ai senti que j'avais acquis un aperçu de l'évolution qui j'ai renversé ce qu'on m'avait enseigné à l'école. Toutes les questions sur " comment la mutation pourrait-elle conduire à ceci et cela?"et" Eh bien, au cours de tant de générations..."est venu à sembler fondamentalement erronée.
Le croisement et la mutation!! En fait, les deux sont nécessaires. Crossover est un opérateur explorateur, mais la mutation est une exploitation. Compte tenu de la structure des solutions, du problème et de la probabilité de taux d'optimisation, il est très important de sélectionner une valeur correcte pour Pc et Pm (Probabilité de croisement et de mutation).
Vérifiez ceci ga-TSP-Solver , il utilise de nombreuses méthodes de croisement et de mutation. Vous pouvez tester n'importe quel croisement à côté de mutations avec donné probabilité.
Cela dépend principalement de l'espace de recherche et du type de croisement que vous utilisez. Pour certains problèmes, j'ai trouvé que l'utilisation du croisement au début, puis de la mutation, accélérerait le processus de recherche d'une solution, mais ce n'est pas une très bonne approche puisque je finirai par trouver des solutions similaires. Si nous utilisons à la fois crossover et mutation, j'obtiens généralement de meilleures solutions optimisées. Cependant, pour certains problèmes de croisement peut être très destructeur.
Aussi les opérateurs génétiques seuls sont pas assez pour résoudre des problèmes grands / complexes. Lorsque vos opérateurs n'améliorent pas votre solution (donc lorsqu'ils n'augmentent pas la valeur de fitness), vous devriez commencer à envisager d'autres solutions telles que l'évolution incrémentale, etc..