Red de conocimiento informático - Material del sitio web - Introducción a los algoritmos evolutivos multiobjetivo

Introducción a los algoritmos evolutivos multiobjetivo

Nombre: Liu Yiting; Número: 20021210599; Facultad: Escuela de Ingeniería Electrónica

Indique la fuente de la reimpresión:

Reimpreso de /sinat_33231573/article/details/80271522

Incrustar introducción a Tao Niu

La mayoría de los problemas prácticos tienen múltiples objetivos que deben cumplirse al mismo tiempo, es decir, hay múltiples objetivos no lineales en el mismo modelo de problema al mismo tiempo. Las funciones objetivas deben optimizarse al mismo tiempo, y entre estos objetivos A menudo hay conflictos. Hay múltiples objetivos no lineales en el modelo al mismo tiempo. Estas funciones objetivas deben optimizarse al mismo tiempo. A menudo hay conflictos entre estos objetivos. Los algoritmos evolutivos suelen ser una buena forma de resolver este tipo de problemas.

Algoritmo evolutivo multiobjetivo anidado Bullnose

Pregunta de Bullnose anidado ¿Cuál es la diferencia entre optimización multiobjetivo y optimización multitarea?

Texto de vaca anidada

1. Conceptos básicos de optimización multiobjetivo

El problema de optimización multiobjetivo (MOP) se puede expresar como:

?sujeto a?

Entre ellos, Ω es el espacio de decisión, que se compone de m funciones objetivo y se denomina espacio objetivo. El conjunto de objetivos alcanzables se define como . Muchas veces, ningún punto en Ω puede maximizar todos los objetivos simultáneamente porque estos objetivos entran en conflicto entre sí, por lo que debemos equilibrarlos. El compromiso óptimo entre objetivos se puede definir en términos de optimización de Pareto.

Dominancia de Pareto:

Solución óptima de Pareto:

Conjunto de soluciones óptimas de Pareto:

Frontera de tofu de Pareto:

2. El proceso básico de los algoritmos evolutivos multiobjetivo

Existen muchos tipos de algoritmos evolutivos multiobjetivo, que se pueden clasificar según determinadas características. Según los diferentes mecanismos de selección, podemos dividirlos en:

(1) Enfoques basados ​​en Pareto

(2) Métodos basados ​​en la población (Enfoques basados ​​en la población)

(3) Funciones de agregación (AggregatingFunctions)

