<  Retour au portail Polytechnique Montréal

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

Kamal Fadlaoui

Mémoire de maîtrise (2009)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (810kB)
Afficher le résumé
Cacher le résumé

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.

Département: Département de génie informatique et génie logiciel
Programme: Génie informatique
Directeurs ou directrices: Philippe Galinier
URL de PolyPublie: https://publications.polymtl.ca/229/
Université/École: École Polytechnique de Montréal
Date du dépôt: 22 mars 2010 15:53
Dernière modification: 13 nov. 2022 07:12
Citer en APA 7: Fadlaoui, K. (2009). Métaheuristiques appliquées au problème de covering design [Mémoire de maîtrise, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/229/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document