Algoritmo para la construcción de arreglos de cubrimiento basado en la mejor búsqueda armónica global y técnicas de optimización local

Abstract

Los Covering Arrays son objetos matemáticos que han sido ampliamente utilizados dentro del diseño de experimentos en diversos sectores y áreas de aplicación como agricultura, medicina, biología, diseño de materiales y manufactura, y más recientemente para realizar pruebas funcionales de componentes software ya que 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, utilizando el mínimo número de casos de prueba. La construcción de un CA es una tarea compleja que conlleva un tiempo de ejecución elevado e involucra una alta carga computacional. El objetivo de los métodos y algoritmos para construir Covering Arrays es satisfacer las propiedades de cobertura con el menor número posible de filas, buscando de esta forma CAs óptimos. A la fecha se han realizado investigaciones sobre diferentes métodos eficaces para construir CAs, entre ellos: métodos exactos, métodos algebraicos, métodos Greedy y métodos basados en meta-heurísticas. Estos últimos han reportado a la fecha los mejores resultados. Como resultado de la presente investigación se diseñó e implementó un algoritmo híbrido que haciendo uso de una adaptación del algoritmo meta-heurístico de la Mejor Búsqueda Armónica Global como técnica de optimización global y del algoritmo de Recocido Simulado como técnica de optimización local, construye Covering Arrays uniformes y mixtos con diferentes niveles de fuerza. Este algoritmo denominado GHSSA logró generar resultados competitivos frente a los mejores resultados (cotas) reportados por otros algoritmos del estado del arte.

Covering Arrays are mathematical objects which have been broadly implemented in the design of experiments in different areas and purposes such as agriculture, medicine, biology, material design and manufacture. More recently, they have been used to perform software component tests, since they allow for the testing of all the interactions in a fixed-sized block of the input parameters in a procedure, function or logic unit by using the minimum amount of test cases. Building a CA is a complex task which takes a long execution time and involves a heavy computational load. The objective of the methods and algorithms to build Covering Arrays is to fulfill the coverage properties by using the minimum possible rows, achieving more efficient CAs. To date, research about the different efficient methods to build CAs has been conducted, namely: exact methods, algebraic methods, Greedy methods, and metaheuristic based methods, among others. The latter have reported the best outcomes this far. As a result of this research, a hybrid algorithm was designed and implemented in order to build uniform and mixed Covering Arrays with different power values. It uses an adaptation of the meta-heuristic Global Best Harmony Search method as a global optimization technique, and the Simulated Annealing algorithm for local optimization. This algorithm, referred to as GHSSA, achieved competitive results when compared to the best results reported by other state of the art algorithms.