Algoritmos heurísticos y aplicaciones a métodos formales

Abstract

Los algoritmos de optimización basados en búsquedas locales recorren el espacio de soluciones tratando de conseguir una buena solución en un tiempo razonable para minimizar o maximizar un valor y tratando de evitar quedarse estancado en mínimos o máx imos locales. Para ello parten de una solución y la modifican aplicando ciertos operadores para calcular soluciones vecinas que mejoren la calidad de la solución inicial. Normalmente, estas técnicas de búsqueda se aplican a problemas NP-duros en los que el espacio de búsqueda es muy grande y es necesario el uso de funciones heurísticas para eliminar rutas de búsqueda no prometedoras. El problema de estas heurísticas es que también se pueden desechar rutas que lleven a buenas soluciones. Entre es tos métodos cabe destacar la escalada, el enfriamiento simulado, los algoritmos genéticos, los algoritmos de optimización basados en nubes de partículas o los algoritmos de colonias de hormigas. Un tema al que se han aplicado métodos evolutivos de m anera exitosa en los últimos años son los métodos formales. Los métodos formales son técnicas que típicamente han sido aplicadas tanto a la especificación formal como a la verificación formal de sistemas software, con la idea de desarrollar especific aciones claras, concisas y ausentes de ambigüedades. El punto de encuentro entre dos áreas tan diferentes es debido a que los métodos formales se encuentran comúnmente con un problema en la práctica: deben analizar sistemas en los que el número de es tados de la especificación crece exponencialmente. Es aquí donde las técnicas heurísticas proporcionan estrategias eficientes que se pueden aplicar para intentar buscar errores potenciales en el sistema. En esta tesis se introduce una nueva técnica evolutiva llamada River Formation Dynamics inspirada en la naturaleza y basada en el proceso geológico de la formación de los ríos. Primero se diseña un algoritmo básico basado en estas ideas para posteriormente aplicarlo a resolver problemas NP-comp letos de diferente índole. Uno de los problemas a los que se ha aplicado este método para probar su funcionamiento es el problema del viajante de comercio. Además se han definido nuevos problemas NP-completos como son los casos del problema del árbol recubridor mínimo y el árbol de distancias mínimas en grafos de costes variables. Para resolver estos problemas es necesario adaptar el algoritmo básico a cada caso.