《遗传算法求解tsp问题的计算机仿真》由会员分享，可在线阅读，更多相关《遗传算法求解tsp问题的计算机仿真（59页珍藏版）》请在金锄头文库上搜索。
1、I题目：遗传算法求解旅行商问题的计算机仿真II遗传算法求解 TSP 问题的计算机仿真摘要由于遗传算法在整体搜索策略和优化搜索方法上不依赖梯度信息或其他辅助知识，只需要影响搜索方向的目标函数和相应的适应度函数，所以提供了一种求解复杂系统问题的通用框架，因此遗传算法广泛应用于数学问题、组合优化、机械设计、人工智能等领域。遗传算法（Genetic Algorithms,简称 GA）是模拟自然界生物自然选择和进化的机制而发展起来的一种高度并行、自适应的随机搜索算法。特别适合于求解传统的搜索算法不好处理的复杂的最优解问题。旅行商问题（Traveling Salesman Problem）就是要决定一条经
2、过路线中所有城市当且仅当一次且距离最短的路线，即距离最短的 Hamilton 回路。旅行商问题是一个具有十分广泛的实用背景和重要理论价值的组合优化问题。目前求解 TSP 问题的主要方法有模拟退火算法、遗传算法、Hopfield 神经网络算法、启发式搜索法、二叉树描述算法。本文选用遗传算法求解 45 个城市的 TSP 问题，基于Microsoft Visual C+环境,采用 Grefenstette 等提出的一种新的巡回路线编码方法，变异算子采用了常规的基本位变异法，通过多组实验和数据近似的求解出了 45 个城市的最优解，实现了计算机仿真求解 TSP 问题。关键字：旅行商问题；遗传算法；变异算
3、法；编码方式IIIThe computer simulation of genetic algorithm to solve TSP problemAbstractDue to genetic algorithm on the overall search strategy and optimization search method does not depend on the gradient information or other auxiliary knowledge, only need to influence the search direction of the object
4、ive function and the corresponding fitness function, and so provides a generic framework for solving complicated system problem, so the genetic algorithm is widely used in mathematical problem, combinatorial optimization, mechanical design, artificial intelligence, etc Genetic algorithm (based Algor
5、ithms, the GA) is mimic natural biological natural selection and evolution mechanism and developed a kind of highly parallel, adaptive random search algorithm. Particularly suitable for solving the traditional search algorithm is not good to deal with complex optimal solution of problem. Traveling S
6、alesman Problem (ll Salesman Problem) is to determine a through route if and only if all cities in time and distance is the shortest route, the shortest distance of Hamilton loop. Traveling salesman problem is a very wide range of practical background and important theoretical value of the combinato
7、rial optimization problem. At present the main method of solving TSP problem with simulated annealing algorithm, genetic algorithm and Hopfield neural network algorithm, the heuristic search method, the binary tree described algorithm. This article chooses 45 cities genetic algorithm to solve the TS
8、P problem, based on Microsoft Visual c + + environment, use the proposed a new tour routes such as Grefenstette coding method, mutation operator adopted conventional basic variation method, through multiple sets of experimental data and the approximate solution of the 45 cities the optimal solution,
9、 has realized the computer simulation to solve the TSP problem.KEY WORDS: TRAVELING SALESMAN PROBLEM. GENETIC ALGORITHM; MUTATION ALGORITHM; IV目录遗传算法求解 TSP 问题的计算机仿真 .IAbstract.II1 绪论 .11.1 研究背景 .11.2 研究意义 .21.3 研究内容 .21.4 本文的结构 .32 遗传算法理论概述 .42.1 遗传算法的产生及发展 .42.2 遗传算法基本原理 .52.3 遗传算法基本步骤 .62.4 遗传算法算法流程图 .62.5 遗传算法的特点 .72.6 遗传算法的应用 .83 基于遗传算法求解 TSP 问题 .103.1 旅行商问题的描述与建模 .103.2 编码方式 .103.3 遗传算子的设计（交叉、选择、变异） .123.3.1 交叉算子 .123.3.2 选择算子 .
