An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem
An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem
复制标题
一种有效的基于混合EDA的多维背包问题算法
DOI：
10.1016/j.eswa.2011.11.058
复制
发表时间：
2012-04
影响因子：
8.5
通讯作者：
Xu Y.
中科院分区：
文献类型：
--
作者：
Wang L;Wang SY;Xu Y.
针对多维背包问题，提出了一种基于分布估计算法(EDA)的混合算法。在EDA框架下，利用优势种群建立概率模型，在概率模型的基础上生成新的个体。此外，为了提高收敛速度，提出了概率模型的更新机制和基于MKP特定知识的概率模型初始化机制。同时，提出了一种自适应局部搜索算法，以增强算法的开发能力。在此基础上，基于田口试验设计方法，研究了参数的影响，并通过模拟试验和比较，研究了维修算子的重要性。最后，基于基准实例进行了数值仿真，并与一些已有算法进行了比较，验证了该算法的有效性。
In this paper, an effective hybrid algorithm based on estimation of distribution algorithm (EDA) is proposed to solve the multidimensional knapsack problem (MKP). With the framework of EDA, the probability model is built with the superior population and the new individuals are generated based on probability model. In addition, an updating mechanism of the probability model is proposed and a mechanism for initializing the probability model based on the specific knowledge of the MKP is also proposed to improve the convergence speed. Meanwhile, an adaptive local search is proposed to enhance the exploitation ability. Furthermore, the influences of parameters are investigated based on Taguchi method of design of experiment and the importance of repair operator is also studied via simulation testing and comparisons. Finally, numerical simulation is carried out based on the benchmark instances, and the comparisons with some existing algorithms demonstrate the effectiveness of the proposed algorithm.
登录
查看更多内容
影响因子：
14.3
作者：
Harik, GR;Lobo, FG;Goldberg, DE
通讯作者：
Goldberg, DE
DOI：
10.1016/j.ejor.2004.01.024
发表时间：
2005-08
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Michel Vasquez;Yannick Vimont
通讯作者：
Michel Vasquez;Yannick Vimont
DOI：
--
发表时间：
2007
期刊：
Computer Engineering and Applications
影响因子：
--
作者：
Quan Hui-yun
通讯作者：
Quan Hui-yun
影响因子：
2.3
作者：
S. Basu
通讯作者：
S. Basu
DOI：
--
发表时间：
2001-10
期刊：
--
影响因子：
--
作者：
Pedro Larraanaga;Jose A. Lozano
通讯作者：
Pedro Larraanaga;Jose A. Lozano