Optimización Evolutiva Multiobjetivos (MOP)

D.Sc. Yván Jesús Túpac Valdivia

Ciencias de la Computación
Universidad Católica San Pablo

May 26, 2012

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 1 / 53
 Optimización Evolutiva Multiobjetivos Motivación

Optimización Multiobjetivos
Muchos problemas de la vida real pueden tratarse como optimización
de un único objetivo, pero
La mayoría de problemas tienen varios objetivos para satisfacer y aún,
algunos pueden ser conflitivos.
Estos problemas suelen tratarse como problemas de único objetivo,
viendo los demás objetivos como restricciones

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 2 / 53
 Optimización Evolutiva Multiobjetivos Motivación

Optimización Evolutiva Multiobjetivos

Ejemplo - Modelo de EDPs para motociclistas

Uso de material compuesto [Magistrali, 2007]:

Laminación de los materiales usados: láminas de Kevlar-Carbon junto
a PVC, PMI, PU y Honeycomb.
Confiabilidad respecto a rupturas
Respuesta ante pruebas de impacto, para verificar capacidad de
absorción de energía y características de vibración.
Morfología del diseño (curvas)

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 3 / 53
 Optimización Evolutiva Multiobjetivos El Problema de Optimización Multiobjetivo (MOP)

Optimización Evolutiva Multiobjetivos

Conocido también como optimización multicriterio, se define en

palabras como el problema de:

Encontrar un vector de variables de decisión que satisfagan restricciones y

optimicen una función vectorial cuyos elementos representan funciones
objetivo.

Ya no se busca una solución óptima, sino un conjunto de soluciones

posibles de calidad equivalente.
El espacio de búsqueda se convierte en parcialmente ordenado, donde
existe un conjunto de soluciones trade-offs óptimas entre los objetivos
conflictivos, que puedan ser aceptadas por el tomador de decisiones

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 4 / 53
 Optimización Evolutiva Multiobjetivos El Problema de Optimización Multiobjetivo (MOP)

MOP – Definición Formal

Un MOP consiste en buscar el vector x∗ = {x1 , . . . , xn } que satisfaciendo:
m restricciones de desigualdad.

gi (x) ≥ 0, i = 1, . . . , m (1)

p restricciones de igualdad.

hi (x) = 0, i = 1, . . . , p (2)

optimice la función vectorial

F(x) = {f1 (x), f2 (x), . . . , fk (x)} (3)

de k funciones objetivo fi (x), ∀i = 1, . . . , k, así:

F = {fi : X 7→ Yi : 0 < i ≤ k, Yi ⊆ R} (4)

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 5 / 53
 Optimización Evolutiva Multiobjetivos El Problema de Optimización Multiobjetivo (MOP)

Noción de Óptimo en MOP

Habiendo más de una función objetivo F(x) = {f1 (x), . . . , fk (x)} a

optimizar, cambia la noción de óptimo.
En MOP se intenta encontrar un conjunto de soluciones que sean buenos
compromisos (trade-offs) entre los diversos objetivos fi más que una
solución óptima.

La noción más adoptada es la propuesta por Francis Ysidro

Edgeworth (en 1881).
Esta noción fue generalizada por [Pareto, 1896] y es conocida como
Pareto-óptimo (Pareto Optimality)

La noción de Pareto-óptimo, se basa en la definición de dominancia.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 6 / 53
 Optimización Evolutiva Multiobjetivos El Problema de Optimización Multiobjetivo (MOP)

Dominancia

Sea F = {f1 (x), . . . , fk (x)} un conjunto de k funciones objetivo.

