Un Covering Array (CA) es un diseño combinatorio que ha sido usado de manera exitosa para realizar pruebas de hardware y de software, y en general para obtener diseños experimentales competitivos.
Siendo N, k, v, y t enteros positivos, un CA es una matriz de tamaño N x k donde cada renglón representa un experimento (N es el total de renglones); cada columna representa una variable involucrada en un proceso (k es el total de columnas); un valor en una celda de dicha matriz indica que en el experimento respectivo la variable referenciada toma dicho valor (v es el total de valores de cada columna); y el parámetro t indica que para cada submatriz de tamaño N x t se cubre al menos una vez cada una de las vt posibles combinaciones de valores entre las t variables respectivas.
El problema principal de construir CAs implica hacerlos con el mínimo valor de N satisfaciendo la condición de cobertura. Éste es un problema combinatorio duro para el cuál no existe (en general) solución eficiente, por este motivo se han usado enfoques aproximados de solución como algoritmos avaros y algoritmos metaheurísticos.
Una manera de construir CAs es usar un enfoque de una sola etapa con un sólo tipo de algoritmo, otros enfoques han reportado el uso de dos etapas generalmente usando diferentes tipos de algoritmos. Con respecto al dominio en el que se construye un CA se puede hacer en un dominio: vectorial, matricial o de alto nivel (CPHF=Covering Perfect Hash Family).
En este trabajo se reporta por primera vez el uso de un enfoque de tres etapas que combina algoritmos avaros y metaheurísticos; pero además la construcción se realiza usando un dominio matricial y la estructura de alto nivel CPHF.
La primera etapa de nuestro enfoque trabaja en el dominio de alto nivel CPHF y usa un algoritmo metaheurísitco para construir una solución parcial. La segunda etapa trabaja en el dominio matricial de CAs y usa un enfoque avaro para completar la solución. La tercera etapa trabaja en el dominio matricial de CAs y usa una mezcla de algoritmos avaros con un algoritmo metaheurístico para reducir el número de renglones de la matriz.
Gracias a nuestro enfoque: tres etapas, mezcla de algoritmos avaros y metaheurísticos, y uso de CAs en el dominio matricial y CPHFs, fue posible mejorar 21,217 CAs que eran los mejores conocidos.
Como ejemplo de aplicación de CAs presentamos su uso en el diseño experimental de una composta que involucra el uso de: materia orgánica de desecho, bagazo de caña, bagazo de tequila, estiércol de vaca y opciones de ventilación.
José Torres Jiménez
Cinvestav Ciudad Victoria
