Optimización multiobjetivo - Multi-objective optimization

Optimización multi-objetivo (también conocida como la programación multi-objetivo , la optimización de vectores , la optimización multicriterio , optimización multiatributo o la optimización de Pareto ) es un área de toma de decisiones criterios múltiples que se ocupa de los problemas de optimización matemática que implica más de una función objetivo a optimizar simultáneamente . La optimización multiobjetivo se ha aplicado en muchos campos de la ciencia, incluida la ingeniería, la economía y la logística, donde se deben tomar decisiones óptimas en presencia de compensaciones entre dos o más objetivos en conflicto. Minimizar los costos mientras se maximiza la comodidad al comprar un automóvil y maximizar el rendimiento mientras se minimiza el consumo de combustible y la emisión de contaminantes de un vehículo son ejemplos de problemas de optimización multiobjetivo que involucran dos y tres objetivos, respectivamente. En problemas prácticos, puede haber más de tres objetivos.

Para un problema de optimización multiobjetivo no trivial , no existe una solución única que optimice simultáneamente cada objetivo. En ese caso, se dice que las funciones objetivas están en conflicto. Una solución se denomina no dominada , óptima de Pareto, eficiente de Pareto o no inferior, si ninguna de las funciones objetivo puede mejorarse en valor sin degradar algunos de los otros valores objetivos. Sin información adicional de preferencias subjetivas , puede existir un número (posiblemente infinito) de soluciones óptimas de Pareto, todas las cuales se consideran igualmente buenas. Los investigadores estudian los problemas de optimización multiobjetivo desde diferentes puntos de vista y, por tanto, existen distintas filosofías de solución y metas a la hora de plantearlos y resolverlos. El objetivo puede ser encontrar un conjunto representativo de soluciones óptimas de Pareto y / o cuantificar las compensaciones para satisfacer los diferentes objetivos y / o encontrar una única solución que satisfaga las preferencias subjetivas de un tomador de decisiones (DM) humano.

La optimización de bicriterios denota el caso especial en el que hay dos funciones objetivo.

Introducción

Un problema de optimización multiobjetivo es un problema de optimización que involucra múltiples funciones objetivo. En términos matemáticos, un problema de optimización multiobjetivo se puede formular como

{\ Displaystyle {\ begin {alineado} \ min & \ left (f_ {1} ({\ vec {x}}), f_ {2} ({\ vec {x}}), \ ldots, f_ {k} ({\ vec {x}}) \ right) \\ {\ text {st}} & {\ vec {x}} \ en X, \ end {alineado}}}

donde el número entero es el número de objetivos y el conjunto es el conjunto factible de vectores de decisión, que es típicamente pero depende del dominio de aplicación -dimensional. El conjunto factible generalmente se define mediante algunas funciones de restricción. Además, la función objetivo con valores vectoriales se define a menudo como ${\ Displaystyle k \ geq 2}$ ${\ Displaystyle X}$ ${\ Displaystyle X \ subseteq \ mathbb {R} ^ {n}}$ ${\ Displaystyle n}$

{\ Displaystyle {\ vec {f}}: X \ to \ mathbb {R} ^ {k}, \ {\ vec {f}} ({\ vec {x}}) = (f_ {1} ({\ vec {x}}), \ ldots, f_ {k} ({\ vec {x}})) ^ {\ intercal}}

. Si alguna función objetivo debe maximizarse, es equivalente a minimizar su negativo. La imagen de se denota por

{\ Displaystyle X}

{\ Displaystyle Y \ subseteq \ mathbb {R} ^ {k}}

Ejemplo de una frontera de Pareto (en rojo), el conjunto de soluciones óptimas de Pareto (aquellas que no están dominadas por ninguna otra solución factible). Los puntos encuadrados representan opciones factibles y se prefieren los valores más pequeños a los más grandes. Punto C no está en la frontera de Pareto, ya que está dominada por tanto el punto A y el punto B . Los puntos A y B no están estrictamente dominados por ningún otro y, por lo tanto, se encuentran en la frontera.

Un elemento se denomina solución factible o decisión factible . Un vector para una solución factible se llama vector objetivo o resultado . En la optimización multiobjetivo, normalmente no existe una solución factible que minimice todas las funciones objetivo simultáneamente. Por lo tanto, se presta atención a las soluciones óptimas de Pareto ; es decir, soluciones que no se pueden mejorar en ninguno de los objetivos sin degradar al menos uno de los otros objetivos. En términos matemáticos, se dice que una solución factible (Pareto) domina a otra solución , si ${\ Displaystyle {\ vec {x}} ^ {*} \ en X}$ ${\ Displaystyle {\ vec {z}} ^ {*}: = {\ vec {f}} ({\ vec {x}} ^ {*}) \ in \ mathbb {R} ^ {k}}$ ${\ Displaystyle {\ vec {x}} ^ {*}}$ ${\ Displaystyle {\ vec {x}} _ {1} \ en X}$ ${\ Displaystyle {\ vec {x}} _ {2} \ en X}$

${\ Displaystyle f_ {i} ({\ vec {x}} _ {1}) \ leq f_ {i} ({\ vec {x}} _ {2})}$ , para todos los índices , y ${\ Displaystyle i \ in \ left \ {{1,2, \ dots, k} \ right \}}$
${\ Displaystyle f_ {j} ({\ vec {x}} _ {1}) <f_ {j} ({\ vec {x}} _ {2})}$ , para al menos un índice . ${\ Displaystyle j \ in \ left \ {{1,2, \ dots, k} \ right \}}$

