【作者】 吴进波；

【导师】 熊盛武；

【作者基本信息】 武汉理工大学 ， 计算机应用技术， 2007， 硕士

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

【Abstract】 Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem and NP-hard. But it is applied in abroad field in practice. In the past, people have been struggling to seek a new method that has not only high quality but also fast convergence rate all the while. One of the important methods in mathematic processing is solving the old problem using updating standard. In the past twenty years, many technologies of bionic algorithms spring up quietly. And pullulate companied with the developing of computer science synchronously. So a kind of new energy was emitted to the study of TSP. The simulated annealing algorithm is simple and easy to implement, so it has been used in every broad fields. It is used in solving engineering optimal problems. The vertebrate immune system is a highly evolutionary system, which is highly adaptive, highly distributed and self-organizing. It can effectively recognize the antigens and kill them rapidly to protect the stability of the body. The Artificial Immune System (AIS) is an intelligent information processing technology that is based on the mechanism of the vertebrate immune system. As a novel branch of computational intelligence, AIS has strong capabilities of pattern recognition, learning and associative memory, hence it is natural to view AIS as a powerful information processing and problem-solving paradigm in both the scientific and engineering fields.In this paper, some topics are mainly talked about:Some basic concepts, framework, functions and principles of the biological immune system are introduced. Then the research range, research status and basic theory of the artificial immune system and simulated annealing algorithm are simply analyzed.Secondly, we deeply analyze the mechanism of simulated annealing algorithm, then the paper proposes a simulated annealing algorithm based on controllable temperature parameter for solving TSP. By testing the data of CHN144 and benchmark TSPLIB, the experiments show that the algorithm is easy to find out the best answer. Thirdly, after understanding some basic concepts and some principles of the vertebrate immune system, an immune algorithm is proposed and realized on the basis of immune principal. By testing it, the algorithm obtains a good solution.Finally, we do the research on immune algorithm and simulated annealing algorithm, and a new immune simulated annealing algorithm for TSP is proposed on the basis of simulated annealing algorithm and immune algorithm. By testing the data of PR1002, the experiences show that the algorithm has a good performance.更多还原