一类大规模TSP问题的遗传算法研究

论文摘要

遗传算法是一类借鉴生物的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机搜索方法,具有隐并行性和全局寻优能力,鲁棒性强,操作简单。不需要确定的规则,采用概率化的寻优方法,能自动获取和优化搜索空间,自适应的调整搜索方向。遗传算法已被人们广泛地应用于组合优化,解决了许多传统优化方法难以解决的问题。旅行商问题就是组合优化中典型的NP难问题,应用遗传算法解决旅行商问题,不仅启发了其他问题的求解,更被广泛地应用于机器学习、信号处理、自适应控制和人工生命等领域。本文针对一类特殊的大规模TSP问题,提出了一个新的遗传算法,主要工作如下:1.结合带聚类特征的大规模旅行商问题,提出了一种在聚类过程中找到最优的簇的数目的方法,并据此将大规模TSP问题转化为若干个小规模问题。2.在聚类得到的各个簇中,设计了一种基于图论的交叉算子,在此基础上提出了一种改进的遗传算法,用该遗传算法求解各簇中的最优回路,并证明了算法的收敛性。3.提出了一种新的连接策略将各个簇中的最优回路连接成一个整体回路,在此基础上进行仿真实验,得到了较好的结果,证明以上的解决方案是有效的。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 遗传算法的发展与应用
• 1.3 本文的主要工作和内容安排
• 第二章 旅行商问题
• 2.1 旅行商问题概述
• 2.2 旅行商问题的定义和数学模型
• 2.3 旅行商问题的分类
• 2.4 旅行商问题的研究价值和应用
• 2.5 旅行商问题的已知算法
• 第三章 遗传算法综述
• 3.1 遗传算法的基本概念
• 3.2 遗传算法的基本原理和流程
• 3.3 遗传算法的数学基础
• 3.4 遗传算法的控制参数
• 3.5 遗传算法的优劣
• 3.6 遗传算法求解TSP 的基本方法
• 3.6.1 编码方案
• 3.6.2 种群的初始化和适应度函数的选择
• 3.6.3 选择算子
• 3.6.4 交叉算子
• 3.6.5 变异算子
• 第四章 求解小规模TSP问题的遗传算法
• 4.1 编码策略
• 4.2 交叉策略
• 4.2.1 图论的基础知识
• 4.2.2 多父代交叉策略
• 4.3 变异算子
• 4.4 局部搜索
• 4.5 求解TSP 的改进遗传算法
• 4.6 遗传算法的全局收敛性
• 第五章 求解一类大规模TSP问题的新的遗传算法
• 5.1 聚类问题介绍
• 5.2 一类大规模TSP 问题聚类方法及聚类数目的确定
• 5.3 连接策略
• 5.4 求解一类特殊大规模TSP 问题的遗传算法
• 5.5 数值仿真
• 5.6 本章小结
• 结束语
• 致谢
• 参考文献