遗传算法的改进及其在TSP问题中的应用

摘要:TSP是一种最经典的求最优解的优化问题，有各种算法可以有效求解，其中，遗传算法是一种能够协助处理高维组合优化问题的算法，它可以通过其独有的特点，求出最优解。同时，由于遗传算法有着比较显著的缺点，即容易早熟并且陷入局部最优解的情况，希望能改进遗传算法，得到更优的解，所以需要将其他算法与之混合使用以此来改进之。而禁忌搜索算法则能够根据其特点很好的避免陷入局部最优解以大幅改进遗传算法。本文将经过混合二者的算法进一步来利用求解TSP问题，以取得更加好的解。79888

关键词：遗传算法；TSP问题；禁忌搜索算法

Improvement of Genetic Algorithm and Its Application in TSP Problem

Abstract: TPS is one of the most classical optimal solutions, and there are various algorithms to solve the TSP problem。 Among them, genetic algorithm is an algorithm which can help deal with high-dimensional combination optimization problem, which can be characterized by its unique , Find the optimal solution。 At the same time, because the genetic algorithm has a significant drawback, that is easy to premature and fall into the local optimal solution of the situation, hoping to improve the genetic algorithm to get a better solution, so the need to mix and match other algorithms used to improve it。 And the tabu search algorithm can avoid the local optimal solution according to its characteristics to improve the genetic algorithm。 In this paper, we will use the algorithm of the two to further solve the TSP problem to obtain a better solution。

Key words: genetic algorithm；TPS problem；tabu search algorithm

1。绪论 1

1。1本次研究的背景及意义 1

1。2遗传算法的发展情况 1

1。3本文研究内容 3

1。4全文安排 4

2。遗传算法简介 5

2。1遗传算法的基本概念 5

2。2遗传算法的操作算法 7

2。3遗传算法的优缺点 8

3。禁忌搜索算法 9

3。1禁忌搜索算法的概念和思想 9

3。2禁忌搜索算法构成要素 10

3。2。1初始解的确定 10

3。2。2邻域移动 10

3。2。3禁忌表 11

3。2。4选择策略 12

3。2。5破禁策略 12

3。2。6停止规则 12

3。2。7禁忌搜索算法的流程 12

3。3禁忌搜索算法的特点 13

4求解TSP问题及仿真 14

4。1TSP问题描述 14

4。2求解TSP的基本步骤与思想 14

4。3遗传算法求解TSP问题 15

4。4禁忌搜索算法求解TSP 16

5总结与展望 19

致谢 20

参考文献 20

1。绪论

1。1课题研究的背景及意义

遗传算法是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群向更好的解进化。传统上，解用二进制表示(即0和1的串)，但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体(基于它们的适应度)，通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。遗传算法是由John，H。Holland教授于1975年首先提出来的。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群向更好的解进化。传统上，解用二进制表示(即0和1的串)，但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体(基于它们的适应度)，通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。近年来遗传算法在解决连续变量的函数最优化问题和离散变量的组合最优化问题时所表现出的全局最优性、隐含并行性和自适应性而使其成为目前应用较为广泛的一种智能优化方法。[11]论文网遗传算法的改进及其在TSP问题中的应用:http://www.youerw.com/zidonghua/lunwen_92621.html