Una solución (y el resultado correspondiente ) se llama óptimo de Pareto, si no existe otra solución que la domine. El conjunto de resultados óptimos de Pareto a menudo se denomina frente de Pareto, frontera de Pareto o límite de Pareto. ${\ Displaystyle {\ vec {x}} ^ {*} \ en X}$ ${\ Displaystyle {\ vec {f}} ({\ vec {x}} ^ {*})}$

El frente de Pareto de un problema de optimización multiobjetivo está delimitado por un vector objetivo llamado nadir y un vector objetivo ideal , si son finitos. El vector objetivo nadir se define como ${\ Displaystyle {\ vec {z}} ^ {nad}}$ ${\ Displaystyle {\ vec {z}} ^ {ideal}}$

{\ Displaystyle {\ vec {z}} ^ {nad} \ ni {\ vec {z}} _ {i} ^ {nad} = {\ underset {x \ in X} {\ sup}} \ {f_ { i} (x) \} {\ text {para todos}} i = 1, \ ldots, k,}

y el vector objetivo ideal como

{\ Displaystyle {\ vec {z}} ^ {ideal} \ ni {\ vec {z}} _ {i} ^ {ideal} = {\ underset {x \ in X} {\ inf}} \ {f_ { i} (x) \} {\ text {para todos}} i = 1, \ ldots, k.}

En otras palabras, los componentes de un nadir y un vector objetivo ideal definen los límites superior e inferior para los valores de la función objetivo de las soluciones óptimas de Pareto, respectivamente. En la práctica, el vector objetivo nadir solo puede aproximarse ya que, típicamente, se desconoce todo el conjunto óptimo de Pareto. Además, un vector objetivo utópico con ${\ Displaystyle {\ vec {z}} ^ {utópico}}$

{\ Displaystyle {\ vec {z}} _ {i} ^ {utopian} = {\ vec {z}} _ {i} ^ {ideal} - \ epsilon {\ text {para todos}} i = 1, \ ldots, k,}

donde es una pequeña constante, a menudo se define debido a razones numéricas. ${\ Displaystyle \ epsilon> 0}$

Ejemplos de aplicaciones

Ciencias económicas

En economía , muchos problemas involucran múltiples objetivos junto con restricciones sobre qué combinaciones de esos objetivos son alcanzables. Por ejemplo, la demanda del consumidor de varios bienes está determinada por el proceso de maximización de las utilidades derivadas de esos bienes, sujeto a una restricción basada en la cantidad de ingresos disponibles para gastar en esos bienes y en los precios de esos bienes. Esta restricción permite comprar más de un bien sólo con el sacrificio de consumir menos de otro bien; por lo tanto, los diversos objetivos (se prefiere un mayor consumo de cada bien) están en conflicto entre sí. Un método común para analizar un problema de este tipo es utilizar un gráfico de curvas de indiferencia , que representan preferencias, y una restricción presupuestaria, que representa las compensaciones a las que se enfrenta el consumidor.

Otro ejemplo involucra la frontera de posibilidades de producción , que especifica qué combinaciones de varios tipos de bienes puede producir una sociedad con ciertas cantidades de diversos recursos. La frontera especifica las compensaciones a las que se enfrenta la sociedad: si la sociedad está utilizando plenamente sus recursos, solo se puede producir más de un bien a expensas de producir menos de otro bien. Entonces, una sociedad debe utilizar algún proceso para elegir entre las posibilidades en la frontera.

La formulación de políticas macroeconómicas es un contexto que requiere una optimización multiobjetivo. Por lo general, un banco central debe elegir una postura de política monetaria que equilibre los objetivos en competencia: baja inflación , bajo desempleo , bajo déficit en la balanza comercial , etc. Para hacer esto, el banco central utiliza un modelo de la economía que describe cuantitativamente los diversos vínculos causales en la economía; que simula el modelo en varias ocasiones en diversas posiciones posibles de la política monetaria, con el fin de obtener un menú de posibles resultados previstos para las diferentes variables de interés. Entonces, en principio, puede usar una función objetivo agregada para calificar los conjuntos alternativos de resultados previstos, aunque en la práctica los bancos centrales usan un proceso no cuantitativo, basado en juicios, para clasificar las alternativas y tomar la decisión de política.

Finanzas

En finanzas , un problema común es elegir una cartera cuando hay dos objetivos en conflicto: el deseo de que el valor esperado de los rendimientos de la cartera sea lo más alto posible y el deseo de tener riesgo , a menudo medido por la desviación estándar de los rendimientos de la cartera. , sea lo más bajo posible. Este problema a menudo se representa mediante un gráfico en el que la frontera eficiente muestra las mejores combinaciones de riesgo y rendimiento esperado que están disponibles, y en el que las curvas de indiferencia muestran las preferencias del inversor por varias combinaciones de riesgo-rendimiento esperado. El problema de optimizar una función del valor esperado (primer momento ) y la desviación estándar (raíz cuadrada del segundo momento central) del rendimiento de la cartera se denomina modelo de decisión de dos momentos .

Control optimo

En ingeniería y economía , muchos problemas involucran múltiples objetivos que no pueden describirse como cuanto más, mejor o menos, mejor; en cambio, existe un valor objetivo ideal para cada objetivo, y el deseo es acercarse lo más posible al valor deseado de cada objetivo. Por ejemplo, los sistemas de energía suelen tener un equilibrio entre rendimiento y costo, o uno podría querer ajustar el uso y la orientación de combustible de un cohete para que llegue tanto a un lugar específico como en un momento específico; o se podría querer realizar operaciones de mercado abierto para que tanto la tasa de inflación como la tasa de desempleo estén lo más cerca posible de sus valores deseados.

