IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO.

6, DECEMBER 2007 1

MOEA/D: A Multiobjective Evolutionary Algorithm

Based on Decomposition
Qingfu Zhang, Senior Member, IEEE, and Hui Li

AbstractLa descomposicion es una estrategia basica en la un objetivo induce al deterioro de almenos otro objetivo. El
optimizacion multi-objectivo tradicional. Sin embargo, todava conjunto de todos estos puntos se le conoce como conjunto
no se ha utilizado ampliamente en la optimizacion evolutiva de pareto (PS), y su imagen es decir el conjunto de todos los
multiobjetivo. Este artculo propone un algoritmo evolutivo
multiobjetivo basado en la descomposicion (MOEA / D). De- vectores optimos de Pareto es el frente de Pareto (PF).
scompone un problema de optimizacion multiobjetivo en una En muchas aplicaciones reales de optimizacion multiobje-
serie de subproblemas de optimizacion escalares y los optimiza tivo, una aproximacion al PF requiere de un decisor para se-
simultaneamente. Cada subproblema se optimiza usando infor- leccionar una solucion final preferida. La mayora de los MOP
macion de sus subproblemas vecinos, lo que hace que MOEA/D pueden tener muchos o incluso infinitos vectores optimos
tenga menor complejidad computacional en cada generacion
que MOGLS y el NSGA-II. Los resultados experimentales de Pareto, lo que implica que conocer el PF completo es
han demostrado que MOEA/D con metodos de descomposicion casi imposible, ademas del desborde de informacion que esto
simples supera o se comporta de manera similar a MOGLS supondra, es por ello que muchos algoritmos MO lo que
y NSGA-II en problemas de mochila multiobjetivos de 0-1 buscan es un numero manejable de vetores optimos de pareto,
y problemas de optimizacion multiobjetivo continuos. Se ha distribuidos uniformemente a lo largo del PF.
demostrado que MOEA/D utilizando la normalizacion objetiva
puede hacer frente a objetivos de escala desigual, y MOEA/D Es bien sabido que una solucion optima de Pareto a un MOP,
con un metodo de descomposicion avanzada puede generar un en condiciones suaves, podra ser una solucion optima de un
conjunto de soluciones muy uniformemente distribuido para problema de optimizacion escalar en el que el objetivo es una
pruebas 3-objetivo. La capacidad de MOEA/D con poblacion agregacion de todos los fi s. Por lo tanto, la aproximacion de
pequena, la escalabilidad y sensibilidad de MOEA/D tambien se la FP puede descomponerse en una serie de sub-parametros de
han investigado experimentalmente en este documento.
optimizacion objetivo escalar. Esta es una idea basica detras
Index TermsComputational complexity, decomposition, de muchos metodos de programacion matematica tradicional
evolu- tionary algorithm, multiobjective optimization, Pareto para aproximar el PF. Los metodos para construir las funciones
optimality.
de agregacion mas populares son el enfoque de suma pon-
derada y el enfoque de Tchebycheff. No hay descomposicion
I. I NTRODUCTION involucrada en la mayora de los actuales algoritmos evolutivos
multiobjetivos (MOEAs). Estos algoritmos tratan un MOP
U N problema de optimizacion multiobjetivo (MOP) se
puede definir como: como un todo.
En un problema de optimizacion objetivo escalar, todas
maximizar F (x) = (f1 (x), ..., fm (x))T con x las soluciones pueden ser comparadas en base a sus valores
Donde es el espacio de decision (variable), consta de fun- objetivos de funcion y la tarea de un algoritmo evolutivo evo-
ciones objetivas de valor real y se denomina espacio objetivo. lutivo escalar (EA) es a menudo encontrar una sola solucion
El conjunto objetivo alcanzable se define como el conjunto optima. En las MOPs, sin embargo, la dominacion no define
f (x)|x un ordenamiento completo entre las soluciones en el espacio
A menudo, ya que los objetivos se contradicen entre s, objetivo y las MOEA apuntan a producir un numero de
ningun punto maximiza todos los objetivos simultaneamente. soluciones opticas de Pareto tan diversas como sea posible
Se deben equilibrar. Las mejores compensaciones entre los para representar el PF entero. Por lo tanto, los operadores de
objetivos se pueden definir en terminos de optimalidad de seleccion convencionales, que originalmente fueron disenados
Pareto. para la optimizacion escalar, no pueden ser utilizados directa-
Sean u, v Rm se dice que u domina a v si y solo si mente en MOEAs de no-descomposicion.
ui vi i 1, ..., m y almenos para un indice j, uj > vj . Si hay un esquema de asignacion de aptitud para asignar
Un punto x es Pareto Optimal si y solo si 6 x |F (x) a una solucion individual un valor relativo de aptitud para
domine a F (x ), reflejar su utilidad en la seleccion, entonces los EAs de
F (x ) se denomina vector optimo de Pareto, en otras optimizacion escalar pueden ampliarse facilmente para tratar
palabras, en un punto Pareto Optimal, cualquier mejora de con MOPs, aunque otras tecnicas como la restriccion de
acoplamiento [20] , El mantenimiento de la diversidad [21],
M. Shell is with the Department of Electrical and Computer Engineering, algunas propiedades de las MOP [22], y las poblaciones
Georgia Institute of Technology, Atlanta, GA, 30332 USA e-mail: (see externas [23] tambien puede ser necesaria para mejorar los
http://www.michaelshell.org/contact.html).
J. Doe and J. Doe are with Anonymous University. resultados de estos algoritmos extendidos. Por esta razon, la
Manuscript received April 19, 2005; revised September 17, 2014. asignacion de la aptitud ha sido un tema importante en la
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 2

investigacion actual del MOEA. Las estrategias de asignacion continua. MOEA/D con un enfoque de descomposicion
de aptitud populares incluyen asignacion de aptitud basada en avanzada es mucho mejor que NSGA-II en instancias
objetivos alternativos como el algoritmo genetico de evalu- de prueba continua de 3 objectivos. MOEA/D utilizando
acion de vector (VEGA) [24], y asignacion de aptitud basada una pequena poblacion es capaz de producir un pequeno
en dominacion como Pareto archived evolutionary strategy numero de soluciones muy uniformemente distribuidas.
(PAES) [14], fuerza Pareto algoritmo evolutivo II (SPEA-II) Las tecnicas de normalizacion objetiva pueden ser in-
[15], y el algoritmo genetico de clasificacion no dominada corporadas en el MOEA/D para tratar con objetivos
algoritmo genetico II (NSGA-II) [16]. desigualmente escalados.
La idea de la descomposicion se ha utilizado en cierta me- Es muy natural utilizar metodos de optimizacion escalares
dida en varias metaheursticas para MOPs como la busqueda en MOEA/D ya que cada solucion esta asociada con un
local de dos fases (TPLS) , considera un conjunto de prob- problema de optimizacion escalar. Por el contrario, uno
lemas de optimizacion escalar, en el que los objetivos son de los principales inconvenientes de las MOEAs de no-
agregaciones de los objetivos en el MOP bajo consideracion, descomposicion es que no hay una manera facil para que
se aplica un algoritmo escalar de optimizacion a estos prob- aprovechen los metodos de optimizacion escalar.
lemas de optimizacion escalar en una secuencia basada en
coeficientes de agregacion, se establece una solucion obtenida II. D ESCOMPOSICIONES DE O PTIMIZACIONES
en el problema anterior como punto de partida para resolver el M ULTI O BJETIVO
problema siguiente, ya que su objetivo de agregacion es liger-
amente diferente al de la anterior. La busqueda local genetica Hay varios enfoques para convertir el problema de la aprox-
multiobjetiva (MOGLS) apunta a la optimizacion simultanea imacion de la PF en una serie de problemas de optimizacion
de todas las agregaciones construidas por el enfoque de suma escalar. Mostraremos tres enfoques:
ponderada o enfoque de Tchebycheff . En cada iteracion, opta
por un objetivo de agregacion generado al azar. A. Suma Ponderada
En este artculo proponemos un nuevo algoritmo evolu-
Este enfoque considera una combinacion convexa de los
tivo multiobjetivo basado en la descomposicion (MOEA/D).
diferentes objetivos, tomando = (1 , ..., m )T un vector de
MOEA/D explcitamente descompone el MOP en sub-
pesos, todos positivos y cuya suma es 1. Luego la solucion se
programas de optimizacion escalar. Resuelve estos subproble-
haya maximizando el siguiente problema escalar:
mas simultaneamente mediante la evolucion de una poblacion
m
de soluciones. En cada generacion, la poblacion se compone de X
la mejor solucion encontrada hasta el momento (es decir, desde g ws (x|) = i fi (x) para x
i=1
el inicio de la ejecucion del algoritmo) para cada subproblema.
Las relaciones de vecindad entre estos subproblemas se de- . Donde usamos g ws (x|) para enfatizar que es un vector
finen en base a las distancias entre sus vectores de coeficientes de coeficientes mientras que x es la variable a optimizar.
de agregacion. Las soluciones optimas para dos subproblemas Para generar un conjunto de diferentes vectores optimos de
vecinos deben ser muy similares. Cada subproblema (es decir, Pareto, se pueden utilizar diferentes vectores de peso, si el PF
funcion de agregacion escalar) se optimiza en MOEA/D uti- es concavo (convexo para minimizar), este enfoque funciona,
lizando informacion solamente de sus subproblemas vecinos. sin embargo, no se puede obtener todo el vector optimo de
MOEA/D tiene las siguientes caractersticas: Pareto mediante este enfoque en el caso de serlo.
Proporciona una manera sencilla pero eficiente de in-
troducir enfoques de descomposicion en computacion B. Tchebycheff
evolutiva multiobjetiva. Un enfoque de descomposicion,
a menudo desarrollado en la comunidad de programacion En este caso el problema de optimizacion escalar es de la
matematica, puede ser facilmente incorporado en EAs en forma:
el marco MOEA/D para resolver MOPs. minimizar g te (x|, z ) = maxi |fi (x) zi |) para x
Dado que optimiza los problemas de optimizacion escalar
en lugar de resolver directamente un MOP como un donde z = (zi , ..., zm
T
) es un punto de referencia, por
todo, cuestiones como la asignacion de la aptitud y el ejemplo los puntos que maximizan cada una de las fi .
mantenimiento de la diversidad que causan dificultades Para cada punto optimo de Pareto, existe un vector de pesos
para la no descomposicion MOEAS podra ser mas facil de forma que ese punto es solucion optima del problema
de manejar. anterior y para cada una de estas soluciones es una solucion
MOEA/D tiene menor complejidad computacional en optima de Pareto del problema Multiobjetivo inicial.
cada generacion que NSGA-II y MOGLS. En general, Por lo tanto, uno es capaz de obtener diferentes soluciones
MOEA/D supera, en terminos de calidad de solucion optimas de Pareto alterando el vector de peso. Una debilidad
a MOGLS en instancias de prueba de mochila multi- con este enfoque es que su funcion de agregacion no es suave
objetivo 0-1 cuando ambos algoritmos usan el mismo para una MOP continua. Sin embargo, todava se puede utilizar
enfoque de descomposicion. MOEA/D con el enfoque de en el marco EA propuesto en este documento, ya que nuestro
descomposicion de Tchebycheff realiza de manera similar algoritmo no necesita calcular la derivada de la funcion de
a NSGA-II en un conjunto de instancias de prueba MOP agregacion.
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 3

