Resumen

Una matriz de cobertura (CA) es una estructura combinatoria especificada como una matriz de N filas y k columnas sobre un alfabeto de v símbolos, de forma que para cada conjunto de t columnas cada t-tupla de símbolos está cubierta al menos una vez. Dados los valores de t, k, y v, el problema de construcción de matrices de cobertura óptima (CAC) consiste en construir una CA (N; t, k, v) con el mínimo valor posible de N. Existen varios métodos reportados para atender el problema CAC, entre ellos están los métodos directos, los métodos recursivos, los métodos codiciosos, y los métodos metaheurísticos. En este trabajo, hay tres enfoques paralelos para el recocido simulado: las búsquedas independientes, semi-independientes y cooperativas se aplican al problema CAC. La evidencia empírica apoyada por el análisis estadístico indica que el enfoque cooperativo ofrece los mejores tiempos de ejecución y los mismos límites que los enfoques independiente y semi-independiente. Se ha llevado a cabo una amplia experimentación, utilizando 182 casos de referencia bien conocidos de matrices de cobertura ternarias, para evaluar su rendimiento con respecto a los límites más conocidos de los que se ha informado anteriormente. Los resultados muestran que el enfoque cooperativo alcanza 134 nuevos límites e iguala las soluciones para otras 29 instancias.

• Materias:Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:problema cac, enfoque cooperativo, problema de construcción de matrices de recubrimiento óptimas, mejores tiempos de ejecución, valor mínimo posible, matrices de recubrimiento ternarias, experimentación extensiva, n filas, instancias de referencia, estructura combinatoria
• Keywords:cac problem, cooperative approach, optimal covering array construction problem, best execution times, minimum possible value, ternary covering arrays, extensive experimentation, n rows, benchmark instances, combinatorial structure