遗传算法解决TSP问题

这是我们大三的专业课人工智能,最优化以及算法设计与分析的实现代码和论文

算法设计技巧与分析

题 目 遗传算法解决TSP问题

学 院电子工程学院

专 业智能科学与技术

学生姓名

教师姓名

这是我们大三的专业课人工智能,最优化以及算法设计与分析的实现代码和论文

摘要

根据TSP 问题的特征信息并借鉴邻域搜索算法的有关思想，提出了一种基于近邻策略的TSP 问题求解算法，该算法首先依据TSP 问题的特殊性求出相应的近邻模式，再将近邻模式用于初始种群的生成，而后在进化过程中随机引入这类模式。该算法可以大大缩短遗传进程，提高进化效率。通过仿真实验，验证了该算法的有效性，并且随着城市数目的增加其优越性更为明显。

关键字：近邻策略；遗传算法；旅行商问题

1.引言

遗传算法（Genetic Algorithm，GA）是一种借鉴生物界中自然选择和进化机制发展起来的随机、自适应全局搜索算法，由Holland 教授于1975 年提出。Goldberg 总结了一种统一的最基本的遗传算法的形式SGA（Simple Genetic Algorithms）。SGA在选定了染色体编码方案后，随机生成初始群体，再通过选择、交叉、变异三种遗传算子的作用对种群不断实行优化，直至找到问题的最优解或近似最优解。遗传算法具有很强的全局搜索能力，但是对于大型旅行商问题（TSP），它存在收敛速度过慢的缺点。

TSP 是一个著名的NP 难的组合优化问题，对称TSP 问题可描述为：给定n 个城市和每两个城市之间的距离，求一条经过所有城市一次且仅一次的长度最短的回路。TSP 问题的数学表述：寻找一条遍历n 个城市的最短路径，或者说搜索到自然数集X={1，2，3，…，n}（X 中元素表示对n 个城市的编号）的一个全排列

1π（X）={v1，v2，…，vn}，使Td= ni=1（vi，vi+1）+d（v1，vn）取最小

这是我们大三的专业课人工智能,最优化以及算法设计与分析的实现代码和论文

值，式中的d（vi，vi+1）表示城市vi到城市vi+1的距离。对于n 个城市的TSP，其所有的旅程路线组合数目是（n-1）! /2。当城市数目n 增加时，可能的路径数将呈指数级增长。这大大降低了遗传算法的求解速度、求解精度。一些研究结果表明，根据TSP 问题的特点，通过把遗传算法与局部启发式算法结合起来能有效提高求解大型TSP 问题的效率。该文借助

这一思想，提出了一种近邻策略，取得了较好的结果，验证了算法的有效性。

2.近邻策略

从实际经验出发，在某一时刻，当某人从一城市前往下一城市时，通常选择距离该城市最近的一个城市作为目标城市，若此城市已遍历，则选择除此城市外距离所处城市最近的另一城市作为目标城市，这就是近邻策略的思想。按照该思想，可得一遍历序列，虽不能保证所得到的路径为最短路径，但常常含有和最短路径相匹配的某些路段，这些路段能够为求得最短路径提供信息。通过对TSP问题大量最优解的分析表明，最优解在很大程度上包含这样的片断或相似片断。为叙述方便，把这样的近邻片段称之为近邻模式，并把这样的近邻模式与最优解相应片断的相似程度称之为匹配度，即：

匹配度=近邻模式与最优解相应片断相同的路径数该片断总路径数

2.1近邻模式

首先给出构造近邻模式的具体方法和步骤：

（1）确定阈值δ

通常选取两两城市距离的平均值作为阈值，若城市间距离悬殊太大，则排除距离悬殊太大的城市，对余下的城市，求两两城市距离的平均值作为阈值。

（2）构造近邻模式

