-
题名求解0-1背包问题的混合贪婪遗传算法
被引量：11
- 1
-
-
作者
陈桢
钟一文
林娟
-
机构
福建农林大学计算机与信息学院
智慧农林福建省高等学校重点实验室(福建农林大学)
-
出处
《计算机应用》
CSCD
北大核心
2021年第1期87-94,共8页
-
基金
福建省自然科学基金资助项目(2019J01401,2019J01661)
福建省教育厅中青年教师教育科研项目(KLA19027A)。
-
文摘
求解0-1背包问题(KP)的最优解的时候,传统遗传算法(GA)的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法(HGGA)。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基于物品价值密度的修复算子,增加基于物品价值的贪婪混合选项,从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索,另一方面依靠GA的经典操作算子开拓全局搜索空间,从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试,结果表明在第一组15个测试用例中的12个上,HGGA能够百分百找到最优解,成功率达到80%;在第二组小规模数据集上,HGGA的性能明显好于其他同类GA和其他元启发算法;在第三组大规模数据集上,HGGA较其他元启发式算法具有更好的稳定性和高效性。
-
关键词
0-1背包问题
混合贪婪遗传算法
求精能力
求泛能力
混合贪婪算子
局部搜索
-
Keywords
0-1 knapsack problem(kp)
Hybrid Greedy Genetic Algorithm(HGGA)
refinement ability
generalization ability
hybrid greedy operator
local search
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名基于和声搜索算法求解组合优化问题
被引量：7
- 2
-
-
作者
李宁
刘建芹
贺毅朝
-
机构
石家庄经济学院信息工程学院
石家庄信息工程职业学院国际教育部
-
出处
《计算机应用》
CSCD
北大核心
2012年第4期1041-1044,共4页
-
基金
河北省高等学校科学技术研究项目(Z2011143)
-
文摘
为了能够应用和声搜索算法(HSA)求解组合优化问题,基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA),并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题,通过与粒子群优化(BPSO)和遗传算法(GA)的实例计算对比验证了新算法的可行性与有效性。
-
关键词
进化算法
二进制和声搜索
组合优化
k-SAT问题
0-1背包问题
-
Keywords
evolutionary algorithm
binary harmony search
combinational optimization
k-SAT problem
0-1 knapsack problem（kp）
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
