Scatter Search Pour le problème du Sac à Dos
Loading...
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
UMMTO
Abstract
Les métaheuristiques constituent une classe de méthodes approchées
adaptables à un très grand nombre de problèmes combinatoires. Elles
ont révélé leur grande efficacité pour fournir des solutions
approchées de bonne qualité pour un grand nombre de problèmes
d'optimisation de grande taille. C'est pourquoi l'étude de ces
méthodes est en développement progressif.
L'étude présentée dans ce modeste travail est consacrée à
l'application de la méthode de scatter search pour le problème du
sac à dos, une métaheuristique opérant sur un ensemble de solutions
appelé ensemble de référence, en les combinant pour en créer de
nouvelles.
Un des avantages de la méthode de scatter search est aussi qu'elle génère
plusieurs solutions de bonne qualité. Cela peut être intéressant
dans différents contextes lorsqu'il est demandé de fournir plusieurs
solutions élites.
Nous avons résolu une instance du problème à huit variables pour
laquelle nous avons trouvé la solution exacte. (Nous avons
implémenté l'instance du problème en utilisant la programmation
dynamique avec le langage python).
Ce modeste travail nous a permis d'un coté d'acquérir des connaissances dans le domaine d'optimisation combinatoire,
en particulier les méthodes de résolutions (exactes et approchées) et plus précisément la méthode de scatter search. D'un autre coté, de toucher un peu au domaine pratique en implémentant l'instance étudiée.
Description
57 f. : ill. ; 30 cm
Keywords
Métaheuristique, Scatter search, Résolution approchée, Problème du sac à dos
Citation
Mathématiques appliquées à la gestion