文献类型：期刊文章

作　　者：杨洋[1]

YANG Yang(College of Mathematics Education,China West Normal University,Nanchong,Sichuan 637009,China)

机构地区：[1]西华师范大学公共数学学院,四川南充637009

出　　处：《电子学报》

基　　金：国家自然科学基金(No.11871059);四川省教育厅自然科学基金(No.18ZA0469);西华师范大学校级科研团队(No.CXTD2015-4);西华师范大学英才基金(No.17YC385);西华师范大学青年教师科研基金专项(No.19D035)。

年　　份：2020

卷　　号：48

期　　号：6

起止页码：1205-1212

语　　种：中文

收录情况：BDHX、BDHX2017、CAS、CSCD、CSCD2019_2020、EI、IC、JST、PROQUEST、RCCSE、SCOPUS、ZGKJHX、核心刊

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

关 键 词：多选择背包问题 贪心算法 大数据 帕累托前沿  凸优化 群智能算法 整数优化  

分 类 号：TP18] O224]