Tesis "Algoritmo Metaheurístico para Construir Sequence Covering Arrays de Fuerza 3"
Sustentante: Óscar Iván Puga Sánchez
Director: Dr. José Torres Jiménez, Cinvestav Unidad Tamaulipas
Sinodales: Dr. José Juan García Hernández, Cinvestav Unidad Tamaulipas; Dr. José Torres Jiménez, Cinvestav Unidad Tamaulipas; Dr. Said Polanco Martagón, Universidad Politécnica de Victoria.
Resumen:
Un Covering Array (CA) es un objeto combinatorio ampliamente utilizado como conjunto de pruebas para evaluar el funcionamiento de componentes de software y hardware durante el proceso de elaboración de los mismos. Un CAs realiza un muestreo de las combinaciones de valores de las variables de entrada, a este tipo de pruebas se les denomina pruebas de interacción, en estas pruebas se muestrean todos los posibles valores de cada t variables de entrada de un componente de software o hardware. Si un componente tiene k variables de entrada donde cada variable cuenta con v posibles valores, un CA permite evaluar el funcionamiento de un componente de software y hardware utilizando el menor número de pruebas posible y garantizando la cobertura de cada v^t combinaciones de valores de variables de entrada. No obstante, un CA sólo evalúa las posibles combinaciones de valores de las variables de entrada y no el orden en el que son ingresados los valores de dichas variables al componente de software o hardware. Una solución a este problema es el uso de los Sequence Covering Arrays (SCA) como objetos combinatorios en los que cada renglón está definido por una permutación de k variables. Un SCA realiza un muestreo del orden de ocurrencia de cada t variables con el menor número de pruebas. El uso de un CA combinado con un SCA permite realizar una verificación más completa del funcionamiento de componentes de software o hardware, ya que, se evalúan tanto las combinaciones de valores de variables de entrada, así como el orden en el que son ingresados dichos valores al componente de hardware o software.
Las dos características fundamentales de los SCAs son mínima cardinalidad y máxima cobertura, es decir, se cubren todas las t! subsecuencias de cada t variables usando el menor número de renglones. En esta tesis se reporta la construcción de SCAs de fuerza t=3 con hasta k=200 variables, dicha construcción fue realizada usando una metodología de construcción que hace uso de algoritmos de manipulación de SCAs y de un algoritmo metaheurístico basado en el paradigma de recocido simulado. Los resultados más importantes son 19 SCAs, cubriendo desde 4 hasta 200 variables, necesitando para esto desde 6 hasta 24 renglones. Gracias a estos resultados se logró mejorar o igualar todos los resultados previamente reportados y se establecieron un total de 118 nuevas cotas superiores en el tamaño de los SCAs.