Metaheuristic algorithms for building Covering Arrays: A review
Covering Arrays (CA) are mathematical objects used in the functional testing of software components. They enable the testing of all interactions of a given size of input parameters in a procedure, function, or logical unit in general, using the minimum number of test cases. Building CA is a complex...
| Main Authors: | , , |
|---|---|
| Format: | Online |
| Language: | eng |
| Published: |
Universidad Pedagógica y Tecnológica de Colombia
2016
|
| Subjects: | |
| Online Access: | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5295 |
| _version_ | 1801706074875625472 |
|---|---|
| author | Timaná-Peña, Jimena Adriana Cobos-Lozada, Carlos Alberto Torres-Jimenez, Jose |
| author_facet | Timaná-Peña, Jimena Adriana Cobos-Lozada, Carlos Alberto Torres-Jimenez, Jose |
| author_sort | Timaná-Peña, Jimena Adriana |
| collection | OJS |
| description | Covering Arrays (CA) are mathematical objects used in the functional testing of software components. They enable the testing of all interactions of a given size of input parameters in a procedure, function, or logical unit in general, using the minimum number of test cases. Building CA is a complex task (NP-complete problem) that involves lengthy execution times and high computational loads. The most effective methods for building CAs are algebraic, Greedy, and metaheuristic-based. The latter have reported the best results to date. This paper presents a description of the major contributions made by a selection of different metaheuristics, including simulated annealing, tabu search, genetic algorithms, ant colony algorithms, particle swarm algorithms, and harmony search algorithms. It is worth noting that simulated annealing-based algorithms have evolved as the most competitive, and currently form the state of the art. |
| format | Online |
| id | oai:oai.revistas.uptc.edu.co:article-5295 |
| institution | Revista Facultad de Ingeniería |
| language | eng |
| publishDate | 2016 |
| publisher | Universidad Pedagógica y Tecnológica de Colombia |
| record_format | ojs |
| spelling | oai:oai.revistas.uptc.edu.co:article-52952022-06-15T16:21:49Z Metaheuristic algorithms for building Covering Arrays: A review Algoritmos metaheurísticos para construir Covering Arrays: Revisión Timaná-Peña, Jimena Adriana Cobos-Lozada, Carlos Alberto Torres-Jimenez, Jose ant colony optimization Covering Array genetic algorithms harmony search algorithm metaheuristics particle swarm optimization simulated annealing tabu search algoritmo de búsqueda armónica algoritmos genéticos búsqueda tabú Covering Array metaheurística optimización por colonia de hormigas optimización por enjambre de partículas recocido simulado Covering Arrays (CA) are mathematical objects used in the functional testing of software components. They enable the testing of all interactions of a given size of input parameters in a procedure, function, or logical unit in general, using the minimum number of test cases. Building CA is a complex task (NP-complete problem) that involves lengthy execution times and high computational loads. The most effective methods for building CAs are algebraic, Greedy, and metaheuristic-based. The latter have reported the best results to date. This paper presents a description of the major contributions made by a selection of different metaheuristics, including simulated annealing, tabu search, genetic algorithms, ant colony algorithms, particle swarm algorithms, and harmony search algorithms. It is worth noting that simulated annealing-based algorithms have evolved as the most competitive, and currently form the state of the art. 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 (problema NP-completo) 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. Universidad Pedagógica y Tecnológica de Colombia 2016-09-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion investigation investigación application/pdf text/html https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5295 10.19053/01211129.v25.n43.2016.5295 Revista Facultad de Ingeniería; Vol. 25 No. 43 (2016); 31-45 Revista Facultad de Ingeniería; Vol. 25 Núm. 43 (2016); 31-45 2357-5328 0121-1129 eng https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5295/4425 https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5295/5060 |
| spellingShingle | ant colony optimization Covering Array genetic algorithms harmony search algorithm metaheuristics particle swarm optimization simulated annealing tabu search algoritmo de búsqueda armónica algoritmos genéticos búsqueda tabú Covering Array metaheurística optimización por colonia de hormigas optimización por enjambre de partículas recocido simulado Timaná-Peña, Jimena Adriana Cobos-Lozada, Carlos Alberto Torres-Jimenez, Jose Metaheuristic algorithms for building Covering Arrays: A review |
| title | Metaheuristic algorithms for building Covering Arrays: A review |
| title_alt | Algoritmos metaheurísticos para construir Covering Arrays: Revisión |
| title_full | Metaheuristic algorithms for building Covering Arrays: A review |
| title_fullStr | Metaheuristic algorithms for building Covering Arrays: A review |
| title_full_unstemmed | Metaheuristic algorithms for building Covering Arrays: A review |
| title_short | Metaheuristic algorithms for building Covering Arrays: A review |
| title_sort | metaheuristic algorithms for building covering arrays a review |
| topic | ant colony optimization Covering Array genetic algorithms harmony search algorithm metaheuristics particle swarm optimization simulated annealing tabu search algoritmo de búsqueda armónica algoritmos genéticos búsqueda tabú Covering Array metaheurística optimización por colonia de hormigas optimización por enjambre de partículas recocido simulado |
| topic_facet | ant colony optimization Covering Array genetic algorithms harmony search algorithm metaheuristics particle swarm optimization simulated annealing tabu search algoritmo de búsqueda armónica algoritmos genéticos búsqueda tabú Covering Array metaheurística optimización por colonia de hormigas optimización por enjambre de partículas recocido simulado |
| url | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5295 |
| work_keys_str_mv | AT timanapenajimenaadriana metaheuristicalgorithmsforbuildingcoveringarraysareview AT coboslozadacarlosalberto metaheuristicalgorithmsforbuildingcoveringarraysareview AT torresjimenezjose metaheuristicalgorithmsforbuildingcoveringarraysareview AT timanapenajimenaadriana algoritmosmetaheuristicosparaconstruircoveringarraysrevision AT coboslozadacarlosalberto algoritmosmetaheuristicosparaconstruircoveringarraysrevision AT torresjimenezjose algoritmosmetaheuristicosparaconstruircoveringarraysrevision |
