Propuestas Multiobjetivas de la Metaheurística Harmony Search

Propuestas Multiobjetivas de la Metaheurística Harmony Search Germán Hüttemann Arza

Juan Ricart Debernardi

Facultad Politécnica Universidad Nacional de Asunción San Lorenzo, Paraguay [email protected]

Facultad Politécnica Universidad Nacional de Asunción San Lorenzo, Paraguay [email protected]

Abstract— La metaheurística Harmony Search ha demostrado su efectividad y ventajas en varias aplicaciones de ciencia e ingeniería. Sin embargo, su aplicación a problemas de optimización multiobjetivo de manera natural, correcta y eficiente sigue como tarea pendiente. Este trabajo propone dos algoritmos multiobjetivos de la metaheurística Harmony Search, utilizando como base de pruebas las funciones ZDT y CEC 2009. Los resultados experimentales indican que estos algoritmos son competitivos con el NSGA-II respecto a métricas de distancia, distribución y extensión, superiores respecto a cantidad de soluciones encontradas e inferiores con respecto a velocidad de convergencia. Keywords—harmony search, optimización improvisación musical, dominancia Pareto

I.

multiobjetivo,

INTRODUCCIÓN

La mayoría de los problemas de optimización en ingeniería son multiobjetivos por naturaleza, ya que normalmente tienen varios objetivos que deben ser optimizados al mismo tiempo. Por lo general, estos objetivos están en conflicto o competencia, es decir, mejorar uno empeora otros. Por esta razón, no siempre es posible encontrar una única solución óptima para este tipo de problemas, como ocurre con los problemas de optimización mono-objetivo. En cambio, en los problemas de optimización multiobjetivo se intenta encontrar un conjunto de buenas soluciones de compromiso (trade-off), de entre las cuales un experto elige una o varias soluciones aceptables para el problema abordado [3]. La metaheurística Harmony Search (HS) [10] es una técnica de optimización reciente que se inspira en el proceso de improvisación musical del jazz. Fue propuesta como una metaheurística de optimización de problemas mono-objetivo y, desde su creación, ha demostrado ser efectiva y ventajosa en varias aplicaciones de ciencia e ingeniería, como puede verse en [11]. La aplicación de la metaheurística HS a problemas de optimización multiobjetivo de manera natural, correcta y eficiente ha quedado como tarea pendiente de las investigaciones existentes. Más aún, el uso de esta metaheurística para resolución de problemas multiobjetivos complejos como los NP-hard, es considerado como un próximo desafío [21]. Este trabajo presenta dos algoritmos multiobjetivos de la metaheurística HS, aplicando adecuadamente los conceptos de

optimalidad Pareto, explicando en detalle cada una de las partes que conforman la estructura de los algoritmos y orientándose a la resolución de problemas de optimización multiobjetivo en general. Para comprobar la efectividad de las soluciones generadas por los algoritmos propuestos, se utiliza como base de pruebas las funciones ZDT [24] y algunas de las funciones propuestas en el CEC 2009 [20], y se comparan los resultados de dichos algoritmos con los del reconocido algoritmo evolutivo NSGA-II [4]. El resto del documento está organizado como sigue. En la sección II, se presenta la definición de problema de optimización multiobjetivo y de otros conceptos relacionados. En la sección III, se explica detalladamente la metaheurística Harmony Search. En la sección IV, se presentan las adaptaciones realizadas al algoritmo HS mono-objetivo para cada algoritmo propuesto en este trabajo. Seguidamente, en la sección V, se presentan los resultados experimentales. Finalmente, en la sección VI, se presentan las conclusiones y posibles trabajos futuros. II.

PROBLEMAS DE OPTIMIZACIÓN MULTIOBJETIVOS

Formalmente, un problema de optimización multiobjetivo puede definirse de como: Definición 1 (Problema de Optimización Multiobjetivo): Minimizar

y = F(x) = [f1(x), f2(x),…, fk(x)]

(1)

sujeto a

g(x) = [g1(x), g2(x),…, gm(x)] ≥ 0

(2)

donde

x = [x1, x2,…, xn] ∈ X ⊆ ℝ! y = [y1, y2,…, yk] ∈ Y ⊆ ℝ!

