Ventajas y desventajas del SPEA2

[pic 1][pic 2]

Strength Pareto Evolutionary Algorithm II.

Diego Araneda Hidalgo, Gustavo Sepúlveda Ocampo, y Javier Victoriano Rivas

Resumen—La mayoría de los problemas existentes en el mundo real contienen 2 o más variables que son con- tradictorias a considerar cuando se busca una solución, en otras palabras la mejora de una de estas variables puede afectar a las otras, lo que puede dificultar la tarea de encontrar la mejor solución, esto se llama optimización de multiobjetivo. Para poder resolver un problema de optimización multiobjetivo se pueden utilizar algoritmos para realizar la tarea de manera mas eficiente, y una de las opciones mas frecuentes suelen ser los algoritmos genéticos o evolutivos ya que estos son capaces de analizar múltiples soluciones al mismo tiempo haciendo el trabajo de buscar la solución óptima mucho mas rápido. En este trabajo se estudiara el algoritmo genético o evolutivo llamado strength pareto evolutionary algorithm II (SPEA2), el cual se enfoca en estudiar e iterar sobre el conjunto de soluciones óptimas o soluciones de pareto para encontrar la mejor de las opciones a algún problema de optimización de multiobjetivo. Se estudiara sobre su origen, la forma en la que opera, y las posibles aplicaciones en diferentes problemas del mundo real a los que puede ayudar a encontrar una mejor solución que otros métodos.

1. Introducción[pic 3]

N un problema de optimización de multiobjetivo existe un conjunto de posibles soluciones donde no

se puede mejorar una variable sin afectar a otra, estos puntos son llamados óptimos de pareto y dentro de las posibles soluciones a un problema de optimización de mul- tiobjetivo existen muchas soluciones óptimas de pareto. Hay muchos algoritmos capaces de ayudar en la búsqueda de una solución óptima de un problema de optimización de multiobjetivo y uno de los tipos de algoritmos mas frecuen- temente usados son los algoritmos genéticos o evolutivos, y uno de los mas usados antiguamente era el strength pareto evolutionary algorithm (SPEA) [1] que analizaba el conjunto de soluciones óptimas de pareto de un problema multivariable para encontrar una solución óptima, pero con el paso del tiempo este fue quedándose atrás en desempeño en ciertos problemas, por lo que se diseño y creo el strength pareto evolutionary algorithm II (SPEA2) [2], el cual realizaba varias mejoras al algoritmo original, entre ellas esta la mejora a la función de fitness la cual es la función que permite calcular que tan buena o mala es una solución. El SPEA2 es muy bueno cuando se trata de trabajar con 2 o 3 variables permitiendo optimizar muchos problemas reales y aunque es capaz de trabajar con mas

Diego Araneda Hidalgo, Gustavo Sepúlveda Ocampo y Javier Vic- toriano Rivas son estudiantes de la carrera de Ingeniería Civil Infor- mática del Departamento de Ingeniería Informática, Facultad de In- geniería, Universidad Católica de la Santísima Concepción, Concep- ción, Chile. Email: {daranedah,gsepulvedao,jvictoriano}@ing.ucsc.cl.

Manuscrito recibido el 29 de Septiembre de 2022.

variables, su certeza decae al agregar mas y mas variables al problema, es por eso que sus principales aplicaciones son en problemas reales con 2 o 3 variables ya que si se desea optimizar un problema de mas variables se pueden usar otros tipos de algoritmos especializados en esos problemas llamados many-objective optimization problems (MaOPs) [3]. Los objetivos que nos planteamos para este articulo son.

Explicar la historia y el porque de la creación del SPEA2.[pic 4]

Entender que son los algoritmos evolutivos.[pic 5]

Exponer distintas aplicaciones del SPEA2 en la vida real.[pic 6]

Comprender las ventajas y desventajas del SPEA2.[pic 7]

I-A. Historia

Para saber de dónde proviene o desde donde se va armando el Strenghth Pareto Evolutionary Algorithm que cuyo acrónimo es SPEA, primeramente tenemos que saber, cómo fue que sé desarrollo este algoritmo. A mediados de los 1980s después de los primeros estudios sobre la optimización evolutiva multiobjetivo, varias técnicas ba- sadas en Pareto fueron propuestas en 1993 por Fonseca y Fleming y en 1994 por Horn, Nafpliotis y Goldberg, los cuales pudieron demostrar la suficiente  competencia que presentaba la optimización evolutiva multiobjetivo o en su acrónimo en ingles EMO, el cuál sé aproximaba al conjunto de compensaciones óptimas en una sola ejecu- ción de la optimización, estas aproximaciones hechas por los autores anteriormente mencionados no incorporaban explícitamente el elitismo, la cual nos menciona que aquel o aquellos individuos que son los más aptos de la población actual sobrevivan y continúen participando del proceso evolutivo. Unos años más tarde este mismo concepto de elitismo fue reconocido experimentalmente. A través de los avances antes mencionados, fue que sé pudieron presentar algunos algoritmos evolutivos multiobjetivo elitistas, que consiguientemente nos fue presentado por Eckart Zitzler y Lothar Thiele en 1999 y que sería llamado SPEA, el cual es un algoritmo que encuentra el conjunto de pareto óptimos para problemas de  optimización  multiobjetivo, con el pasar del tiempo y a partir de diferentes estudios hechos de la misma manera por Zitzler, Thiele y ahora también Deb, nos muestra  que  el  algoritmo  se  desarro- lla de mejor manera en comparación a otros algoritmos evolutivos multiobjetivo. Luego de un tiempo comenza- ron a aparecer nuevos algoritmos capaces de superar en desempeño al algoritmo SPEA dejándolo algo obsoleto y fue por eso que se decidió el mejorarlo y adaptarlo a los nuevos estándares de desempeño en la optimización de

multiobjetivos, Creando así el SPEA2 que buscaba tener un mejor desempeño que su antecesor SPEA mediante el cambio a ciertas funcionalidades como su función de fitness o una mejora en su proceso de búsqueda [2].[pic 8][pic 9]

I-B.        Analogía

Los algoritmos  evolutivos  o  genéticos  se  inspiran  en la evolución, para ser mas específicos se enfocan en la selección, reproducción y  mutación. En estos  algoritmos se simula a varios individuos como distintas soluciones de

Figura 1: Representación del Strength Pareto Evolutio- nary Algorithm.Fuente obtenida de, SPEA2: Improving the Strength Pareto Evolutionary Algorithm [2].

...