Análisis comparativo de métodos para resolver el problema de la supersecuencia común más corta.

Sarid 23/Noviembre/2011
RESUMEN
*Análisis comparativo de métodos para resolver el problema de la supersecuencia común más corta.
En este trabajo se presenta el problema de la Supersecuencia Común más Corta, el cual es un problema NP y tiene aplicaciones en compresión de datos,ingeniería mecánica y planeación entre otros. Para resolverlo, se aplica la metaheurística de Colonia de Hormigas, junto con las heurísticas Majority Merge y Lookahead para tomar la decisión sobre el símbolo que pasará a formar parte de la Supersecuencia. Se compara con un método de Programación Dinámica a fin de medir su eficiencia para problemas sintéticos generados aleatoriamente.
El problemade la Supersecuencia Común más Corta (Shortest Common Supersequence, SCS) 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. Dentro de losproblemas de optimización combinatoria, se encuentra el problema de la SCS, el cual está clasificado como un problema NP-duro [1,2], el problema de la SCS tiene aplicaciones en compresión de datos, ingeniería mecánica y planeación entre otros [3].
En este trabajo se describe la aplicación de la metaheurística ACO para el Problema de la SCS; adicionalmente, se utiliza el enfoque de programacióndinámica para poder comparar la longitud de la SCS obtenida por la metaheurística ACO.
En la siguiente sección se dará el enfoque de los algoritmos basados en colonias de hormigas; la sección posterior explica brevemente el enfoque de programación dinámica; en el siguiente apartado se muestran los experimentos y resultados de los mismos. En la última sección, se exponen las conclusiones yfinalmente se presentan las referencias. Los algoritmos ACO están inspirados en la observación de colonias de hormigas reales, las cuales son insectos sociales y tienen un comportamiento más dirigido a la supervivencia de la colonia que a un individuo en particular, para sobrevivir tienen que buscar fuentes de alimentos, para ello inicialmente cada hormiga busca una fuente de alimento aleatoriamente,después de un tiempo se observa que la mayoría de las hormigas sigue un mismo camino, el cual es el más corto entre su nido y la fuente de alimento. Las hormigas se comunican mediante el uso de una sustancia química llamada feromona, y cada una de ellas coopera en la solución del problema segregando una cierta cantidad de feromona, por lo cual aún cuando se modifique su ambiente las siguienteshormigas son guiadas hacia las fuentes de alimento [10].
La metaheurística ACO, utiliza tres heurísticas diferentes para elegir el símbolo que formará parte de la SCS, las heurísticas son: Majority Merge (MM), Lookahead Function (LF), y L-Majority Merge (L-MM) [10]. La heurística MM elige aquél símbolo que esté al frente de cada cadena y que sea el de mayor probabilidad, la función de probabilidadde elegir el símbolo a es:

,
donde, es un parámetro que controla la varianza de la distribución.
La heurística LF además de fijarse en el símbolo que aparece al inicio de cada cadena considera la probabilidad del segundo símbolo en la cadena y el caracter con la máxima suma de probabilidades es el elegido, esto se calcula de la siguiente forma:

Sarid23/Noviembre/2011
donde, y denotan la cantidad de feromona y el conjunto de símbolos candidatos en el nuevo estado , formado una vez que se ha elegido el símbolo a. Además la función de probabilidad ahora se calcula de acuerdo a:
,
aquí regula la influencia de .
La heurística L-MM es la heurística Majority...