Descente Multi Voisinage pour le problème du Sac-à-Dos.

Abstract

L’objectif de cette thèse est de proposer des méthodes pour la résolution de problèmes d’optimisation académiques difficiles. Dans le but de réaliser notre objectif, nous avons proposé deux contributions essentielles. Notre première contribution noté Rundom Descente RD de principe à trouvé un voisin aléatoire de la liste des voisins d’une solution initiale. Notre deuxième contribution Multi Descente MD de principe d’explorer itérativement chacun des voisinages, en recommençant au premier à chaque fois qu’une meilleure solution peut être trouvée .La méthode s’arrête lorsqu’il n’est plus possible de trouver de meilleure solution sur l’ensemble des k_max structures de voisinage. Afin de tester la performance des algorithmes que nous avons proposés, nous avons essayé de résoudre le problèmes d’optimisation académiques NP-Difficiles: Sac à Dos unidimensionnel de variable binaire.