共查询到18条相似文献,搜索用时 93 毫秒
1.
求解0-1背包问题的混合遗传算法 总被引:7,自引:0,他引:7
对于0-1背包问题设计一种价值密度,并在此基础上提出求解0-1背包问题的混合遗传算法.经大量数值实验比较该方法与传统方法及简单遗传算法,结果表明算法能有效求解0-1背包问题. 相似文献
2.
0-1背包问题是计算机算法研究中NP完备类的一个困难问题,对这个问题国内外很多学者己经研究出了不少经典的方法,但是这些传统的优化法存在一些缺点。本文介绍了近年来兴起的一种演化算法—遗传算法解决背包问题的基本思路,井通过实例计算证明了此方法的可行性和有效性。 相似文献
3.
多维O-1背包问题的混合遗传算法 总被引:5,自引:0,他引:5
将贪婪法和遗传算法相结合,设计了一种价值密度,提出了一种求解多维0-1背包问题的混合遗传算法。经实例证明,该方法能较好地解决多维0-1背包问题并较简单遗传算法有较好的改善。 相似文献
4.
针对基本遗传算法在求解大规模问题时,收敛速度缓慢、容易早熟的现象,借鉴生物区域性进化的原理,设计了一种基于星型迁移策略的并行混合遗传算法(Parallel Hybrid Genetic Algorithm,简称PHGA).该算法采用高效的超贪心算子进行解码,使遗传进化过程从多个平均适应度较高的文明群体开始进化,并采用定期将各群体的最优个体输出给其他群体,使得最优个体共享,促进所有群体共同进化的共产主义迁移策略.在PVM环境下,对背包问题进行求解的实验,已取得超线性的加速比,并改进了解质量. 相似文献
5.
针对标准遗传算法易早熟收敛以及收敛速度慢的问题,提出一种自适应遗传退火算法用于解决高维约束优化问题.该算法采用轮盘赌和最优保存策略相结合的选择机制,并结合自适应交叉、变异概率,继而引入模拟退火算法,加快迭代后期算法的收敛速度.最后,比较了标准遗传算法和自适应遗传算法的实验结果,证明了自适应遗传退火算法在0/1背包应用中的高效性和精确性. 相似文献
6.
0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解. 相似文献
7.
多维0-1背包问题是典型的NP难题,设计了一种求解它的差异演化算法,阐述了算法求解多维0-1背包问题的具体操作过程。用提出的算法对55个测试算例进行了仿真实验,得到了全部算例的最优解。测试结果表明了文中算法是求解多维0-1背包问题的一种有效方法。 相似文献
8.
0/1背包问题的动态状态树的回溯算法 总被引:1,自引:0,他引:1
本文给出了一个以动态状态空间树为基础的0/1背包问题的回溯算法。动态树方法对求解线性规划问题等是非常有用的,该算法所用时间比静态状态空间树方法要少。文中给出的Sparks算法经用C语言写成程度上机验证,思路正确。 相似文献
9.
10.
乐天 《浙江海洋学院学报(自然科学版)》2013,32(1)
背包问题是一种组合优化问题,有很多类型,如多维背包问题等,本文讨论的0/1背包问题是背包问题中最原始最基本的类型.遗传算法在求解背包问题上已经显示了巨大优势.本文分析了遗传算法求解0/1背包问题存在的主要问题,在总结分析近6年的相关文献基础上,提出了未来研究方向,为遗传算法求解0/1背包问题提供参考. 相似文献
11.
解0-1背包问题的遗传算法及其改进 总被引:7,自引:0,他引:7
刘洋 《天津师范大学学报(自然科学版)》2003,23(3):69-72
遗传算法是一种基于自然选择和遗传机制的搜索算法.讨论了用其解决著名的0-1背包问题,尝试混合使用一点杂交与多点杂交以及将传统的算法与遗传算法相结合的方法,对经典遗传算法进行改进,并在实验中获得了对于问题的更佳近似解. 相似文献
12.
背包问题的遗传算法求解 总被引:5,自引:2,他引:5
探讨利用遗传算法解决背包问题并设计新型的遗传算法,给出了背包问题的数学模型,建立了有效的约束条件。在引入一种新的具有自适应性的杂交概率和变异概率的基础上,提出了面向背包问题的遗传算法和一种构造染色体的新方法,提供了遗传算法的结构并讨论了遗传算法,给出了一个例子说明算法的收敛性和收敛效率,仿真说明了算法的有效性。 相似文献
13.
遗传退火进化算法在背包问题中的应用 总被引:22,自引:1,他引:22
从增强算法收敛性和减少参数依赖性的角度出发,提出应用遗传退火进化算法求解背包问题,遗传退火进化算法结合了遗传算法和模拟退火算法的优点,并有效地克服了各自的弱点,使其在优化性能、优化效率和可靠性方面具有明显的优越性.阐明了用该算法求解背包问题的具体实现过程,并通过实际数值计算和结果比较表明,该算法优于遗传算法和模拟退火算法. 相似文献
14.
阐述了遗传算法的基本原理和实现步骤,重点介绍了利用遗传算法在解决旅行商问题时采用的交叉和变异算子的设计与实现. 相似文献
15.
基于小生境遗传算法的多峰函数全局优化研究 总被引:2,自引:0,他引:2
针对基本遗传算法在求解多峰函数时很难找到全部最优解的问题,研究了基于淘汰相似结构机制的小生境遗传算法。用该算法对两个典型多峰函数求解的测试结果表明,该算法较之基本遗传算法有更强的全局搜索能力和更快的收敛速度。 相似文献
16.
为了改善动态规划法的空间复杂度,基于动态规划算法的一种改进策略,提出了采用动态链表结构存储数据的实现方式,从而达到降低空间复杂度的目的。通过运算验证,表明该改进方法是可行有效的,且其空间复杂度有所优化。 相似文献
17.
求解车辆路径问题的改进遗传算法 总被引:1,自引:0,他引:1
陈久梅 《重庆工商大学学报(自然科学版)》2005,22(5):464-468
在建立车辆路径问题数学模型的基础上,设计了求解该问题的改进遗传算法,即采用自然数编码,构造一定长度的遗传个体表,动态记录适应度以及引入新交叉算子。实验结果表明,该算法用于求解车辆路径问题,不但可以解决传统遗传算法在求解该问题所遇到的“早熟收敛”,而且大大提高算法的运行效率。 相似文献
18.
提出了一种改进的自适应遗传算法.它使网格法思想在二进制编码表示个体的情况下得以实现,因此保证了初始种群内个体的遍历性和多样性;其遗传算子由个体在种群中的排序位置自适应地决定.该算法能维持种群内个体在各个运行阶段多样性,加快种群收敛速度,克服遗传算法早熟现象.几种典型的多峰函数优化结果证明该算法的有效性和实用性. 相似文献