• 学术论文 •

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

1. 西华师范大学公共数学学院, 四川南充 637009
• 收稿日期:2019-08-20 修回日期:2019-11-04 出版日期:2020-06-25 发布日期:2020-06-25
• 作者简介:杨 洋 男,1993年5月出生,四川资阳人.西华师范大学助教,主要研究方向为整数规划,图论与组合最优化. E-mail:zhugemutian@outlook.com
• 基金资助:
国家自然科学基金（No.11871059）；四川省教育厅自然科学基金（No.18ZA0469）；西华师范大学校级科研团队（No.CXTD2015-4）；西华师范大学英才基金（No.17YC385）；西华师范大学青年教师科研基金专项（No.19D035）

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

YANG Yang

1. College of Mathematics Education, China West Normal University, Nanchong, Sichuan 637009, China
• Received:2019-08-20 Revised:2019-11-04 Online:2020-06-25 Published:2020-06-25

Abstract: 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%.