C. Boundary Intersection (BI) proyeccion de F (x) en L , d1 la distancia entre z e y, d2

Existen actualmente varias descomposiciones que entran entre F (x) y L.
dentro del enfoque BI, fueron disenados para MOP Continuos,
basandose en que bajo ciertas condiciones de regularidad, el
PF es parte del lmite superior derecho de su conjunto objetivo
alcanzable.
Geometricamente, estos enfoques BI buscan encontrar pun-
tos de interseccion del lmite superior y un conjunto de lneas.
Si estas lneas estan distribuidas uniformemente en un sentido,
se puede esperar que los puntos de interseccion resultantes
proporcionen una buena aproximacion al PF completo. Estos
enfoques son capaces de hacer frente a PFs no concavas.
En este trabajo utilizamos un conjunto de lneas que emanan
del punto de referencia. Matematicamente, consideramos el
siguiente subproblema de optimizacion escalar:

minimizar g bi = d
restringido a z F (x) = d para x
Donde y z vuelven a ser un vector de peso y un punto Fig. 2. Ilustracion del PBI
de referencia respectivamente. Como se ilustra en la Fig 1,
la restriccion asegura que F (x) este en L la linea de que Las ventajas de los enfoques basados en BI sobre los
atraviesa a z . Tchebycheff son:
En el caso de mas de dos objetivos, permita que el y el
Tchebycheff utilicen el mismo conjunto de vectores de
peso uniformemente distribuidos, las soluciones optimas
resultantes en el PBI deberan distribuirse de manera
mucho mas uniforme que las obtenidas por el enfoque
de Tchebycheff , particularmente cuando el numero de
vectores de peso no es grande.
te
Si x domina a y, aun es posible que g (x|, z ) =
te bip
g (x|, z ), mientras que es raro para g y otras
funciones de agregacion BI
Estas ventajas tienen un precio, fijar el valor de la penalizacion
, pues uno erroneo mermara notablemente el rendimiento de
dicho metodo.
Los enfoques anteriores pueden usarse para descomponer
la aproximacion del PF en una serie de problemas de opti-
mizacion escalar. Un numero razonablemente grande de vec-
tores de peso uniformemente distribuidos conduce usualmente
Fig. 1. Ilustracion del BI original a un conjunto de vectores optimos de Pareto, que pueden no
estar uniformemente extendidos pero podran aproximarse al
El objetivo es empujar a K lo mas alto posible para PF muy bien. Hay muchos otros enfoques de descomposicion
que alcance el lmite de el objetivo alcanzable. Uno de los en la literatura que tambien podran ser utilizados en nuestro
inconvenientes del enfoque anterior es que tiene que manejar la marco de algoritmos. Dado que nuestro proposito principal es
restriccion de igualdad. En nuestra implementacion, usamos un estudiar la viabilidad y la eficiencia de la estructura del al-
metodo de penalizacion para lidiar con la restriccion (P BI). goritmo. Solo utilizamos los tres enfoques de descomposicion
Mas precisamente, consideramos : anteriores en los estudios experimentales de este trabajo.

