Comment trouver les meilleurs paramètres pour un algorithme génétique?

Question

Certains cadres algorithmes génétiques, tels que http://www.aforgenet.com/ nécessite de nombreux paramètres , comme le taux de mutation, la taille de la population, etc

Il est le meilleur nombre de ces paramètres universels? Je crois que cela dépend du problème (retard de la fonction de remise en forme, retard de mutation, le retard de recombinaison, le taux d'évolution, etc.). Ma première pensée était d'utiliser un GA pour configurer un autre GA.

Les meilleures idées?

Answer 1

La seule fois que je programmé un algorithme génétique I inclus ces valeurs dans les valeurs à muter, essentiellement comme vous l'avez dit à l'aide d'un GA pour se configurer. Cela a fonctionné étonnamment bien, surtout que je l'ai trouvé pour être bénéfique pour les valeurs de changer au cours de son calcul.

Answer 2

Je trouve utile de penser à ces problèmes comme un paysage, où vous essayez de trouver le point le plus bas.

Des méthodes telles que les algorithmes génétiques sont utilisés lorsque le paysage est trop grand pour tester juste tous les points, et la « forme » du paysage est telle que les méthodes comme gradient de descente auront vous coincé dans des minima locaux.

Un bon exemple est fonction de rastrigin ( ref image ):
_{(source: scientific-computing.com )}
:

Vos choix sont:

Taille de génération:

• Trop grand: vous allez avoir un longtemps d'époque, ce qui limite le nombre de chances de chaque individu a explorer son quartier.
• Trop petit: vous ne recevez pas bon la couverture de l'espace de recherche.

Taux de mutation:

• Trop élevé: vous risquez de les individus « Sauter » sur une solution qu'ils étaient proche de.
• Trop bas: ils vont tous obtenir coincé dans des minima locaux.

Il ne dépend vraiment de votre propre espace de recherche particulier. Expérimentez avec les paramètres et essayer de trouver la combinaison optimale. Je suis d'accord que d'utiliser un autre GA pour optimiser les paramètres ne va pas résoudre le problème.

Answer 3

Je trouve assez décevant il y a tellement de réponses qui suppose que vous ne pouvez pas trouver les meilleurs paramètres de l'algorithme génétique automatiquement. Je suis d'accord que les paramètres ne dépendent du problème mais il existe des méthodes où vous pouvez les trouver.

En outre, le No Free Lunch théorème en aucun cas vous empêche de trouver les meilleurs paramètres, comme il y a déjà eu des discussions que conteste le fait que:

• Pratiquement, il ne tient pas
• longueur Description peut contester le théorème
• coévolution peut faire le théorème hors de propos

Il existe deux types de paramétrage:

• Paramètre Tuning (recherche des paramètres hors ligne - avant l'AG est exécuté)
• Contrôle des paramètres (peaufinage des paramètres en ligne - pendant la course GA)
  • Adaptive
  • auto adaptatif
  • déterministes

Il y a beaucoup de littérature là-bas qui décrivent comment on peut trouver ces paramètres optimaux, cela dépend si vous êtes désireux de faire la recherche des paramètres hors ligne ou en ligne. La croyance populaire est que hors-ligne est mieux adapté à la plupart des cas parce que les méthodes de contrôle des paramètres en ligne ajouteraient trop de complexité sur hors-ligne.

Voici quelques exemples pour trouver les paramètres « meilleur »:

Paramètre Tuning :

• balayage de paramètre simple (tout essayer)
• Meta-GA ontop d'un GA
• stratégie Racing pour trouver les meilleurs paramètres
• Meta-GA et Racing ensemble

Paramètres de contrôle :

• probabilités d'adaptation pour la mutation et de croisement
• taille de popuation auto adaptatif
• déterministes génétique Opérateurs de

Et bien d'autres, il suffit de chercher pour la littérature en utilisant des mots-clés utilisés ci-dessus. Il existe des méthodes scientifiques pour trouver des paramètres appropriés pour un problème donné!

Answer 4

Il est pas facile.

Pourquoi? En raison de la No Free Lunch théorème. Cela indique simplement qu'il n'y a pas Général algorithme de recherche qui fonctionne bien pour tous les problèmes .

Le mieux que vous pouvez faire est de mesure la recherche d'un espace de problème spécifique . Vous devrez modifier manuellement vos paramètres pour adapter votre solution. Désolé.

L'utilisation d'un GA pour trouver les paramètres GA se complique. Comment trouvez-vous les paramètres optimaux pour votre recherche GAGA? Une autre GA ...?

Answer 5

Il n'y a vraiment pas de façon automatique le faire pour un ensemble de données. S'il y avait, ils ne l'exposerait pas ces paramètres. L'utilisation d'un deuxième GA pour régler les paramètres de la première AG est périlleuse - utilisez-vous un troisième GA pour régler les paramètres de la seconde? Même si vous avez fait cela, il est une recette pour overfitting de toute façon.

Mon conseil serait de jouer avec les paramètres, et de voir comment ils affectent votre distrubution de la population à chaque génération, combien de générations qu'il faut pour arriver à une réponse acceptable, etc. Si vous avez trop de mutation votre population ne sera jamais stabiliser . Trop peu et vous vous retrouverez avec homogénéité.

Il est un secret sale de AGs qui les désintéressent est un art, pas une science.

Answer 6

Comme tout le monde l'a déjà dit, il n'y a pas de réponse. Bien qu'il y ait une certaine tendance à utiliser le taux de croisement au niveau 0,7-0,9 et mutation sur 0,1-0,3 cela dépend vraiment. Cela dépend de problème, peut dépendre de la fonction de remise en forme, et dépend sans aucun doute sur l'algorithme génétique lui-même. Il existe de nombreuses variantes de GA, les paramètres optimaux pour le même problème peut varier.

En ce qui concerne l'utilisation des paramètres GA tune de cible GA il y a des approches comme ça, mais, comme il a été souligné, comment les paramètres tune de première GA? Gardez à l'esprit, que peut-être le taux de mutation devrait être plus élevé au début, et qu'il ne devrait diminuer en croix sur le taux devrait augmenter. Il est question de l'exploration par rapport à l'exploitation. Il existe des approches pour laisser GA être plus adaptative et le laisser changer ses paramètres comme il cherche la solution. Les contrôleurs flous sont parfois utilisés pour manipuler les paramètres de GA. Il y a aussi d'autres approches.

Si vous voulez savoir sur plus, acheter des livres ou regarder à travers des documents de recherche universitaires.
Si vous devez configurer votre propre GA sans des recherches approfondies, essayez quelques valeurs des autres travaillent, et d'expérimenter avec eux.