A menudo, estos problemas están sujetos a restricciones de igualdad lineal que impiden que todos los objetivos se cumplan de manera simultánea y perfecta, especialmente cuando el número de variables controlables es menor que el número de objetivos y cuando la presencia de choques aleatorios genera incertidumbre. Comúnmente se usa una función de objetivo cuadrático de múltiples objetivos , con el costo asociado con un objetivo aumentando cuadráticamente con la distancia del objetivo de su valor ideal. Dado que estos problemas implican típicamente ajustar las variables controladas en varios puntos en el tiempo y / o evaluar los objetivos en varios puntos en el tiempo, se emplean técnicas de optimización intertemporal .

Diseño optimo

El diseño de productos y procesos se puede mejorar en gran medida utilizando técnicas modernas de modelado, simulación y optimización. La pregunta clave en un diseño óptimo es la medida de lo bueno o deseable de un diseño. Antes de buscar diseños óptimos, es importante identificar las características que más contribuyen al valor general del diseño. Un buen diseño generalmente involucra múltiples criterios / objetivos tales como costo de capital / inversión, costo operativo, beneficio, calidad y / o recuperación del producto, eficiencia, seguridad del proceso, tiempo de operación, etc. Por lo tanto, en aplicaciones prácticas, el desempeño del proceso y El diseño del producto a menudo se mide con respecto a múltiples objetivos. Por lo general, estos objetivos son contradictorios, es decir, lograr el valor óptimo para un objetivo requiere algún compromiso con uno o más de otros objetivos.

Por ejemplo, al diseñar una fábrica de papel, se puede buscar disminuir la cantidad de capital invertido en una fábrica de papel y mejorar la calidad del papel simultáneamente. Si el diseño de una fábrica de papel se define por grandes volúmenes de almacenamiento y la calidad del papel se define por parámetros de calidad, entonces el problema del diseño óptimo de una fábrica de papel puede incluir objetivos tales como: i) minimización de la variación esperada de esos parámetros de calidad de su valores nominales, ii) minimización del tiempo esperado de pausas y iii) minimización del costo de inversión de los volúmenes de almacenamiento. Aquí, el volumen máximo de torres son variables de diseño. Este ejemplo de diseño óptimo de una fábrica de papel es una simplificación del modelo utilizado en. La optimización del diseño multiobjetivo también se ha implementado en sistemas de ingeniería en circunstancias tales como la optimización del diseño del gabinete de control, la optimización de la forma de la superficie aerodinámica utilizando flujos de trabajo científicos, el diseño de nano- Semiconductores CMOS , diseño de sistema en chip , diseño de sistemas de riego con energía solar, optimización de sistemas de moldes de arena, diseño de motores, despliegue óptimo del sensor y diseño óptimo del controlador.

Optimización de procesos

La optimización multiobjetivo se ha empleado cada vez más en la ingeniería química y la fabricación . En 2009, Fiandaca y Fraga utilizaron el algoritmo genético multiobjetivo (MOGA) para optimizar el proceso de adsorción por oscilación de presión (proceso de separación cíclica). El problema de diseño implicó la maximización dual de la recuperación de nitrógeno y la pureza del nitrógeno. Los resultados proporcionaron una buena aproximación de la frontera de Pareto con compensaciones aceptables entre los objetivos.

En 2010, Sendín et al. resolvió un problema multiobjetivo para el procesamiento térmico de alimentos. Abordaron dos estudios de caso (problemas biobjetivo y triple objetivo) con modelos dinámicos no lineales y utilizaron un enfoque híbrido que consistía en el enfoque ponderado de Tchebycheff y el enfoque de intersección de límites normales. El nuevo enfoque híbrido pudo construir un conjunto óptimo de Pareto para el procesamiento térmico de alimentos.

En 2013, Ganesan et al. llevó a cabo la optimización multiobjetivo del reformado combinado de dióxido de carbono y la oxidación parcial del metano. Las funciones objetivo fueron conversión de metano, selectividad de monóxido de carbono y relación de hidrógeno a monóxido de carbono. Ganesan utilizó el método de intersección de límites normales (NBI) junto con dos técnicas basadas en enjambres (algoritmo de búsqueda gravitacional (GSA) y optimización de enjambres de partículas (PSO)) para abordar el problema. Las aplicaciones que implican la extracción química y los procesos de producción de bioetanol han planteado problemas multiobjetivos similares.

En 2013, Abakarov et al propusieron una técnica alternativa para resolver los problemas de optimización multiobjetivo que surgen en la ingeniería alimentaria. El enfoque de funciones agregadas, el algoritmo de búsqueda aleatoria adaptativa y el enfoque de funciones de penalización se utilizaron para calcular el conjunto inicial de soluciones no dominadas o óptimas de Pareto. El proceso de jerarquía analítica y el método tabular se utilizaron simultáneamente para elegir la mejor alternativa entre el subconjunto calculado de soluciones no dominadas para los procesos de deshidratación osmótica.

En 2018, Pearce et al. formuló la asignación de tareas a trabajadores humanos y robóticos como un problema de optimización multiobjetivo, considerando el tiempo de producción y el impacto ergonómico en el trabajador humano como los dos objetivos considerados en la formulación. Su enfoque utilizó un programa lineal de enteros mixtos para resolver el problema de optimización para una suma ponderada de los dos objetivos para calcular un conjunto de soluciones óptimas de Pareto . La aplicación del enfoque a varias tareas de fabricación mostró mejoras en al menos un objetivo en la mayoría de las tareas y en ambos objetivos en algunos de los procesos.