x es una variable de decisión vectorial n-dimensional, y es un vector objetivo k-dimensional, X ⊆ ℝ! denota el espacio de decisión, Y ⊆ ℝ! denota el espacio objetivo. Así, un problema de optimización multiobjetivo tiene n variables de decisión, m restricciones y k objetivos. Definición 2 (Conjunto factible): el conjunto factible Xf ⊆ ℝ! está definido como el conjunto de vectores de decisión x que satisfacen las restricciones (2): Xf = {x ∈ X | g(x) ≥ 0}

(3)

La existencia de más de una solución óptima o de compromiso en los problemas de optimización multiobjetivo (k > 1) hace necesaria una noción distinta de óptimo. La noción de óptimo más comúnmente aceptada es una propuesta conocida como Óptimo Pareto [3]. Los conceptos fundamentales para entender la noción de Óptimo Pareto son: Dominancia Pareto, Optimalidad Pareto, Conjunto Pareto Óptimo y Frente Pareto Óptimo, definidos a continuación [19]: Definición 3 (Dominancia Pareto): un vector u = [u1, u2,…, uk] domina a otro vector v = [v1, v2,…, vk] si y sólo si u es parcialmente mejor que v, esto es, ∀𝑖 ∈ {1, 2,…, k}, ui ≤vi ∧   ∃  𝑖 ∈ {1, 2,…, k} tal que ui < vi. En este caso, se dice que el vector u domina a (o es mejor que) el vector v, lo cual es denotado como u ≻ v. Otras dos notaciones utilizadas son: u ≺ v, significando que u es dominado por v y u ∼ v, significando que ni u domina a v (u ⊁ v) ni v domina a u (u ⊀ v) y, por tanto, son no comparables, esto es, u ∼ v si u ⊁ v ∧ u ⊀ v. Definición 4 (Optimalidad Pareto): se dice que una solución x ∈ X es Pareto óptima con respecto a X si y sólo si no existe una solución x’ ∈ X para la cual v = F(x’) = [f1(x’), f2(x’),…, fk(x’)] domina a u = F(x) = [f1(x), f2(x),…, fk(x)]. Definición 5 (Conjunto Pareto Óptimo): para un problema de optimización multiobjetivo F(x), el conjunto Pareto óptimo es definido como el conjunto de todas las soluciones no dominadas respecto a Xf, esto es, P = {x ∈ Xf | ∄ x’ ∈ Xf para el cual F(x’) ≻ F(x)}. Definición 6 (Frente Pareto Óptimo): para un problema de optimización multiobjetivo F(x) y un conjunto Pareto óptimo P, el frente Pareto óptimo es definido como: PF = {u = F(x) = [f1(x), f2(x),…, fk(x)] | x ∈ P}. III.

LA METAHEURÍSTICA HARMONY SEARCH

En esta sección, primero se realiza un breve contraste entre los procesos de improvisación musical y optimización. Seguidamente, se presenta la estructura del algoritmo HS junto a cada una de sus partes. A. Improvisación musical y optimización La metaheurística Harmony Search es una técnica de optimización inspirada en los principios de la improvisación musical del jazz. Cuando los músicos componen una armonía, por lo general prueban varias combinaciones posibles de tonos musicales almacenados en su memoria. El proceso de búsqueda de soluciones óptimas en problemas de ingeniería es análogo a esta eficiente búsqueda de un perfecto estado armónico [20]. La Fig. 1 muestra la estructura de la memoria de armonías (Harmony Memory, HM), que es el núcleo del algoritmo HS, como así también una analogía entre la improvisación musical y la optimización. Consideremos un trío de jazz compuesto por saxofón, doble bajo y guitarra. Existe cierta cantidad de tonos preferidos en la memoria de cada uno de los músicos: saxofonista, {Do, Re, Mi}; doble bajista, {Mi, Fa, Sol}; y guitarrista, {Sol, La, Si}. Si el saxofonista elige aleatoriamente {Do} de su memoria, el doble bajista elige {Mi}, y el guitarrista elige {Sol}, se forma la nueva armonía {Do, Mi, Sol}.

Figura 1. Estructura de la memoria de armonías y analogía entre improvisación musical y optimización.