从某一城市出发，寻找距离该城市最近的城市作为目标城市，若寻找到的这个城市已被遍历，则寻找除这个城市之外，距离所处城市最近的另一城市作为目标城市，当所处城市与目标城市间距离小于δ时，把该目标城市列入所要到达的下一城市，以此类推，继续寻找，当所处城市与目标城市间距离大于δ时，则中断这一次的搜索，得到一个近邻模式。再将下一城市作为起点开始新一回的搜索。当

这是我们大三的专业课人工智能,最优化以及算法设计与分析的实现代码和论文

所有的城市搜索完毕时，得到了一系列的近邻模式，其数目为所有城市数目n。

2.2 复杂度分析

通过以上给出的方法和步骤来生成近邻模式，其时间复杂度仅为O（n2），因此在算法运行过程中是切实可行的。并且在n较大的情况下，构造近邻模式的时间开销要远小于后续遗传进程的时间开销。

3 基于近邻策略的TSP 问题求解

该文提出的这种策略首先将近邻模式用于初始种群的生成，然后在进化过程中随机引入这类模式。该策略可以有效地缩短进化过程，提高求解效率。 3.1 利用近邻模式生成初始种群

利用近邻模式生成初始种群的方法：

首先用2.1 节中所述的近邻模式的生成方法来生成n 个近邻模式，保持n 个近邻模式的确定位不变，对非确定位，采用随机生成的方法，即可得到n 个初始个体。为避免遗传算法陷入早熟收敛，用随机生成的方法再生成另外的N-n 个初始个 体（其中N 为设定的初始种群规模），让这N 个个体共同作为初始种群。

3.2 基于近邻策略的遗传算法及TSP 求解步骤

下面给出了基于近邻策略遗传算法求解TSP 问题的具体步骤，如下：

（1）种群初始化：用3.1 节方法生成初始种群。

（2）遗传策略：①选择，采用轮盘赌及最优解保留策略，并在每一代随机选择一个近邻模式生成一个个体替换当前种群中的最差个体。②交叉，用较为常用的顺序交叉算子，该算子能较为完整地保留部分结点的相对访问顺序。③变异，采用双点逆转变异算子。

（3）对算法终止条件进行判断：如果条件不满足，则转（2），否则，结束。 由于近邻模式与最优解相应的路径片断具有极高的匹配度，它能够在整个算法的搜索过程中具有良好的导向作用，避免了随机搜索的盲目性，大大提高了算法的速率及效率。

4 仿真实验及分析

为验证该算法的有效性，对算法进行实验。算法的求解效率主要涉及三个方面：

（1）所求近似解精度。（2）算法的时间效率。（3）算法对问题规模的适应度。

这是我们大三的专业课人工智能,最优化以及算法设计与分析的实现代码和论文

TSPLIB 是一个研究TSP 问题的常用数据集，选取TSPLIB中16 个城市的数据集ulysess16，22 个城市的数据集ulysess22分别进行测试，已知最好解分别为6 859 km、7 013 km，用VC6.0 对算法进行实现，将文中的基于近邻策略的遗传算法（NSGA）与SGA 进行对比，为公平比较，初始种群均为N，交叉概率为0.6，变异概率为0.1。

由表1 可以看出，SGA 在第230 代才得到近似最优解，而NSGA 在第127 代就得到了全局最优解，无论在求解精度还是在求解速度上都明显优于SGA。 对该实验进行分析：

在ulysess16 中，最优解路径为：

0-13-12-11-6-5-14-4-10-8-9-15-2-1-3-7-0

取阈值δ=800，得到的近邻模式分别为：

0-7-15-12-11-13-6-5-14-4；

1-2-0-7-15-12-11-13-6-5-14-4；

2-1-3-7-15-0-12-11-13-6-5-14-4；

3-7-0-15-12-11-13-6-5-14-4；

4-14-13-12-11-6-5；

5-6-11-12-13-14-4；

6-5-13-12-11-14；

7-0-15-12-11-13-6-5-9-8-14-4；

8-9-6-5-13-12-11-14-4；

9-6-5-13-12-11-14-4；

11-12- …… 此处隐藏：3792字，全部文档内容请下载后查看。喜欢就下载吧 ……