一种求解多维多选择背包问题的分布估计算法

doi:10.16182/j.issn1004731x.joss.201712025

摘要/Abstract

摘要： 针对多维多选择背包问题(MMKP)局部难以优化的特点,提出将分布估计算法(EDA)应用于优化MMKP问题。为了提升EDA优化局部的能力,以构建待选物品价值权重因子的方式来改进EDA的初始模型和概率模型更新方法; 并平衡了极值效应对算法寻优过程的影响,克服了传统EDA局部优化能力不强的缺陷.同时采用新的非可行解的修复机制,维护了机器学习法对概率模型的促进作用,提高了改进算法的全局优化能力。实验结果表明,该算法能够有效地优化MMKP问题,其性能高于传统的优化算法。

关键词: 启发式, 多维多选择背包, 价值权重, 分布估计, 优化

Abstract: As it is difficult to realize local optimization of the Multidimensional Multiple-choice Knapsack Problem (MMKP), the Estimation of Distribution Algorithms (EDA) is applied to optimize the MMKP. In order to improve the local optimization ability of EDA, value weight factors of items for selection are built to improve the EDA initial model and probabilistic model updating methods. The impact of the extreme effects on the algorithm optimization process is balanced to overcome the defect that the local optimization ability of the traditional EDA is weak. A new non-feasible solution repair mechanism is adopted to maintain the facilitation of machine learning methods for the probabilistic model and improve the global optimization ability of the improved algorithm. Experimental results show that this algorithm can effectively optimize the MMKP and its performance is much better than traditional optimization algorithms.

Key words: heuristics, multidimensional multiple-choice knapsack, value weight, estimation of distribution, optimality

中图分类号:

TP391

谭阳>, 刘章, 周虹. 一种求解多维多选择背包问题的分布估计算法[J]. 系统仿真学报, 2017, 29(12): 3123-3131.

Tan Yang, Liu Zhang, Zhou Hong. Distributed Estimation Algorithm for Multi-dimensional Multi-choice Knapsack Problem[J]. Journal of System Simulation, 2017, 29(12): 3123-3131.

参考文献

[1] Shapiro J L.Diversity Loss in General Estimation of Distribution Algorithms[M]// Parallel Problem Solving from Nature-PPSN IX. Springer Berlin Heidelberg, 2006: 92-101.
[2] Zhou Q, Luo W.A Novel Multi-Population Genetic Algorithm for Multiple-Choice Multidimensional Knapsack Problems[J]. Lecture Notes in Computer Science (S0302-9743), 2010, 63(82): 148-157.
[3] Cherfi N, Hifi M.A column generation method for the multiple-choice multi-dimensional knapsack problem[J]. Computational Optimization and Applications (S0926-6003), 2010, 46(1): 51-73.
[4] Taha Ghasemi, Mohammadreza Razzaz.Development of core to solve the Multidimensional Multiple choice Knapsack Problem[J]. Computers & Industrial Engineering (S0360-8352), 2011, 60(2): 349-360.
[5] Khalili-Damghani K, Nojavan M, Tavana M.Solving fuzzy Multidimensional Multiple-Choice Knapsack Problems: The multi-start Partial Bound Enumeration method versus the efficient epsilon-constraint method[J]. Applied Soft Computing (S1568-4946), 2013, 13(4): 1627-1638.
[6] Baluja S.Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive[J]. Learning Proceedings of IEEE Conference on Evolutionary Computation (S2210-6502 ), 1994, 2(4): 710-715.
[7] 高尚. 背包问题的分布估计算法[J]. 中南大学学报(自然科学版), 2013, 44(2): 165-168.
GAO Shang.Solving knapsack problem by estimation of distribution algorithm[J]. Journal of Central South University(Science and Technology). 2013, 44(2): 165-168.
[8] Osorio M A, Glover F, Hammer P.Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions[J]. Annals of Operations Research (S0254-5330), 2002, 117(1/2/3/4): 71-93.
[9] Hifi M, Michrafy M, Sbihi A.Heuristic algorithms for the multiple-choice multidimensional knapsack problem[J]. Journal of the Operational Research Society (S2194-6698), 2004, 55(12): 1323-1332.
[10] Sin C Ho, Michel Gendreau.Path relinking for the vehicle routing problem[J]. Journal of Heuristics (S1381-1231), 2006, 12(1/2): 55-72.
[11] Moser M, Jokanovic D P, Shiratori N.An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem[J]. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences (S0916-8508), 1997, 80(3): 582-589.
[12] Khan S, Li K F, Manning E G, et al.Solving the knapsack problem for adaptive multimedia systems[J]. Studia Informatica Universalis (S0867-1753), 2002, 2(1): 157-178.
[13] Hifi M, Michrafy M, Sbihi A.A Reactive Local Search-Based Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem[J]. Computational Optimization and Applications (S0926-6003), 2006, 33(2/3): 271-285.
[14] 张晓霞, 唐立新. 一种新的求解MMKP问题的ACO&PR算法[J]. 控制与决策, 2009, 24(5): 729-733.
Zhang Xiaoxia, Tang Lixin.A new ACO&PR algorithm for multiple-choice multidimensional knapsack problem[J]. Control and Decision, 2009, 24(5): 729-733.
[15] Cherfi N, Hifi M.Hybrid algorithms for the Multiple-choice Multi-dimensional Knapsack Problem[J]. International Journal of Operational Research (S1109-2858), 2009, 5(1): 89-109.
[16] Hifi M, Wu L.An equivalent Model for Exactly Solving the Multiple-choice Multidimensional Knapsack Problem[J]. International Journal of Combinatorial Optimization Problems and Informatics (S2007-1558), 2012, 3(3): 43-58.
[17] Cr´evits I, Hanafi S, Mansi R, Wilbaut C.Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem[J]. Computers and Operations Research (S0305-0548), 2012, 39(1): 32-41.
[18] 柳寅, 马良, 黄钰. 模糊人工蜂群算法的多选择多维背包问题求解[J]. 运筹与管理, 2013, 22(5): 98-103.
Liu Yin, Ma Liang, Huang Yu.Fuzzy artificial bees colony algorithm for solving multi-choice multidimensional knapsack problem[J]. Operations Research & Management Science, 2013, 22(5): 98-103.
[19] Raïd Mansi, Cláudio Alves, J M Valério de Carvalho, et al. A hybrid heuristic for the multiple choice multidimensional knapsack problem[J]. Engineering Optimization (S0305-215X), 2013, 45(8): 983-1004.
[20] Shojaei H, Basten T, Geilen M, et al.A fast and scalable multi-dimensional multiple-choice knapsack heuristic[J]. ACM Transactions on Design Automation of Electronic Systems (S1084-4309), 2013, 18(4): 96-95.