Si esta armonía es mejor que la peor existente en la memoria de los músicos, entonces la nueva armonía remplaza a la peor. Este proceso es repetido hasta que la armonía perfecta es alcanzada. En una optimización de ingeniería, cada músico es remplazado por cada variable de decisión, y los tonos preferidos por valores preferidos de las variables. Si cada variable representa el diámetro de una cañería entre dos nodos, en una red de distribución de agua, cada una tiene un cierto número de diámetros preferidos. Si la primera variable, x1 elige {100mm} de {100mm, 200mm, 300mm}, la segunda variable x2 elige {300mm} de {300mm, 400mm, 500mm} y la tercera variable x3 elige {500mm} de {500mm, 600mm, 700mm}, esos valores hacen un nuevo vector solución, {100mm, 300mm, 500mm}. Si este vector solución es mejor que el peor vector en HM, entonces el nuevo vector remplaza al peor. Este proceso se repite hasta que se cumpla el criterio de terminación del algoritmo o se encuentre el óptimo global. B. Estructura del Algoritmo Para explicar el algoritmo HS con mayor detalle, se requiere idealizar el proceso de improvisación realizado por un músico experto. Cuando un músico está improvisando, puede elegir entre tres opciones: (1) ejecutar cualquier tono de su memoria; (2) ejecutar un tono adyacente a cualquier tono de su memoria; (3) ejecutar un tono aleatorio de todo el rango posible de tonos. Estas tres opciones son aplicadas en el algoritmo HS utilizando dos parámetros: grado de consideración o uso de la memoria (Harmony Memory Considering Rate, HMCR) y grado de ajuste de tono (Pitch Adjusting Rate, PAR). El pseudocódigo del algoritmo HS se presenta en el Algoritmo 1. 1) Formulación del problema Según se expone en la sección I, el algoritmo HS fue inicialmente concebido para resolver problemas de optimización donde se considera un solo objetivo. Un problema de optimización mono-objetivo puede ser definido haciendo k=1 en (1): Optimizar

y = f(x) =f(x1, x2,…, xn)

(4)

sujeto a

g(x) = [g1(x), g2(x),…, gm(x)] ≥ 0

(5)

donde

x = [x1, x2,…, xn] ∈ X ⊆ ℝ!

Algoritmo 1. Pseudocódigo del algoritmo Harmony Search. Entrada: f(x), HMCR, PAR, HMS, FW Salida: xbest de HM

a) Selección aleatoria: Cuando HS determina el valor 𝑥!!"# para la nueva solución 𝒙!"# = 𝑥!!"# , 𝑥!!"# , … , 𝑥!!"#  , elige aleatoriamente un valor de todo el rango posible de valores 𝑥! 1 , 𝑥! 2 , … , 𝑥! 𝐾!   o 𝑥!! < 𝑥! < 𝑥!!   con una probabilidad igual a (1   −  HMCR). b) Consideración de la memoria: Cuando HS determina ! el valor 𝑥!!"# , elige aleatoriamente el valor 𝑥! de HM ( 𝑗 = 1,2, … , HMS ) con una probabilidad igual a HMCR. El índice 𝑗 puede ser calculado utilizando una distribución uniforme U 0,1 : 𝑗 ← int 𝑈 0,1 ∗ 𝐻𝑀𝑆 + 1 (7) c) Ajuste de tono: Después de que el valor 𝑥!!"# haya sido elegido aleatoriamente de HM en el proceso explicado anteriormente, éste puede ser ajustado a valores vecinos sumando o restando cierta cantidad, con probabilidad PAR. Para variables discretas, si 𝑥! ∅ = 𝑥!!"! , el ajuste de tono es 𝑥! ∅ + 𝛿 , donde ∅ ∈ 1,2, … , 𝐾! y 𝛿 ∈ −1, 1 . Para variables continuas, el ajuste de tono es 𝑥!!"# + Δ! , donde Δ! = U −1, 1 ∗ FW 𝑖 .

Inicializar HM aleatoriamente while no se cumpla criterio de terminación do for cada variable xi do if U(0,1) < HMCR then ! xnew ← 𝑥! donde j ← int(U(0,1)*HMS)+1 if U(0,1) < PAR then Actualizar xinew con xi(ϕ + δ) o (xinew + Δi) end if else xnew ← valor aleatorio end if end for Evaluar xnew según f(x) if xnew es mejor que xworst then Reemplazar xworst en HM con xnew end if end while xbest ← mejor solución de HM

