Algoritmos para el cálculo de la cadena media.

Abstract

El problema de la cadena media es NP-hard para muchas de sus formulaciones, específicamente cuando se emplea la distancia de edición de Levenshtein. Las heurísticas más competitivas aplicadas a este problema usan algoritmos basados en hacer perturbaciones sucesivas a una solución inicial, estos algoritmos son llamados perturbation-based iterative algorithms. La cadena inicial y la política para establecer un orden entre las posibles ediciones son esenciales en la eficiencia de estos algoritmos. En esta tesis se abordan estos sub-problemas. Primero, se estudia cómo una mejor clasificación de las posibles perturbaciones atendiendo a su calidad, tiene efectos en la convergencia de los algoritmos, como consecuencia de esto, se obtiene un nuevo ranking de perturbaciones, que no solamente tiene en cuenta lo que ocurre en relación con las cadenas en las que dicha perturbación está presente, si no, también con respecto al resto de las cadenas del conjunto. Luego, se muestra como la cadena inicial influye en el proceso, analizando principalmente dos variantes de inicialización para estos algoritmos, la cadena perteneciente al conjunto con menos distancia al resto, y la media de un subconjunto de la entrada del algoritmo. Este subconjunto mencionado anteriormente es determinado por los vecinos obtenidos al aplicar el algoritmo Half Space Proximal (HSP) a la cadena mediana del conjunto. De la misma forma, se proponen alternativas para la reducción del conjunto de datos a procesar, sustituyéndolo por un subconjunto de éste, con el fin de disminuir los costes computacionales de los algoritmos. Finalmente, se valida la calidad de los algoritmos obtenidos mediante algoritmos de optimización que resuelven este problema de forma óptima. En el proceso de validación se lleva a cabo un gran número de experimentos que dan soporte a las conclusiones obtenidas. En estos experimentos se muestra que el error de los algoritmos diseñados se encuentra bien acotado, obteniendo soluciones óptimas para los casos en que SAT o ILP logran determinar el ´óptimo. En los casos en que el óptimo no es determinado por SAT o ILP, la solución encontrada es mejor o igual, logrando obtenerla en un tiempo de cómputo menor.