Gestión de recursos de radio

El propósito de la gestión de recursos de radio es satisfacer las velocidades de datos que solicitan los usuarios de una red celular. Los principales recursos son los intervalos de tiempo, los bloques de frecuencia y las potencias de transmisión. Cada usuario tiene su propia función objetivo que, por ejemplo, puede representar alguna combinación de velocidad de datos, latencia y eficiencia energética. Estos objetivos son contradictorios ya que los recursos de frecuencia son muy escasos, por lo que existe la necesidad de una reutilización de frecuencias espacial estricta que causa una inmensa interferencia entre usuarios si no se controla adecuadamente. Las técnicas MIMO multiusuario se utilizan hoy en día para reducir la interferencia mediante la precodificación adaptativa . Al operador de red le gustaría brindar una gran cobertura y altas velocidades de datos, por lo que el operador le gustaría encontrar una solución óptima de Pareto que equilibre el rendimiento total de datos de la red y la equidad del usuario de una manera subjetiva adecuada.

La gestión de recursos de radio a menudo se resuelve mediante la escalarización; es decir, la selección de una función de utilidad de red que intenta equilibrar el rendimiento y la equidad del usuario. La elección de la función de utilidad tiene un gran impacto en la complejidad computacional del problema de optimización de objetivo único resultante. Por ejemplo, la utilidad común de la tasa de suma ponderada da un problema NP-difícil con una complejidad que escala exponencialmente con el número de usuarios, mientras que la utilidad de equidad máxima-mínima ponderada da como resultado un problema de optimización cuasi-convexo con solo una escala polinomial con el número de usuarios.

Sistemas de energía eléctrica

La reconfiguración, mediante el intercambio de enlaces funcionales entre los elementos del sistema, representa una de las medidas más importantes que pueden mejorar el rendimiento operativo de un sistema de distribución. El problema de la optimización mediante la reconfiguración de un sistema de distribución de energía, en términos de su definición, es un problema histórico único objetivo con restricciones. Desde 1975, cuando Merlin y Back introdujeron la idea de la reconfiguración del sistema de distribución para la reducción activa de la pérdida de potencia, hasta la actualidad, muchos investigadores han propuesto diversos métodos y algoritmos para resolver el problema de la reconfiguración como un problema de objetivo único. Algunos autores han propuesto enfoques basados en la optimización de Pareto (que incluyen pérdidas de potencia activa e índices de confiabilidad como objetivos). Para ello, se han utilizado diferentes métodos basados en inteligencia artificial: microgenético, intercambio de ramas, optimización de enjambres de partículas y algoritmo genético de clasificación no dominado.

Inspección de infraestructura

La inspección autónoma de la infraestructura tiene el potencial de reducir costos, riesgos e impactos ambientales, además de garantizar un mejor mantenimiento periódico de los activos inspeccionados. Por lo general, la planificación de tales misiones se ha visto como un problema de optimización de un solo objetivo, donde uno apunta a minimizar la energía o el tiempo invertido en inspeccionar una estructura objetivo completa. Sin embargo, para estructuras complejas del mundo real, cubrir el 100% de un objetivo de inspección no es factible, y la generación de un plan de inspección puede verse mejor como un problema de optimización multiobjetivo, donde uno apunta tanto a maximizar la cobertura de inspección como a minimizar el tiempo y los costos. Un estudio reciente ha indicado que la planificación de inspecciones multiobjetivo tiene el potencial de superar a los métodos tradicionales en estructuras complejas.

Solución

Como normalmente existen múltiples soluciones óptimas de Pareto para problemas de optimización multiobjetivo, lo que significa resolver un problema de este tipo no es tan sencillo como lo es para un problema de optimización de objetivo único convencional. Por ello, diferentes investigadores han definido el término "resolución de un problema de optimización multiobjetivo" de diversas formas. Esta sección resume algunos de ellos y los contextos en los que se utilizan. Muchos métodos convierten el problema original con múltiples objetivos en un problema de optimización de un solo objetivo . A esto se le llama problema escalarizado. Si se puede garantizar la optimización de Pareto de las soluciones de un solo objetivo obtenidas, la escalarización se caracteriza como hecha de manera ordenada.

La resolución de un problema de optimización multiobjetivo a veces se entiende como la aproximación o el cálculo de todas o un conjunto representativo de soluciones óptimas de Pareto.

Cuando se enfatiza la toma de decisiones , el objetivo de resolver un problema de optimización multiobjetivo se refiere a ayudar al tomador de decisiones a encontrar la solución óptima de Pareto más preferida de acuerdo con sus preferencias subjetivas. El supuesto subyacente es que se debe identificar una solución al problema para implementarla en la práctica. Aquí, un tomador de decisiones (DM) humano juega un papel importante. Se espera que el DM sea un experto en el dominio del problema.

Los resultados más preferidos se pueden encontrar utilizando diferentes filosofías. Los métodos de optimización multiobjetivo se pueden dividir en cuatro clases.