Si las variables de decisión tienen valores discretos, el conjunto de valores posibles está dado por 𝑥! ∈ 𝒙 = 𝑥! 1 , 𝑥! 2 , … , 𝑥! 𝐾! , donde 𝐾! es la cantidad de valores en el rango de la variable 𝑖 . Si las variables tienen valores continuos, el conjunto de valores posibles para cada una está dado por 𝑥!! ≤ 𝑥! ≤ 𝑥!! , siendo 𝑥!! el límite inferior y 𝑥!! el límite superior de 𝑥! ∈ 𝒙. 2) Configuración de parámetros Además de HMCR y PAR, el algoritmo HS contiene otros parámetros tales como: tamaño de la memoria (HM size, HMS) y rango de variabilidad de tonos (Fret Width, FW [9]), que actúa conjuntamente con PAR en el ajuste de tonos, determinando el ajuste máximo a ser realizado. De manera a utilizar eficientemente la memoria y a realizar ajustes de tonos adecuadamente, se recomienda en [21] que HMCR ∈ [0.70, 0.95] y PAR ∈ [0.1, 0.5].

Las tres operaciones básicas mencionadas anteriormente pueden ser expresadas como sigue:

𝑥!!"#

𝑥! ∈ 𝑥! 1 , 𝑥! 2 , … , 𝑥! 𝐾! 𝑥! ∈ 𝑥!! , 𝑥!! ← 𝑥! ∈ HM = 𝑥!! , 𝑥!! , … , 𝑥!!"# 𝑥! ∅ + 𝛿 si 𝑥! ∅ ∈ HM 𝑥! + Δ!  si 𝑥! ∈ HM

4) Improvisación Como fuera mencionado en la subsección III.B, existen tres opciones entre las que el algoritmo HS puede elegir a la hora de realizar una improvisación:

𝑐. 𝑝.    HMCR ∗   1 − PAR

(8)

𝑐. 𝑝.    HMCR ∗  PAR

5) Actualización de la memoria Si la nueva solución 𝒙!"# es mejor, en términos del valor de la función objetivo, que la peor solución en HM, la nueva solución es incluida en HM y la peor es excluida: 𝒙!"# ∈  HM   ∧   𝒙!"#$% ∉ HM IV.

3) Inicialización de la memoria El algoritmo HS inicialmente improvisa varias soluciones aleatoriamente. El número de soluciones debe ser por lo menos igual a HMS. Sin embargo, puede ser mayor, como el doble o el triple [5]. HM puede ser considerada como una matriz: 𝑓 𝑥! 𝑥!! 𝑥!! ⋯ 𝑥!! ! ! ! 𝑓 𝑥! 𝑥! ⋯ 𝑥! HM = 𝑥! (6) ⋮ ⋮ ⋮ ⋱ ⋮ 𝑥!!"# 𝑥!!"# ⋯ 𝑥!!"# 𝑓 𝑥 !"#

𝑐. 𝑝.     1 − HMCR

(9)

ALGORITMOS HARMONY SEARCH MULTIOBJETIVOS

La diferencia principal entre el algoritmo HS monoobjetivo y las variantes multiobjetivas propuestas en el presente trabajo se basa en el procedimiento de clasificación de soluciones, también conocido como asignación de ranking. La técnica de asignación de ranking consiste en asociar a cada solución un número según se considere mejor o peor que el resto. Esto determina un orden entre las soluciones donde las mejores tienen un ranking menor que las peores. Para un problema mono-objetivo, el ranking de las soluciones está determinado por la función objetivo. Sin embargo, para los problemas multiobjetivos fueron desarrollados varios métodos que incorporan los conceptos de optimalidad Pareto [1]. El método de asignación de ranking elegido para las variantes multiobjetivas del algoritmo HS es el propuesto por

Fonseca y Fleming [6], donde el ranking de una solución 𝑝 se define según la ecuación: 𝑝!"#$ = 1 + 𝑛!

(10)

donde 𝑛! denota la cantidad de soluciones que dominan a la solución p. Por lo tanto, las soluciones no-dominadas de HM tienen asignadas un ranking igual a 1, mientras que las dominadas tienen un ranking comprendido entre 2 y HMS. En la Fig. 2 se muestra un ejemplo hipotético donde se ilustran varios puntos en un espacio objetivo con dos funciones a optimizar y donde cada punto tiene asignado el ranking Fonseca-Fleming.

