基于核问题的果蝇优化算法求解多维背包问题
|
摘要
针对多维背包问题(MKP)维度高、约束强的特点,提出了一种基于核问题的果蝇优化算法(CBFOA).该算法通过求解MKP的线性规划松弛问题(LPR-MKP)的对偶问题得到MKP效用比,并运用核问题降低问题规模;果蝇的生成采用的二级结构和时变的搜索步距有利于前期快速寻优和后期精确搜索,采用的修复补偿策略、一级果蝇交流以及视觉搜索中的突跳机制以提高求解质量.通过标准测试集的测试和算法性能的对比,结果表明CBFOA对于MKP有较强的搜索能力.
A core-based fruit fly optimization algorithm(CBFOA) was proposed for solving multidimensional knapsack problem(MKP),which was characterized as high dimension and strong constraint.By solving the dual problem of the linear programming relaxion of MKP,a pseudo-utility ratio was attained.The core concept was applied to reduce the problem scale.The two-level structure was also employed to widen the search range.Simultaneously,the time varying searching step was employed to balance the searching speed and quality.A repair operator and communication strategy between flies of first level,as well as the mutation mechanism in the visual search were used to improve the quantity of solution.The test experiments conducted on the standard test set and algorithm comparison demonstrates that CBFOA has a strong search capability for MKP.
A core-based fruit fly optimization algorithm(CBFOA) was proposed for solving multidimensional knapsack problem(MKP),which was characterized as high dimension and strong constraint.By solving the dual problem of the linear programming relaxion of MKP,a pseudo-utility ratio was attained.The core concept was applied to reduce the problem scale.The two-level structure was also employed to widen the search range.Simultaneously,the time varying searching step was employed to balance the searching speed and quality.A repair operator and communication strategy between flies of first level,as well as the mutation mechanism in the visual search were used to improve the quantity of solution.The test experiments conducted on the standard test set and algorithm comparison demonstrates that CBFOA has a strong search capability for MKP.
引文
[1]CHU P C,BEASLEY J E.A genetic algorithm for the multidimensional knapsack problem[J].Journal of Heuristics,1998,4(1):63-86.
[2]BAS E.A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0-1 bidimensional knapsack model[J].Expert Systems with Applications,2011,38(10):12415-12422.
[3]WEI S.A branch and bound method for the multiconstraint zero-one knapsack problem[J].Journal of the Operational Research Society,1979,30(4):369-378.
[4]RONG A,Figueira J R.Dynamic programming algorithms for the bi-objective integer knapsack problem[J].European Journal of Operational Research,2014,236(1):85-99.
[5]MENG T,PAN Q.An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Applied Soft Computing,2017,50:79-93.
[6]吴虎胜,张凤鸣,战仁军,等.利用改进的二进制狼群算法求解多维背包问题[J].系统工程与电子技术,2015,37(5):1084-1091.
[7]ZHANG B,PAN Q K,ZHANG X L,et al.An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems[J].Applied Soft Computing,2015,29:288-297.
[8]PAN W.A new fruit fly optimization algorithm:taking the financial distress model as an example[J].KnowledgeBased Systems,2012,26:69-74.
[9]王凌,郑晓龙.果蝇优化算法研究进展[J].控制理论与应用,2017(5):557-563.
[10]XU C.An improved fruit fly optimization algorithm and its application of PID parameters tuning[J].Journal of Information and Computational Science,2015,12(9):3647-3654.
[11]HU R,WEN S,ZENG Z,et al.A short-term power load forecasting model based on the generalized regression neural network with decreasing step fruit fly optimization algorithm[J].Neurocomputing,2017,221:24-31.
[12]郑晓龙,王凌,王圣尧.求解置换流水线调度问题的混合离散果蝇算法[J].控制理论与应用,2014(2):159-164.
[13]PAN Q,SANG H,DUAN J,et al.An improved fruit fly optimization algorithm for continuous function optimization problems[J].Knowledge-Based Systems,2014,62:69-83.
[14]PUCHINGER J,RAIDL G R,PFERSCHY U.The multidimensional knapsack problem:structure and algorithms[J].Informs Journal on Computing,2010,22(2):250-265.
[15]任志刚,赵松云,黄姗姗,等.求解多维背包问题的蚁群-拉格朗日松弛混合优化算法[J].控制与决策,2016(7):1178-1184.
[16]MARTINS J P,FONSECA C M,DELBEM A C B.On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problem[J].Neurocomputing,2014,146:17-29.
[17]张清勇,钱浩,雷德明.求解多维背包问题的二级协作果蝇优化算法[EB/OL].[2018-01-20].http://doi.org/10.131951j.kzyjc.2017.1111.
[18]WANG L,ZHENG X,WANG S.A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Knowledge-Based Systems,2013,48:17-23.
[19]MONTGOMERY D C.Design and analysis of experiments[M].2nd Edition.New York:John Wiley and Sons,2000.
[2]BAS E.A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0-1 bidimensional knapsack model[J].Expert Systems with Applications,2011,38(10):12415-12422.
[3]WEI S.A branch and bound method for the multiconstraint zero-one knapsack problem[J].Journal of the Operational Research Society,1979,30(4):369-378.
[4]RONG A,Figueira J R.Dynamic programming algorithms for the bi-objective integer knapsack problem[J].European Journal of Operational Research,2014,236(1):85-99.
[5]MENG T,PAN Q.An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Applied Soft Computing,2017,50:79-93.
[6]吴虎胜,张凤鸣,战仁军,等.利用改进的二进制狼群算法求解多维背包问题[J].系统工程与电子技术,2015,37(5):1084-1091.
[7]ZHANG B,PAN Q K,ZHANG X L,et al.An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems[J].Applied Soft Computing,2015,29:288-297.
[8]PAN W.A new fruit fly optimization algorithm:taking the financial distress model as an example[J].KnowledgeBased Systems,2012,26:69-74.
[9]王凌,郑晓龙.果蝇优化算法研究进展[J].控制理论与应用,2017(5):557-563.
[10]XU C.An improved fruit fly optimization algorithm and its application of PID parameters tuning[J].Journal of Information and Computational Science,2015,12(9):3647-3654.
[11]HU R,WEN S,ZENG Z,et al.A short-term power load forecasting model based on the generalized regression neural network with decreasing step fruit fly optimization algorithm[J].Neurocomputing,2017,221:24-31.
[12]郑晓龙,王凌,王圣尧.求解置换流水线调度问题的混合离散果蝇算法[J].控制理论与应用,2014(2):159-164.
[13]PAN Q,SANG H,DUAN J,et al.An improved fruit fly optimization algorithm for continuous function optimization problems[J].Knowledge-Based Systems,2014,62:69-83.
[14]PUCHINGER J,RAIDL G R,PFERSCHY U.The multidimensional knapsack problem:structure and algorithms[J].Informs Journal on Computing,2010,22(2):250-265.
[15]任志刚,赵松云,黄姗姗,等.求解多维背包问题的蚁群-拉格朗日松弛混合优化算法[J].控制与决策,2016(7):1178-1184.
[16]MARTINS J P,FONSECA C M,DELBEM A C B.On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problem[J].Neurocomputing,2014,146:17-29.
[17]张清勇,钱浩,雷德明.求解多维背包问题的二级协作果蝇优化算法[EB/OL].[2018-01-20].http://doi.org/10.131951j.kzyjc.2017.1111.
[18]WANG L,ZHENG X,WANG S.A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Knowledge-Based Systems,2013,48:17-23.
[19]MONTGOMERY D C.Design and analysis of experiments[M].2nd Edition.New York:John Wiley and Sons,2000.