<  Back to the Polytechnique Montréal portal

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

Kamal Fadlaoui

Master's thesis (2009)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (810kB)
Show abstract
Hide abstract

Abstract

A (v; k; t)-covering design is a collection of k-subsets (called blocks) of a v-set Vsuch 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 minimumnumber of blocks. In this paper, we present a new tabu algorithm with a mechanismof diversication and a new memetic algorithm for the solution of the problem. Ouralgorithms use a new implementation totally incremental designed in order to evaluateefficiently the performance of the neighbors of the current conguration. Thenew implementation is much less space-consuming than the currently used technique,making it possible to tackle much larger problem instances. It is also signicantlyfaster (between 10 and 100 times faster) and the speeding rate gets higher and higheras the size of the instances raises. We mesured the performance of our tabu algorithmtrying 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 andstill hold the record for 71 of them.

Résumé

Un (v; k; t)-covering design est un ensemble de blocs (sous ensemble à k élémentsd'un ensemble de référence V à v éléments) tel que tout sous-ensemble à t élémentsde 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. Pourré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 algorithmemé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 basniveau 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édentesmé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 plusde 700 jeux de données. Nous avons ainsi réussi à trouver un meilleur covering designpour 77 jeux de données, dont 71 n'ont pas été améliorés par la suite.
Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: Philippe Galinier
PolyPublie URL: https://publications.polymtl.ca/229/
Institution: École Polytechnique de Montréal
Date Deposited: 22 Mar 2010 15:53
Last Modified: 13 Nov 2022 07:12
Cite in APA 7: Fadlaoui, K. (2009). Métaheuristiques appliquées au problème de covering design [Master's thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/229/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item