Comparación entre algoritmos evolutivos de objetivo único y multiobjetivo para resolver el problema de la mochila y el problema del viajante de comercio
Autores: Mahrach, Mohammed; Miranda, Gara; León, Coromoto; Segredo, Eduardo
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Comparación entre algoritmos evolutivos de objetivo único y multiobjetivo para resolver el problema de la mochila y el problema del viajante de comercio
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Diversidad
Población
Convergencia
Optimización
Objetivos
Algoritmos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
Uno de los componentes principales de la mayoría de los Algoritmos Evolutivos Multi-Objetivo Modernos (MOEAs, por sus siglas en inglés) es mantener una diversidad adecuada dentro de una población para evitar el problema de la convergencia prematura. Debido a esta característica implícita que comparten la mayoría de los MOEAs, su aplicación para la Optimización de un Solo Objetivo (SO) podría ser útil y proporciona un campo de investigación prometedor. Algunos enfoques comunes sobre este tema se basan en agregar objetivos adicionales, generalmente artificiales, a la formulación del problema. Sin embargo, al aplicar MOEAs a Problemas de Optimización Multi-Objetivo Implícitos (MOPs), no es común analizar qué tan efectivos son dichos enfoques en relación con la optimización de cada objetivo por separado. En este trabajo, presentamos un estudio comparativo entre MOEAs y Algoritmos Evolutivos de un Solo Objetivo (SOEAs) al optimizar cada objetivo en un MOP, considerando aquí el caso bi-objetivo. Para el estudio, nos enfocamos en dos problemas de optimización bien conocidos y ampliamente estudiados: el Problema de la Mochila (KNP) y el Problema del Viajante de Comercio (TSP). El estudio experimental considera tres MOEAs y dos SOEAs. Cada SOEA se aplica de forma independiente para cada objetivo de optimización, de modo que los valores optimizados obtenidos para cada objetivo puedan compararse con las soluciones multi-objetivo logradas por los MOEAs. Sin embargo, los MOEAs permiten optimizar dos objetivos a la vez, ya que las fronteras de Pareto resultantes se pueden utilizar para analizar los extremos, es decir, el punto que optimiza el objetivo 1 y el punto que optimiza el objetivo 2. Los resultados experimentales muestran que, aunque los MOEAs tienen que lidiar con varios objetivos simultáneamente, pueden competir con los SOEAs, especialmente al tratar con instancias fuertemente correlacionadas o grandes.
Descripción
Uno de los componentes principales de la mayoría de los Algoritmos Evolutivos Multi-Objetivo Modernos (MOEAs, por sus siglas en inglés) es mantener una diversidad adecuada dentro de una población para evitar el problema de la convergencia prematura. Debido a esta característica implícita que comparten la mayoría de los MOEAs, su aplicación para la Optimización de un Solo Objetivo (SO) podría ser útil y proporciona un campo de investigación prometedor. Algunos enfoques comunes sobre este tema se basan en agregar objetivos adicionales, generalmente artificiales, a la formulación del problema. Sin embargo, al aplicar MOEAs a Problemas de Optimización Multi-Objetivo Implícitos (MOPs), no es común analizar qué tan efectivos son dichos enfoques en relación con la optimización de cada objetivo por separado. En este trabajo, presentamos un estudio comparativo entre MOEAs y Algoritmos Evolutivos de un Solo Objetivo (SOEAs) al optimizar cada objetivo en un MOP, considerando aquí el caso bi-objetivo. Para el estudio, nos enfocamos en dos problemas de optimización bien conocidos y ampliamente estudiados: el Problema de la Mochila (KNP) y el Problema del Viajante de Comercio (TSP). El estudio experimental considera tres MOEAs y dos SOEAs. Cada SOEA se aplica de forma independiente para cada objetivo de optimización, de modo que los valores optimizados obtenidos para cada objetivo puedan compararse con las soluciones multi-objetivo logradas por los MOEAs. Sin embargo, los MOEAs permiten optimizar dos objetivos a la vez, ya que las fronteras de Pareto resultantes se pueden utilizar para analizar los extremos, es decir, el punto que optimiza el objetivo 1 y el punto que optimiza el objetivo 2. Los resultados experimentales muestran que, aunque los MOEAs tienen que lidiar con varios objetivos simultáneamente, pueden competir con los SOEAs, especialmente al tratar con instancias fuertemente correlacionadas o grandes.