MosesA metaheuristic optimization software ecosystem. Applications to the automated analysis of software product lines and service-based applications

Resumen

Muchas de las situaciones a las que nos enfrentamos cada día pueden expresarse como problemas de optimización. Un problema de optimización se resuelve encontrando, de entre un conjunto de soluciones candidatas, aquella que mejor satisface un conjunto de objetivos. Encontrar la mejor solución para un problema de optimización es difícil o incluso inviable en muchos casos reales. Los algoritmos heurísticos se han utilizado durante décadas para guiar la búsqueda de soluciones satisfactorias para problemas de optimización duros en un plazo de ejecución asequible. Las metaheurísticas son esquemas de algoritmos reutilizables que facilitan el diseño de algoritmos heurísticos para resolver problemas de optimización duros. El uso de metaheurísticas para resolver problemas de optimización es un tema ampliamente estudiado. En este contexto, los ingenieros de software recientemente se dieron cuenta de los beneficios del uso de metaheurísticas para resolver problemas de optimización duros, generalmente conocidos como problemas de búsqueda (del inglés search-based problems). Esto ha llevado a una línea de investigación emergente sobre problemas basados en búsqueda que se aprecia en las conferencias de ingeniería de software y los números especiales de revistas sobre el tema. Sin embargo, a pesar de sus muchas ventajas, la aplicación de metaheurísticas presenta numerosos obstáculos. En primer lugar, la implementación de las metaheurísticas como programas eficientes es un proceso complejo y propenso a errores que requiere desarrolladores expertos. Aunque se han propuesto algunas herramientas de apoyo, por lo general éstas sólo automatizan tareas aisladas de este proceso. Otro desafío clave en la aplicación de metaheurísticas es la experimentación. Esto se debe a que no hay ningún método teórico general para elegir un programa metaheurístico adecuado para un problema dado, pues deben realizarse experimentos para comparar las técnicas candidatas y sus posibles variantes. Esto puede conducir a cientos de alternativas posibles que deben compararse haciendo que el diseño, la ejecución y el análisis de los experimentos sean complejos y se dilaten en el tiempo. Finalmente, los experimentos se realizan generalmente con herramientas genéricas y sin directrices respecto a las amenazas a la validez, su automatización y replicabilidad. El objetivo de esta tesis es el de reducir el costo de la aplicación de metaheurísticas para la resolución de problemas de optimización. Para tal fin, se presenta un conjunto de herramientas para apoyar la selección, configuración y evaluación de las soluciones basadas en metaheurísticas. En primer lugar, se presenta un marco de comparación, en base al cual se han estudiado las características de varios frameworks para optimización con metaheurísticas (MOFs). Esto da soporte la selección del MOF adecuado para el problema de optimización a resolver. En segundo lugar, se presenta un lenguaje de descripción experimental (SEDL), y una extensión del mismo (MOEDL), para dar soporte a la descripción de los experimentos y sus resultados, de manera sucinta, autocontenida y procesable automáticamente. En tercer lugar, se presenta un conjunto de operaciones de análisis de documentos SEDL. Entre otras, estas operaciones dan soporte a la validación automática de las amenazas potenciales a la validez, y advertir a los usuarios de SEDL y sugerir posibles soluciones. En cuarto lugar, se presenta un ecosistema software (MOSES) para dar soporte a la integración de las herramientas de metaheurísticas y de experimentación. Además, se presenta una implementación de referencia del ecosistema, incluyendo las siguientes herramientas: i) FOM, el framework desarrollado por los autores, ii) un entorno de ejecución Experimental (E3) para el análisis automatizado, la ejecución y la replicación de experimentos descritos en SEDL y MOEDL, y iii) una suite de herramientas de software en línea (STATService) que da soporte al análisis estadístico con los test más comunes en el contexto de las metaheurísticas. Para la validación de este trabajo, se ha usado MOSES para resolver dos problemas de optimización basados en búsqueda relevantes en el contexto de la ingeniería del software: la maximización de la calidad de composiciones de servicios web y las pruebas de rendimiento en el análisis de los modelos de características. Como resultado, MOSES ha disminuido el esfuerzo en la implementación y la carga de la experimentación, y se han diseñado algoritmos que mejoran el estado de la técnica para ambos problemas.