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

YANG Yang

doi:10.3969/j.issn.0372-2112.2020.06.023

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-16

- Improved Pareto Algorithm for Solving Very Large Scale Multiple-Choice Knapsack Problem
- Acta Electronica Sinica Vol. 48, Issue 6, Pages: 1205-1212(2020)
- 作者机构：
  
  1. 西华师范大学公共数学学院,四川,南充,637009
  2. 西华师范大学公共数学学院,四川,南充,637009
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China (No.11871059);Natural Science Fund of Department of Education of Sichuan Province (No.18ZA0469);Research Team of China West Normal University (No.CXTD2015-4);Talent Fund of China West Normal University (No.17YC385);Science Research Foundation for Young Teachers of China West Normal University (No.19D035)
- DOI：10.3969/j.issn.0372-2112.2020.06.023
  CLC： TP18O224
- Published Online：25 June 2020，
  
  Published：2020
- 稿件说明：
移动端阅览
YANG Yang. Improved Pareto Algorithm for Solving Very Large Scale Multiple-Choice Knapsack Problem[J]. Acta Electronica Sinica, 2020, 48(6): 1205-1212.
DOI：

YANG Yang. Improved Pareto Algorithm for Solving Very Large Scale Multiple-Choice Knapsack Problem[J]. Acta Electronica Sinica, 2020, 48(6): 1205-1212. DOI： 10.3969/j.issn.0372-2112.2020.06.023.

摘要

实际生产生活中大量多选一的问题都可以转为多选择背包问题（MCKP），但MCKP是一个经典的NP难问题，因此对于超大规模MCKP而言，往往只能利用粒子群算法、狼群算法、鱼群算法等群智能算法对问题进行求解.对于群智能算法而言，高效快捷的贪心算法对于初始解的生成起着至关重要的作用.基于凸帕累托算法（CPA），提出一种能够快速求解线性支配子集的改进帕累托算法（IPA）.IPA首先选择各类项集的质量最小项，然后计算所有物品的价值密度，最后按照价值密度从高到低选择对物品进行贪心选择，若贪心选择项的价值大于其所在项集原有选择项，则进行迭代.仿真实验结果表明：IPA相比于CPA，求解速度平均提升98.86%.且PSO-IPA求解精度平均提升28.92%.

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

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

First Filling Strategy-Based Partitioning Method to Balance Data in Spark

Route Planning Method of Master-Slave UAV Formation for Target Positioning Accuracy

Power Allocation in Satellite-Terrestrial NOMA Network Based on Energy Efficiency

A Review on Microwave Resonant Sensors

Study on the BER Optimization of UWOC Systems Based on APD and PIN Receivers

Related Author

HE Yu-lin

WU Dong-tong

Philippe Fournier-Viger

HUANG Zhe-xue

HUANG Xiang-song

YU Ri-long

PAN Da-peng

LI Xin

Related Institution

Guangdong Laboratory of Artificial Intelligence and Digital Economy

College of Computer Science and Software Engineering, Shenzhen University

School of Information and Communication Engineering， Harbin Engineering University

Institute of Information and Navigation， Air Force Engineer University

Zhejiang Provincial Key Laboratory of Large-Scale Integrated Circuit Design, School of Electronics and Information, Hangzhou Dianzi University

⁰