Problema de optimización multiobjetivo

Características:

① Contiene múltiples funciones objetivas y estas funciones objetivas pueden entrar en conflicto entre sí.

② Espero encontrar un conjunto de soluciones que pueda equilibrar bien todos los objetivos de optimización.

La optimización de Pareto se refiere a un estado ideal de asignación de recursos. Dado un conjunto de personas inherentes y recursos asignables, si pasar de un estado de asignación a otro mejora la situación de al menos una persona sin empeorar la situación de otras, este es el estado óptimo de Pareto; en otras palabras, es imposible mejorar la situación de; algunas personas sin empeorar las cosas para otras.

Dominar: Cuando x1 y x2 satisfacen las siguientes condiciones, x1 se denomina dominando a x2: (i) para todas las funciones objetivo, x1 no es peor que x2 (ii) para al menos una función objetivo, x1; es estrictamente superior en x2.

Para el punto 1 y el punto 2: Para la función objetivo f1, cuanto más grande mejor, al tomar la misma f2, el punto 1 es mejor que el punto 2 para la función objetivo f2, cuanto más pequeña mejor, al tomar el mismo f1 Cuando, el punto 1 es mejor que el punto 2.

Para el punto 1 y el punto 4: En lo que respecta a la función objetivo f1, cuando f2 se considera igual, el punto 4 es mejor que el punto 1 en lo que respecta a la función objetivo f2; , cuando se considera que f1 es el mismo, el punto 4 es mejor que el punto 1. 1 es mejor que el punto 4. Por tanto, los puntos 1 y 4 son mutuamente excluyentes.

Conjunto de soluciones no dominado: Cuando cualquier solución de un conjunto de soluciones no puede ser dominada por otras soluciones del conjunto de soluciones, este conjunto de soluciones se denomina conjunto de soluciones no dominado.

Conjunto óptimo de Pareto: El conjunto de todas las soluciones factibles no dominadas se denomina conjunto óptimo de Pareto.

Frente óptimo de Pareto: La frontera del conjunto óptimo de Pareto se denomina frente óptimo de Pareto.

Los objetivos de los problemas de optimización multiobjetivo: (1) encontrar un conjunto de soluciones que sea lo más cercano posible al óptimo (2) aumentar la diversidad de las soluciones encontradas tanto como sea posible;

Ventajas:

Desventajas: (1) Es difícil establecer un vector de peso para obtener una solución óptima de Pareto (2) En algunas situaciones no convexas, no está garantizado; Obtenga la solución óptima de Pareto.

Las ventajas se aplican tanto a funciones convexas como a no convexas.

Desventajas: Las funciones deben elegirse con cuidado y deben estar dentro de los valores mínimos o máximos de las funciones independientes.

Ventajas: El círculo ponderado de Tchebichev garantiza todas las soluciones óptimas de Pareto.

Desventajas: ① Los valores máximo y mínimo de cada función deben conocerse a priori ② El z* de cada función objetivo debe encontrarse de forma independiente ③ Para valores de p más pequeños, es posible que no; necesariamente posible Se garantiza obtener todas las soluciones óptimas de Pareto ④ A medida que p aumenta, el problema se vuelve irresoluble;

① Generar aleatoriamente la población inicial

② Calcular el valor de la función objetivo y el valor de la función de restricción en cada punto

③ Clasificar la población según el objetivo; valor de la función;

④ Calcule la penalización por restricción, la penalización por mala solución y la penalización total de cada punto en función del valor de la función de restricción y el resultado de la clasificación.

⑤ Calcule el grado de aptitud según el penalización total de cada punto;

p>

⑤ Calcular el grado de aptitud en función de la penalización total de cada punto

⑥ Calcular el grado de aptitud en función de la penalización total de cada punto.

⑦ Coloque los puntos con un término de penalización total de 0 en la lista de candidatos del conjunto de soluciones no inferiores, verifique la lista de candidatos, retenga los puntos de soluciones no inferiores en la primera capa y elimine otros puntos;

⑧ Compruebe si converge. Si no, vaya al paso ②;

⑨ Elimine los puntos que estén demasiado cerca de otras tiendas en la tabla de candidatos; ⑩ Salida en la tabla de candidatos del conjunto de soluciones óptimas de Pareto y el valor de la función objetivo correspondiente;

Finalmente, el tomador de decisiones selecciona la solución más adecuada al problema del conjunto de soluciones óptimas de Pareto según sus preferencias personales.

En comparación con los algoritmos tradicionales, la ventaja de los algoritmos genéticos es que pueden obtener un conjunto de soluciones óptimas en lugar de una única solución óptima, lo que proporciona más opciones, pero la complejidad computacional puede ser ligeramente mayor. y algunas de las funciones implicadas también deben diseñarse cuidadosamente.

1. Método de conversión del coeficiente de peso

A cada función objetivo fi (x) se le asigna un peso wi, que es la importancia de la función objetivo. μ = Σwi-fi(x), donde la función multiobjetivo se convierte en una función de objetivo único y μ se utiliza como función de evaluación.

2. Método de selección paralela

Pasos principales: (1) Dividir la población en varias subpoblaciones según el número de funciones objetivo y asignar una función objetivo a cada subpoblación. población. (2) Seleccione individuos en la subpoblación de acuerdo con sus respectivas funciones objetivas, seleccione individuos con alta aptitud y luego conviértalos en una subpoblación. (3) Luego, las subpoblaciones se aparean y mutan para generar la población parental de la próxima generación. Luego repita el paso uno.

La desventaja del método de selección paralela es que es fácil producir una solución óptima extrema para una única función objetivo, pero es difícil producir una solución de compromiso que tenga múltiples objetivos que sean más satisfactorios para algunos. medida.

