首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 15 毫秒
1.
求解大规模0-1背包问题的主动进化遗传算法   总被引:9,自引:0,他引:9       下载免费PDF全文
针对遗传算法求解大规模0-1背包问题中存在的不足,将定向变异机制引入到遗传算法中,提出了基于主动进化遗传算法的0-1背包问题求解算法。该算法利用概率编码方案对种子个体进行编码,每代种群中的个体通过对该代种子个体进行测度而产生,用于定向变异的诱变因子将参与种子个体的进化。实验结果表明,该算法具有较好的全局寻优能力和执行效率。  相似文献   

2.
基于蜂群遗传算法的0-1背包问题   总被引:1,自引:0,他引:1  
针对0-1背包问题,本文提出了基于蜂群遗传算法的优化求解方案。该算法包括两个种群,一个主要用于全局搜索,另一个主要用于局部搜索;每个个体采用二进制编码;采用最优个体交叉策略;对当前解的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止;不符合约束条件的解采用诱变因子指导变异处理;遗传算子包括单点交叉算子、简单变异算子、主动进化算子和抑制算子。本算法充分发挥了遗传算法的群体搜索和全局收敛的特性,快速地并行搜索,有效地克服了经典遗传算法容易陷入局部最优问题。数值实验表明,该算法在求解0-1背包问题中取得了较好的效果,同样可以应用于其它的组合优化问题。  相似文献   

3.
针对传统遗传算法(SGA)容易"早熟"的不足,提出一种求解0-1背包问题(KP)的改进遗传算法。借鉴二重结构编码的解码处理方法设计了一种新解码方法,在保证解可行性的同时修正种群中无对应可行解的个体;采用模拟退火算法和改进的精英选择算子改进SGA。实例仿真结果验证了改进遗传算法在进化效率和最优解搜索能力上的优越性。  相似文献   

4.
GA是一类基于自然选择和遗传学原理的有效搜索方法,它从一个种群开始,利用选择、交叉、变异等遗传算子对种群进行不断进化,最后得到全局最优解.但随着求解问题的复杂性及难度的增加,提高GA的运行速度便显得尤为突出,采用并行遗传算法(PGA)是提高搜索效率的方法之一.本文分析了并行遗传算法的四种模型,最后应用于0-1背包问题的求解.实验结果表明,该算法在具有较高搜索效率的同时,仍能维持很高的种群多样性.  相似文献   

5.
王小良  李强 《微计算机信息》2007,23(3X):205-206
GA是一类基于自然选择和遗传学原理的有效搜索方法,它从一个种群开始,利用选择、交叉、变异等遗传算子对种群进行不断进化。最后得到全局最优解。但随着求解问题的复杂性及难度的增加,提高GA的运行速度便显得尤为突出,采用并行遗传算法(PGA)是提高搜索效率的方法之一。本文分析了并行遗传算法的四种模型,最后应用于0-1背包问题的求解。实验结果表明.该算法在具有较高搜索效率的同时,仍能维持很高的种群多样性。  相似文献   

6.
一种基于模式替代的遗传算法解0/1背包问题*   总被引:3,自引:1,他引:2  
背包问题是一个典型的 NP完全问题。提出一种基于模式替代的遗传算法解0/1背包问题思想,通过收集每代种群中最好的几个个体生成模式来引导种群的搜索方向,以提高遗传算法的搜索速度和寻找最优解的能力。通过仿真数值实验,将该方法与简单遗传算法、贪心算法计算结果比较分析,充分证明了使用基于模式替代遗传算法来求解背包问题的有效性和实用性。  相似文献   

7.
求解多维0-1背包问题的一种改进的遗传算法   总被引:2,自引:1,他引:2  
针对多维0-1背包问题,通过应用贪心法和二分搜索法的思想,本文提出了一种新的杂交算子——中值杂交,并且基于此算子提出了求解多维0-1背包问题的一种改进的遗传算法。最后本文通过一系列数值实验,把改进算法与传统的遗传算法以及其他最新的遗传算法进行比较,经过对求得近似解的精度及计算所需时间两方面的对比,验证了其有效性。  相似文献   

8.
0-1背包问题是背包问题中的基础也是最为经典的一大分支,其组合优化模型被广泛的应用于社会生产生活的各个领域,对NP完全问题的求解有重要价值.传统的启发式算法如遗传算法、基本差分进化算法、粒子群算法,在解决相同0-1背包问题时,差分进化算法在解决离散型0-1背包问题时收敛更快,但存在早熟问题.论文从启发式算法角度出发,结合差分进化算法中变异策略的特点,提出一种新的变异策略rand/3/bin求解方法,与遗传算法、粒子群算法、采取两种变异策略的差分进化进行性能对比实验(实验测试数据已公开在Github),结果表明:该算法实现了相对于原有实验收敛更快和结果更优的结果,具有良好的应用价值.  相似文献   

9.
求解0-1背包问题的混沌遗传算法   总被引:1,自引:0,他引:1  
提出一种改进的混沌遗传算法来求解0-1背包问题。通过利用幂函数载波技术增强混沌搜索的遍历性,把混沌搜索得到的最优解直接作为新群体嵌入遗传算法来改善遗传算法的早熟问题,从而使算法有能力避免陷入局部极值而快速收敛于全局最优解。仿真实验结果表明了该算法求解0-1背包问题的有效性和适用性。  相似文献   

10.
基于遗传算法的多目标0-1背包问题优化模型   总被引:1,自引:1,他引:1  
多目标0-1背包问题是一个NP-complete的多目标优化问题,基于群体搜索机制的遗传算法非常适合多目标优化问题的求解。在著名的多目标优化遗传算法NSGA-II中,引入邻域搜索机制,并将其应用于多目标0-1背包问题的求解。数值实验表明,引入邻域搜索机制的NSGA-II算法在求解多目标0-1背包问题时表现出更好的性能。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号