运筹学基础 课件 第9章

第9章旅行商问题9.1TSP的构造启发式算法9.2线性规划模型9.3TSP路径构造的贪婪启发式算法9.4TSP的改进启发式算法9.5TSP的遗传算法

9.1TSP的构造启发式算法

旅行商问题(TravelingSalesmanProblem,TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。TSP是运筹学中目前研究最为广泛的问题之一,但对于一般情况,还没有有效的解决方法。虽然TSP的复杂性未知,但60多年来,其求解方法在不断改进。表9-1显示了TSP问题的求解记录。

9.2线性规划模型

此模型的决策变量有n(n-1)个,式(9-2)和式(9-3)均有n个,连通性约束有2n-2n-2个,因此共有2n-2个约束条件,即使对于n=318这样小规模的TSP问题,也有5.34e+95个约束条件,比宇宙中的原子数量还要多!

一般来讲,通过算法构建一条可行的旅行商路径并不困难,虽然一般情况下证明是最优的很困难。在这种情况下,我们不知道找到的路径是否是最优解,但是知道这个解还不错,因此可以称之为优化解,它可能是最优的,也可能不是,并且很多情况下,可以通过解的下界大概估计优化解的优化程度。

9.3TSP路径构造的贪婪启发式算法

9.3.1最近邻算法所谓最近邻算法,就是从一个点开始逐步增加距离当前点最近的点构造出一个TSP路径。

例9-1在Matlab上实现最近邻函数,并随机生成城市节点进行验证。

使用Matlab编写最近邻函数的代码如下:

在平面上随机生成30个点,使用最近邻方法构造TSP路径的代码如下:

进行4次实验,算法构造生成的TSP路径如图9-1所示。图9-1最近邻算法生成的几个TSP路径

9.3.2插入算法

插入算法是从一个较小的圈开始,逐步将不在圈上的点插入圈上,直到扩充为一条TSP路径为止。

例9-2在Matlab上实现插入函数,并随机生成城市节点进行验证。

在平面上随机生成30个点,使用插入算法构造TSP路径的代码如下:

进行4次实验,算法构造生成的TSP路径如图9-2所示。由图可见,生成的不是最优解,而是优化解。图9-2插入算法生成的几个TSP路径

9.3.3Merger算法

9.4TSP的改进启发式算法

9.4.12opt操作

例9-3在如图9-3所示的TSP路径上,查看有没有两条边能满足交叉消除操作的条件。图9-3TSP路径的交叉消除操作

如图9-3所示,当前TSP路径上有(1,2)和(3,4)两条边在平面上是有交叉的,于是根据三角不等式可得

因此,在TSP路径上去掉(1,2)和(3,4)两条边,并增加(1,3)和(2,4)两条边,TSP路径的总长度缩短,解得到改进。

例9-4在Matlab上实现2opt函数,并随机生成城市节点进行验证。

进行实验,结果如图9-4所示,可以发现在平面上已经没有交叉了。图9-42opt操作通过消除平面交叉改进TSP路径

9.4.2k－opt操作

所谓k－opt操作,就是在TSP路径上去掉k条边,并使用另外的k条总长度更小的边将其代替并重新连接成一条可行TSP路径的操作。

如果一条TSP路径无法通过kopt操作改进,则称其为k－optimal的。如果一条TSP路径是koptimal的,则对于比k小的自然数k',这条路径一定也是k'optimal的。

如果一条TSP路径是n－optimal的,则这条TSP路径是最优的。

虽然能够验证k－optimal中的k越大,解越接近最优,但是随着k的增大,k－optimal的验证难度呈指数级增加,因此一般情况下只利用k=2,3来改进。

9.5TSP的遗传算法

9.5.1基本原理与步骤TSP路径构造的贪婪启发式算法通过贪婪规则从无到有构造一个优化解,TSP的改进启发式算法对一个已有的解进行改进,而TSP的遗传算法中上述两个算法的工作都要做,因此,也称之为元启发式算法。遗传算法计算的过程框架如图9-5所示。

图9-5遗传算法(元启发式算法)计算的过程框架

遗传算法的基本步骤如下:

步骤1:将问题的解编码为染色体,并生成初始染色体群,每个染色体代表一个解。

步骤2:进行交叉、变异、选择等操作,计算每个染色体的适应度函数值,更新染色体群。

步骤3:直到满足算法停止条件的时候,停止计算,最优的染色体代表的解即为所得的优化解,否则转步骤2。

9.5.2算法设计要点

1.解的编码

在旅行商问题中,对问题解的编码应该采用城市编号序列的方法,这样更加有利于交叉、变异等操作生成可行解,否则一个交叉之后,生成可行解的概率很低。

2.生成初始种群

所谓生成初始种群,就是生成一定数量的可行解,一般随机生成,而不太采用构造启发式算法。作为全局性算法,随机生成初始种群的方式有可能会避免过早陷入局部最优解。

3.交叉操作

一般的交叉操作是选择两个染色体作为父母,从随机的位置截断后,重新组合到一起。但是对于旅行商问题的两个染色体来讲,如果采用一般的交叉操作,多数情况下会得到一

个不可行的解,例如:

作为父母染色体,从第一个基因与第