大黄蜂算法

俞健明

摘要：本文介绍了一种新颖的关于TSP问题的算法，它通过计算每条边属于最短哈密顿回路的概率来找到最佳路径，是目前关于TSP问题的最新解决方案

关键词：NP 问题；旅行商问题 ；数理统计；大黄蜂

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）30-0258-02

TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

2010年英国科学家的一项研究发现，大黄蜂显示出能轻易破解“旅行商问题”的能力。进行研究的奈杰尔·雷恩博士说，蜜蜂每天都要在蜂巢和花朵间飞来飞去，为了采蜜而在不同的花朵间飞行是一件很耗精力的事情，因此蜜蜂每天都在解决“旅行商”问题。

本文介绍了一种新的旅行商问题的算法，实验表明，该算法能较好的解释大黄蜂是如何解决旅行商问题，本文同时还探讨了该算法在解决旅行商问题中的一些问题和思路。

因为大黄蜂在觅食的过程中采用了和本算法类似的策略，所以把这算法称为大黄蜂算法。

1 问题的提出

我们知道，在一个有n个结点的图中，较短的边不一定会属于该图的最短哈密顿回路，有些较长的边反而属于最短哈密顿回路。

那么，我们自然会问：每个边属于最短哈密顿回路的可能性是多少呢？

我们能否量化它吗？

对一个n个结点的图中，当我们找出该图的最短哈密顿回路时，我们知道这n个边的概率是1，其他边的概率是0.

但这对问题的解决没有任何帮助，当n变大时，问题仍然很困难。

我们的基本思路是：对一个大的图按照一定的方法划分成很多个子图，对每个子图我们进行计算，然后汇总并计算出每条边在该划分下属于最短哈密顿回路的概率。

2 算法介紹

为了方便理解同时不失一般性，我们假定讨论的图只存在一个最短哈密顿回路。

同时，本算法同样适用一般的拓扑图。

2.1 K_划分（K>=4）

对一个有n个结点的图，我们可以对它划分为由K个点的所组成的子图。这样，该图共有[nk]个这样的子图。

例如 对图1（n=5）。可以生成C（5，4）个 4_划分图（见图2）

2.2 K_路径（K>=4）

是指在一个K_划分图中，过每个顶点一次的一条路径。例如图3是图1的一个4_划分图，BECD就是一条从B到D，经过E、C的4_路径。

2.3 K_有效路径（K>=4）

K_有效路径是指一条可能属于最短哈密顿回路中的一个连续段的K_路径。

一般来说，从A到B的K_路径里最短的一条是K_有效路径。

在不同的假设下，会有不同的K_有效路径。

对每一个K_划分图，我们可以找出它的所有K_有效路径。例如，对（图1）的一个4_划分图（图3）。

它的有效路径有：

B到C：只有一条唯一路径 BEDC 所以BEDC是一条4_有效路径。

B到D ：这里存在两条4_路径 BCED和BECD，因为L（BCED）=17，L（BECD）=16，所以BECD是4_有效路径。

B到E：只有一条有效路径 BCDE。

C到D：只有一条有效路径 CBED。

C到E：无有效路径

D到E：只有一条有效路径 DCBE。

2.4 K_统计

对图中每条边添加成功和失败两个属性。假设a1a2…an 是一条K_有效路径。对aiai+1（ i=1，2…n-1）边在成功属性上加1，其他边在失败属性上加1，边a1an不做处理。

我们有S（X）代表边X成功的次数，用F（X）代表边X失败的次数。

K_统计是指对每一个K_划分图，计算出每条边的成功和失败的次数。然后对每条边统计出它的成功和失败的总次数。

以（图3）为例，总共有5条4_有效路径： BEDC、BECD、BCDE、CBED和DCBE。

对每条可能路径作以下分析：以 BEDC为例，总共有 BE、DE、CD、CE参与竞争（B和C是端点，所以BC不参与竞争），结果BE、DE和CD胜出。胜出的成功上加1，没选上的失败上加1。

2.5 K_链接度（K>=4）

对每条边X我们定义以下公式， LK（X）=[S（X）SX+FX] （K>=4） ，（称LK（X）为边X的K_链接度。

对于图1，根据汇总表（图4），我们可以计算出每条边的链接度L4（X）。

LK（X）代表了X边在k_划分下的属于最短哈密顿回路的概率。

对于LK（X）有一个重要的定理。

定理：在一个有n个结点的图中（假设存在最短哈密顿回路），如果LK（X）=1，则边X一定属于该图的最短哈密顿回路（证明较简单，在这里就不作具体详述了）。

根据汇总表，我们可以简单的算出最短哈密顿回路是ABCDA。

2.6 条件K_链接度（K>=4）

当我们假定某条边或几条边属于最短哈密顿回路时，其他边的K_链接度就会发生变化，我们把在某种条件下的K_链接度称为条件链接度，用 CLK（X）来表示变X的条件K_链接度。

CLK（X）有类似于LK（X）的定理。

2.7解集M

是指包含能构成一条最短哈密顿回路的边的集合。当把一条边要加入到解集M的时候，要检查它和解集M里的边是否会发生冲突。只有相容的边才能加入解集M。

对有n个结点的图来说，解集M最多只能包含N条边。

3 算法描述

一个广义的TSP问题是一个有n个结点的拓扑图，为了算法描述方便，我们假设该图只存在一条最短哈密顿回路。

算法描述如下：

确定K值（K>=4）；

K_统计；

计算图中每条边的K_链接度；

REPEAT

{

找到一条具有最大（条件）K_链接度的边X && X与解集M相容；

将X加入解集M；

K_统计；

计算每条边的条件K_链接度。

}

UNTIL 解集M包含了N条边。

该算法可以实现用一个较小的K来解决一个较大n的TSP 问题，它的复杂度是： O（nK+3）。

4 对大黄蜂算法的一些思考和今后的方向

对于大黄蜂算法，我们还有很多工作要做，重点有以下几个方面：

1）k和之间的关系，一个很大的n，如何选取一个合适的k来进行计算。我们还需要更多的实验来确定。

2）对CLK（X）的一些思考，我们现在是认为CLK（X） 最大，该边属于最短哈密顿回路的可能性就最大。我们是否能对k进行插值，CLK（X） 的单调上升的边也许是属于最短哈密顿回路的可能性最大。不过现在还是一个猜想，需要更多实验和严格的数学证明

3）对大n的算法验证。

参考文献：

[1]Travel Optimization by Foraging Bumblebees through Readjustments of Traplines after Discovey of New Feeding Locations The American Naturalist December 2010，176（6）.

[2] How to Solve It：Modern Heuristics Zhigniew Michalewicz David B.Fogel