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

• 作者: 杨洋
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 多选择背包问题 贪心算法 大数据 帕累托前沿 凸优化 群智能算法 整数优化
• 年，卷（期）: 2020,（6）
• 所属期刊栏目: 学术论文
• 页码范围: 1205-1212
• 页数: 8页
• 分类号: TP18|O224
• 字数: 4807字
• 语种: 中文
• 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％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨洋	西华师范大学公共数学学院	19	32	4.0	5.0