En los llamados métodos sin preferencia , no se espera que haya DM disponible, pero se identifica una solución de compromiso neutral sin información de preferencia. Las otras clases son métodos llamados a priori, a posteriori e interactivos y todos involucran información de preferencias del DM de diferentes maneras.
En los métodos a priori , primero se solicita al DM información sobre preferencias y luego se encuentra una solución que satisfaga mejor estas preferencias.
En los métodos a posteriori , primero se encuentra un conjunto representativo de soluciones óptimas de Pareto y luego el DM debe elegir una de ellas.
En los métodos interactivos , el tomador de decisiones puede buscar iterativamente la solución más preferida. En cada iteración del método interactivo, el DM se muestra la (s) solución (es) óptima (es) de Pareto y describe cómo la (s) solución (es) podrían mejorarse. La información proporcionada por el tomador de decisiones se toma en cuenta mientras se generan nuevas soluciones óptimas de Pareto para que el DM las estudie en la siguiente iteración. De esta forma, el DM aprende sobre la viabilidad de sus deseos y puede concentrarse en las soluciones que le interesan. El DM puede detener la búsqueda cuando quiera.

En las siguientes secciones se proporcionan más información y ejemplos de diferentes métodos en las cuatro clases.

Métodos sin preferencia

Cuando un tomador de decisiones no articula explícitamente ninguna información de preferencia, el método de optimización multiobjetivo puede clasificarse como método sin preferencia. Un ejemplo bien conocido es el método de criterio global, en el que un problema escalarizado de la forma

{\ Displaystyle {\ begin {alineado} \ min & \ | f (x) -z ^ {ideal} \ | \\ {\ text {st}} & x \ in X \ end {alineado}}}

está resuelto. En el problema anterior, puede haber cualquier norma , con opciones comunes que incluyen , y . El método de criterio global es sensible a la escala de las funciones objetivo, por lo que se recomienda que los objetivos se normalicen en una escala uniforme y adimensional. ${\ Displaystyle \ | \ cdot \ |}$ ${\ Displaystyle L_ {p}}$ ${\ Displaystyle L_ {1}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L _ {\ infty}}$

Métodos a priori

Los métodos a priori requieren que se exprese suficiente información de preferencia antes del proceso de solución. Los ejemplos más conocidos de métodos a priori incluyen el método de función de utilidad , lexicográfico método, y la programación de metas .

En el método de la función de utilidad, se supone que está disponible la función de utilidad del tomador de decisiones . Una asignación es una función de utilidad si para todo si se sostiene que si el tomador de decisiones prefiere a , y si el tomador de decisiones es indiferente entre y . La función de utilidad especifica un orden de los vectores de decisión (recuerde que los vectores se pueden ordenar de muchas formas diferentes). Una vez obtenido, basta con resolver ${\ Displaystyle u \ colon Y \ rightarrow \ mathbb {R}}$ ${\ Displaystyle \ mathbf {y} ^ {1}, \ mathbf {y} ^ {2} \ in Y}$ ${\ Displaystyle u (\ mathbf {y} ^ {1})> u (\ mathbf {y} ^ {2})}$ ${\ Displaystyle \ mathbf {y} ^ {1}}$ ${\ Displaystyle \ mathbf {y} ^ {2}}$ ${\ Displaystyle u (\ mathbf {y} ^ {1}) = u (\ mathbf {y} ^ {2})}$ ${\ Displaystyle \ mathbf {y} ^ {1}}$ ${\ Displaystyle \ mathbf {y} ^ {2}}$ ${\ Displaystyle u}$

{\ Displaystyle \ max \; u (\ mathbf {f} (\ mathbf {x})) {\ text {sujeto a}} \ mathbf {x} \ in X,}

pero en la práctica es muy difícil construir una función de utilidad que represente con precisión las preferencias del tomador de decisiones, particularmente porque el frente de Pareto se desconoce antes de que comience la optimización.

El método lexicográfico asume que los objetivos se pueden clasificar en orden de importancia. Podemos suponer, sin pérdida de generalidad, que las funciones objetivo están en el orden de importancia por lo que es el más importante y el menos importante para quien toma las decisiones. El método lexicográfico consiste en resolver una secuencia de problemas de optimización de un solo objetivo de la forma ${\ Displaystyle f_ {1}}$ ${\ Displaystyle f_ {k}}$

{\ Displaystyle {\ begin {alineado} \ min & f_ {l} (\ mathbf {x}) \\ {\ text {st}} & f_ {j} (\ mathbf {x}) \ leq \ mathbf {y} _ {j} ^ {*}, \; j = 1, \ dotsc, l-1, \\ & \ mathbf {x} \ in X, \ end {alineado}}}

donde es el valor óptimo del problema anterior con . Por lo tanto, y cada nuevo problema de la forma en el problema anterior en la secuencia agrega una nueva restricción a medida que va de a . Tenga en cuenta que aquí no se especifica una meta o un valor objetivo para ningún objetivo, lo que lo hace diferente del método de programación de metas lexicográficas . ${\ Displaystyle \ mathbf {y} _ {j} ^ {*}}$ ${\ Displaystyle l = j}$ ${\ Displaystyle \ mathbf {y} _ {1} ^ {*}: = \ min \ {f_ {1} (\ mathbf {x}) \ mid \ mathbf {x} \ in X \}}$ ${\ Displaystyle l}$ ${\ Displaystyle 1}$ ${\ Displaystyle k}$

Escalarizar

Escalarizar un problema de optimización multiobjetivo es un método a priori, lo que significa formular un problema de optimización de un solo objetivo de modo que las soluciones óptimas para el problema de optimización de un solo objetivo sean soluciones óptimas de Pareto para el problema de optimización de múltiples objetivos. Además, a menudo se requiere que se pueda alcanzar cada solución óptima de Pareto con algunos parámetros de la escalarización. Con diferentes parámetros para la escalarización, se producen diferentes soluciones óptimas de Pareto. Por tanto, una formulación general para la escalarización de una optimización multiobjetivo es

