Un algorithme évolutif avec division de l’espace des objectifs pour le problème de sac-à-dos bi-objectif en 0-1

Abstract

Le problème NP-difficile de sac-à-dos multi-objectif en variables 0-1 est bien connu et utilisé dans la communauté multi-objectif. De nombreuses méthodes exactes et métaheuristiques [2, 3] ont spécifiquement été développées pour leur résolution. Cependant, il est difficile d’introduire de la diversité dans le processus de recherche des solutions lorsque des algorithmes évolutionnaires tels que NSGA–II [1] sont appliqués au problème de sac-à-dos avec deux objectifs. La difficulté réside dans l’apparition de multiples solutions dans la population avec la même localisation dans l’espace des objectifs ; ce facteur entraîne une diminution de la diversité génétique de la population et une faible couverture du front de Pareto (FP). Pour faire face à ces difficultés, une méthodologie de division de l’espace des objectifs dans plusieurs régions, en utilisant la solution Nadir calculée dans chaque génération gt de l’algorithme, est proposée dans ce travail. La stratégie proposée est mise en oeuvre sur l’algorithme NSGA–II, bien qu’une autre métaheuristique pourrait être utilisée. La procédure algorithmique proposée, donne de meilleures performances par rapport à celles de NSGA–II en termes de diversité et d’hypervolume.