Algoritmos para el cálculo de la cadena media.
Loading...
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción.
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.
Description
Tesis para optar al grado de Doctorado en Ciencias de la Computación.
Keywords
Algoritmos Computacionales, Programación Lineal, Industria, Innovación e Infraestructura