{\ Displaystyle {\ begin {array} {ll} \ min & g (f_ {1} (x), \ ldots, f_ {k} (x), \ theta) \\ {\ text {st}} x \ in X _ {\ theta}, \ end {matriz}}}

donde es un parámetro vectorial, el conjunto es un conjunto en función del parámetro y es una función. ${\ Displaystyle \ theta}$ ${\ Displaystyle X _ {\ theta} \ subseteq X}$ ${\ Displaystyle \ theta}$ ${\ Displaystyle g: \ mathbb {R} ^ {k + 1} \ rightarrow \ mathbb {R}}$

Ejemplos muy conocidos son los llamados

escalarización lineal

{\ Displaystyle \ min _ {x \ in X} \ sum _ {i = 1} ^ {k} w_ {i} f_ {i} (x),}

donde los pesos de los objetivos son los parámetros de la escalarización, y la

{\ Displaystyle w_ {i}> 0}

${\ Displaystyle \ epsilon}$ -método de restricción (ver, por ejemplo)

{\ Displaystyle {\ begin {array} {ll} \ min & f_ {j} (x) \\ {\ text {st}} & x \ in X \\ & f_ {i} (x) \ leq \ epsilon _ {i } {\ text {para}} i \ in \ {1, \ ldots, k \} \ setminus \ {j \}, \ end {array}}}

donde los límites superiores son parámetros como arriba y es el objetivo a minimizar.

{\ Displaystyle \ epsilon _ {j}}

{\ Displaystyle f_ {j}}

Ejemplos algo más avanzados son:

problemas de escalarización de logros de Wierzbicki . Un ejemplo de los problemas de escalarización de logros se puede formular como

