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

• Autores: José Antonio Parejo Maestre
• Directores de la Tesis: Antonio Ruiz Cortés (dir. tes.) , Sergio Segura Rueda (codir. tes.)
• Lectura: En la Universidad de Sevilla ( España ) en 2013
• Idioma: español
• Tribunal Calificador de la Tesis: José Miguel Toro Bonilla (presid.) , José Cristobal Riquelme Santos (secret.) , Stefan Wagner (voc.) , José Raúl Romero Salguero (voc.) , Jorge Cardoso (voc.)
• Enlaces
  • Tesis en acceso abierto en: Idus
• Resumen
  • español

    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.

  • English

    In almost any area of human activity, the spirit of constant improvement and the re- quirements of performance, quality and efficiency, lead us to face scenarios of ever growing complexity. Most of these scenarios can be expressed as optimization prob- lems. Heuristic algorithms have been used for decades to guide the search of satisfy- ing solutions for hard optimization problems at an affordable execution time. In turn, Metaheuristics are reusable algorithm schemes that ease design heuristic algorithms.

    Even with metaheuristics, the process of designing and executing heuristic algo- rithms for solving optimization problems -so called the Metaheuristic Problem Solving (MPS) life-cycle in this thesis- is difficult and costly. The root of these difficulties is twofold: First, the design of algorithms using metaheuristics involves making deci- sions such as setting parameters values, choosing a solution encoding, etc. Since there does not exist an analytical method for making such decisions, a set of costly and de- manding experiments is required. Second, the MPS lifecycle involves implementing efficient programs which is non-trivial and error-prone. With the aim of reducing such complexity and costs of implementation, dozens of software frameworks -so called Metaheuristic Optimization Frameworks (MOFs)- have been proposed in literature.

    The goal of this thesis is to reduce the cost and complexity of executing the MPS lifecycle. To address this goal, a set of methods and tools is proposed. Specifically, the appropriate decision making in the MPS lifecycle is supported by: (i) a set of tools integrated into a software ecosystem that reduce the effort and time required by ex- perimentation; (ii) the automation of consistency validations on experimental design, conduction and analysis, decreasing the expertise required for experimentation; and (iii) increasing the degree of automation in experimental replication. Moreover, the se- lection of the appropriate MOF for a given problem is supported through a comparison framework and a survey.

    The proposed software ecosystem has been validated by solving two optimization problems in software engineering. It reduced the workload of executing the MPS life- cycle, lessening the implementation effort and the experimentation burden, and pro- ducing algorithms that improve the state of the art for both problems.