改进帕累托算法求解超大规模多选择背包问题
Improved Pareto Algorithm for Solving Very Large Scale Multiple-Choice Knapsack Problem
查看参考文献33篇
|
文摘
|
实际生产生活中大量多选一的问题都可以转为多选择背包问题(MCKP),但MCKP是一个经典的NP难问题,因此对于超大规模MCKP而言,往往只能利用粒子群算法、狼群算法、鱼群算法等群智能算法对问题进行求解.对于群智能算法而言,高效快捷的贪心算法对于初始解的生成起着至关重要的作用.基于凸帕累托算法(CPA),提出一种能够快速求解线性支配子集的改进帕累托算法(IPA).IPA首先选择各类项集的质量最小项,然后计算所有物品的价值密度,最后按照价值密度从高到低选择对物品进行贪心选择,若贪心选择项的价值大于其所在项集原有选择项,则进行迭代.仿真实验结果表明:IPA相比于CPA,求解速度平均提升98.86%.且PSO-IPA求解精度平均提升28.92%. |
|
其他语种文摘
|
In the actual production life conditions,a large number of multiple choices can be converted into a multiple-choice knapsack problem(MCKP),but MCKP is a classic NP-hard problem.Therefore,for very large scale MCKP,it is often only possible to use the particle swarm algorithm,wolf pack algorithm,fish swarm algorithm and so on to solve the problem.For swarm intelligence algorithms,efficient and fast greedy algorithms play a key role in the generation of initial solutions.Based on the convex Pareto algorithm(CPA),an improved Pareto algorithm(IPA)that can quickly get the linear programming dominated set is proposed.IPA firstly selects the minimum weight item of each set,then computes the value density of all items,and finally chooses the greedy choice of the item according to the value density from high to low.When the value of the greedy option is greater than the original selection of the item set,then IPA is iterated.The simulation results show that compared with CPA,the speed of IPA is increased by 98.86%.The PSO-IPA solution accuracy is increased by an average of 28.92%. |
|
来源
|
电子学报
,2020,48(6):1205-1212 【核心库】
|
|
DOI
|
10.3969/j.issn.0372-2112.2020.06.023
|
|
关键词
|
多选择背包问题
;
贪心算法
;
大数据
;
帕累托前沿
;
凸优化
;
群智能算法
;
整数优化
|
|
地址
|
西华师范大学公共数学学院, 四川, 南充, 637009
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
0372-2112 |
|
学科
|
数学;自动化技术、计算机技术 |
|
基金
|
国家自然科学基金
;
四川省教育厅自然科学基金
;
西华师范大学校级科研团队
;
西华师范大学英才基金
;
西华师范大学青年教师科研基金专项
|
|
文献收藏号
|
CSCD:6770184
|
参考文献 共
33
共2页
|
|
1.
Nauss R M. The 0-1 knapsack problem with multiple choice constraints.
European Journal of Operational Research,1978,2(2):125-131
|
CSCD被引
2
次
|
|
|
|
|
2.
Balintfy J L. A mathematical programming system for preference and compatibility maximized menu planning and scheduling.
Mathematical Programming,1978,15(1):63-76
|
CSCD被引
1
次
|
|
|
|
|
3.
Sinha P. Integer programming models for sales resource allocation.
Management Science,1980,26(3):242-260
|
CSCD被引
1
次
|
|
|
|
|
4.
Rong A Y. Dynamic programming based algorithms for the discounted {0-1} knapsack problem.
Applied Mathematics and Computation,2012,218(12):6921-6933
|
CSCD被引
12
次
|
|
|
|
|
5.
He Y C. Exact and approximate algorithms for discounted {0-1} knapsack problem.
Information Sciences,2016,369:634-647
|
CSCD被引
13
次
|
|
|
|
|
6.
冯艳红. 差分进化帝王蝶优化算法求解折扣{ 0-1} 背包问题.
电子学报,2018,46(6):1343-1350
|
CSCD被引
12
次
|
|
|
|
|
7.
He Y C. A novel binary artificial bee colony algorithm for the set-union knapsack problem.
Future Generation Computer Systems,2018,78(1):77-86
|
CSCD被引
5
次
|
|
|
|
|
8.
Wei Z Q. Iterated two-phase local search for the Set-Union Knapsack Problem.
Future Generation Computer Systems,2019,101(7):1005-1017
|
CSCD被引
1
次
|
|
|
|
|
9.
Pisinger D. A minimal algorithm for the multiple-choice knapsack problem.
European Journal of Operational Research,2007,83(2):394-410
|
CSCD被引
4
次
|
|
|
|
|
10.
Martello S. Dynamic programming and strong bounds for the 0-1 knapsack problem.
Management Science,1999,45(3):414-424
|
CSCD被引
11
次
|
|
|
|
|
11.
Dyer M E. A branch and bound algorithm for solving the multiple-choice knapsack problem.
Journal of Computational and Applied Mathematics,1984,11(2):231-249
|
CSCD被引
2
次
|
|
|
|
|
12.
Balas E. An algorithm for large zero-one knapsack problems.
Operations Research,1980,28(5):1130-1154
|
CSCD被引
11
次
|
|
|
|
|
13.
Martello S. A new algorithm for the 0-1 knapsack problem.
Management Science,1988,34(5):633-644
|
CSCD被引
4
次
|
|
|
|
|
14.
Martello S.
Knapsack Problems:Algorithms and Computer Implementations,1990
|
CSCD被引
10
次
|
|
|
|
|
15.
Pisinger D. An expanding-core algorithm for the exact 0-1 knapsack problem.
European Journal of Operational Research,1995,87(1):175-187
|
CSCD被引
10
次
|
|
|
|
|
16.
王熙照. 求解背包问题的演化算法.
软件学报,2017,28(1):1-16
|
CSCD被引
14
次
|
|
|
|
|
17.
吴虎胜. 利用改进的二进制狼群算法求解多维背包问题.
系统工程与电子技术,2015,37(5):1084-1091
|
CSCD被引
12
次
|
|
|
|
|
18.
李迎. 求解大规模多背包问题的高级人工鱼群算法.
系统工程与电子技术,2018,40(3):710-716
|
CSCD被引
4
次
|
|
|
|
|
19.
薛俊杰. 二进制反向学习烟花算法求解多维背包问题.
系统工程与电子技术,2017,39(2):451-458
|
CSCD被引
12
次
|
|
|
|
|
20.
印桂生. 面向离散优化问题的改进二元粒子群算法.
哈尔滨工程大学学报,2015,36(2):191-195
|
CSCD被引
2
次
|
|
|
|
|
了解气象卫星更多信息，请访问