Question Quel est le schéma de Niching?


Je suis en train de lire un article sur l'utilisation de GA dans les problèmes d'optimisation sous contraintes. À un certain moment, il est question d’appliquer régime de niching sur les individus (ou le front de Pareto qu'ils font).

Cela semble être un schéma de sélection typique, mais comme je cherchais, je ne pouvais pas trouver une bonne explication à cela.

Quelqu'un peut-il m'expliquer aussi simplement que possible régime de niching est?


15
2017-12-08 08:28


origine


Réponses:


En termes simples, niching est une classe de méthodes qui tentent de converger vers plusieurs solutions au cours d'une même opération.

Nicher est l'idée de segmenter la population de l'AG en ensembles disjoints, de sorte que vous ayez au moins un membre dans chaque région de la fonction de remise en forme qui soit "intéressant"; Cela signifie généralement que vous couvrez plus d’un optima local.

Imaginez une fonction comme f(x) = sin(x^2).

enter image description here

Une AG normale finira par converger vers l'un des deux minima globaux. Lequel dépend de la population initiale et de la dérive génétique aléatoire qui se produit tout au long de la course, mais finalement, vous obtiendrez n copies d'une personne dans l'une ou l'autre des vallées. Par exemple, si vous regardiez une telle GA alors que celle-ci était presque convergente, vous pourriez voir quelque chose comme:

standard GA

La niche est une classe générale de techniques destinées à se retrouver avec environ la moitié de la population convergeant dans chaque minimum (voire même en incluant quelques membres dans le moins adapté au minimum). x=0).

niching

Comme je viens de le dire, niching n'est pas vraiment un algorithme, mais plutôt une classe générale d'algorithmes. Une de ces méthodes est le partage de fitness de Goldberg. Dans cette méthode, nous définissons un rayon de niche sigma. Deux individus plus rapprochés que cela sigma sont considérés comme étant dans le même créneau, et doivent donc partager leurs valeurs de condition physique (pensez à cela comme une fonction qui diminue l'aptitude de chaque membre de la niche, plus la niche est densément peuplée). Vous faites alors fonctionner l’AG sur les valeurs de fitness partagées au lieu des valeurs brutes.

L'idée ici est de décourager la convergence vers une seule région de la fonction de remise en forme en prétendant qu'il existe des ressources limitées. Plus les individus tentent d'emménager, plus ils sont désavantagés. Le résultat est que, à mesure que l'AG converge vers un optimum local unique, l'aptitude de cet optimum diminue en raison de la concurrence accrue au sein de la niche. À terme, une autre région du paysage de remise en forme devient plus attrayante et les individus migrent là-bas. L'idée est d'atteindre un état stable - un point fixe dans la dynamique - où une représentation appropriée de chaque niche est maintenue.

Le partage est difficile en raison de la nécessité de définir manuellement le rayon de niche, et l'algorithme est assez sensible à ce choix. Une autre alternative est le surpeuplement. En particulier, vous pourriez rechercher le "surdimensionnement déterministe", qui était une méthode populaire pendant un certain temps. Dans les méthodes basées sur le surpeuplement, au lieu de traiter d'un rayon explicite, nous limitons le nombre d'individus qu'un nouveau produit peut remplacer à un ensemble de solutions similaires. Par exemple, une progéniture pourrait être autorisée à ne remplacer qu'un seul de ses parents. Cela a pour effet d'empêcher le remplacement d'un individu unique par un individu très similaire à une douzaine d'autres personnes et de préserver ainsi la diversité.


32
2017-12-10 11:42



Yep bonne explication par deong pour niching. Toutes ces techniques sont faites pour maintenir la diversité de la population.

C'est ce que fait le front de Pareto. Les GA qui recherchent un front de Pareto sont des algorithmes évolutifs multi-objectifs. Ils essaient d'optimiser non seulement un critère, mais deux ou plus. Donc, le front de Pareto sont tous des individus qui ne sont pas dominés par un individu de la population. http://en.wikipedia.org/wiki/Pareto_efficiency

En bref: Un individu A est membre du front de pareto s'il n'y a pas d'individu B dans la population qui soit au moins aussi bon que A pour tous les critères et meilleur que A pour au moins un critère.


1
2018-01-10 14:42