HS mono-objetivo. La actualización de memoria se realiza en base al ranking Pareto de cada solución, con el mismo procedimiento empleado en el algoritmo HS mono-objetivo. En cada iteración, las soluciones no-dominadas contenidas en HM corresponden a una aproximación al conjunto Pareto del problema que se pretende resolver. Al cumplirse el criterio de terminación, las soluciones con ranking igual a la unidad (no dominadas) contenidas en HM son retornadas como la mejor aproximación al conjunto Pareto óptimo. B. MOHS2: Multiobjective Harmony Search, propuesta 2 La idea principal de esta propuesta, cuyo pseudocódigo se muestra en el Algoritmo 3, consiste en generar en cada iteración una nueva memoria HM2, con la misma cantidad de soluciones que la memoria original, HM1, tal como lo realizan los algoritmos evolutivos con su población de individuos. De la unión de ambas memorias, Hu ← HM1 ∪ HM2, solo la mitad de las soluciones son admitidas como componentes de la memoria para la próxima iteración. Algoritmo 3. Pseudocódigo de MOHS2. Entrada: F(x), HMCR, PAR, HMS, MI, FW Salida: P extraído de HM1

Figura 2. Ranking Fonseca-Fleming para puntos de un espacio objetivo bidimensional.

A. MOHS1: Multiobjective Harmony Search, propuesta 1 Esta propuesta fue concebida de manera a que no requiera cambios significativos en la estructura del algoritmo HS original. El pseudocódigo de la propuesta se muestra en el Algoritmo 2. La diferencia consiste en la utilización de la memoria HM como un repositorio de las mejores soluciones de compromiso halladas hasta un instante dado, especificando sobre las mismas un ranking según el criterio de Fonseca-Fleming. Algoritmo 2. Pseudocódigo de MOHS1. Entrada: F(x), HMCR, PAR, HMS, FW Salida: P extraído de HM Inicializar HM aleatoriamente Calcular ranking Pareto de HM while no se cumpla el criterio de terminación do Improvisar una nueva solución xnew Evaluar xnew según F(x) Calcular el ranking Pareto de xnew con respecto a HM if (xnewrank ≤ xworstrank) and (xnew ∉ HM) then Reemplazar xworst en HM con xnew end if end while

En cada iteración, el algoritmo intenta encontrar una nueva solución de compromiso, utilizando soluciones contenidas en HM. Este procedimiento permanece idéntico al del algoritmo

Inicializar HM1 aleatoriamente Calcular ranking Pareto de HM1 while no se cumpla el criterio de terminación do Vaciar HM2 while no se llenó HM2 do Improvisar una nueva solución xnew a partir de HM1 Evaluar xnew según F(x) Guardar xnew en HM2 end while Hu ← HM1 ∪ HM2 Computar el ranking Pareto sobre Hu /* Obtener mejores soluciones de Hu */ Vaciar HM1 R←1 F ← Extraer toda solución de Hu con ranking R while HM1 tenga espacio ≥ |F| do Mover a HM1 toda solución de F R←R+1 F ← Extraer toda solución de Hu con ranking R end while T ← Espacio restante en HM1 if T > 0 then Aplicar truncamiento con tamaño T a F Mover a HM1 toda solución de F end if end while

El algoritmo propuesto comienza generando soluciones con valores aleatorios para las variables hasta llenar HM1. Cada iteración inicia con la improvisación de todas las soluciones que pertenecerán a HM2, usando la misma técnica de selección que el algoritmo HS mono-objetivo. Al terminar la improvisación de soluciones y haber realizado la unión de ambas memorias, se procede a calcular el ranking FonsecaFleming de Hu.

Terminado el proceso de asignación de ranking, se seleccionan a las mejores soluciones de Hu. Para llevar esto a cabo, primero se agrupan las soluciones de Hu en frentes, donde cada uno está compuesto por las soluciones que tienen un mismo ranking. Luego, se transfieren las soluciones de estos frentes a HM1 en orden ascendente, es decir, primero las soluciones de frentes con menor ranking y luego aquellas de frentes con ranking sucesivamente más altos. Este procedimiento continúa hasta que la cantidad de soluciones de un frente sea igual o mayor al tamaño disponible en HM1. Si el tamaño del frente excede el espacio disponible en HM1, se aplica el procedimiento de truncamiento desarrollado para el algoritmo evolutivo SPEA2 [25]. El truncamiento reduce la cantidad de soluciones hasta que el tamaño del frente sea igual al espacio disponible en HM1. Habiendo finalizado la transferencia de soluciones, HM1 está compuesto de un nuevo conjunto de soluciones para la próxima iteración.

