-
题名贪心核加速动态规划算法求解折扣{0-1}背包问题
被引量:4
- 1
-
-
作者
史文旭
杨洋
鲍胜利
-
机构
中国科学院大学
中国科学院成都计算机应用研究所
西华师范大学数学与信息学院
-
出处
《计算机应用》
CSCD
北大核心
2019年第7期1912-1917,共6页
-
基金
四川省科技厅重点研发项目(2018SZ0040)
四川省大学生创新创业训练计划支持项目(201810638085)~~
-
文摘
针对现有动态规划算法求解折扣{0-1}背包问题(D{0-1}KP)缓慢的问题,基于动态规划思想并结合新型贪心修复优化算法(NGROA)与核算法,通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划(GCADP)算法。首先利用NGROA对问题进行贪心求解,得到非完整项;然后通过计算得到模糊核区间的半径和模糊核区间范围;最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划(BDP)算法求解。实验结果表明:GCADP算法适用于求解D{0-1}KP,且在求解速度上相比BDP算法平均提升了76.24%,相比FirEGA算法平均提升了75.07%。
-
关键词
折扣{0-1}背包问题
贪心核加速动态规划算法
新型贪心修复优化算法
核算法
基础动态规划
-
Keywords
Discounted {0-1} Knapsack Problem (D{0-1}KP)
Greedy Core Acceleration Dynamic Programming (GCADP) algorithm
New Greedy Repaired Optimization Algorithm(NGROA)
core algorithm
Basic Dynamic Programming (BDP)
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名核加速遗传算法求解折扣{0-1}背包问题
被引量:4
- 2
-
-
作者
杨洋
潘大志
贺毅朝
-
机构
西华师范大学数学与信息学院
河北地质大学信息工程学院
-
出处
《西华师范大学学报(自然科学版)》
2018年第2期165-172,共8页
-
基金
国家自然科学基金项目(11371015)
四川省教育厅自然科学基金项目(18ZA0469)
+2 种基金
西华师范大学博士启动基金项目(12B022)
西华师范大学校级科研团队(CXTD2015-4)
西华师范大学英才科研基金项目(17YC385)
-
文摘
针对现有遗传算法求解折扣{0-1}背包问题(D{0-1}KP)易陷入局部最优解,同时存在大量无效交叉变异操作使得算法收敛较慢等问题,本文基于精英保存策略(EGA)和贪心修复算法(GROA),将核算法与遗传算法进行融合,提出求解D{0-1}KP的核加速遗传算法(CEGA)。将CEGA用于求解四类大规模D{0-1}KP实例,结果表明:CEGA适用于求解D{0-1}KP,且精确度和收敛速度均好于第一遗传算法(FirEGA)。
-
关键词
折扣{0-1}背包问题
精英保存策略
贪心修复算法
核
第一遗传算法
-
Keywords
Discounted { 0-1 } backpack problem
elitist reservation strategy
greedy repair optimization algorithm
core
FireGA
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-