Séminaire 20-janvier-2018 : Problème de sac à dos

Un problème d’optimisation multiobjectif consiste à optimiser simultanément plusieurs objectifs souvent conflictuels sur un ensemble de contraintes qui constitue un ensemble de solutions réalisables non vide. Plusieurs techniques de recherche, exactes et approximative ont été mise en point pour résoudre de ce type de problèmes dans ses différents cas, soit discret, continu, combinatoire ou mixte. Dans toutes ces méthodes on cherche un ensemble ou un sous ensemble admissible vérifiant la non-dominance des solutions, ce dernier peut être très large et malheureusement dans certaines situations, le décideur n’a pas besoin de toutes les solutions efficaces mais uniquement de solutions efficaces qui réalisent l’optimum d’un objectif différent des objectifs déjà fixés. Ceci nous mène vers la recherche de la solution optimale d’un critère sur l’ensemble des solutions efficaces du problème multiobjectifs. Ce type de problème à été largement étudié dans le cas continu, le cas discret n’a pas reçu beaucoup d’attention des chercheurs, notamment pour les problèmes combinatoires aucune étude n’a été mené.

Dans ce travail on s’intéresse au problème de sac à dos bi-objectif à variables binaires, notre but est de déterminer un sous ensemble de solutions efficaces de ce problème qui

optimise une fonction objectif qu’on suppose linéaire et cela sans avoir énumérer la totalité de l’ensemble des solutions efficaces. Le processus de résolution est basé essentiellement

sur la programmation dynamique et la programmation linéaire pour tester l’efficacité des solutions.

La cryptographie à clé publique ou asymétrique est introduite en 1976 par Whitfield Diffie et Martin Hellman en se reposant sur la notion de fonction à sens unique, deux ans après, Ralph Merkle et Martin Hellman ont publié un cryptosystème asymétrique dit MH basé sur une variante du problème du sac à dos dite le problème de la somme de sous-ensembles (subset-sum problem) qui est reconnu NP-difficile. D’autre part, au cours des quatre dernières décennies, les métaheuristiques ont permis de réaliser un progrès remarquable dans la résolution des problèmes d’optimisation combinatoire réputés difficile, néanmoins, la conception de ces méthodes soulève plusieurs challenges notamment l’adaptation et le choix des paramètres.
Dans cette modeste contribution, un algorithme génétique parallèle est adapté à une exploration rapide d’un espace de recherche de taille assez importante, permettant de décrypter des informations chiffrées à l’aide du MH.