TABLA I.

Parámetro HMCR PAR HMS FW (ZDT5) FW (otros ZDT)

TABLA II.

RESULTADOS EXPERIMENTALES

Para validar los algoritmos MOHS1 y MOHS2 fueron realizadas pruebas experimentales sobre dos conjuntos representativos de funciones de prueba, ZDT [24] y algunas propuestas en el CEC 2009 [20], y comparados contra el algoritmo evolutivo NSGA-II, disponible en [16]. Cada uno de los tres algoritmos fue ejecutado 10 veces, durante un tiempo de 10 segundos en cada una de las ejecuciones, para cada una de las funciones de prueba. Las métricas consideradas en la evaluación de cada ejecución, fueron propuestas en [24]: •

𝑀!∗ : Distancia entre el frente Pareto calculado y el frente Pareto óptimo (representa calidad de soluciones).

•

𝑀!∗ : Distribución del frente Pareto calculado.

•

𝑀!∗ : Extensión del frente Pareto calculado.

Además, en este trabajo se utilizó una métrica adicional sobre el frente Pareto resultante de la combinación de los frentes calculados por cada algoritmo en todas sus ejecuciones: •

𝑀!∗ : Cantidad de soluciones del frente Pareto.

Los valores calculados para las métricas de desempeño 𝑀!∗ , ∗ 𝑀! y 𝑀!∗ fueron normalizados a un número en el intervalo [0, 1] y para la métrica de desempeño 𝑀!∗ a un número en el intervalo [0, ∞], según [13]. De esta manera, para cada métrica, la unidad representa el valor óptimo mientras que se consideran peores a los valores sucesivamente más alejados de la unidad. La Tabla I muestra los valores adoptados para parámetros de los algoritmos MOHS propuestos, y fueron elegidos según recomendaciones de Yang [20], Gao [7] y Geem [8], [9]. La Tabla II muestra los valores adoptados para parámetros del algoritmo NSGA-II, y fueron tomados de [16].

Valor 0.95 0.1 100 40% 1%

PARÁMETROS DEL ALGORITMO NSGA-II.

Parámetro Tamaño de población Probabilidad de cruzamiento Probabilidad mutación (ZDT5) Probabilidad de mutación (otros ZDT) Índice de distribución para cruzamiento Índice de distribución para mutación

Al cumplirse el criterio de terminación del algoritmo, las soluciones contenidas en HM1 con ranking igual a la unidad (soluciones no dominadas) son retornadas como la mejor aproximación al conjunto Pareto óptimo. V.

PARÁMETROS DE LOS ALGORITMOS HS MULTIOBJETIVOS

Valor 100 0.9 1/b 1/n 15 20

n es la cantidad de variables del problema y b es la cantidad total de bits de todas las variables (para problemas binarios).

A. Resultados En la Tabla III se presenta el ranking general de los algoritmos y el de las métricas 𝑀!∗ , 𝑀!∗ y 𝑀!∗ . Estos valores representan el promedio de los valores obtenidos por cada algoritmo en todas las funciones de prueba. Los resultados indican que los algoritmos MOHS propuestos se encuentran al nivel del algoritmo NSGA-II, principalmente en la métrica 𝑀!∗ , la más relevante. Respecto a la métrica 𝑀!∗ , los algoritmos MOHS superan considerablemente al algoritmo NSGA-II para cada una de las funciones de prueba. En la Tabla IV se presenta el ranking de los algoritmos para esta métrica de desempeño. Los valores de esta tabla representan el promedio de los valores obtenidos por cada algoritmo en todas las funciones de prueba.

TABLA III. Pos

RANKING GENERAL DE ALGORITMOS.

𝑴∗𝟐

𝑴∗𝟑

Ranking

NSGA-II 0.77

NSGA-II 0.96

NSGA-II 0.72

𝑴∗𝟏 MOHS1

2º

NSGA-II 0.44

MOHS2

0.76

MOHS1

0.90

MOHS1

0.69

3º

MOHS2

MOHS1

0.74

MOHS2

0.90

MOHS2

0.69

TABLA IV.

0.44

General

1º

0.41

CANTIDAD DE SOLUCIONES DE LOS ALGORITMOS. Pos

𝑴∗𝟒

1º

MOHS1

0.95

2º

MOHS2

0.90

3º

NSGA-II 0.62

Figura 3. Evolución temporal de la métrica M!∗

