Please use this identifier to cite or link to this item: http://repositorio.udec.cl/jspui/handle/11594/896
Title: Algoritmos para el cálculo de la cadena media.
Authors: Seco Naveiras, Diego, supervisor de grado
Abreu Salas, José Ignacio, supervisor de grado
Sánchez Mirabal, Pedro Aniel
Keywords: Algoritmos Computacionales;Programación Lineal
Issue Date: 2019
Publisher: Universidad de Concepción, Facultad de Ingeniería, Departamento de Ingeniería Informática y Ciencias de la Computació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.
URI: http://repositorio.udec.cl/jspui/handle/11594/896
Appears in Collections:Ingeniería Informática y Ciencias de la Computación - Tesis Doctorado

Files in This Item:
File Description SizeFormat 
Tesis algoritmo para el calculo.pdf1,22 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.