<  Back to the Polytechnique Montréal portal

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

Kamal Fadlaoui

Masters thesis (2009)

[img]
Preview
Download (810kB)
Cite this document: Fadlaoui, K. (2009). Métaheuristiques appliquées au problème de covering design (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/229/
Show abstract Hide abstract

Abstract

Résumé 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.----------Abstract A (v; k; t)-covering design is a collection of k-subsets (called blocks) of a v-set V such that every t-subset of V is contained in at least one block. Given v, k and t, the goal of the Covering Design problem is to nd a covering made of a minimum number of blocks. In this paper, we present a new tabu algorithm with a mechanism of diversication and a new memetic algorithm for the solution of the problem. Our algorithms use a new implementation totally incremental designed in order to evaluate efficiently the performance of the neighbors of the current conguration. The new implementation is much less space-consuming than the currently used technique, making it possible to tackle much larger problem instances. It is also signicantly faster (between 10 and 100 times faster) and the speeding rate gets higher and higher as the size of the instances raises. We mesured the performance of our tabu algorithm trying more than 700 problem instances. Thanks to the improved data structures, our tabu algorithm was able to improve the upper bound of 77 problem instances and still hold the record for 71 of them.

Open Access document in PolyPublie
Department: Département de génie informatique et génie logiciel
Dissertation/thesis director: Philippe Galinier
Date Deposited: 22 Mar 2010 15:53
Last Modified: 27 Jun 2019 16:49
PolyPublie URL: https://publications.polymtl.ca/229/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only