Metaheuristic algorithms for building Covering Arrays: A review

Algoritmos metaheurísticos para construir Covering Arrays: Revisión

Los Covering Arrays (CA) son objetos matemáticos usados en pruebas funcionales de componentes software. Los CA permiten probar todas las interacciones de un tamaño determinado, de los parámetros de entrada de un procedimiento, función o unidad lógica en general, usando el mínimo número de casos de prueba. La construcción de CA es una tarea compleja que requiere largos periodos de ejecución y gran capacidad computacional. Los métodos más efectivos para construir CA son los algebraicos, voraces y basados en metaheurísticas. Estos últimos son los que han arrojado mejores resultados hasta la fecha. Este artículo presenta una descripción de las contribuciones más importantes hechas por diferentes metaheurísticas, incluyendo el simulated annealing (recocido simulado), búsqueda tabú, algoritmos genéticos, algoritmo de la colonia de hormigas, algoritmo de enjambre de partículas y algoritmo de búsqueda armónica. Cabe anotar que los algoritmos basados en recocido simulado se han convertido en los más competitivos y actualmente son el estado del arte.

I. INTRODUCCIÓN

En las últimas décadas, las pruebas de software han sido el método más utilizado para garantizar la calidad del software [1]. Las pruebas pueden considerarse como un conjunto de procesos que se diseñan, desarrollan y aplican a lo largo de la vida del desarrollo del software para detectar y corregir los defectos y fallos encontrados durante y después de la implementación del código, y así elevar la calidad y fiabilidad del programa entregado al usuario final [2]. Sin embargo, aplicar pruebas de software exhaustivas que permitan probar el componente de software en su totalidad, además de ser una tarea costosa y que requiere mucho tiempo, es una tarea casi imposible. Incluso cuando se trata de probar el software más sencillo, se puede generar un gran número de casos de prueba debido a las numerosas combinaciones posibles de parámetros de entrada. Crear casos de prueba para todas estas posibilidades es un proceso inviable y poco práctico [1, 2]. Por ejemplo, si se requiere probar un componente de software que recibe como parámetros de entrada valores de cinco sensores y cada sensor puede tomar 10 valores diferentes, se necesitarían 10⁵ o 100.000 casos de prueba diferentes para probar exhaustivamente ese componente.

Las pruebas combinatorias ofrecen una alternativa a las pruebas exhaustivas, que seleccionan los casos de prueba mediante un mecanismo de muestreo que cubre sistemáticamente las combinaciones de valores de los parámetros de entrada, definiendo un conjunto más pequeño de pruebas que es relativamente fácil de gestionar y ejecutar [3]. Este tipo de pruebas reduce los costes y aumenta considerablemente la eficacia de las pruebas de software. Sin embargo, el reto de las pruebas combinatorias reside precisamente en encontrar el número mínimo de casos de prueba que consigan la máxima cobertura con la mínima cardinalidad [4, 5].