{\ Displaystyle {\ begin {array} {ll} \ min & \ max _ {i = 1, \ ldots, k} \ left [{\ frac {f_ {i} (x) - {\ bar {z}} " _ {i}} {z_ {i} ^ {\ text {nad}} - z_ {i} ^ {\ text {utopian}}}} \ right] + \ rho \ sum _ {i = 1} ^ {k } {\ frac {f_ {i} (x)} {z_ {i} ^ {nad} -z_ {i} ^ {\ text {utopian}}}} \\ {\ text {sujeto a}} & x \ in S, \ end {matriz}}}

donde el término se llama término de aumento, es una pequeña constante, y y son los vectores nadir y utópico , respectivamente. En el problema anterior, el parámetro es el llamado punto de referencia que representa los valores de la función objetivo preferidos por el tomador de decisiones.

{\ Displaystyle \ rho \ sum _ {i = 1} ^ {k} {\ frac {f_ {i} (x)} {z_ {i} ^ {nad} -z_ {i} ^ {\ text {utopian} }}}}

{\ Displaystyle \ rho> 0}

{\ Displaystyle z ^ {\ text {nad}}}

{\ Displaystyle z ^ {\ text {utópico}}}

{\ Displaystyle {\ bar {z}}}

Programación multiobjetivo de Sen

{\ Displaystyle {\ begin {array} {ll} \ max & {\ frac {\ sum _ {j = 1} ^ {r} Z_ {j}} {W_ {j}}} - {\ frac {\ sum _ {j = r + 1} ^ {s} Z_ {j}} {W_ {r + 1}}} \\ {\ text {st}} & AX = b \\ & X \ geq 0, \ end {array} }}

donde es optima individuo (absoluta) para objetivos de maximización y minimización a .

{\ Displaystyle W_ {j}}

{\ Displaystyle r}

{\ Displaystyle r + 1}

{\ Displaystyle s}

Por ejemplo, la optimización de la cartera se realiza a menudo en términos de análisis de varianza media . En este contexto, el conjunto eficiente es un subconjunto de las carteras parametrizadas por el rendimiento medio de la cartera en el problema de elegir las acciones de la cartera para minimizar la varianza de la rentabilidad de la cartera sujeta a un valor dado de ; consulte el teorema de separación de fondos mutuos para obtener más detalles. Alternativamente, el conjunto eficiente puede especificarse eligiendo las acciones de la cartera para maximizar la función ; el conjunto de carteras eficientes consta de las soluciones ya que b varía de cero a infinito. ${\ Displaystyle \ mu _ {P}}$ ${\ Displaystyle \ sigma _ {P}}$ ${\ Displaystyle \ mu _ {P}}$ ${\ Displaystyle \ mu _ {P} -b \ sigma _ {P}}$

Métodos a posteriori

Los métodos a posteriori tienen como objetivo producir todas las soluciones óptimas de Pareto o un subconjunto representativo de las soluciones óptimas de Pareto. La mayoría de los métodos a posteriori pertenecen a una de las dos clases siguientes:

Programación matemática: métodos a posteriori, donde un algoritmo se repite y cada ejecución del algoritmo produce una solución óptima de Pareto;
Algoritmos evolutivos donde una ejecución del algoritmo produce un conjunto de soluciones óptimas de Pareto.

Ejemplos bien conocidos de métodos a posteriori basados en programación matemática son los métodos de Intersección de límite normal (NBI), Intersección de límite normal modificado (NBIm) Restricción normal (NC), Optimización de Pareto sucesiva (SPO) y Dominio de búsqueda dirigida (DSD) que resuelven el problema de optimización multiobjetivo mediante la construcción de varias escalarizaciones. La solución para cada escalarización produce una solución óptima de Pareto, ya sea local o globalmente. Las escalarizaciones de los métodos NBI, NBIm, NC y DSD se construyen con el objetivo de obtener puntos de Pareto distribuidos uniformemente que den una buena aproximación distribuida uniformemente del conjunto real de puntos de Pareto.

Los algoritmos evolutivos son enfoques populares para generar soluciones óptimas de Pareto a un problema de optimización multiobjetivo. Actualmente, la mayoría de los algoritmos evolutivos de optimización multiobjetivo (EMO) aplican esquemas de clasificación basados en Pareto. Los algoritmos evolutivos como el Algoritmo Genético de Clasificación No Dominado-II (NSGA-II) y el Algoritmo Evolutivo Pareto de Fuerza 2 (SPEA-2) se han convertido en enfoques estándar, aunque algunos esquemas basados en la optimización del enjambre de partículas y el recocido simulado son significativos. La principal ventaja de los algoritmos evolutivos, cuando se aplican para resolver problemas de optimización multiobjetivo, es el hecho de que normalmente generan conjuntos de soluciones, lo que permite calcular una aproximación de todo el frente de Pareto. La principal desventaja de los algoritmos evolutivos es su menor velocidad y no se puede garantizar la optimización de Pareto de las soluciones. Solo se sabe que ninguna de las soluciones generadas domina a las demás.

Recientemente se mejoró otro paradigma para la optimización multiobjetivo basado en la novedad utilizando algoritmos evolutivos. Este paradigma busca soluciones novedosas en el espacio objetivo (es decir, búsqueda de novedad en el espacio objetivo) además de la búsqueda de soluciones no dominadas. La búsqueda de novedades es como peldaños que guían la búsqueda a lugares previamente inexplorados. Es especialmente útil para superar sesgos y mesetas, así como para guiar la búsqueda en problemas de optimización de muchos objetivos.

Los métodos a posteriori comúnmente conocidos se enumeran a continuación:

método de restricciones ε
Ramificación y límite de objetivos múltiples
Intersección de límite normal (NBI)
Intersección de límite normal modificada (NBIm) Restricción normal (NC),
Optimización de Pareto sucesiva (SPO)
Dominio de búsqueda dirigida (DSD)
NSGA-II
PGEN (generación de superficie de Pareto para instancias convexas multiobjetivo)
IOSO (Optimización indirecta sobre la base de la autoorganización )
SMS-EMOA (algoritmo multiobjetivo evolutivo de selección S-métrica)
Evolución guiada por aproximación (primer algoritmo para implementar y optimizar directamente el concepto formal de aproximación de la informática teórica)
Optimización de búsqueda reactiva (utilizando el aprendizaje automático para adaptar estrategias y objetivos), implementada en LIONsolver
Algoritmo de Benson para múltiples programas objetivos lineales y para múltiples programas objetivos convexos
Optimización del enjambre de partículas multiobjetivo
Algoritmo de subpoblación basado en la novedad

Métodos interactivos

En los métodos interactivos para optimizar múltiples problemas objetivos, el proceso de solución es iterativo y el tomador de decisiones interactúa continuamente con el método cuando busca la solución más preferida (ver, por ejemplo, Miettinen 1999, Miettinen 2008). En otras palabras, se espera que el tomador de decisiones exprese preferencias en cada iteración para obtener soluciones óptimas de Pareto que sean de interés para el tomador de decisiones y aprender qué tipo de soluciones son alcanzables.

Los siguientes pasos suelen estar presentes en los métodos interactivos de optimización:

inicializar (por ejemplo, calcular los vectores objetivo nadir ideales y aproximados y mostrarlos al tomador de decisiones)
generar un punto de partida óptimo de Pareto (utilizando, por ejemplo, algún método o solución sin preferencia dada por el tomador de decisiones)
solicitar información de preferencia del tomador de decisiones (por ejemplo, niveles de aspiración o número de nuevas soluciones que se generarán)
generar nuevas soluciones óptimas de Pareto de acuerdo con las preferencias y mostrarlas y posiblemente alguna otra información sobre el problema al tomador de decisiones
Si se generaron varias soluciones, solicite al tomador de decisiones que seleccione la mejor solución hasta el momento.
detenerse (si la persona que toma las decisiones lo desea; de lo contrario, vaya al paso 3).

Los niveles de aspiración anteriores se refieren a valores de función objetivo deseables que forman un punto de referencia. En lugar de la convergencia matemática que a menudo se utiliza como criterio de detención en los métodos de optimización matemática , a menudo se enfatiza una convergencia psicológica en los métodos interactivos. En términos generales, un método finaliza cuando el responsable de la toma de decisiones está seguro de haber encontrado la solución más preferida disponible .

Tipos de información de preferencias

Existen diferentes métodos interactivos que involucran diferentes tipos de información de preferencias. Tres de esos tipos pueden identificarse basándose en

información de compensación,
puntos de referencia y
clasificación de funciones objetivas.

Por otro lado, se incluye un cuarto tipo de generación de una pequeña muestra de soluciones: un ejemplo de método interactivo que utiliza información de compensación es el método de Zionts-Wallenius , donde al tomador de decisiones se le muestran varias compensaciones objetivas en cada iteración, y se espera que diga si le gusta, no le gusta o es indiferente con respecto a cada compensación. En los métodos basados en puntos de referencia (ver p. Ej.), Se espera que el tomador de decisiones en cada iteración especifique un punto de referencia que consta de valores deseados para cada objetivo y luego se calcula la solución o soluciones óptimas de Pareto correspondientes y se le muestra para su análisis. . En los métodos interactivos basados en la clasificación, se asume que el tomador de decisiones da preferencias en la forma de clasificar los objetivos en la solución óptima de Pareto actual en diferentes clases que indican cómo se deben cambiar los valores de los objetivos para obtener una solución más preferida. Luego, la información de clasificación proporcionada se tiene en cuenta cuando se calculan nuevas (más preferidas) soluciones óptimas de Pareto. En el método de compensación satisfactoria (STOM) se utilizan tres clases: objetivos cuyos valores 1) deben mejorarse, 2) pueden relajarse y 3) son aceptables como tales. En el método NIMBUS, también se utilizan dos clases adicionales: los objetivos cuyos valores 4) deben mejorarse hasta un límite dado y 5) se pueden relajar hasta un límite dado.

