| 标题 | 大黄蜂算法 |
| 范文 | 俞健明 摘要：本文介绍了一种新颖的关于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 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。