遗传算法求解TSP问题的研究与改进

论文摘要

遗传算法是模仿生物进化和自然选择机理,模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。近年来,遗传算法由于在解决各类最优化问题时表现出的鲁棒性、全局性、隐含并行性和自适应性而成为一种应用日益广泛的智能优化算法。旅行商问题（TSP）是组合优化领域中的一个典型NP完全问题,是诸多领域内出现的多种复杂问题的集中概括和简化形式。快速、有效地解决TSP问题有着较高的理论意义和实际应用价值。本文根据TSP问题的特点和当前研究情况,选用遗传算法对它进行求解。介绍了遗传算法的原理及基本实现技术,着重阐述了遗传算法的特性和影响遗传算法性能的因素,针对TSP问题对遗传算法进行相应的改进。首先针对传统遗传算法中初始种群平均适度度低的缺点,设计了一种贪婪选择策略代替随机化生成初始种群,从而提高初始种群的质量；然后根据TSP问题种群个体编码的特点,结合贪婪算法,设计了一种贪婪交叉算子,使之既能有效地保留父代个体的优良基因,又能以较大的概率产生新的优良个体；在变异算子设计上,采用了两种变异算子相结合的方法,以提高种群的多样性；此外,在进化过程中算法引入了自适应策略来控制遗传参数的变化。本文使用改进的遗传算法对国际通用的TSP测试库TSPLIB中不同城市规模的数据进行测试,实验结果表明了该算法具有较高的执行效率。在以上改进遗传算法的基础上,结合主从式并行程序设计的特点,提出了工作站机群环境中基于MPI求解TSP问题的并行遗传算法。该算法采用按城市结点编号分配种群,并定期在主从进程中交换优良个体。最后利用VC++和MPICH并行库对算法进行了实现,通过分析多组实验数据表明该算法在求解速度和精度上均有所提高。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究意义
• 1.3 国内外研究现状
• 1.4 论文的主要工作
• 1.5 论文的组织结构
• 第2章 遗传算法的基本理论
• 2.1 基本概念
• 2.2 基本原理
• 2.3 遗传算法的结构
• 2.3.1 编码机制
• 2.3.2 控制参数
• 2.3.3 适应度函数
• 2.3.4 遗传算子
• 2.4 遗传算法的运行流程
• 2.5 模式定理
• 2.6 遗传算法的优缺点分析
• 2.6.1 遗传算法的优点
• 2.6.2 遗传算法的缺点
• 2.7 遗传算法的改进与发展趋势
• 2.8 本章小结
• 第3章 改进的遗传算法求解TSP问题
• 3.1 TSP问题描述
• 3.2 传统遗传算法求解TSP问题
• 3.2.1 编码及适应度函数
• 3.2.2 遗传算子
• 3.3 改进的遗传算法主要操作
• 3.3.1 编码及适应度函数
• 3.3.2 初始化种群
• 3.3.3 控制参数
• 3.3.4 遗传算子
• 3.4 改进的遗传算法主程序
• 3.5 算法的实现与实验结果分析
• 3.6 本章小结
• 第4章 并行遗传算法
• 4.1 并行计算和并行计算模型
• 4.1.1 共享存储模型
• 4.1.2 消息传递模型
• 4.2 并行遗传算法的类型
• 4.2.1 主从式并行遗传算法
• 4.2.2 粗粒度并行遗传算法
• 4.2.3 细粒度并行遗传算法
• 4.3 并行遗传算法的性能分析与评价
• 4.3.1 遗传代数和种群规模
• 4.3.2 迁移率与迁移周期
• 4.3.3 性能评价
• 4.4 本章小结
• 第5章 基于MPI的并行遗传算法求解TSP问题
• 5.1 工作站机群
• 5.2 MPI消息传递接口
• 5.3 程序结构
• 5.4 基于MPI的并行遗传算法的实现
• 5.4.1 主进程的工作流程
• 5.4.2 从进程的工作流程
• 5.4.3 算法说明
• 5.5 实验结果分析
• 5.6 本章小结
• 第6章 结论与展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论文