Sean las soluciones x1 , x2 ∈ X.
Se dice que x1 domina a x2 , (denotado por x1 ≺ x2 ), si existe una
función objetivo en la que x1 sea mejor que x2 sin ser peor en los
demás objetivos, como se expresa en la ecuación 5.
(
∀i = 1, . . . , k ⇒ ωi fi (x1 ) ≤ ωi fi (x2 )
x1 ≺ x2 ⇔ (5)
∃j = 1, . . . , k : ωj fj (x1 ) < ωj fj (x2 )

donde ωi = 1 si es problema de minimización, ωi = −1, si es

problema de maximización

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 7 / 53
 Optimización Evolutiva Multiobjetivos El Problema de Optimización Multiobjetivo (MOP)

Pareto Optimality

Dada una solución x∗ ∈ X se dice que es Pareto-óptima, es decir que

pertenezca a un conjunto óptimo X∗ si no es dominada por ningún
elemento x ∈ X.
El conjunto óptimo X∗ se denomina Conjunto Pareto o Frontera de
Pareto, definido en 6

x∗ ∈ X∗ ⇔6 ∃x ∈ X : x ≺ x∗ (6)
.
Es decir que (para minimización) no existe valor x ∈ X que disminuya
un objetivo sin aumentar en, al menos un otro.
Si se grafican las funciones pareto-óptimas, se obtiene el gráfico
Pareto front

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 8 / 53
 Optimización Evolutiva Multiobjetivos El Problema de Optimización Multiobjetivo (MOP)

Pareto Front

f2 (x)

So to-ó
pa

lu pt
re

cio im
ne as
s
Ni dominantes ni dominadas Soluciones que dominan a x
(buenas soluciones)

Soluciones dominadas por x Ni dominantes ni dominadas

(peores soluciones) f1 (x)

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 9 / 53
 Optimización Evolutiva Multiobjetivos El Problema de Optimización Multiobjetivo (MOP)

Ejemplo de un problema MOP

Un produtor desea minimizar costos de producción f1 y distribución f2

obteniendo las siguientes soluciones:

A : f1 = 2, f2 = 10 f2

B : f1 = 4, f2 = 6
C : f1 = 8, f2 = 4 A(2, 10)

D : f1 = 9, f2 = 5 10 E(7, 8)

E : f1 = 7, f2 = 8 B(4, 6)
D(9, 5)
C(8, 4)
5

0 5 10 f1
Se observa que A, B, C son soluciones no dominadas, D, E
son dominadas por C , B: C ≺ D, B ≺ E.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 10 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Motivación

¿Por qué usar Algoritmos Evolutivos?

Por su característica de búsqueda paralela (poblacional) que permiten

encontrar varias soluciones del conjunto Pareto óptimo en una
ejecución.
Pueden tratar problemas de forma o discontinuidad en la Pareto-Front
que no es posible al utilizar técnicas de programación matemática
clásicas [Coello, 1999]

Objetivo: minimizar la distancia entre las soluciones generadas

xi ∈ Xt y el conjunto Pareto-óptimo X∗ .
Selección y operadores deben ser críticos en detectar y retener
cualquier solución no dominada que sea encontrada.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 11 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Sin uso del Criterio de Pareto

No emplean el conjunto Pareto X∗ , por lo que no garantizan la

obtención de la frontera de Pareto en su totalidad.
Son eficientes y fáciles de implementar, aunque limitadas para algunos
pocos objetivos
Algunos modelos sin uso del criterio de Pareto
- Agregación de funciones.
- VEGA (Vector Evaluated Genetic Algorithm)
- Orden Lexicográfico
- Método −constraint.
- Vector Objetivo.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 12 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Agregación de Funciones

Consiste en combinar todas las funciones objetivo fi (x) en una función

única F (f1 (x), . . . , fk (x)).
Agregación lineal de objetivos
La función más utilizada es la combinación lineal de los objetivos de la
ecuación 7
k
X
F= ωi fi (x) (7)
i=1

donde ωi son las importancias de cada función objetivo, siendo comun que
sean normalizadas, tal que:
k
X
ωi = 1
i=1

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 13 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Agregación de Funciones

Ventajas
Fácil de implementar
Eficientes

Desventajas
No funcionan si la frontera de Pareto es cóncava

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 14 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

VEGA – Vector Evaluated Genetic Algorithm

Propuesta por [Schaffer, 1984], usa sub-poblaciones que optimizan

cada objetivo por separado
El concepto Pareto-óptimo es incorporado indirectamente en el
mecanismo de selección del AG

Ventajas y desventajas
Eficiente y fácil de implementar
No hay un mecanismo explícito para mantener la diversidad.
No necesariamente producirá vectores no dominados

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 15 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

VEGA – Vector Evaluated Genetic Algorithm

Cromosoma xi fj (xi)
f1 f2 ... fk

Generación Xt Generación Xt+1

x1 x1
1

seleccionar 2
k subgrupos
usando cada operaciones
objetivo barajar genéticas

1 2 3

k
xm xm

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 16 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Orden Lexicográfico

Se solicita al usuario un orden de importancia de los objetivos

La solución óptima se obtiene minimizando las funciones objetivo
comenzando por la más importante y siguiendo el orden dado
Se puede escoger al azar un objetivo para optimizar en cada ejecución
del AL

Desventajas
Exige un orden predefinido de los objetivos, su desempeño se puede
ver afectado por este orden.
No es adecuado si se trata de muchos objetivos

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 17 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Método −constrain

Tiene como principio minimizar un objetivo preferido, considerando los

demás como restricciones cercadas por niveles i permitidos, de la
siguiente manera:
Se hace una única minimización para el objetivo más importante
sujeto a las restricciones dadas por los demás objetivos.
Los niveles i son alterados para poder obtener el conjunto
Pareto-óptimo entero.

Desventaja
Puede requerir de un alto costo computacional

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 18 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Vector Objetivo

Se define un conjunto de metas que se desea alcanzar para cada función

objetivo. El algoritmo minimizará la diferencia entre la solución y esas
metas.
También se pueden usar estrategias de agregación, por ejm min-max,
aunque pueden generarse partes cóncavas del Pareto-front
Ventajas y desventajas
Facilidad de implementación
La definición de objetivos puede tener costo computacional extra.
Puede ocurrir desvío de la presión selectiva por la agregación de
objetivos.
Debe cumplirse que Objetivos ∈ X para garantizar soluciones en X∗

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 19 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Usando el Criterio de Pareto

Esta idea surgió en [Goldberg, 1989] para atacar deficiencias en VEGA,

donde el principio de selección de individuos se basa ahora en el concepto
de Optimalidad de Pareto:

Se usa un ranking de elementos no dominados y selección para llevar

la población hacia la Pareto Front
Es necesario un procedimiento de ranking y una técnica que mantenga
la diversidad de la población; esto es para evitar la convergencia a una
única solución x∗ debido al ruido estocástico del proceso

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 20 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Usando el Criterio de Pareto

Los métodos más conocidos de la primera generación usando criterio de

Pareto son los siguientes:

Ranking Pareto puro

Multi-Objective Genetic Algorithm (MOGA)
Nondominated Sorting Genetic Algorithm (NSGA)
Niched-Pareto Genetig Algorithm (NPGA)
Niched-Pareto Genetig Algorithm 2 NPGA 2

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 21 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

Ranking Pareto Puro

Es la idea original de Goldberg [Goldberg, 1989]

La complejidad computacional es O(kM 2 ) dada por la necesidad de
revisar la no dominancia, donde:
k es la cantidad de objetivos
M es el tamaño de la población
La complejidad del cálculo de la evaluación es O(M 2 )
Es poco susceptible a la forma y continuidad del Pareto front

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 22 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

MOGA –Multi-objective Genetic Algorithm

Se hace ranking de un individuos por el número de individuos que lo

dominan [Goldberg, 1989]
Complejidad computacional O(kM 2 ) dada por la necesidad de revisar
la no dominancia, donde:
k es la cantidad de objetivos
M es el tamaño de la población
Se emplea fitness compartido y restricciones para los cruces. forma y
continuidad del Pareto front

Ventajas, desventajas
El desempeño depende de una buena selección y el factor de
compartición
Fue el primer algoritmo GA MO verdadero, superó a sus competidores
contemporáneos.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 23 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

NSGA –Non-dominated Sorting Genetic Algorithm

Propuesto por [Srinivas and Deb, 1994], ordenan por su calidad de no

dominados colocando los no dominados en una lista y dándoles una
aptitud fantasma de acuerdo al tamaño m de la población.
Para mantener la diversidad, los individuos no dominados comparten
sus aptitudes, se ignoran y se genera otra lista de individuos no
dominados y se continua hasta lograr clasificar toda la población X

Selección mediante sobrante estocástico

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 24 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

NSGA –Non-dominated Sorting Genetic Algorithm

Diagrama de flujo

inicializa población
INICIO
gen = 0

front = 1

si Identificar
reproducción sigue las ¿población
individuos
reglas de aptitud? clasificada? no
no dominados

asignar aptitud
cruce mutación
fantasma

no compartir fitness
gen +=1 gen < maxgen en front actual

si

front+=1
FIN

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 25 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

NPGA –Niched-Pareto Genetic Algorithm

Uso de selección por torneo basada en la dominancia

Dos individuos aleatorios se comparan con un subconjunto de la
población (10% típico).
Si los dos elementos son dominados o no dominados (empate) el
torneo se decide por el fitness compartido en el dominio del objetivo,
usando la técnica llamada clase equivalente compartida

Ventajas y desventajas
No aplica el ranking Pareto a la población entera (eficiencia).
Se requiere un parámetro adicional (tamaño del torneo) dado el factor
de compartición

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 26 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 1a Generación

NPGA2

Uso de Ranking Pareto manteniendo la selección por torneo (similar al

NPGA)
En este algoritmo se usan individuos de la próxima generación
(población parcialmente completada). Esta técnica se conoce como
actualización de fitness continua.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 27 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

Características

Se enfatiza la eficiencia.
Se usan poblaciones secundarias (o externas) para generar soluciones
que sean no dominadas y uniformemente distribuidas.

Desafíos
Los problemas que se tratan son:
El fitness compartido, con complejidad O(M 2 )
Verificación de la dominancia de Pareto con complejidad O(kM 2 ) por
generación.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 28 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

PESA –Pareto Envelope-based Selection Algorithm

Usa una población interna pequeña y una gran población externa.

Emplea una división del hyper-grid del fenotipo (o sea la función
objetivo) para mantener la diversidad
La selección se basa en una medida de agrupamiento de los grids.
Con esta medida se decide cuál solución se colocará en la población
externa que almacenará las soluciones no dominadas encontradas a lo
largo del proceso.

Hay una revisión llamada PESA-II que usa selección basada en hiperboxes
en vez de individuos

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 29 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

SPEA–Streng Pareto Evolutionary Algorithm

Usa un archivo con soluciones no dominadas previamente encontradas

Se calcula un valor de ranking de individuos similar a MOGA
Usa average linkage method para clusterizar y mantener la diversidad.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 30 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

SPEA–Streng Pareto Evolutionary Algorithm

Se muestran dos escenarios de un problema de maximizacion con dos

objetivos. Se muestra la aptitud de cada punto que es su ranking de
Pareto.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 31 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

SPEA–Streng Pareto Evolutionary Algorithm

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 32 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

MOEA – 2a Generación
SPEA-II – Streng Pareto Evolutionary Algorithm 2

Con tres diferencias básicas con la versión anterior:

Incorpora una estrategia de asignación fine-grained que, para un
individuo x toma en cuenta la cantidad de individuos que domina y
que lo dominan.
Emplea una técnica de estimación de densidad de vecinos más
próximos para dirigir mejor la búsqueda.
Posée un método mejorado de truncado para garantizar la
preservación de las soluciones en la frontera y mantenerlas diversas.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 33 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

MOEA – 2a Generación
SPEA-II – Streng Pareto Evolutionary Algorithm 2

Se muestra una comparación entre las aptitudes de SPEA (izquierda)

y SPEA-II (derecha).

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 34 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

Algoritmo Microgenético

Propuesto por [Coello and Pulido, 2001], se caracteriza por usar una
población X = {xi }m
i=1 con m pequeño y un proceso de
reinicialización
Se genera una población X0 en la memoria de población reemplazable
y no reemplazable.
La parte no reemplazable no se altera en la ejecución del algoritmo,
sirve para dar diversidad. La población reemplazable cambia durante
cada ciclo del micro-GA.
La población Xt se compone por individuos aleatorios provenientes de
la parte no reemplazable e individuos evolucionados de la parte
reemplazable.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 35 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

Algoritmo Microgenético

Durante el ciclo, la población del micro-GA pasa por los operadores

genéticos clásicos.
Acabado el ciclo micro-GA, se seleccionan dos individuos xi no
dominados de la población y se comparan con los que ya existen en la
memoria externa incluyéndose en ésta si no son dominados por ningún
individuo de la memoria externa.
Cualquier individuo que se vuelva dominado se elimina de la memoria
externa.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 36 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

Algoritmo Microgenético
Memoria de población

Población Reemplazable No reemplazable

aleatoria
Colocar individuos en ambas
partes de la población

Población
inicial

Selección

Cruce

Mutación
Ciclo Micro-GA

Elitismo

Nueva
Población

¿Convergencia? No

Sı́

Filtrar

Memoria
externa

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 37 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA MOEA – 2a Generación

Algoritmo Microgenético

En el modelo de micro-GA se emplean tres estrategias elitistas:

1 Retener soluciones no dominadas que fueron encontradas en el ciclo
micro-GA
2 El uso de una memoria reemplazable cuyo contenido es parcialmente
refrescado a cada ciertos periodos
3 Reemplazar la población del micro-GA por soluciones nominales ya
evolucionadas, como las soluciones encontradas luego de un ciclo
micro-GA completo.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 38 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Métricas de desempeño

MOEA: Métricas de desempeño

Al tratar con problemas de MO se encuentran muchas situaciones que

dificultan la evaluación cualitativa de los resultados obtenidos:
1 El propio objetivo de la OMO, en vez de buscar una solución óptima,
debe generar un conjunto de soluciones X que contengan la máxima
cantidad posible de elementos del conjunto óptimo-Pareto, X → X∗ .
2 La naturaleza estocástica de AE. Se requieren varias ejecuciones para
evaluar su desempeño y poder validarlos con herramientas de análisis
estadístico.
3 El interés de mensurar diferences aspectos como:
a) un algoritmo que aproxime la frontera de Pareto global con robustez y
consistencia.
b) un algoritmo que pueda convergir a la frontera de Pareto aunque sea
ocasionalmente.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 39 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Métricas de desempeño

