Optimització multiobjectiu

L'optimització multiobjectiu o optimització de Pareto (també coneguda com a programació multiobjectiu, optimització vectorial, optimització multicriteri o optimització multiatribut) és una àrea de la presa de decisions de múltiples criteris que s'ocupa de problemes d'optimització matemàtica que impliquen més d'una funció objectiu que s'ha d'optimitzar simultàniament. L'optimització multiobjectiu és un tipus d'optimització vectorial que s'ha aplicat en molts camps de la ciència, com ara l'enginyeria, l'economia i la logística, on cal prendre decisions òptimes en presència de compromisos entre dos o més objectius en conflicte. Minimitzar el cost alhora que es maximitza la comoditat en comprar un cotxe, i maximitzar el rendiment alhora que es minimitza el consum de combustible i l'emissió de contaminants d'un vehicle són exemples de problemes d'optimització multiobjectiu que impliquen dos i tres objectius, respectivament. En problemes pràctics, hi pot haver més de tres objectius.

Per a un problema d'optimització multiobjectiu, no es garanteix que una sola solució optimitzi simultàniament cada objectiu. Es diu que les funcions objectiu són contradictòries. Una solució s'anomena no dominada, òptima de Pareto, eficient de Pareto o no inferior si cap de les funcions objectiu es pot millorar en valor sense degradar alguns dels altres valors objectius. Sense informació addicional de preferències subjectives, pot existir un nombre (possiblement infinit) de solucions òptimes de Pareto, totes les quals es consideren igualment bones. Els investigadors estudien els problemes d'optimització multiobjectiu des de diferents punts de vista i, per tant, existeixen diferents filosofies i objectius de solució a l'hora d'establir-los i resoldre'ls. L'objectiu pot ser trobar un conjunt representatiu de solucions òptimes de Pareto i/o quantificar els compromisos per satisfer els diferents objectius i/o trobar una única solució que satisfaci les preferències subjectives d'un responsable de la presa de decisions (DM).

L'optimització bicriterial denota el cas especial en què hi ha dues funcions objectives.

Hi ha una relació directa entre l'optimització multitasca i l'optimització multiobjectiu.^[1]

Un problema d'optimització multiobjectiu és un problema d'optimització que implica múltiples funcions objectives.^[2][3][4] En termes matemàtics, un problema d'optimització multiobjectiu es pot formular com

${\displaystyle \min _{x\in X}(f_{1}(x),f_{2}(x),\ldots ,f_{k}(x))}$

on l'enter ${\displaystyle k\geq 2}$ és el nombre d'objectius i el conjunt ${\displaystyle X}$ és el conjunt factible de vectors de decisió, que normalment és ${\displaystyle X\subseteq \mathbb {R} ^{n}}$ però depèn de la ${\displaystyle n}$ domini d'aplicació de dimensió quadrada. El conjunt factible es defineix normalment per algunes funcions de restricció. A més, la funció objectiu amb valors vectorials sovint es defineix com

${\displaystyle {\begin{aligned}f:X&\to \mathbb {R} ^{k}\\x&\mapsto {\begin{pmatrix}f_{1}(x)\\\vdots \\f_{k}(x)\end{pmatrix}}\end{aligned}}}$

Si s'ha de maximitzar alguna funció objectiu, és equivalent a minimitzar el seu negatiu o la seva inversa. Denotem ${\displaystyle Y\subseteq \mathbb {R} ^{k}}$ la imatge de ${\displaystyle X}$ ; ${\displaystyle x^{*}\in X}$ una solució o decisió factible; i ${\displaystyle z^{*}=f(x^{*})\in \mathbb {R} ^{k}}$

${\displaystyle z^{*}=f(x^{*})\in \mathbb {R} ^{k}}$ un vector objectiu o un resultat.

En l'optimització multiobjectiu, no sol existir una solució factible que minimitzi totes les funcions objectiu simultàniament. Per tant, es presta atenció a les solucions òptimes de Pareto; és a dir, solucions que no es poden millorar en cap dels objectius sense degradar almenys un dels altres objectius. En termes matemàtics, una solució factible ${\displaystyle x_{1}\in X}$ es diu que (Pareto) domina una altra solució ${\displaystyle x_{2}\in X}$

${\displaystyle x_{2}\in X}$, si

1. ${\displaystyle \forall i\in \{1,\dots ,k\},f_{i}(x_{1})\leq f_{i}(x_{2})}$, and
2. ${\displaystyle \exists i\in \{1,\dots ,k\},f_{i}(x_{1})<f_{i}(x_{2})}$.

Una solució ${\displaystyle x^{*}\in X}$ (i el resultat corresponent ${\displaystyle f(x^{*})}$ ) s'anomena òptim de Pareto si no existeix una altra solució que el domini. El conjunt de resultats òptims de Pareto, denotat com ${\displaystyle X^{*}}$, sovint s'anomena front de Pareto, frontera de Pareto o límit de Pareto.

