Aplicación de metaheurísticas en Computación

APLICACIONES DE METAHEURÍSTICAS EN COMPUTACIÓN
Marcela Rivera Martínez, Luis René Marcial Castillo, Lourdes Sandoval Solís
Facultad de Ciencias de la Computación
Benemérita Universidad Autónoma de Puebla.
INTRODUCCIÓN Y OBJETIVOS
Las metaheurísticas son técnicas que permiten aproximar los óptimos globales, además de
poderse paralelizar. Nuestro grupo de trabajo ha aplicado éstas técnicas a problemas como:
Supersecuencia común más corta (SCS)
Restauración de Imágenes
Ancho de banda de matrices dispersas
Makespan en problemas de calendarización
Asignación Cuadrática
Agente viajero
Coloreo de grafos
Problema de la mochila
Entrenamiento de Redes Neuronales Supervisadas
Análisis de Correlaciones Canónicas
Se han aplicado las siguientes técnicas:
Recocido Simulado
Algoritmos Genéticos
Colonia de Hormigas
Colonia de Abejas
Búsqueda Armónica
Colonia de luciérnagas
En particular, el problema SCS se han implementado las heurísticas H1, H2, H3 con
diferentes propuestas para elegir la letra que incluimos en la supersecuencia, este trabajo
está publicado en [1]. Actualmente está aceptado una estrategia evolutiva para resolver
SCS, en el CLAIO 2014.
Los problemas de restauración de imágenes son de gran escala y además requieren del
óptimo global, por lo que una paralelización de estos algoritmos reduciría los tiempos de
cómputo.
Todos los problemas citados arriba son NP-completos, por lo que requieren bastante tiempo
de cómputo.
En este proyecto se propone publicar los resultados en revistas indexadas, exponerlos en
eventos académicos internacionales e involucrar estudiantes de la Facultad de Ciencias de
la Computación.
METODOLOGÍA Y JUSTIFICACIÓN DE USO DE SUPERCÓMPUTO
En este proyecto se propone paralelizar las meta heurísticas ya implementadas y probadas
secuencialmente, en los problemas ya trabajados, con el objetivo de mejorar los tiempos y
el tamaño de los problemas.
Hay que considerar que las meta heurísticas son técnicas estocásticas, por lo que para
reportar resultados científicos hay que ejecutar un mismo problema prueba (benchmark), de
tamaño medio, alrededor de 100 veces, además de tomar en cuenta que cada ejecución
requiere horas de procesamiento, en máquinas con procesadores i7.
No hay que olvidar que para calibrar una meta heurística se requieren un gran número de
ejecuciones.
Se podrían probar nuestras implementaciones de las meta heurísticas en problemas prueba a
gran escala.
El problema de la supersecuencia común más corta está dado de la siguiente forma:
Dado un lenguaje L sobre un alfabeto , se desea encontrar una de las cadenas w de menor
longitud que sea una supersecuencia de L. Se dice que S es una supersecuencia de una
cadena T, si S se puede obtener desde T mediante la inserción de cero o más símbolos de la
misma cadena. Ejemplo: Dado  = {a, b} y L = {ab, ba}; las siguientes cadenas son
supersecuencias de L: “abba”, “aabba”, “aba”, “bab”. No son las únicas, existen muchas
más, se dice que todas ellas son supersecuencias porque cada una de ellas contiene a todas
las cadenas de L (aún cuando no las contengan de manera contigüa). Ahora bien, las
supersecuencias comunes más cortas son dos y son: S = aba y S = bab. Ambas son
supersecuencias de L y son las más cortas porque ambas son de longitud 3, se denota: |S| =
3, es decir, la supersecuencia puede no ser única.
En el caso de la SCS, se ha logrado realizar una meta heurística basada en población, esto
es, una técnica iterativa que aplica estocásticamente operadores sobre una población de
individuos, algunas operadores estocásticos, requieren de un gran costo computacional, por
ejemplo, en cada iteración se tiene que evaluar la función objetivo, en éste caso específico
el de la SCS, hasta ahora, la función objetivo involucra la reducción hacia adelante y hacia
atrás de cada cadena sobre todo el lenguaje.
El paralelismo en la mayoría de los meta heurísticas poblacionales se da de manera natural,
en donde se tiene la opción de dividir la población (islas) y realizar el algoritmo en cada
isla, manteniendo una comunicación entre dichas islas.
La restauración de imágenes digitales con funciones potenciales no convexas y no suaves
requieren de encontrar el mínimo global, las meta heurísticas son la forma más conveniente
de resolver el problema. Se han implementado las heurísticas colonia de luciérnagas y
colonia artificial de abejas para resolver el problema pero se requiere de gran potencia de
cálculo para resolver problemas de alta dimensión, que con computadoras personales no es
posible de lograr.
La clasificación mediante redes neuronales artificiales no da buenos resultados cuando la
función de error es continuamente diferenciable y se usan métodos de descenso. Es
conveniente modificar la función de error de modo que ya no sea continuamente
diferenciable, donde la aplicación de meta heurísticas es conveniente. Se han implementado
la colonia artificial de abejas y colonia de luciérnagas para este problema funcionando bien
para bases de datos pequeñas. Pero en bases de datos grandes las computadoras personales
ya no son funcionales de ahí que se requiere un equipo que tenga gran poder de cálculo.
En el análisis de correlaciones canónicas se desea encontrar la mayor covarianza entre
dos conjuntos de atributos de los mismos individuos, hasta ahora se ha utilizado la
regularización para resolverlo, pensamos que usando meta heurísticas se podrá evitar el
hecho de su mal condicionamiento y trabajar grandes volúmenes de información.
SOFTWARE REQUERIDO. PRIORIDADES E INDICAR SI ES COMERCIAL O
LIBRE
Actualmente se ha trabajado en MATLAB, este lenguaje nos permite programar en
paralelo.
Este software es comercial.
PRODUCTOS ESPERADOS (TESIS, ARTÍCULOS, DESARROLLO DE SOFTWARE)
En este proyecto se propone publicar los resultados en revistas indexadas, exponerlos en
eventos académicos internacionales e involucrar estudiantes de la Facultad de Ciencias de
la Computación. Además de generar nuestro propio software que nos permita experimentar
y así poder proponer los algoritmos más adecuados a cada problema. Desarrollar tesis de
licenciatura, maestría y doctorado en Computación y Matemáticas.
REFERENCIAS
1.
2.
3.
4.
5.
6.
M. Rivera, L. R. Marcial, L Sandoval. Heurísticas para resolver el problema de la Supersecuencia Común
más corta. Research in Computing Science, 60, 55-64, 2012.
S. Rajendran, C. Rajendran and H. Ziegler. An Ant-Colony Algorithm to Transform Jobshops into
Flowshops: A Case of Shortest-Common-SupersequenceStringology Problem. Bio-Inspired Models of
Network, Information, and Computing Systems Lecture Notes of the Institute for Computer Science,
Social Informatics and Telecomunications Engineering. Vol. 87, 413-224, 2012.
J. M. Framiñan. Efficient heuristic approaches to transform job shops into flow shops. IIE Transactions,
37, 441-451, 2005.
Enrique Alba, Gabriel Luquea and Sergio Nesmachnowb.Parallel metaheuristics: recent advances and
new trends. Intl. Trans. in Op. Res. 20 ,1–48, 2013.
Enrique Alba,Parallel Metaheuristics: A New Class of Algorithms. John Wiley and Sons. 2005.
Teodor Gabriel Crainic, TatjanaDavidović , Chapter 11. Designing Parallel Meta-Heuristic
Methods. Handbook of Research on High Performance and Cloud Computing in Scientific Research and
Education, IGI Global 2014

Download Report