genetic-algorithm - individual - mutation in genetic algorithm
¿Qué es el esquema de niching? (2)
Actualmente estoy leyendo un artículo sobre el uso de GA en problemas de optimización restringidos. En alguna parte, se trata de aplicar un esquema de niching a los individuos (o el frente de Pareto que hacen).
Parece un esquema de selección típico, pero cuando busqué, no pude encontrar una buena explicación para ello.
¿Puede alguien explicarme lo más simple posible, qué es un esquema de niching ?
En pocas palabras, niching es una clase de métodos que intentan converger a más de una solución en una sola ejecución.
Niching es la idea de segmentar la población de la AG en conjuntos separados, con la intención de que tenga al menos un miembro en cada región de la función de aptitud que sea "interesante"; En general, con esto queremos decir que cubre más de un óptimo local.
Imagina una función como f(x) = sin(x^2) .
Una AG normal eventualmente convergerá hacia uno de los dos mínimos globales. Cuál depende de la población inicial y la deriva genética aleatoria que se produce a lo largo de la carrera, pero eventualmente, obtendrá n copias de un individuo en uno u otro valle. Por ejemplo, si observa una AG de este tipo cuando está casi convergente, es posible que vea algo como
Niching es una clase general de técnicas destinadas a terminar con aproximadamente la mitad de la población que converge en cada mínimo (o posiblemente incluso incluir algunos miembros en el mínimo de ajuste menor en x=0 ).
Como acabo de decir, niching no es realmente un algoritmo sino una clase general de algoritmos. Uno de estos métodos es compartir la condición física de Goldberg. En este método, definimos un radio de nicho sigma . Cualquiera de los dos individuos más cercanos que este sigma se considera que están en el mismo nicho y, por lo tanto, deben compartir sus valores de aptitud física (piense en esto como una función que disminuye la aptitud física de cada miembro del nicho a medida que el nicho está más poblado). A continuación, haga que la AG opere con los valores de aptitud compartidos en lugar de los valores sin procesar.
La idea aquí es que usted desalienta la convergencia a una sola región de la función de aptitud simulando que hay recursos limitados allí. Cuantos más individuos intenten mudarse, peor están todos. El resultado es que a medida que la AG converge en un único local óptimo en algún lugar, la aptitud de ese óptimo disminuye debido al aumento de la competencia dentro del nicho. Eventualmente, otra región del paisaje físico se vuelve más atractiva y las personas migran allí. La idea es alcanzar un estado estable, un punto fijo en la dinámica, donde se mantiene una representación adecuada de cada nicho.
Compartir es difícil debido a la necesidad de establecer manualmente el radio de nicho, y el algoritmo es bastante sensible a esta elección. Otra alternativa es el hacinamiento. En particular, puede buscar "Multitud determinista", que fue un método popular durante un período de tiempo. En los métodos basados en el hacinamiento, en lugar de tratar con un radio explícito, trabajamos limitando el conjunto de individuos que una nueva descendencia puede reemplazar a un conjunto de soluciones similares, por ejemplo, una descendencia podría tener permitido reemplazar solo a uno de sus padres. El efecto es tratar de evitar que se reemplace a un individuo único con uno que sea muy similar a una docena de otros en la población y así preservar la diversidad de esa manera.
Sí, buena explicación por deong para niching. Todas estas técnicas están hechas para mantener la diversidad de la población.
Eso es lo que hace el frente de Pareto también. Los GA que buscan un frente de Pareto son algoritmos evolutivos de múltiples objetivos. Intentan optimizar no solo un criterio sino dos o más. Entonces, el frente de Pareto son todos los indiviudales que no están pareto dominados por un individuo de la población. http://en.wikipedia.org/wiki/Pareto_efficiency
En pocas palabras: un individuo A es miembro del frente de Pareto si no hay un individuo B en la población que sea al menos tan bueno como A con respecto a todos los criterios y mejor que A en al menos un criterio.