Scatter Search Pour le problème du Sac à Dos

Loading...
Thumbnail Image

Date

2019

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