改进帕累托算法求解超大规模多选择背包问题

Improved Pareto Algorithm for Solving Very Large Scale Multiple-Choice Knapsack Problem

实际生产生活中大量多选一的问题都可以转为多选择背包问题(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%.