Desempeño de metaheurísticas sin memoria en el problema del LABS

Published in: Innovation in Engineering, Technology and Education for Competitiveness and Prosperity: Proceedings of the 11th Latin American and Caribbean Conference for Engineering and Technology
Date of Conference: August 14-16, 2013
Location of Conference: Cancun, Mexico
Authors: Jhon Edgar Amaya Salazar
María de los Ángeles Tarazona
Refereed Paper: #246

Abstract:

In English:
This paper addresses the low-autocorrelation binary sequences (LABS) problem, which is a difficult combinatorial optimization problem. The LABS problem has been studied since the early 60's by physicists and researchers in the area of artificial intelligence, since the problem has many applications in various fields (chemistry, physics, telecommunications, etc.). This research analyzes the performance of different metaheuristics without memory for solving the LABS problem, such as: Hill Climbing (HC), Iterated Local Search (ILS), Genetic Algorithm (GA), a memetic algorithm (MA) and a cooperative version. In particular, we performed a basic analysis of the performance of each algorithm in solving the LABS problem. A comparative method was used for statistical analysis of data. Experimental results show that the cooperative algorithm presented the best results for instances of LABS problem analyzed.


In Spanish:
El presente trabajo aborda la búsqueda de secuencias binarias de baja autocorrelación (LABS), el cual es un problema difícil de optimización combinatoria. El problema del LABS ha sido estudiado desde la década de los 60’s por las comunidades de físicos y en el área de inteligencia artificial, pues el problema tiene muchas aplicaciones en diversas áreas (radares, química, física, telecomunicaciones, entre otras). En la investigación se analiza el comportamiento de diferentes metaheurísticas sin memoria para solucionar el problema del LABS, como lo son: Hill Climbing (HC), Búsqueda Local Iterada (ILS), Algoritmo Genético (GA), un Algoritmo Memético (MA) y una versión cooperativa. En particular, se realizó un análisis básico del desempeño de cada algoritmo en la solución del problema del LABS, utilizando un método comparativo estadístico para el tratamiento de los datos. Los resultados experimentales muestran que el algoritmo cooperativo presentó los mejores resultados para las instancias del problema del LABS analizadas.