Para comprender en profundidad el algoritmo evolutivo, presentamos el proceso básico de MOEA basado en Pareto, como se muestra en la Figura 2.1. Primero inicialice la población P y luego seleccione un determinado algoritmo evolutivo (por ejemplo, algoritmo evolutivo multiobjetivo basado en descomposición, MOEA/D) para realizar la operación evolutiva (por ejemplo, si el tamaño del conjunto de soluciones óptimas actual Nset es Si no es consistente con el tamaño de N, es necesario ajustar el tamaño de Nset. Cabe señalar que el Nset ajustado debe cumplir con los requisitos de distribución. Después de eso, determinamos si se cumple la condición de terminación del algoritmo. copiar los individuos en Nset a la población P y continuar con la siguiente ronda de evolución. Terminar Generalmente usamos el número de iteraciones del algoritmo para controlar su ejecución.

En MOEA, una condición necesaria para la convergencia del algoritmo. y un aspecto extremadamente importante es retener el conjunto de soluciones óptimas de la generación anterior y agregarlo a la evolución de una nueva generación. Al evolucionar de esta manera, el conjunto de soluciones óptimas del grupo evolutivo continúa convergiendo hacia el verdadero frente de Pareto. , y finalmente se obtiene un resultado evolutivo satisfactorio

3. Conjunto de pruebas de problemas de optimización multiobjetivo

Las funciones de prueba pueden ayudarnos a comprender mejor las ventajas y desventajas del algoritmo, por lo que el La selección de funciones de prueba es particularmente importante para comprender y juzgar el rendimiento del algoritmo al seleccionar funciones de prueba, la facilidad de construcción, la escalabilidad del número de variables de decisión y objetivos, y si las barreras corresponden a la convergencia y diversidad del algoritmo. Es necesario establecer dos factores de referencia importantes. Un conjunto de funciones de prueba comúnmente utilizado para problemas de optimización multiobjetivo.

Deb et al. propusieron por primera vez la función de prueba DTLZ en 2002 y le pusieron el nombre de las iniciales de los investigadores (Deb, Thiele, Laumanns, Zitzler). Con base en las expectativas para diferentes niveles de dificultad, Deb et al. agregaron dos funciones de prueba a las siete funciones originales en 2005 para formar el conjunto de funciones de prueba DTLZ. El conjunto de funciones de prueba DTLZ se puede ampliar a cualquier número de objetivos (mgt; =2) y con cualquier número de variables (ngt; =m). Dado que el número de variables y objetivos es fácilmente controlable, el conjunto de funciones DTLZ se utiliza ampliamente como función de prueba estándar para problemas de optimización multiobjetivo.

El conjunto de funciones de prueba WFG propuesto por Huband et al., 2006, consta de 9 preguntas de prueba y puede ampliarse a cualquier número de objetivos. En comparación con el conjunto de funciones de prueba DTLZ, el problema DTLZ es menos complejo porque las variables son separables, mientras que el problema de prueba WFG es más complejo y más difícil de manejar. Las características del problema de prueba WFG incluyen separabilidad o inseparabilidad, unimodal o multimodal, si la forma PF es convexa o no convexa y sin o con parámetros sesgados.

4. Indicadores de evaluación del desempeño del algoritmo

Generalmente, al analizar el desempeño de MOEA, esperamos que el algoritmo tenga un buen desempeño en los siguientes tres aspectos.

(1) La distancia entre el frente de Pareto real PFtrue y el algoritmo PFknown debe ser mínima.

(2) Aunque los puntos de solución buscados son solo soluciones parciales, los puntos de solución final deben distribuirse uniformemente en el conjunto de soluciones óptimas de Pareto y los puntos en la frontera de Pareto deben distribuirse lo más uniformemente posible.

(3) Se debe encontrar una gran cantidad de puntos de solución en toda la superficie de la frontera, y cada región en la superficie de la frontera debe tener un punto de solución, a menos que falte la región en PFtrue.

Generalmente consideramos que la primera métrica anterior es la más importante, ya que el objetivo de MOEA es encontrar un conjunto de soluciones aproximadas que se acerquen más al frente real.

Distancia Generacional Invertida: representa la distancia promedio desde el conjunto de soluciones óptimas de Pareto real y uniformemente distribuido P* hasta el conjunto de soluciones óptimas P obtenido por el algoritmo, definido de la siguiente manera:

Entre entre ellos, la distancia euclidiana mínima entre un individuo y el individuo v en el grupo P está representada por d (v, P) se selecciona uniformemente en el PF real, representado por el algoritmo obtenido El óptimo; el conjunto solución está representado por P. IGD es el índice de evaluación integral del rendimiento del algoritmo, que refleja la distribución y convergencia del algoritmo. Cuanto menor sea el valor, mejor. El valor de IGD es muy pequeño, lo que indica que el conjunto de soluciones óptimas obtenido por el algoritmo tiene buenas propiedades de distribución y convergencia.

Hipervolumen: El hipervolumen mide el volumen del área de dimensión del espacio objetivo encerrada por el conjunto de soluciones no dominadas y el punto de referencia obtenido por el algoritmo de optimización multiobjetivo. La representación matemática del hipervolumen es la siguiente:

donde δ representa la métrica de Lebesgue, que se utiliza para medir el volumen. |HV es una medida de calidad unidimensional eficaz, que tiene una estricta monotonicidad en términos de dominancia de Pareto. Cuanto mayor sea el valor de HV, mejor será el rendimiento del algoritmo correspondiente. Además, el cálculo del indicador HV no requiere el PF ideal del problema de prueba, lo que facilita enormemente el uso de HV en aplicaciones prácticas. Sin embargo, el indicador HV tiene dos limitaciones: 1) el costo computacional del hipervolumen es alto; 2) el valor HV se ve muy afectado por el punto de referencia seleccionado.