Problème du sac à dos - Définition

Résolution approchée

Comme pour la plupart des problèmes NP-complets, il peut être intéressant de trouver des solutions réalisables mais non optimales. De préférence avec une garantie sur l'écart entre la valeur de la solution trouvée et la valeur de la solution optimale.

La terminologie suivante est adoptée :

• on appelle efficacité d'un objet le rapport de sa valeur sur son poids. Plus la valeur de l'objet est importante par rapport à ce qu'il consomme, plus l'objet est intéressant ;

Algorithme glouton

L'algorithme le plus simple est un algorithme glouton. L'idée est d'ajouter en priorité les objets les plus efficaces, jusqu'à saturation du sac :

      trier les objets par ordre décroissant d'efficacité      w_conso:= 0            pour i de 1 à n        si w[i] + w_conso <= W alors          x[i]:= 1          w_conso:= w_conso + w[i]        sinon          x[i]:= 0        fin si      fin pour      

Les deux phases de l'algorithme glouton. À gauche : tri des boîtes par ordre d'intérêt (ici en dollars par kilogramme). À droite : insertion dans l'ordre des boîtes, si cela est possible. On obtient ici une solution de 11$ pour 11 kg alors que la solution optimale est de 12 $ et 14 kg.

Analyse de l'algorithme glouton

On notera z ^* la valeur des solutions optimales.

La solution X retournée par l'algorithme glouton peut être d'aussi mauvaise qualité que possible. Considérons par exemple que nous n'ayons que deux objets à placer dans le sac. Le premier a un profit de 2 et un poids de 1, le deuxième a un profit et un poids tous deux égaux à W. Le premier objet est le plus efficace, il sera choisi en premier et empêchera la prise du second, donnant ainsi une solution de valeur 1 alors que la solution optimale vaut W. Il existe donc des valeurs du problème pour lesquelles le rapport entre la solution trouvée et la solution optimale est aussi proche de zéro que possible.

Il existe d'autres algorithmes d'approximation pour le problème de sac à dos permettant d'avoir une solution garantie à une distance k ou à un rapport ε de la qualité de solution optimale. C’est-à-dire que la solution X trouvée est telle que ou . La complexité de ces algorithmes est, en général, fonction de l'inverse de la qualité attendue ; par exemple ou . Les temps d'exécution peuvent être très conséquents.

Métaheuristiques

Les méthodes métaheuristiques comme les algorithmes génétiques ou les optimisations basées sur des algorithmes de colonies de fourmis permettent d'obtenir une approximation raisonnable tout en évitant de monopoliser trop de ressources.

Algorithme génétique

Exemple de l'évolution d'une population avec un algorithme génétique. Les objets sont ceux utilisés pour l'exemple de l'algorithme glouton. Par exemple, le génome (0,1,0,1,0) correspond à une sélection de la boîte de 12 kg et celle de 7 kg.

Les algorithmes génétiques sont souvent utilisés dans les problèmes d'optimisation difficiles comme celui du sac à dos. Ils sont relativement faciles à mettre en œuvre et permettent d'obtenir rapidement une solution satisfaisante même si la taille du problème est importante.

On génère une population d'individus dont les chromosomes symbolisent une solution du problème. La représentation d'un individu est binaire puisque chaque objet sera soit retenu, soit écarté du sac. Le nombre de bits dans le génome de chaque individu correspond au nombre d'objets disponibles.

L'optimisation suit les principes habituels de l'algorithme génétique. Les individus sont évalués puis les meilleurs sont retenus pour la reproduction. Selon l'évolution retenue, les opérateurs de reproduction peuvent être plus ou moins complexes (cross-over), des mutations peuvent également intervenir (remplacement d'un 0 par 1 ou l'inverse). On peut également décider de copier le meilleur individu pour la génération suivante (élitisme). Après un certain nombre de générations, la population tend vers un optimum, voire la solution exacte.

Algorithmes basés sur les colonies de fourmis

Analogie avec les fourmis : le chemin qui mène à la goutte de miel (très sucrée) reçoit plus de phéromones que ceux qui mènent aux gouttes d'eau peu sucrée, plus grandes mais moins intéressantes pour la colonie qui a des ressources limitées (nombre de fourmis ou emplacement de stockage disponible)

Ce concept a été utilisé pour résoudre le problème du sac à dos multidimensionnel où plusieurs contraintes doivent être satisfaites. Les premiers algorithmes s'appuyaient sur l'idée de l'algorithme glouton : les fourmis sélectionnaient progressivement les objets les plus intéressants. Cette sélection peut varier mais se base toujours sur des traces de phéromones déposées par les fourmis et qui conditionnent les choix ultérieurs. Parmi les solutions proposées, on peut citer le dépôt de phéromone sur les meilleurs objets, le dépôt sur des paires d'objets insérés l'un après l'autre dans la solution ou encore l'ajout de phéromones sur des paires d'objets, indépendamment de l'ordre d'insertion.

Une synthèse réalisée par des chercheurs tunisiens et français a montré que l'algorithme qui consiste à laisser des traces sur les paires d'objets successivement sélectionnés s'avère moins efficace que les variantes qui se focalisent sur un objet ou des paires quelconques. Les améliorations restent toutefois possibles puisque ces algorithmes pourraient être combinés à d'autres métaheuristiques afin de s'approcher de la solution optimale.