改进进化算法及其在旅行商问题中的应用

论文摘要

进化算法是模拟生物界的进化过程而产生的一种现代优化方法,作为一种有效的随机搜索方法,在优化方法中具有独特的优越性,有着非常重要的意义和极其广泛的应用。本文首先简述了遗传算法的基本理论及其应用领域,对简单遗传算法和进化算法进行了研究和分析,将两者有机结合,在基于“反序-杂交”算子的进化算法的基础上,根据局部最优解与全局最优解之间的关系,提出了一种新型的改进进化算法,并将其应用于求解旅行商问题。本文的主要工作如下:①改进反序-杂交算子。反序-杂交算子兼有杂交和变异的特征,以一定的概率对个体进行盲目倒置和自适应倒置,是验证过的非常好的求解TSP的算子。改进后的算子是既保留了原算子的特性,又避免原逆转操作中对基因位置的限制,提高了算法的收敛速度。②引入基因模块映射操作。基因模块映射操作能把父代中优秀的基因片段遗传到下一代,使好的基因片段能让更多的个体所享有,不会因为父代被替代而让好的基因模式丢失。这种做法是结合环路改进算法（SizeScale-Improve）的思想提出的。③提出改进进化算法,用C++编程设计,对TSPLIB中部分TSP算例和随机算例进行试验,并应用于求解中国的31个城市的TSP问题。④对改进进化算法所求得的结果和最近邻算法、贪婪算法、Clarke-Wright算法、Christofides算法、SizeScale构造算法、郭涛算法、SizeScale改进算法、循环Lin-Kernighan算法等经典算法的实验结果进行了数值比较。本文算法的改进是有效可行的,具体而言就是在解的质量上,比最近邻算法、贪婪算法、Clarke-Wright算法、Christofides算法要好的多,与SizeScale构造算法相近;改进进化算法的收敛速度比郭涛算法快,并且解的质量也有所提高;比循环Lin-Kernighan算法的成功率高;比SizeScale改进算法操作简单,而成功率和解的质量并没有受到影响。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 旅行商问题
• 1.2 进化算法的发展及其存在的问题
• 1.3 本文的主要研究工作及贡献
• 2 进化计算概述
• 2.1 进化计算及其分类
• 2.2 遗传算法
• 2.3 进化计算和遗传算法的联系
• 2.4 交叉算子和变异算子的比较
• 3 进化算法的若干改进
• 3.1 需要改进的几个方面
• 3.1.1 进化算法的设计决策
• 3.1.2 郭涛算法及存在的问题
• 3.2 改进的进化算法
• 3.2.1 IEA 从生物借用的一些术语
• 3.2.2 改进反序－杂交算子
• 3.2.3 基因模块的选取和映射操作
• 3.2.4 改进算法实现过程
• 3.2.5 改进进化算法的评价标准
• 3.2.6 改进算法主要特点
• 3.3 改进算法的数学理论基础
• 3.4 改进算法的收敛性
• 3.4.1 收敛阶和收敛因子
• 3.4.2 进化算法的效率
• 3.4.3 改进算法的收敛性叙述
• 3.5 预防早熟的几点措施
• 3.5.1 产生早熟的主要原因
• 3.5.2 防止早熟的措施
• 4 改进算法在旅行商问题中的应用
• 4.1 算法实现的若干细节
• 4.1.1 编码
• 4.1.2 初始解的形成
• 4.1.3 解码
• 4.1.4 适应值函数
• 4.1.5 种群更新过程
• 4.2 算法重要参数的设定
• 4.2.1 映射频率的控制参数
• 4.2.2 其它参数的具体设定
• 4.3 测试问题
• 4.4 测试结果及分析比较
• 5 结论与展望
• 5.1 本文工作总结
• 5.2 研究展望
• 致谢
• 参考文献
• 附录