Algoritmo genético multiobjetivo NSGA-2. ¿Alguien podría darme una "explicación simple"?

Question

Estoy trabajando en un algoritmo genético.

Hay dos objetivos y cada uno tiene sus propios valores de condición física (fv1, fv2).

Sé cómo funcionan los algoritmos genéticos generacionales (SGE) y de estado estable (SS).

Estoy tratando de entender cómo NSGA-2 y SPEA-2 (estoy usando la aplicación de la biblioteca de Java JCLEC) funciona, en particular:

• lo que es la "población externa" y cómo en caso de que dimensionarse
• cuál es la diferencia con la SS y SGE algoritmo de un objetivo (una parte del hecho de que cada individuo tiene sólo un valor de aptitud)

En caso de que alguien está trabajando con la biblioteca JCLEC estos son los parámetros Configuré:

• población externa: 1000
• valor k: 10
• otros atributos son los mismos de SS y SGE (población-size: 100, de cruce: MPX cruce etc ..)

Answer 1

Aquí hay una explicación para NSGAII

1. primer lugar, se inicializa al azar de la población.
2. Los cromosomas se clasifican y colocan en frentes basados ​​en conjuntos no dominados por Pareto. Dentro de un frente de Pareto, los cromosomas se clasifican según euclidiano entre las soluciones o I-dist (término utilizado en NSGA-II).En general, las soluciones que están lejos (no están llenas) de otras soluciones reciben una mayor preferencia durante la selección. Esto se hace para establecer una solución diversa y evitar un conjunto de soluciones multitudinarias.
3. Los mejores cromosomas N (población) se eligen de la población actual y se colocan en un grupo de apareamiento
4. En el grupo de apareamiento, selección de torneo, cruce y apareamiento se hace.
5. El grupo coincidente y la población actual se combinan. El conjunto resultante se clasifica y los mejores cromosomas N llegan a la nueva población.
6. Vaya al paso 2, a menos que se haya alcanzado el número máximo de generaciones.
7. El conjunto de soluciones es el conjunto de Pareto no dominado mejor clasificado de la última población.

Answer 2

Recomiendo leer los documentos sobre estos algoritmos que explican bastante bien la funcionalidad:

• Deb, Pratab, Agarwal, Meyarivan. Un algoritmo genético multiobjetivo rápido y elitista: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2), pp. 182-197, 2002.
• Zitzler, Laumanns, Thiele. SPEA2: Mejora de la fuerza del algoritmo evolutivo de Pareto. Informe técnico (TIK-103), Instituto Federal Suizo de Tecnología (ETH), 2001.

Estoy seguro de que puede encontrar el PDF de estas publicaciones en la web.

Acerca de la diferencia entre GA de estado estacionario y GA generacional: en el reemplazo generacional se crea una población completamente nueva del mismo tamaño que la anterior utilizando solo los genes de la población anterior y luego se reemplaza en conjunto. En el reemplazo de estado estable, usted crea solo un nuevo individuo que luego reemplaza a solo un individuo en la población. Los GA de estado estable generalmente convergen más rápido, pero es menos probable que encuentren el óptimo óptimo local, ya que no exploran el paisaje de la aptitud física tanto como cuando usan el reemplazo generacional. Depende del problema, por supuesto, y a veces puede elegir qué cantidad de la generación anterior desea reemplazar, lo que le permite tener una escala arbitraria entre estos dos.

Existen otros algoritmos multiobjetivo como AbYSS y PAES.