Métaheuristiques appliquées au problème de covering design

Un (v; k; t)-covering design est un ensemble de blocs (sous ensemble à k éléments d'un ensemble de référence V à v éléments) tel que tout sous-ensemble à t éléments de V soit contenu dans un des blocs. Considérant v, k et t, le problème de Covering Design consiste à trouver un covering contenant le moins de blocs possible. Pour résoudre le problème, nous avons adapté des métaheuristiques au Covering Design. Nous avons en particulier conçu un algorithme tabou avec diversication et un algorithme mémétique. Afin de rendre ces algorithmes plus rapides, nous les avons munis de nouvelles structures de données totalement incrémentales. Nos algorithmes de bas niveau sont devenus ainsi plus rapides et moins gourmands en espace mémoire. Nos algorithmes ont donc été capables de traiter des jeux de données que les précédentes métaheuristiques développées ne pouvaient pas tester. En matière de vitesse, nos algorithmes sont entre 10 et 100 fois plus rapides et l'accélération est d'autant plus élevé que les jeux de données à traiter sont gros. Nous avons testé nos algorithmes sur plus de 700 jeux de données. Nous avons ainsi réussi à trouver un meilleur covering design pour 77 jeux de données, dont 71 n'ont pas été améliorés par la suite.