El front de Pareto d'un problema d'optimització multiobjectiu està delimitat per un vector objectiu nadir. ${\displaystyle z^{nadir}}$ i un vector objectiu ideal ${\displaystyle z^{ideal}}$, si aquests són finits. El vector objectiu nadir es defineix com

${\displaystyle z^{nadir}={\begin{pmatrix}\sup _{x^{*}\in X^{*}}f_{1}(x^{*})\\\vdots \\\sup _{x^{*}\in X^{*}}f_{k}(x^{*})\end{pmatrix}}}$

i el vector objectiu ideal com a

${\displaystyle z^{ideal}={\begin{pmatrix}\inf _{x^{*}\in X^{*}}f_{1}(x^{*})\\\vdots \\\inf _{x^{*}\in X^{*}}f_{k}(x^{*})\end{pmatrix}}}$

En altres paraules, els components dels vectors objectius nadir i ideal defineixen els límits superior i inferior de la funció objectiu de les solucions òptimes de Pareto. A la pràctica, el vector objectiu nadir només es pot aproximar, ja que, normalment, es desconeix tot el conjunt òptim de Pareto. A més, un vector objectiu utòpic ${\displaystyle z^{utop}}$, de manera que ${\displaystyle z_{i}^{utop}=z_{i}^{ideal}-\epsilon ,\forall i\in \{1,\dots ,k\}}$ on ${\displaystyle \epsilon >0}$ és una constant petita, sovint es defineix per raons numèriques.

Com que normalment existeixen múltiples solucions òptimes de Pareto per a problemes d'optimització multiobjectiu, el que significa resoldre un problema d'aquest tipus no és tan senzill com ho és per a un problema d'optimització convencional d'un sol objectiu. Per tant, diferents investigadors han definit el terme "resoldre un problema d'optimització multiobjectiu" de diverses maneres. Aquesta secció resumeix algunes d'elles i els contextos en què s'utilitzen. Molts mètodes converteixen el problema original amb múltiples objectius en un problema d'optimització d'un sol objectiu. Això s'anomena problema escalaritzat. Si es pot garantir l'optimalitat de Pareto de les solucions d'un sol objectiu obtingudes, l'escalarització es caracteritza com a feta de manera ordenada.

Resoldre un problema d'optimització multiobjectiu de vegades s'entén com aproximar o calcular totes o un conjunt representatiu de solucions òptimes de Pareto.^[37][38]

Quan s'emfatitza la presa de decisions, l'objectiu de resoldre un problema d'optimització multiobjectiu es refereix a ajudar a la persona que pren decisions a trobar la solució òptima de Pareto més preferida d'acord amb les seves preferències subjectives.^[39][40] La suposició subjacent és que s'ha d'identificar una solució al problema per implementar-la a la pràctica. Aquí, un responsable de decisions humà (DM) hi juga un paper important. S'espera que el DM sigui un expert en el domini del problema.

Els resultats més preferits es poden trobar utilitzant diferents filosofies. Els mètodes d'optimització multiobjectiu es poden dividir en quatre classes.^[41]

1. En els anomenats mètodes sense preferència, no s'espera que hi hagi cap DM disponible, però s'identifica una solució de compromís neutral sense informació de preferència.^[42] Les altres classes són els anomenats mètodes a priori, a posteriori i interactius, i tots impliquen informació de preferència del DM de maneres diferents.
2. En els mètodes a priori, primer es demana informació de preferències al DM i després es troba una solució que satisfà millor aquestes preferències.
3. En els mètodes a posteriori, primer es troba un conjunt representatiu de solucions òptimes de Pareto i, a continuació, el DM ha d'escollir-ne una.
4. En els mètodes interactius, el responsable de la presa de decisions pot cercar iterativament la solució preferida. A cada iteració del mètode interactiu, es mostren al DM la(es) solució(ns) òptima(ns) de Pareto i es descriu com es podrien millorar. La informació proporcionada pel DM es té en compte a l'hora de generar noves solucions òptimes de Pareto perquè el DM les estudiï a la següent iteració. D'aquesta manera, el DM aprèn sobre la viabilitat dels seus desitjos i es pot concentrar en les solucions que li interessen. El DM pot aturar la cerca quan vulgui.

A les seccions següents es proporciona més informació i exemples de diferents mètodes de les quatre classes.

Quan un responsable de la presa de decisions no articula explícitament cap informació de preferència, el mètode d'optimització multiobjectiu es pot classificar com un mètode sense preferència.^[43] Un exemple ben conegut és el mètode del criteri global,^[44] en què un problema escalaritzat de la forma

${\displaystyle {\begin{aligned}\min &\|f(x)-z^{ideal}\|\\{\text{s.t. }}&x\in X\end{aligned}}}$