3. Método de clasificación

La idea básica es ordenar los individuos del grupo según el concepto de "individuo óptimo de Pareto" y luego seleccionar el grupo en este orden. De esta manera, los individuos óptimos de Pareto tienen mayores posibilidades de pasar a la siguiente generación. La desventaja de este método es que sólo puede medir el orden de excelencia entre los individuos, pero no el grado de dispersión de cada individuo. Por lo tanto, es fácil producir soluciones similares en lugar de múltiples soluciones óptimas que estén más ampliamente distribuidas.

4.**** Método de función armónica

En vista de las deficiencias del método de selección de clasificación, es decir, múltiples soluciones óptimas generalmente se concentran en un área pequeña de el conjunto de soluciones óptimas, en lugar de dispersarse en todo el conjunto de soluciones óptimas de Pareto. Por lo tanto, la tecnología de nicho basada en la función * compartir (la tecnología de nicho consiste en dividir cada generación de individuos en varias categorías, seleccionar varios individuos con gran adaptabilidad en cada categoría como los mejores representantes de una categoría para formar un grupo y luego formar un La hibridación y la mutación ocurren dentro de una población y entre diferentes poblaciones para producir una nueva generación de poblaciones individuales. También se pueden utilizar mecanismos de preselección y exclusión o intercambio para realizar esta tarea. .Este algoritmo limita el número de individuos idénticos o similares para producir más soluciones óptimas diferentes. Esto plantea la pregunta: ¿Cómo se mide la similitud entre dos individuos? Esa es la cantidad de hábitats pequeños que hay. Como sugiere el nombre, un nicho es una población de individuos similares en un entorno pequeño. Las fórmulas más utilizadas son:

s(d) es la función hedónica, que es una función que representa el grado de cercanía entre dos individuos de la población. d(X,Y) es la distancia de Hanmin entre individuos X,Y y también es una función utilizada para medir la similitud entre individuos. Después de calcular el número de microhábitats, se puede concluir que los individuos con un menor número de microhábitats tienen mayores posibilidades de ser seleccionados y heredados a la población de la siguiente generación, es decir, los individuos con menor similitud tienen mayores posibilidades de ser heredados a la siguiente generación. población de próxima generación.

Desventajas: Cada operación de selección requiere una gran cantidad de evaluación y comparación de las relaciones ventajosas entre individuos, lo que hace que la eficiencia de búsqueda del algoritmo sea baja.

5. El algoritmo genético multiobjetivo de Pareto (NPGA) basado en nichos confirmado por Horn y Nafploitis

Al igual que en el segundo método de selección paralela, cada generación de individuos se divide en varias Cada clase selecciona varios individuos con mayor aptitud como los mejores representantes de una clase para formar una población, y luego se somete a apareamiento y mutación para generar una nueva generación de población. Basado en este algoritmo genético de nicho (algoritmos genéticos de nicho, NGA), puede mantener mejor la diversidad de soluciones y, al mismo tiempo, tiene altas capacidades de optimización global y velocidad de convergencia, y es especialmente adecuado para problemas de optimización de funciones multimodales complejas.

6. El algoritmo genético de clasificación no dominante NSGA de Srinvivas y Deb

Surgió en 1980. Mejoró el método de regeneración de selección basado en el algoritmo genético: cada individuo se clasifica según sus ventajas y relaciones no dominantes se reestratifican y luego se realizan operaciones de selección para lograr el objetivo.

La importancia de la estratificación es eliminar a los individuos no dominantes de la población y formar una población pequeña (la primera capa óptima no dominante), para que todos los individuos en ella puedan disfrutar de la mejor condición física virtual. valor.

Luego continúe eliminando individuos no dominantes en la población, forme una población pequeña (la segunda capa de optimización no dominante) después de la eliminación y dé a todos los individuos un valor de aptitud virtual. Repita los pasos anteriores hasta que se distribuya la población original. Esto es estratificación, también llamada clasificación no dominante.

Desventajas del algoritmo genético de clasificación no dominado: alta complejidad computacional; ② sin estrategia de élite; ③ necesidad de establecer un radio máximo de intercambio.

En respuesta a los problemas anteriores, k-Deb propuso el método 7 en 2002.

7. Método de divergencia genética de clasificación no dominada con estrategia de élite-NSGAII

1). Al utilizar una clasificación rápida no dominada, se reduce la complejidad del algoritmo. Su complejidad se reduce a O(MN**2).

2) Se proponen operadores de congestión y comparación de congestión en lugar de la estrategia adaptativa de disfrute de **** que requiere especificar el radio de disfrute de ****. Se utiliza como criterio ganador en comparaciones entre pares después de una clasificación rápida. De esta manera, los individuos en la solución cuasi-Pareto pueden expandirse a todo el campo de Pareto y distribuirse uniformemente, manteniendo la diversidad de la población.

3). Introducir la estrategia de élite y ampliar el espacio de muestreo. La combinación de poblaciones de padres e hijos garantiza que se retengan los individuos de élite.

Los pasos del algoritmo son los siguientes: 1. Primero, genere aleatoriamente una población inicial de n números y luego ordénela de manera no dominante. Luego, a partir de la segunda generación, fusione las generaciones de padres e hijos. Luego, realice una clasificación rápida no dominante sobre ellos y, simultáneamente, calcule el grado de hacinamiento de individuos en cada capa no dominante. Luego seleccione individuos adecuados para formar un nuevo grupo de padres según las relaciones no dominantes y el grado de hacinamiento. Finalmente, la descendencia se produce mediante una mayor selección, cruce y mutación. 3. A continuación, repita el paso dos.

Para más detalles, consulte: /quinn1994/article/details/80679528/