PROPOSITION DAIDE AU CHOIX AVEC DES ALGORITHMES ÉVOLUTIONNAIRES MULTI-OBJECTIF

MÁXIMO MÉNDEZ; DANIEL A. ROSSIT; ANTONIO LUIS ÁLAMO; MARIANO FRUTOS; RICARDO AGUASCA

Compiègne

Conferencia; XVII Conférence ROADEF de la société Française de Recherche Opérationnelle et Aide à la Décision; 2016

Société Française de Recherche Opérationnelle et d'Aide à la Décision

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 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 NSGAII sont appliqués au problème de sac-à-dos avec deux objectifs. La difficulté réside dans apparition de multiples solutions dans la population avec la même localisation dans 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 algorithme, est proposée dans ce travail. La stratégie proposée est mise en oeuvre sur algorithme NSGAII, bien qune autre métaheuristique pourrait être utilisée. La procédure algorithmique proposée, donne de meilleures performances par rapport à celles de NSGAII en termes de diversité et d?hypervolume.