està resolt. En el problema anterior, ${\displaystyle \|\cdot \|}$ pot ser qualsevol ${\displaystyle L_{p}}$ norma, amb opcions comunes que inclouen ${\displaystyle L_{1}}$, ${\displaystyle L_{2}}$, i ${\displaystyle L_{\infty }}$^[45] El mètode del criteri global és sensible a l'escala de les funcions objectives. Per tant, es recomana que els objectius es normalitzin en una escala uniforme i adimensional.^[45][46]

Els mètodes a priori requereixen que s'expressi prou informació de preferències abans del procés de solució.^[47] Exemples coneguts de mètodes a priori inclouen el mètode de la funció d'utilitat, el mètode lexicogràfic i la programació d'objectius.

Escalarització

Escalaritzar un problema d'optimització multiobjectiu és un mètode a priori, que significa formular un problema d'optimització d'un sol objectiu de manera que les solucions òptimes per al problema d'optimització d'un sol objectiu siguin solucions òptimes de Pareto per al problema d'optimització multiobjectiu.^[49] A més, sovint es requereix que cada solució òptima de Pareto es pugui assolir amb alguns paràmetres de l'escalarització.^[49] Amb diferents paràmetres per a l'escalarització, es produeixen diferents solucions òptimes de Pareto. Una formulació general per a una escalarització d'un problema d'optimització multiobjectiu és

${\displaystyle {\begin{array}{ll}\min &g(f_{1}(x),\ldots ,f_{k}(x),\theta )\\{\text{s.t.}}&x\in X_{\theta }\end{array}}}$

on ${\displaystyle \theta }$ és un paràmetre vectorial, el conjunt ${\displaystyle X_{\theta }\subseteq X}$ és un conjunt que depèn del paràmetre ${\displaystyle \theta }$, i ${\displaystyle g:\mathbb {R} ^{k+1}\rightarrow \mathbb {R} }$ és una funció.

Els mètodes a posteriori tenen com a objectiu produir totes les solucions òptimes de Pareto o un subconjunt representatiu de les solucions òptimes de Pareto. La majoria dels mètodes a posteriori es divideixen en una de les tres classes següents:

• Mètodes a posteriori basats en la programació matemàtica on un algorisme s'executa repetidament, i cada execució produeix una solució òptima de Pareto;
• algorismes evolutius on una execució de l'algorisme produeix un conjunt de solucions òptimes de Pareto;
• Mètodes d'aprenentatge profund on un model s'entrena primer sobre un subconjunt de solucions i després es consulta per proporcionar altres solucions en el front de Pareto.

En els mètodes interactius d'optimització de problemes amb objectius múltiples, el procés de solució és iteratiu i el responsable de la presa de decisions interactua contínuament amb el mètode quan busca la solució més preferida (vegeu per exemple, Miettinen 1999,^[50] Miettinen 2008).^[51] En altres paraules, s'espera que el responsable de la presa de decisions expressi les seves preferències a cada iteració per obtenir solucions òptimes de Pareto que siguin d'interès per al responsable de la presa de decisions i aprengui quin tipus de solucions són assolibles.

Existeixen diferents mètodes híbrids, però aquí considerem la hibridació de MCDM (presa de decisions multicriteri) i EMO (optimització evolutiva multiobjectiu). Un algorisme híbrid en optimització multiobjectiu combina algorismes/enfocaments d'aquests dos camps (vegeu per exemple,).^[52] Els algorismes híbrids d'EMO i MCDM s'utilitzen principalment per superar les deficiències mitjançant l'ús dels punts forts. S'han proposat diversos tipus d'algorismes híbrids a la literatura, per exemple, la incorporació d'enfocaments MCDM als algorismes EMO com a operador de cerca local, que porta un DM a la solució o solucions més preferides, etc. Un operador de cerca local s'utilitza principalment per millorar la taxa de convergència dels algorismes EMO.

La visualització del front de Pareto és una de les tècniques de preferència a posteriori de l'optimització multiobjectiu. Les tècniques de preferència a posteriori proporcionen una classe important de tècniques d'optimització multiobjectiu.^[53] Normalment, les tècniques de preferència a posteriori inclouen quatre passos: (1) l'ordinador aproxima el front de Pareto, és a dir, el conjunt òptim de Pareto a l'espai objectiu; (2) el decisor estudia l'aproximació del front de Pareto; (3) el decisor identifica el punt preferit al front de Pareto; (4) l'ordinador proporciona la decisió òptima de Pareto, la sortida de la qual coincideix amb el punt objectiu identificat pel decisor. Des del punt de vista del decisor, el segon pas de les tècniques de preferència a posteriori és el més complicat. Hi ha dos enfocaments principals per informar el decisor. En primer lloc, es poden proporcionar diversos punts del front de Pareto en forma de llista (es donen una discussió i referències interessants a^[54]) o mitjançant mapes de calor.^[55]