CMSA para el problema de la generación de casos de prueba priorizados en líneas de productos software

Abstract

En las líneas de producto software puede ser difícil o incluso imposible probar todos los productos de la familia debido al gran número de combinaciones de características que puede existir. Esto conlleva la necesidad de buscar un subconjunto de productos de la familia que nos permita probar todas las posibles combinaciones. Los algoritmos del estado del arte basados en heurísticos junto con programación lineal entera (ILP) son lo bastante rápidos para instancias de tamaño pequeño o mediano. Sin embargo, existen algunas instancias del mundo real que son demasiado grandes para obtener una respuesta en un tiempo razonable, debido al crecimiento exponencial del espacio de búsqueda. Por otro lado, estos heurísticos no siempre conducen a las mejores soluciones. En este trabajo proponemos un nuevo enfoque basado en un algoritmo metaheurístico híbrido llamado Construct, Merge, Solve & Adapt (CMSA). Comparamos este enfoque con un algoritmo del estado del arte basado en programación entera y en algoritmos híbridos. El análisis muestra que el algoritmo propuesto conduce a soluciones de mayor calidad.