Métodos híbridos

Existen diferentes métodos híbridos , pero aquí consideramos hibridar MCDM ( toma de decisiones multicriterio ) y EMO (optimización evolutiva multiobjetivo). Un algoritmo híbrido en el contexto de la optimización multiobjetivo es una combinación de algoritmos / enfoques de estos dos campos (ver p. Ej.). Los algoritmos híbridos de EMO y MCDM se utilizan principalmente para superar las deficiencias utilizando fortalezas. Se han propuesto varios tipos de algoritmos híbridos en la literatura, por ejemplo, incorporar enfoques MCDM en algoritmos EMO como un operador de búsqueda local y llevar a un DM a la (s) solución (es) más preferidas, etc. Un operador de búsqueda local se utiliza principalmente para mejorar la tasa. de convergencia de algoritmos EMO.

Las raíces de la optimización híbrida multiobjetivo se remontan al primer seminario de Dagstuhl organizado en noviembre de 2004 (ver aquí ). Aquí, algunas de las mejores mentes en EMO (profesor Kalyanmoy Deb, profesor Jürgen Branke, etc.) y MCDM (profesora Kaisa Miettinen, profesor Ralph E. Steuer, etc.) se dieron cuenta del potencial de combinar ideas y enfoques de los campos MCDM y EMO para preparar híbridos. de ellos. Posteriormente, se organizaron muchos más seminarios Dagstuhl para fomentar la colaboración. Recientemente, la optimización híbrida multiobjetivo se ha convertido en un tema importante en varias conferencias internacionales en el área de EMO y MCDM (ver por ejemplo)

Visualización del frente de Pareto

La visualización del frente de Pareto es una de las técnicas de preferencia a posteriori de optimización multiobjetivo. Las técnicas de preferencia a posteriori proporcionan una clase importante de técnicas de optimización multiobjetivo. Por lo general, las técnicas de preferencia a posteriori incluyen cuatro pasos: (1) la computadora se aproxima al frente de Pareto, es decir, el conjunto óptimo de Pareto en el espacio objetivo; (2) el tomador de decisiones estudia la aproximación del frente de Pareto; (3) el tomador de decisiones identifica el punto preferido en el frente de Pareto; (4) la computadora proporciona la decisión óptima de Pareto, cuyo resultado coincide con el punto objetivo identificado por el tomador de decisiones. Desde el punto de vista del decisor, el segundo paso de las técnicas de preferencia a posteriori es el más complicado. Hay dos enfoques principales para informar al tomador de decisiones. En primer lugar, se pueden proporcionar una serie de puntos del frente de Pareto en forma de una lista (se dan referencias y discusiones interesantes en) o usando Heatmaps.

Visualización en problemas biobjetivos: curva de compensación

En el caso de problemas biobjetivos, informar al tomador de decisiones sobre el frente de Pareto generalmente se lleva a cabo mediante su visualización: el frente de Pareto, a menudo denominado curva de compensación en este caso, se puede dibujar en el plano objetivo. La curva de compensación brinda información completa sobre los valores objetivos y las compensaciones objetivas, que informan cómo la mejora de un objetivo se relaciona con el deterioro del segundo mientras se mueve a lo largo de la curva de compensación. El tomador de decisiones tiene en cuenta esta información al especificar el punto objetivo óptimo de Pareto preferido. La idea de aproximar y visualizar el frente de Pareto fue introducida para problemas de decisión lineal biobjetivo por S.Gass y T.Saaty. Esta idea fue desarrollada y aplicada en problemas ambientales por JL Cohon. En.

Visualización en problemas de optimización multiobjetivo de alto orden

Hay dos ideas genéricas sobre cómo visualizar el frente de Pareto en problemas de decisión multiobjetivo de alto orden (problemas con más de dos objetivos). Uno de ellos, que es aplicable en el caso de un número relativamente pequeño de puntos objetivos que representan el frente de Pareto, se basa en utilizar las técnicas de visualización desarrolladas en estadística (varios diagramas, etc. - ver el subsección correspondiente más abajo). La segunda idea propone la visualización de secciones transversales (cortes) biobjetivo del frente de Pareto. Fue introducido por WS Meisel en 1973, quien argumentó que tales porciones informan al tomador de decisiones sobre compensaciones objetivas. Las figuras que muestran una serie de cortes bi-objetivo del frente de Pareto para problemas de tres objetivos se conocen como mapas de decisión. Dan una imagen clara de las compensaciones entre tres criterios. Las desventajas de tal enfoque están relacionadas con dos hechos siguientes. Primero, los procedimientos computacionales para construir los cortes biobjetivos del frente de Pareto no son estables ya que el frente de Pareto generalmente no es estable. En segundo lugar, es aplicable en el caso de solo tres objetivos. En la década de 1980, la idea de WS Meisel se implementó en una forma diferente, en la forma de la técnica Interactive Decision Maps (IDM). Más recientemente, N. Wesner propuso utilizar una combinación de un diagrama de Venn y múltiples vistas de diagramas de dispersión del espacio objetivo para la exploración de la frontera de Pareto y la selección de soluciones óptimas.

Languages

In other projects