免疫算法和模拟退火算法求解TSP问题的研究

摘要

旅行商问题是一个经典的组合优化问题，也是一个NP难问题。它在实际中的应用却非常广泛。历年来，人们一直努力地寻找一种既有高质量的解，又能快速收敛的近似算法。数学发展的重要手段之一就是用新方法解决老问题。最近二十年，许多仿生计算技术悄然兴起，它随着计算机科学的发展同步成长起来。于是，这个古老问题的研究又重新注入了新的活力；由于模拟退火算法简单易行，从而使它的应用范围极为广泛，并且已在众多领域得到了实际应用，且经常用于解决工程上的寻优；生物免疫系统是一个高度进化的生物系统，它具有高度自适应、高度分布性、自组织等特性。它能够有效识别入侵的抗原并清除抗原，并保持机体的稳定。人工免疫算法正是借鉴生物免疫系统信息处理机制的基础上发展起来的智能信息处理技术。由于人工免疫算法具备模式识别、学习和记忆的能力，因此它成为了一种科学及工程领域中信息处理和问题求解范式，由此也开辟了计算智能研究的新领域。 本文的工作主要集中在以下几个方面： 介绍了生物免疫的一些基本概念、系统组成、功能及原理；简单分析了人工免疫系统的研究内容、研究现状及基本理论；然后，对现已被提出的一些免疫算法和模拟退火算法的基本结构和流程进行了研究和分析。 其次，在深入分析了模拟退火算法基础上，提出一种温度可控的求解TSP问题的模拟退火算法，通过对CHNl44以及标准的TSPLIB中不同国家的城市的数据进行测试，测试结果表明：该算法很容易收敛到问题的最优解。 然后，在理解和掌握生物免疫系统的基本概念和工作原理后，针对免疫原理提出了求解TSP问题的免疫算法并进行了实现和实验。实验表明：该算法能够求得很好的解。 最后，在深入研究免疫算法和模拟退火算法之后，本文提出了一种新的免疫模拟退火算法，并将其应用于求解典型的NP问题--TSP问题，同时进行了仿真实验，通过对标准的TSPLIB中的PR1002的数据进行测试，该算法具有良好的性能。

目录

文摘

英文文摘

声明

第1章 绪论

1.1研究的背景及意义

1.2研究现状

1.2.1 TSP的研究现状

1.2.2模拟退火算法的研究现状

1.2.3人工免疫算法研究现状

1.3本文的主要工作

1.4本文的结构

第2章 求解TSP问题的模拟退火算法

2.1一般模拟退火算法

2.1.1概述

2.1.2模拟退火算法的描述

2.2温度可控的求解TSP问题的模拟退火算法

2.2.1求解TSP问题的变换算子

2.2.2温度可控的求解TSP问题的模拟退火算法设计思路

2.2.3一些重要部分的实现

2.2.4实验及结果

2.2.5小结

第3章 求解TSP问题的人工免疫算法

3.1一般免疫算法的理论思想及算法

3.2求解TSP问题的免疫算法

3.2.1求解TSP问题的免疫算法流程图

3.2.2对上述算法重要部分的设计

3.2.3算法的实现及实验

3.2.4结束语

3.3免疫模拟退火算法求解TSP问题

3.3.1免疫模拟退火算法的思想来源

3.3.2免疫模拟退火算法求解TSP问题的描述

3.3.3对上述算法重要部分的设计和实现

3.3.4实验及结果

3.3.5小结

第4章 总结和展望

参考文献

致谢

硕士在学期间参加的科研项目和发表的论文