Metaheurísticas e ingeniería del software

Zusammenfassung

En esta tesis doctoral se estudia la aplicación de técnicas metaheurísticas a algunos problemas de optimización surgidos en el seno de la Ingeniería del Software. En concreto los problemas son: la planificación de proyectos software, la generación automática de casos de prueba y la búsqueda de violaciones de propiedades de seguridad en sistemas concurrentes. Hemos dado una definición formal de cada problema y hemos estudiado las técnicas metaheurísticas para decidir cuáles aplicar a cada uno de ellos. Para resolver el problema de planificación de proyectos software hemos utilizado un algoritmo genético con representación binaria. Usamos el algoritmo para proponer soluciones de planificación a distintos proyectos software automáticamente generados con un generador de instancias. Este generador, desarrollado durante el transcurso de nuestras investigaciones, permite realizar un estudio sistemático del problema, ofreciendo resultados que ayudan al gestor de proyectos a tomar determinadas decisiones de planificación. Los experimentos realizados muestran que el algoritmo genético puede ser una técnica muy útil para la planificación de proyectos. En el problema de generación de casos de prueba hemos usado dos técnicas metaheurísticas que nunca antes habían sido aplicadas a este problema: la estrategia evolutiva y la optimización basada en cúmulos de partículas. Además de suponer una novedad, su aplicación a la generación de casos de prueba revela que ambas técnicas superan en eficacia a los algoritmos genéticos, ampliamente utilizados para esta labor durante muchos años. También hemos estudiado la aplicación de algoritmos paralelos con población descentralizada. Los resultados indican que la paralelización y descentralización permiten obtener resultados de gran calidad usando un tiempo menor que los algoritmos secuenciales con población centralizada. Para abordar el problema de búsqueda de violaciones de propiedades de seguridad en sistemas concurrentes hemos desarrollado un nuevo algoritmo basado en colonias de hormigas, ACOhg, que es capaz de encontrar trazas de error cortas (buena calidad) usando una cantidad de memoria y tiempo muy reducida. Hemos realizado un estudio de las distintas alternativas del modelo algorítmico para seleccionar una configuración adecuada para el problema. Los resultados muestran que nuestra propuesta mejora algoritmos exactos utilizados en model checking. Hemos combinado ACOhg con una técnica para reducir el número de estados del autómata a explorar: reducción de orden parcial. Los resultados muestran una ventaja de la combinación de ambas técnicas en los modelos analizados.