minimizar g bi = d1 + d2 III. FRAMEWORK PARA MULTIOBJECTIVE

EVOLUTIONARY ALGORITHM BASED ON
restringido a z F (x) = d para x
DECOMPOSITION (MOEA/D)
||(z F (x))T ||
donde d1 = A. Framework General
||||
Este algoritmo necesita descomponer el MOP bajo consid-
d2 = ||F (x) (z d1 )||
eracion, suponemos que se emplea el enfoque de Tchebycheff.
> 0 es el parametro de penalizacion,si se elige correc- Es trivial modificar los siguientes MOEA / D cuando se
tamente da una solucion muy proxima al BI. Siendo Y la utilizan otros metodos de descomposicion.
 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 4

Sean 1 , ..., m un conjunto de pesos uniforme, z un Paso 2.1) Reproduccion: Aleatoriamente se seleccionan
punto de referencia, el problema de aproximar el PF podemos dos ndices j, k de B(i) y generamos una nueva solucion
descomponerlo en N subproblemas escalares de optimizacion y de xk y xl aplicando los operadores geneticos.
usando este enfoque, la funcion de aproximacion era Paso 2.2)Mejora: aplicamos una mejora heuristica a y
para producir y 0
g te (x|j , z ) = max {ji |fi (x)zi |} donde j = j1 , ..., jm Paso 2.3)Actualizar Z: Para cada j=1,...,m si zj <
1im
fj (y 0 ) zj = fj (y 0 )
para cada j-esimo subproblema. Paso 2.4)Actualizacion de soluciones vecinas: Para cada
MOEA/D minimiza todos estas N funciones objetivo en una ndice j B(i) si g te (y 0 |j , z) g te (xj |j , z)
sola ejecucion, Hay que tener en cuenta que g te es continua
en , por tanto una solucion optima para g te (x|j , z ) sera xj = y 0 F V j = F (y 0 )
proxima a la optima de g te (x|i , z ) para j i cercanos. Paso 2.5)Actualizar EP: Eliminamos todos los vectores
Lo cual es una motivacion para MOEA/D ya que cualquier de la EP dominados por F (y 0 ). Agregamos F (y 0 ) a EP
informacion de dicha funcion con cercanos a los optimos si ningun vector de EP domina a F (y 0 ).
nos ayudara en la busqueda del optimo. Paso 3)Criterio de Parada: Si se cumple el criterio de parada, paramos y devolvemos
Definiremos vecindario de i como un subconjunto de la EP, en caso contrario volvemos al Paso 2.
vectores de peso proximos a {1 , ..., N }. El vecindario del Al inicializar, B(i) contiene los ndices de los T vectores
subproblema i-esimo consiste en todos los subproblemas con mas cercanos, por tanto el vector mas cercano es el mismo,
los vectores de peso del vecindario de i . La poblacion se si j B(i) entonces podemos decir que el subproblema j-
compone de la mejor solucion encontrada hasta ahora para e4simo es vecino del subproblema i-esimo
cada subproblema. Solo las soluciones actuales a sus subprob- En la i-esima parte del bucle en el Paso 2, se consideran los
lemas vecinos se explotan para optimizar un subproblema en T subproblemas vecinos del i-esimo subproblema. Puesto que
MOEA/D. xk y xl en el Paso 2.1 son las mejores soluciones actuales
A cada generacion t, MOEA/D con el enfoque Tchebycheff para los vecinos del subproblema i-esimo, su descendencia
mantiene: debera ser una buena solucion para el i-esimo subproblema.
1 N
Una poblacicion de N puntos, x , ..., x donde xi En el paso 2.2, se utiliza una heurstica especfica del problema
es la solucion actual al i-esimo subproblema. para reparar y en el caso en que y invalida cualquier restriccion
1 N
F V , ..., F V , donde F V i es el F-valor para xi , F V i = y / o optimiza el i-esimo gte. En el paso 2.2, se utiliza una
F (xi ) heurstica especfica del problema para reparar z en el caso en
T que z invalida cualquier restriccion y / u optimiza el i-esimo
z = (z1 , ..., zm ) , donde zi es el mejor valor optenido
para la funcion fi gte. Por lo tanto, la solucion resultante y es factible y es muy
Una poblacicion externa (EP), que se usa para alma- probable que tenga una funcion inferior Valor para los vecinos
cenar soluciones no dominadas encontradas durante la del subproblema i-esimo.
busqueda El paso 2.4 considera a todos los vecinos del subproblema i-
El algoritmo funciona de la siguiente manera: esimo, reemplaza xj con y 0 si y 0 es mejor que xj con respecto
al j-esimo subproblema. FVj es necesario para calcular el valor
Input de g te (xj |j , z)
MOP (1);
I wish you the best of success.
Criterio de Parada; mds
N: numero de subproblemas considerados en MOEA/D September 17, 2014
Una distribucion uniforme de los N vectores de peso.
T: El numero de vectores de peso en la vecindad de cada
B. Subsection Heading Here
vector de peso.
Output Subsection text here.
EP
1) Subsubsection Heading Here: Subsubsection text here.
Paso 1) Inicializacion IV. C ONCLUSION
Paso 1.1) EP =
The conclusion goes here.
Paso 1.2) Calcula la distancia euclidea para cada par de
vectores de peso y elabora los T vectores de peso mas
A PPENDIX A
proximos a cada vector de peso. Para cada i = 1, ..., N
P ROOF OF THE F IRST Z ONKLAR E QUATION
, se establece B(i) = {i1 , ..., iT }, donde i1 , ..., iT son
los T vectores de peso mas cercanos a i Appendix one text goes here.
1 N
Paso 1.3) Se genera una poblacion inicial x , ..., x , de
forma aleatoria o basandonos en un metodo especifico y A PPENDIX B
calculamos los F V i Appendix two text goes here.
T
Paso 1.4) Establecemos z = (z1 , ..., Zm ) por un metodo
especfico del problema. ACKNOWLEDGMENT
Paso 2) Actualizacion para i = 1, ..., N do: The authors would like to thank...
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 5

R EFERENCES
[1] H. Kopka and P. W. Daly, A Guide to LATEX, 3rd ed. Harlow, England:
Addison-Wesley, 1999.

Michael Shell Biography text here.

PLACE
PHOTO
HERE

John Doe Biography text here.

Jane Doe Biography text here.