MOEA: Métricas de desempeño

Al tratar con problemas de MO se encuentran muchas situaciones que

dificultan la evaluación cualitativa de los resultados obtenidos:
También puede ser de interés analizar el comportamiento de un
algoritmo durante el proceso de evolución, para determinar la
capacidad de mantener la diversidad y convergencia progresiva hacia
el conjunto de soluciones de la Frontera de Pareto.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 40 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Métricas de desempeño

MOEA: Métricas de desempeño

[Zitzle and Thiele, 2000] menciona que una buena métrica debe considerar
los siguientes aspectos:
1 Minimizar la distancia entre el conjunto de soluciones obtenidas por el
algoritmo y el conjunto frontera de Pareto global del que se debe
conoce su ubicación.
2 Maximizar la dispersión de las soluciones encontradas, tratando que
su distribución sea lo más suave y uniforme posible.
3 Maximizar el número de elementos que pertenezcan al conjunto
óptimo-Pareto.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 41 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Métricas de desempeño

MOEA: Métricas de desempeño

Razón de error (Error Ratio – ER)

[Van Veldhuizen, 1999], propone indicar el porcentaje de soluciones del

actual conjunto X de vectores no dominados que no son miembros del
verdadero conjunto Óptimo-Pareto X∗
n
X
ei
i=1
ER = (8)
n
donde:
n es la cantidad de vectores en el conjunto no dominado X .
ei es definido como:
(
0 si el vector vi ∈ X∗
ei =
1 / X∗
si el vector vi ∈

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 42 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Métricas de desempeño

MOEA: Métricas de desempeño

Distancia Generacional (Generational Distance) – GD

[Van Veldhuizen and B.Lamont, 1999] propone estimar qué tan lejos se
encuentran los elementos de X con respecto al conjunto Óptimo-Pareto
X∗ , definido como: v
u n 2
uX
t d
i
i=1
GD = (9)
n
donde:
n es la cantidad de elementos del conjunto no dominado X hallado
hasta el momento.
di es la distancia euclidiana, medida en el espacio de objetivos entre
cada uno de los vectores xi ∈ X y el vector xj∗ ∈ X∗ más próximo del
conjunto Óptimo-Pareto.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 43 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Métricas de desempeño

MOEA: Métricas de desempeño

Espaciamiento

Verifica la dispersión de los elementos del conjunto X actual. Conociendo

el inicio y fin del conjunto frontera de Pareto actual, [Schott, 1995]
propone usar la varianza de la distancia entre vectores vecinos del conjunto
X actual: v
u
u 1 X n
S ,t (d̄ − di )2 (10)
n − 1 i=1

donde:  
di = minj f1i (x) − f1j (x) + f2i (x) − f2j (x) , para i, j = 1, . . . , n.
d̄ es la media de todos los di ,
n es la cantidad de vectores no dominados encontrados hasta el
momento.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 44 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Investigación en abierto

MOEA – Investigación en abierto

Fundamentos teóricos

En [Abraham et al., 2005], se menciona que el área que requiere de más

investigación en MOEA es la fundamentación teórica.
La mayor parte de la investigación actual se concentra en demostrar la
convergencia en la Optimización Multiobjetivo por Algoritmos Evolutivos.
Además de esta línea principal, hay algunas otras que aún se encuentran
en discusion, tales como:
Estudiar la estructura de las hipersuperficies de aptitud para los
problemas de Optimizacion Multiobjetivo.
Responder a la pregunta fundamentental: ¿Cuál es la dificultad en la
optimización multiobjetivos para un algoritmo evolutivo?
Un desarrollo formal para analizar y demostrar la convergencia en
Algoritmos Evolutivos multiobjetivo paralelos.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 45 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Investigación en abierto

MOEA – Investigación en abierto

Fundamentos teóricos

En [Abraham et al., 2005], se menciona que el área que requiere de más

investigación en MOEA es la fundamentación teórica.
La mayor parte de la investigación actual se concentra en demostrar la
convergencia en la Optimización Multiobjetivo por Algoritmos Evolutivos.
Además de esta línea principal, hay algunas otras que aún se encuentran
en discusion, tales como:
Buscar el límite teórico para el ranking de Pareto asumiendo
poblaciones de tamaño finito.
Hacer un análisis en tiempo real del rendimiento de un Algoritmo
Evolutivo Multiobjetivo.
Tener definiciones aceptadas por la comunidad sobre robustez,
convergencia y diversidad, entre otras en el contexto de optimización
evolutiva multiobjetivo.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 46 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Investigación en abierto

MOEA – Líneas de Investigación Futuras

Incorporar preferencias Muchas de las actuales técnicas usadas en la

toma de decisiones multicriterio que se desarrollan en el área de
Investigación Operativa, aún no son aplicadas del todo en
Optimización Evolutiva Multiobjetivo. Esta incorporación es muy
importante para aplicaciones reales ya que el usuario suele aplicar una
solución Óptima-Pareto y no todo el conjunto Pareto-Óptimo como
se asume en MOEA.
Optimización de funciones dinámicas Considerar que las fronteras
de Pareto cambian en el tiempo debido a la existencia de variables
aleatorias o dinámicas.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 47 / 53
 Algoritmos Evolutivos Multiobjetivo – MOEA Investigación en abierto

MOEA – Líneas de Investigación Futuras

Espacios de búsqueda restringidos En la literatura, se encuentran

algunas investigaciones tratando la solución de problemas
multiobjetivo con espacios de búsqueda altamente restringidos. Estos
problemas son bastante comunes y hacen necesario desarrollar
técnicas nuevas para manejo de restricciones que puedan lidiar con
este tipo de problemas.
Paralelismo Se espera más investigación en MOEA. Es necesario
tener más algoritmos y también modelos formales que comprueben la
convergencia y claro, más aplicaciones reales que usen paralelismo.

Yván Túpac (C.Sc.-UCSP) Optimización Evolutiva Multiobjetivos (MOP) May 26, 2012 48 / 53