B. Análisis temporal Las muestras para el análisis temporal fueron obtenidas cada 50 milisegundos, los valores representan promedios de las 10 ejecuciones de cada algoritmo para todas las funciones de prueba y se encuentran normalizados según [13]. En la Fig. 3 se muestra la evolución temporal de la métrica 𝑀!∗ . Se puede observar que los algoritmos MOHS1 y MOHS2 presentan el peor desempeño en comparación al NSGA-II, si consideramos tiempos muy reducidos. Sin embargo, a medida que trascurre el tiempo, los algoritmos MOHS van mejorando en desempeño, a tal punto que consiguen alcanzar y superar al NSGA-II. Considerando la métrica 𝑀!∗ , mostrada en la Fig. 4, los resultados muestran que los tres algoritmos tienen un rendimiento promedio similar a partir del segundo de ejecución. Sin embargo, se puede notar que los algoritmos MOHS tienen un mejor rendimiento al inicio de la ejecución pero reduciéndolo rápidamente a medida que transcurre el tiempo.

Para la métrica 𝑀!∗ , mostrada en la Fig. 5, los tres algoritmos inician la ejecución con valores superiores a la unidad, teniendo los algoritmos MOHS un mejor rendimiento que el NSGA-II. Sin embargo, a partir de los 0,2 segundos de ejecución, el NSGA-II presenta el mejor rendimiento con valores próximos a la unidad, mientras que los algoritmos MOHS reducen su rendimiento a valores ligeramente inferiores. VI.

CONCLUSIONES Y TRABAJOS FUTUROS

La metaheurística Harmony Search ha demostrado ser eficiente en la resolución de varios tipos de problemas de optimización en ingeniería. Sin embargo, la correcta y eficiente aplicación de esta metaheurística para la resolución de problemas de optimización multiobjetivo es una tarea pendiente.

Figura 5. Evolución temporal de la métrica M!∗ Figura 4. Evolución temporal de la métrica M!∗

El presente trabajo plantea, en detalle, dos propuestas de la metaheurística Harmony Search para la resolución de problemas de optimización multiobjetivo en general, considerando un conjunto representativo de funciones de prueba, reconocidos en la literatura de optimización teórica [4], [17], [25], [14], [18], [23].

[5]

Los resultados obtenidos evidencian que los algoritmos MOHS propuestos son competitivos con respecto al reconocido algoritmo del estado del arte, NSGA-II, en cuanto a las métricas 𝑀!∗ , 𝑀!∗ y 𝑀!∗ , y superiores en cuanto a la métrica 𝑀!∗ . Sin embargo, con el análisis temporal se puede notar que los algoritmos MOHS propuestos son inferiores al NSGA-II en cuanto a velocidad de convergencia.

[7]

De manera a dar continuidad a la investigación iniciada en esta tesis, se proponen los siguientes puntos como posibles trabajos futuros: •

Aplicar técnicas de elitismo a los algoritmos MOHS1 y MOHS2 en el operador de selección para generación de nuevas soluciones.

•

Aplicar algún procedimiento de fitness sharing [15] al algoritmo MOHS1.

•

Crear un procedimiento de actualización de la memoria que resulte de aplicar una combinación de las técnicas empleadas por los algoritmos MOHS1 y MOHS2.

•

•

•

•

Considerar un operador de ajuste de tono para variables reales donde siempre se utilice el rango completo del fret width. Aplicar técnicas de paralelismo tanto para mejorar el rendimiento individual de cada una de las propuestas MOHS, como para integrarlas a un esquema maestro/esclavo, de manera a optimizar varias memorias en paralelo. Aplicar las nuevas propuestas a la resolución de problemas clásicos de optimización combinatoria, como por ejemplo el Traveling Salesman Problem (TSP) [2]. Validar las nuevas propuestas comparándolas con otras metaheurísticas de optimización multiobjetivo, como por ejemplo Particle Swarm Optimization (PSO) [12]. REFERENCES

[1]

[2] [3]

[4]

I. Alberto, C. Azcarate, F. Mallor y P. Mateo. Multiobjective Evolutionary Algorithms. Pareto Rankings. Monografías del Seminario Matemático García de Galdeano, vol. 27, p.27–35 (2003). D. Applegate, R. Bixby, V. Chvátal y W. Cook. The traveling salesman problem: A Computational Study. Princeton University Press (2006). C. A. Coello Coello. A Short Tutorial on Evolutionary Multiobjective Optimization. Evolutionary Multi-Criterion Optimization, vol. 1993, pp. 21–40 (2001). K. Deb, A. Pratap, S. Agarwal, T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182-197 (2002).

