基于遗传算法的tsp问题研究(一)

基于遗传算法的tsp问题研究

TSP 问题被称为 TSP 货运负担问题，是一个普遍组合的优化问题，需要最短的路线旅行，能够从城市穿越整个城市，可能的路线数量随着城市数量的呈指数级增长。找到一种估计有效的问题解决算法是非常重要的。

本文采用遗传算法解决TSP问题，根据轮盘选择方法选择测序评价函数。两点交叉两点法，随机排序和方法化，随机化，根据30个城市的实际样本，发现最短路径为421.5977，优于二元树描述方法428.90的结果和启发式搜索方法436.01的结果，表明遗传算法在解决TSP问题方面是有效的。

一、遗传算法概述和发展背景

（1）遗传算法简介

遗传算法（GA）是一种计算模型，它模拟达尔文的遗传选择和自然生物降解过程，如何通过模拟自然进化过程找到最佳解决方案，最初由美国密歇根大学J.Holland教授提出，并出版了一本有影响力的专著。遗传算法从表示潜在解决方案的种群开始，而总体由由该基因编码的一定数量的个体组成。每个人实际上是一个特征的染色体实体，染色体是遗传学的主要载体，即一组许多内部综合征基因（如基因型），一种基因的混合物，它决定了个体形状的外在症状，如黑头发的出现，是由染色体控制的某些基因特征决定的。这一进程将导致人口与自然进化一样，将比其前代更有利于后世的环境，最终一代人口中最好的人将被破译为解决这一问题的最佳办法。

（2） 遗传算法的特征

遗传算法是一种功能强大的搜索算法，可用于复杂的优化系统。

1. 遗传算法使用决策变量的编码作为操作对象。传统的优化算法通常定义变量和遗传算法的实际生长，操纵决策变量的编码形式，这使我们能够从生物学中的染色体和基因概念中学习，以模拟自然生物的遗传过程和进化，并使我们更容易使用遗传创业。

2.遗传算法直接适应搜索信息，无需导体等辅助信息。

二、关于TSP问题的简介

TSP问题（旅行推销员问题），也称为运输问题，旅行问题是一个组合优化问题，出现在许多应用中。这个问题可以解释为城市与城市之间的距离，每个城市只行驶一次，然后返回出发城市，以及如何安排最短的路线。这是一个普遍组合的优化问题，需要最短的路线，行程可以从城市通过整个城市，与可能的路线数量成倍增加的城市数量。在图形理论方面，假设有一个G（V，E）图，其中V是高潮集，作为边缘集和设置D作为距离矩阵，由高潮 i 和高潮 j 和 tsp 之间的距离组成，是找到汉密尔顿环通过顶点和顶点，每个通过最短的路线。它们通常称为 TSP，它们以对称方式指 TSP。如果 n 城市 V 的访问序列为 t1、t2,...,,...,tn、其中 ti∈V （i，1，2,...,n） 和 t n-1 为 t1,...,tn，则数学格式可以描述为公式 （1.1）。

(1.2)

三、本论文的研究内容

此设计的研究包括：

（1）解TSP遗传算法的主要应用由C编写，系统采用两个点跨法和两个随机点法形成排序;

（2） 注销与c+的接口，以编程遗传算法编写，以解决给定的数据问题;

（一） 遗传算法的设计概念

为了解决TSP问题的想法，遗传算法，即找到多个城市路径的最短，我们模拟程序的生物进化，即，在基因上，我们是第一个在某种方式创建一个默认组为每个函数，计算染色体，然后选择一个种族组来改变群体，所以它直到它重复，以满足需要找到最短路径。

这是从遗传算法的特殊性对设计概念的分析：

1.算法设计

目前，一种更为常见的求解 tsp 、二元树描述、启发式搜索方法、近邻方法、如何模拟神经网络、如何预防火灾、遗传算法等。遗传算法是一种通过模拟自然生物的遗传和进化过程而形成的自适应全局概率的算法，具有巨大的全球效率，是解决TSP问题最有效的方法之一。

2.基因编码

一旦对遗传算法进行编码，要修改的解的形式将变成遗传算法面对的基本编码对象，从而促进遗传操作。对于最短路径问题，可能的解决方案通常以节点下标记的数字字符串的形式出现，因此遗传算法中的编码方法通常是符号编码。它可以分为以下类别：近邻编码编码序列（Grefenstette 编码），边缘加密、自然加密等此设计使用自然编码。

（二） 系统实现

系统是使用vc编写的，遗传算法和接口程序是分开编写的，因此修改起来比较方便，程序的结构也看得很清楚，理解也很简单。在这个程序中，有一个工作模块，我们可以读取保存在文件中的城市坐标文件，然后我们可以计算通过运行遗传算法确定的数据，并获得必要的结果。

本文通过调用 OpenDataFile（） 函数来读取城市坐标。如果需要将城市坐标文件的格式格式化为：

Y 轴坐标，城市名称

将城市坐标文件的内容读取为称为 vecCity 的结构，主代码如图 2.1 所示。

图2.1读取城市坐标代码