基于免疫算法的TSP问题求解

摘要

随着研究领域问题的不断深入，常规的确定性算法越来越不能满足人们的需求。神经网络算法，模拟退火算法，遗传算法跟免疫算法等算法应运而生。
　　自然界免疫系统的研究很早就开始了，六十年代科学计算研究先驱根据相关科学技术的内容和知识，特别是理论和概念在遗传学方面的积累，形成了人工智能的免疫算法，并成功地应用于某些工程科学现场，并收到了良好的效果。与过去相比，由于遗传算法比传统的搜索算法使用简单，功能强大，易于并行处理的特性，被广泛应用于组合优化问题，结构设计问题，人工智能等领域。
　　旅行商问题，也就是TSP问题(Traveling Salesman Problem)，它是数学中著名问题之一。它的问题描述为:假设一个旅行商人有N个城市需要拜访，但他对于所走路径的要求比较高，有一定的限制:首先他所走的路径要访问每个城市一次且只有一次，最后要回到原来的出发城市。当然这样的路径同样有很多条，但选择目标路径是要从所有满足条件的路径中找到一条最短的路径。
　　本设计主要是对免疫算法展开研究讨论。首先，全面介绍了免疫算法的基本概念及实现步骤，并且对算子进行了详细的介绍;然后把免疫算法跟TSP问题相结合，并对传统的免疫算法进行改进。
　　本设计中提出了一种子代产生方法跟多种调节算子，并把各算子应用到免疫算法中，产生不同的方法，实现对TSP问题的求解。设计最后提供了对公开坐标多组城市的测试数据。

目录

声明

摘要

第一章 引言

1．1 选题背景与研究意义

1．1．1 选题背景

1．1．2 研究意义

1．2 国内外研究现状

1．3 本文的研究工作

1．4 本文的组织结构

1．5 本章小结

第二章 免疫算法综述

2．1 免疫算法来源及发展

2．2 自然免疫系统及特征

2．3 免疫算法及特征

2．4 免疫算法的基本概念

2．5 免疫算法的实现

2．5．1 免疫算法的实现流程图

2．5．2 免疫算法的实现步骤

2．6 免疫算法的运用

2．7 本章小结

第三章 免疫算法求解TSP问题

3．1 TSP问题描述

3．2 算法设计

3．2．1 算法流程图

3．2．2 算法实现

3．2．3 数据结构优化设计

3．3 算法评价

3．4 本章小结

第四章 改进的免疫算法求解TSP

4．1 改进简介

4．2 改进举例

4．3 改进的变异调整算子

4．4 算法评价

4．5 本章小结

第五章 本课题免疫新思路

5．1 新思路的提出

5．2 “梯度’’收敛算子

5．3 新算子的应用

5．4 算法评价程序设计

5．5 新算子算法评价

5．6 快速调整算子

5．7 快速调整算子评价

5．8 快速调整算子的运用

5．9 快速算子方法评价

5．10 本章小结

总结语

参考文献

致谢

附录 城市坐标