Optimisació multiobjetivo

En un problema d'optimisació es tractarà de trobar una solució que represente el valor òptim per a una funció objectiu.

En el cas més senzill es tindrà un únic objectiu, que estarà representat per una funció del tipo $f:M\to N$, a on $M\subset ℝ$ i $N\subset ℝ$. Tant el domini com l'image de la funció seran número real (escalares), i el valor òptim correspondrà a un mínim o a un màxim.

Eixemple: En minimisar la funció $f(x)=x^2-5$, el valor òptim és $-5$, i es dona per a $x=0$, segons pot vore's en la figura 1.

Figura 1: Mínim de la funció $f(x)=x^2-5$

Figura 1: Mínim de la funció $f(x)=x^2-5$

Extensió a múltiples objectius

Pero en ciències i ingenieria es donen, en prou ocasions, problemes que requerixen l'optimisació simultànea de més d'un objectiu (optimisació multiobjetivo). Caldrà optimisar per tant una funció de la forma $f:S\to T$, a on $S\subset {ℝ}^n$ i $T\subset {ℝ}^k$. Pero el problema està en que normalment no existix un element de S que produïxca un òptim de forma simultànea per a cada u dels k objectius que componen f. Açò es deurà a l'existència de conflictes entre objectius, que faran que la millora d'un d'ells done lloc a un empijorament d'algun atre. Pensem per eixemple en el cas d'un avió en dos objectius que anaren la seua velocitat i l'aforro de combustible: un aument de la velocitat duria en si una disminució de l'aforro. Caldrà aplegar per tant a una situació de compromís en la que tots els objectius siguen satisfets en un grau acceptable, des del punt de vista de disseny.

A diferència dels problemes d'optimisació en un únic objectiu, el concepte d'òptim és ara relatiu i serà necessari decidir d'alguna forma quin és la millor solució (o quins són les millors solucions) al problema.

En térmens matemàtics, el problema d'optimisació multiobjetivo, pot establir-se de la següent forma:

Trobar un vector $x^{*}={[x_1^{*},x_2^{*},\cdots ,x_n^{*}]}^T$, que satisfaça les m restriccions:

$g_i(x)\ge 0i=1,2,\cdots ,m(1)$

i les p restriccions:

$h_i(x)=0i=1,2,\cdots ,p(2)$

i optimise la funció vectorial

$f(x)={[f_1(x),f_2(x),\cdots ,f_k(x)]}^T$

a on $x={[x_1,x_2,\cdots ,x_n]}^T$ és el vector de variables de decisió.

En atres paraules, es desija determinar la solució particular $x_1^{*},x_2^{*},\cdots ,x_n^{*}$, del conjunt S format per tots els valors que satisfan (1) i (2), que done lloc als valors òptims per a totes les funcions objectiu. Pero com ya s'ha comentat, no existix normalment una solució que optimise de forma simultànea totes les funcions objectiu.

Métodos de solució

Per a tractar el problema comentat del conflicte entre objectius s'han utilisat diversos métodos:

• Métodos basats en el concepte d'eficiència de Pareto.

• Métodos basats en la combinació d'objectius. Dins d'estos métodos es pot mencionar el método de la suma ponderada, en el que s'optimisarà el valor obtingut per mig de la suma dels valors corresponents als distints objectius, multiplicats cada u per un coeficient de pes. Estos coeficients de pes establiran l'importància relativa de cada objectiu. El problema d'optimisació multiobjetivo es transforma aixina en un atre d'optimisació escalar, que per al cas de la minimisació serà de la forma

$\min \sum _{i=1}^k{w}_i{f}_i(x)$

a on $w_i\ge 0$ és el coeficient de pes corresponent a l'objectiu i.

Existixen variants del método anterior, com el método de la programació per metes, en el que s'establix una meta per a cada objectiu i lo que se suma ara (multiplicat pel corresponent coeficient) és la distància de cada objectiu a la seua meta. Per a un cas de minimisació seria

$\min \sum _{i=1}^k{w}_i|f_i(x)-M_i|$

a on $M_i$ representa la meta de l'i-ésimo objectiu.

• Métodos basats en la assignació de prioritats. Estos métodos tenen en comú que establixen unes prioritats entre els distints objectius, tenint-se en conte la seua importància relativa durant el procés d'optimisació.

Tots els métodos anteriors han segut utilisats per distints autors en combinació en els algoritmes evolutius, que s'han mostrat com una ferramenta molt adequada per a resoldre este tipo de problemes. Estos métodos poden englobar-se en lo que es coneix com MOEA (Multi-Objective Evolutionary Algorithms, en espanyol algoritmes evolutius multiobjetivo).

Vore també

• Optimisació
• Eficiència de Pareto
• Algoritme evolutiu