Nouvelles propositions pour la résolution exacte du sac à dos multi-objectif unidimensionnel en variables binaires. (New propositions for the exact solution of the unidimensional multi-criteria knapsack problem with binary variables)
Nouvelles propositions pour la résolution exacte du sac à dos multi-objectif unidimensionnel en variables binaires. (New propositions for the exact solution of the unidimensional multi-criteria knapsack problem with binary variables)
复制标题
（二元变量一维多准则背包问题精确解的新命题）
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Julien Jorge
中科院分区：
文献类型：
--
作者：
Julien Jorge
解决多目标组合优化问题的精确解决方案。 Nous cherchons d'une 是双阶段算法有效性的确认者，也是分离和评估程序的普遍化的一部分，在多目标中，单一目标的干部可能会缺席。该研究是关于解决二元变量的单维问题的多目标问题的研究。在最经典的优化组合中，出现了一些非优化问题。 La Premiere party de nos travaux porte sur un pre-traitement permettant de reduire la taille d’instances de ce Probleme.理性是所有解决方案功效的结构的先验决定因素。 Nous nous Attachons ensuite a decrire une procedure Performante de type deuxphases pour ce Probleme, tout d’abord dans le cas bi-objectif, ou nous ameliorons la procedure decrite par Visee et al. 1998 年。我们提出了新的算法，并在第二阶段有效地研究解决方案。 Nous etendons ensuite cette procedure pour des实例ayant trois objectifs ou plus。 Les resultats obtenus sont 比较了现有的最佳算法，以解决问题并确认两个阶段的方法的有效性。最后一部分涉及分离和评估多目标程序的概括。在提议的新程序中，理智的识别会增加理智的反应困难。数字实验是在时间合理的情况下永久获取实例资源的数字实验，但无需注意双阶段程序的表演
Ce travail porte sur la resolution exacte d’un probleme d’optimisation combinatoire multi-objectif. Nous cherchons d’une part a confirmer l’efficacite de l’algorithme dit en deux phases, et d’autre part a poser une generalisation des procedures de separation et evaluation, populaires dans le cadre monoobjectif mais presque absentes en multi-objectif. Notre etude s’appuie sur le probleme multi-objectif de sac a dos unidimensionnel en variables binaires. Ce dernier est un classique de l’optimisation combinatoire, present comme sous probleme dans de nombreux problemes d’optimisation. La premiere partie de nos travaux porte sur un pre-traitement permettant de reduire la taille d’instances de ce probleme. Nous mettons en evidence plusieurs proprietes permettant de determiner a priori une partie de la structure de toutes les solutions efficaces. Nous nous attachons ensuite a decrire une procedure performante de type deux phases pour ce probleme, tout d’abord dans le cas bi-objectif, ou nous ameliorons la procedure decrite par Visee et al. En 1998. Puis nous proposons un nouvel algorithme permettant de trouver plus efficacement les solutions recherchees durant la seconde phase. Nous etendons ensuite cette procedure pour des instances ayant trois objectifs ou plus. Les resultats obtenus sont compares aux meilleurs algorithmes existants pour ce probleme et confirment l’efficacite de l’approche en deux phases. La derniere partie de notre travail concerne la generalisation au cas multi-objectif d’une procedure de separation et evaluation. Nous identifions plusieurs difficultes auxquelles nous repondons en proposant deux nouvelles procedures. Les experimentations numeriques indiquent que ces dernieres permettent de resoudre des instances en des temps raisonnables, bien qu’elles n’atteignent pas les performances d’une procedure de type deux phases