[6]

[8] [9]

[10] [11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21] [22]

[23]

[24]

[25]

S. Degertekin. Optimum Design of Steel Frames using Harmony Search Algorithm. Structural and multidisciplinary optimization 36(4), 393-401 (2008). C. Fonseca y P. Fleming. Genetic Algorithms for Multiobjective Optimization: Formulation Discussion and Generalization. Proceedings of the 5th International Conference on Genetic Algorithms, 416-423 (1993). X. Gao, X. Wang y S. Ovaska. Harmony search methods for multimodal and constrained optimization. Music-Inspired Harmony Search Algorithm 191/2009, 39-51 (2009). Z. W. Geem. Optimal cost design of water distribution networks using harmony search. Engineering Optimization 38(3), 259-277 (2006). Z. W. Geem. State-of-the-Art in the Structure of Harmony Search Algorithm. Recent Advances in Harmony Search Algorithm 270/2010, 1-10 (2010). Z. W. Geem, J. Kim, G. Loganathan. A New Heuristic Optimization Algorithm: Harmony Search. SIMULATION, 60-68 (2001). G. Ingram y T. Zhang. Overview of applications and developments in the harmony search algorithm. Music-Inspired Harmony Search Algorithm 191/2009, 15-37 (2009). J. Kennedy y R. Eberhart. Particle Swarm Optimization. IEEE International Conference on Neural Networks, Perth, WA , Australia, vol. 4, pp.1942-1948 (1995). J. Lima. Optimización de Enjambre de Partículas aplicada al Problema del Cajero Viajante Bi-objetivo. Universidad Nacional de Asunción, San Lorenzo. Tesis de Grado para el título de Ingeniero en Informática (2007). M. Liu, X. Zou, Y. Chen y Z. Wu. Performance Assessment of DMOEA-DD with CEC 2009 MOEA Competition Test Instances. 2009 IEEE Congress on Evolutionary Computation, pp. 2913-2918 (2009). C. von Lücken. Algoritmos Evolutivos para Optimización Multiobjetivo: Un estudio comparativo en un ambiente paralelo asíncrono. Tesis de Master no publicada, Universidad Nacional de Asunción (2003). Multiobjective NSGA-II code in C. Kanpur Genetic Algorithm Laboratory. (Accedido en Julio 2010) Disponible en: http://www.iitk.ac.in/kangal/codes/nsga2/nsga2-gnuplot-v1.1.564bit.tar.gz. K. E. Parsopoulos y M. N. Vrahatis. Recent approaches to global optimization problems through Particle Swarm Optimization. Natural Computing 1(2-3), 235-306 (2002). K. Sindhya, A. Sinha, K. Deb y K. Miettinen. Local Search based Evolutionary Multi-objective Optimization Algorithm for Constrained and Unconstrained Problems. 2009 IEEE Congress on Evolutionary Computation, pp. 2919-2926 (2009). D. van Veldhuizen y G. Lamont. Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art. Evolutionary Computation 8(2), 125-147 (2000). H. Xu, X. Gao, T. Wang y K. Xue. Harmony Search Optimization Algorithm: Application to a Reconfigurable Mobile Robot Prototype. Recent Advances In Harmony Search Algorithm 270/2010, 11-22 (2010). X. S. Yang. Harmony Search as a Metaheuristic Algorithm. MusicInspired Harmony Search Algorithm 191/2009, 1-14 (2009). Q. Zhang, A. Zhou, S. Zhao, P. Suganthan, W. Liu y S. Tiwari. Multiobjective Optimization Test Instances for the CEC 2009 Special Session and Competition. Technical Report CES-487, University of Essex and Nanyang Technological University (2009). Q. Zhang, W. Liu y H. Li. The Performance of a New Version of MOEA/D on CEC09 Unconstrained MOP Test Instances. 2009 IEEE Congress on Evolutionary Computation, pp. 203–208 (2009). E. Zitzler, K. Deb y L. Thiele. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation 8(2), 173-195 (2000). E. Zitzler, M. Laummans, L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103, Computer Engineering and Networks Laboratory (TIK), Zurich, Switzerland (2001).