问题和解共同进化的优化方法的试探

发布时间：2017-09-22 00:01

  本文关键词：问题和解共同进化的优化方法的试探

  更多相关文章： 进化算法 遗传算法 问题和解共同进化 旅行商问题 局部最优问题

【摘要】：随着生物学与进化算法不断的研究与完善,研究人员研究总结发现,自然界种群个体或物种之间,不但有着个体或物种之间为自然环境生存的竞争关系,它们之间还有着很常见明显的相互作用协作式一起共同进化的规律。协同进化,最早由Ehrlich和Raven提出,协同进化是指各个种群间通过相互作用建立关联,并提高种群的性能的优化。其实,协同进化也有两种:协作型协同进化和竞争型共同进化。在此基础上,我们可以理解为物种的最终的进化成的结果,其实是最终环境的演变过程中物种进化的结果。环境不停的演变,最终演变成我们现在的环境,而现在的物种就是经历环境不断的演变并自身在不断进化已经适应演变之后最终的当前环境的结果。本文的问题和解共同进化算法,就是描述的就是这样的一个方法。我们的问题和解共同进化算法里的问题的进化严格来讲不是进化而是演变,它类似于环境的演变,在这种环境变化的情况下,物种如何变化就是解的进化,最终的解就是在最终的环境下的解,即环境演变伴随着物种自身进化最终的种群。在这里我们可以设置,使问题演化并最终演化成我们希望的问题,这就是问题和解共同进化。该方法在农业应用方面也有借鉴作用。当前,遗传算法很多的改进都在致力于改进它的收敛速度慢和早熟的问题。而在遗传算法局部最优的这个问题上,很多改善只是试图提高算法的全局收索能力,从而使之减少陷入局部最优的可能性。而本文的问题和解共同进化算法,旨在探讨跳出遗传算法局部最优的问题。在本文中,仅以旅行商问题(Traveling Salesman Problem,TSP)来试探本文的问题和解共同进化算法。在传统遗传算法解决TSP问题的基础上,设计我们问题和解共同进化算法在TSP问题上对遗传算法局部最优问题的影响。本文的TSP问题的设计是让它从一个三维空间的TSP问题逐渐演变成传统的二维平面的TSP问题,即在这里我们问题的关键就是第三维坐标Z的初始化与它在进化过程中的变化规律的设置,使之以一种合理的方式逐渐演变成二维平面的TSP问题的求解,这是本文的研究重点,。本文问题和解共同进化算法将从三个方向探讨问题和解共同进化算法对于跳出遗传算法局部最优问题的影响:首先,是让问题演化规则相同即Z初始值和变化规律相同的情况下,从不同的数据量的经典的已经得到解决的TSP问题探讨,这里选取了四个TSPLIB里经典的TSP问题kroA100、att532、pr1002、pr2392进行探讨;其次,是从Z初始值不同,变化规律相同来探讨对遗传算法局部最优问题的影响;最后是从Z初始值相同,变化规律不同来探讨对遗传算法局部最优问题的影响。改进后的算法得到的结果如果能比传统的遗传算法更优的解、相似的解或者是比它稍差的解,总的来说就是得到不一样的跳动很大的和传统的不相同的解,因此问题和解共同进化算法可以使遗传算法的解有所跳动而不再是总处于一个相对来说平稳的局部解,即跳出遗传算法局部最优的问题。
【关键词】：进化算法 遗传算法 问题和解共同进化 旅行商问题 局部最优问题
【学位授予单位】：南昌大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要3-5
• ABSTRACT5-9
• 引言9-11
• 第1章 进化算法概述11-18
• 1.1 进化规划12-13
• 1.2 进化策略13-14
• 1.3 遗传算法14-18
• 1.3.1 遗传算法的概念14-15
• 1.3.2 遗传算法的特点15
• 1.3.3 遗传算法的基本原理15-16
• 1.3.4 遗传算法的步骤16-17
• 1.3.5 参数控制17
• 1.3.6 算法结束条件17-18
• 第2章 共同进化算法18-24
• 2.1 协同进化算法18-21
• 2.1.1 竞争协同进化19-20
• 2.1.2 协作共同进化20-21
• 2.2 问题和解共同进化算法21-24
• 第3章 旅行商问题24-29
• 3.1 旅行商推销员问题描述24
• 3.2 TSP的应用24-25
• 3.3 TSP的进展25
• 3.4 现有的TSP计算方法25-29
• 3.4.1 完全算法26-27
• 3.4.2 不完全算法27-29
• 第4章 问题和解共同进化遗传算法在TSP问题上的试探29-38
• 4.1 传统遗传算法解决TSP问题主要思想29-34
• 4.1.1 编码及适应度函数29-30
• 4.1.2 选择机制30
• 4.1.3 交叉策略30-33
• 4.1.4 变异技术33-34
• 4.2 问题和解共同进化遗传算法在TSP问题上的试探的主要思想34-38
• 4.2.1 TSP问题的演变（或者是“进化”）35-36
• 4.2.2 Z坐标的初始值设置与变化函数设置36-37
• 4.2.3 编码及适应度函数37
• 4.2.4 选择机制37
• 4.2.5 交叉策略37
• 4.2.6 变异技术37-38
• 第5章 实验结果及分析38-58
• 5.1 参照TSPLIB不同城市，改进的方法与传统的方法比较39-50
• 5.1.1 kroA100TSP问题实验结果39-41
• 5.1.2 att532TSP问题实验结果41-44
• 5.1.3 pr1002TSP问题实验结果44-47
• 5.1.4 pr2392TSP问题实验结果47-50
• 5.2 Z初始值不同，改进的方法与传统的方法比较50-54
• 5.3 Z如何趋近于零，，改进的方法与传统的方法比较54-58
• 第6章 结论与展望58-60
• 6.1 结论58-59
• 6.2 进一步工作的方向59-60
• 致谢60-61
• 参考文献61-64

【参考文献】

中国期刊全文数据库 前6条

1 尤文坚;叶雪英;;粒子群和遗传算法在农业工程中的应用[J];农机化研究;2013年01期

2 吕跃进;刘南星;陈磊;;一种基于并行遗传算法的粗糙集属性约简[J];计算机科学;2008年03期

3 罗彪;郑金华;杨平;;基于定向爬山的遗传算法[J];计算机工程与应用;2008年06期

4 王德利,高莹;竞争进化与协同进化[J];生态学杂志;2005年10期

5 曹先彬,罗文坚,王煦法;基于生态种群竞争模型的协同进化[J];软件学报;2001年04期

6 马良;旅行推销员问题的算法综述[J];数学的实践与认识;2000年02期

本文编号：897600