一种改进的遗传算法及其在TSP求解中的应用

摘要

遗传算法(Genetic Algorithm,简称GA)由John Holland于1975年提出,对于传统方法难于求解的组合优化、模式识别、图像处理等复杂问题,使用该算法求解能得到令人较为满意的解。近年来,遗传算法在解决连续变量的函数最优化问题和离散变量的组合最优化问题时表现出的鲁棒性、全局性、隐并行性和自适应性使其成为一种应用日益广泛的智能优化算法。
　　TSP是组合优化中最为著名的问题,它综合了一大类组合优化问题的典型特征,并以不同的形式存在于超大规模集成芯片制造、印刷电路板设计、X—射线结晶学、机器人控制等高科技领域。
　　由NP完全理论可知,TSP属于NP难问题,用常规的搜索方法无法有效地求解。但如今正迅速发展的按自然法则计算的思想在求解大规模组合优化问题时表现出非凡的潜力,其中的一个分枝—遗传算法以其独有的魅力吸引了越来越多的研究者。
　　经典遗传算法的主要特点在于它的简单性和鲁棒性,几乎不需要知道所求问题的任何知识,但也正是由于这一点,遗传算法不能利用问题本身的信息,影响了求解具体问题时的效率。因此,在研究利用遗传算法求解TSP问题上我们存在很大的改进空间。
　　本文对遗传算法的理论与应用进行了一些研究和分析工作。首先介绍了遗传算法的理论和它在组合优化问题中的应用,然后针对TSP问题的求解进一步指出遗传算法存在易陷入早熟收敛和后期收敛速度慢的缺点,最后本文在原有遗传算法的基础上提出了一种改进的遗传算法。由于考虑到交叉算子和变异算子对算法的多样性影响,因此交叉算子和变异算子是本算法改进过程中主要关注的两个问题。本算法在交叉算子方面结合启发式交叉和边重组交叉算子设计出一种新的交叉算子；在变异算子设计上,采用了—种新的变异算子—转位算子。另外,在进化过程中算法引入自适应策略来控制遗传参数的变化,加快了种群的收敛速度。本文使用改进型遗传算法对国际通用的TSP测试库TSPLIB中不同城市规模的数据进行测试,实验数值结果证明了该算法的可行性和有效性。

目录

摘要

Abstract

第1章 绪论

1.1 立项背景与开发意义

1.2 本文研究内容与创新

1.3 本文的篇章组织

第2章 遗传算法简介

2.1 遗传算法的产生与发展

2.2 遗传算法概要

2.2.1 遗传算法的基本概念

2.2.2 遗传算法的基本思想

2.3 遗传算法的原理

2.3.1 遗传算法的基本操作及流程

2.3.2 遗传算法(SGA)设计与实现

2.4 遗传算法的数学基础

2.5 遗传算法的关键技术

2.5.1 遗传编码

2.5.2 遗传算子

2.5.3 适应度函数及其尺度变换

2.5.4 遗传算法的参数

2.5.5 遗传算法的终止条件

2.6 遗传算法的应用情况

第3章 TSP问题的数学模型和基本解法

3.1 TSP数学描述

3.2 传统方法

3.2.1 精确算法

3.2.2 近似算法

3.3 智能优化方法

第4章 求解TSP的传统遗传算法

4.1 求解TSP的基本实现方法

4.1.1 编码

4.1.2 生成初始群体

4.1.3 适应度函数

4.2 遗传算子

4.2.1 选择算子

4.2.2 交叉算子

4.2.3 变异

4.3 算法结构

4.4 自适应遗传算法

4.5 浓度控制遗传算法

4.6 并行遗传算法

4.6.1 主从式模型

4.6.2 粗粒度模型

4.6.3 细粒度模型

第5章 改进型遗传算法求解TSP问题

5.1 编码

5.2 生成初始群体

5.3 确定适应度函数

5.4 选择算子

5.5 交叉算子

5.6 变异算子

5.7 参数选择

5.8 仿真结果

第6章 结束语

6.1 总结

6.2 展望

参考文献

攻读研究生学位期间发表的学术论文

学位论文评阅及答辩情况表