多种群自适应模拟退火遗传算法求解TSP问题

论文摘要

巡回旅行商问题(简称TSP)是一个具有广泛应用背景和重要理论价值的组合优化NP难题。遗传算法是一种模拟自然界生物进化的搜索算法,由于它简单易行、鲁棒性强,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且已在众多领域得到了实际应用,取得了令人瞩目的成果,引起了广大学者和工程人员的关注。在遗传算法研究中,TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。众所周知,遗传算法有两个严重的缺点,即容易过早收敛,以及在进化后期搜索效率较低。本文针对遗传算法上述的两个缺点,对传统的遗传算法进行改进,提出了多种群自适应模拟退火遗传算法求解巡回旅行商问题。该算法采用自适应交叉概率进行轮盘赌最优个体保留和自适应变异概率进行多种变异方法相结合的混合变异,将全局搜索能力较强的遗传算法引入局部搜索能力较强的模拟退火算法,并且同多种群并行遗传进化思想有机地结合起来。各个子种群独立进化到一定代数后,通过种群间的相互交叉和迁移,实现种群分级,这种分级的方法可以使优秀个体中的优良基因片通过相互之间的交叉从而得到保留和优化组合,又可以使低劣个体中的优良基因片通过低劣个体之间大概率的交叉得到保留,甚至通过大概率的变异使低劣的基因片得到改良。做这样处理时,可以选取和保留每个子种群的优秀个体,并在保持优秀个体进化的稳定性的同时加快进化速度,避免单种群进化过程中出现的过早收敛现象。本文使用改进后的算法,针对CHN31、ATT48和EIL51的旅行商问题进行求解,仿真结果表明,该算法避免了遗传算法中存在的过早收敛收敛的问题,增强了算法的全局收敛性,并且提高了算法的收敛速度。

论文目录

• 摘要
• summary
• 第一章 引言
• 1.1 研究的背景和意义
• 1.2 研究的内容
• 1.3 研究的创新点
• 1.4 本文的结构框架
• 第二章 遗传算法概述
• 2.1 遗传算法理论基础
• 2.1.1 遗传算法理论基础
• 2.1.2 遗传算法的基本概念
• 2.1.3 标准遗传算法
• 2.1.4 遗传算法的特点
• 2.2 遗传算法的描述与设计
• 2.2.1 编码表示
• 2.2.2 种群的初始化
• 2.2.3 适应度
• 2.2.4 选择算子
• 2.2.5 交叉算子
• 2.2.6 变异算子
• 2.3 遗传算法的数学基础
• 2.3.1 模式定理和积木块假设
• 2.3.2 收敛性分析
• 2.3.3 欺骗性问题
• 2.3.4 隐式并行性
• 2.4 如何防止过早收敛
• 2.4.1 适应度伸拉法
• 2.4.2 多种群交叉法
• 第三章 TSP问题及研究的基本方法
• 3.1 TSP的数学描述及模型
• 3.2 传统方法
• 3.2.1 精确算法
• 3.2.2 近似算法
• 3.3 智能优化方法
• 第四章 多种群自适应模拟退火遗传算法求解TSP问题
• 4.1 多种群自适应模拟退火遗传算法思想
• 4.2 算法设计纲要
• 4.2.1 算法实现过程
• 4.2.2 算法流程
• 4.3 本文的算法设计
• 4.3.1 编码
• 4.3.2 生成初始群体
• 4.3.3 多种群分级
• 4.3.4 模拟退火的遗传算法
• 4.3.5 交叉、变异遗传算子
• 4.3.6 算法的自适应性
• 第五章 实验分析及结论
• 5.1 CHN31、ATT48、EIL51的TSP问题的执行结果
• 5.2 算法的自身改进机制的比较分析
• 5.2.1 简单遗传算法与本文算法的比较
• 5.2.2 指定概率和概率动态自适应的比较
• 5.2.3 多种群迁移和单种群的比较
• 5.2.4 引入模拟退火与不引入模拟退火的比较
• 5.2.5 采用各种交叉算子的多种群自适应遗传算法的运行结果的比较
• 5.2.6 采用各种变异算子的多种群自适应遗传算法的运行结果的比较
• 5.3 与其他算法求解CHN31的实验结果比较
• 5.4 结论
• 第六章 问题的总结与展望
• 6.1 问题总结
• 6.2 研究展望
• 参考文献
• 致谢