2016年第7期
0037-072475（2016）07-文章编号：1006-
计算机与现代化
JISUANJI YU XIANDAIHUA
总第251期
求解旅行商问题的离散花授粉算法
李
111，2
贺兴时，杨新社前，
（1．西安工程大学理学院，陕西西安710048；2．密德萨斯大学科学与技术学院，英国伦敦NW44BT ）
摘要：针对原始花授粉算法（FPA ）无法用于求解组合优化问题，提出一种离散的花授粉算法，并将其应用于求解旅行商问题（TSP ）。通过重新定义花朵、全局搜索与局部搜索等概念；并对莱维飞行用一种新的方法进行分段，有效避免算法过早陷入局部最优，增强算法的全局搜索能力。最后通过对10个国际通用的TSP 数据（TSPLIB ）进行测试，并将实验结果与离散粒子群算法（DPSO ）、混合离散粒子群算法（HDPSO ）、离散布谷鸟搜索（DCS ）算法、带有遗传模拟退火的蚁群粒子ACS-PSOT ）算法的实验结果进行对比。实验数据显示，群（GSA-该算法在求解旅行商问题中，能较快、较准确地找到最优解，在相同实验条件下，比其他算法求解偏差百分比明显降低。研究结果表明，本文提出的算法具有较好的求解性能。关键词：花授粉算法；离散花授粉算法；旅行商问题；莱维飞行；TSPLIB ；偏差百分比中图分类号：TP18
文献标识码：A
doi ：10．3969/j．issn．1006-2475．2016．07．008
A Discrete Flower Pollination Algorithm for Travelling Salesman Problem
2
LI Qian 1，HE Xing-shi 1，YANG Xin-she 1，
（1．School of Science ，Xi ’an Polytechnic University ，Xi ’an 710048，China ；2．School of Science and Technology ，Middlesex University ，NW44BT London ，UK ）
Abstract ：In view of the standard Flower Pollination Algorithm （FPA ）can not be used to solve combinatorial optimization prob-lem ，a Discrete Flower Pollination Algorithm （DFPA ）was proposed and then applied to Traveling Salesman Problem （TSP ）．By
redefining the concept of flowers ，global search and local search ，etc．，and Levy flight will be segmented by a new method ，ef-fectively avoiding premature falling into local optimum and enhancing the global search ability of the algorithm．Finally the per-formance of the proposed is tested against by some typical instances in the internationally commonly used library of TSP （TSPLIB ）and compared with Discrete Particle Swarm Optimization （DPSO ），Hybrid Discrete Particle Swarm Optimization （HDPSO ），Dis-crete Cuckoo Search （DCS ），Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimisation Technique （GSA-ACS-PSOT ）．The results of the tests show that DFPA can quickly ，accurately find the optimal solution．Under the same experi-mental conditions ，the algorithm reduces the error rate than any other algorithm．The results show that the proposed algorithm has better solving performance．
Key words ：Flower Pollination Algorithm （FPA ）；Discrete Flower Pollination Algorithm （DFPA ）；Travelling Salesman Problem （TSP ）；Levy flight ；TSPLIB ；percentage deviation
1概述
［3］
呈指数增长，搜索所有组合会使计算量迅速膨胀。
许多研究一直致力于解决TSP ，如禁忌搜索［5-6］
、（TS ）［4］、遗传算法（GA ）贪婪随机自适应搜索过［7］［8］
程（GＲASP）、模拟退火（SA ）。在过去的十几年中，基于元启发式算法或群智能的方法，比如蚁群优［9-10］［11-12］
、、化（ACO ）粒子群优化（PSO ）萤火虫算法［14］
，（FA ）［13］、布谷鸟搜索（CS ）已经被提出用于解决
［1］
旅行商问题（TSP ）是由爱尔兰数学家W．Ｒ．Hamilton 和英国数学家托马斯·柯克曼在19世纪提
hard ［2］问题。这个问题的出的，被认为是著名的NP-目的是在给定的城市列表中找到一种恰好访问每个
城市一次，然后回到出发城市的最短的巡回路线。表面上简单却十分难以解决的，因为组合数的增加会使问题
TSP 。因此，解决这一类问题具有重要的实际意义，
12-29收稿日期：2015-JM1006）基金项目：陕西省自然科学基础研究计划项目（2014，
），西安工程大学理学院硕士研究生，研究方向：智能计算与大数据理论。女，陕西商洛人，作者简介：李前（1992-
38计算机与现代化2016年第7期
因此它一直是被积极研究的一个重要课题。
旅行商问题因其简单易懂，操作过程与此同时，
复杂并具代表性，成为检验一个算法解决组合优化问题性能的重要途径。
花授粉算法是一种新型具有全局收敛的元启发
she ［15］在2012年式群智能优化算法，是由Yang Xin-通过模拟自然界中显花植物花朵授粉过程提出的。
同其他的智能优化算法相比，花授粉算法具有需要调整的参数较少、操作简单、易实现等优点。而且花授粉算法利用转换概率参数p 实现了动态控制全局搜索和局部搜索，较好地解决了全局搜索和局部搜索的平衡问题，同时采用了Levy 飞行机制，使得其具有良好的全局寻优能力。正是由于这些优点，花授粉算法引起了学术界的极大兴趣，成为启发式智能算法领域的一个新亮点。
Kirils Bibiks 等提出离散花授粉算法，解决资源受限项目调度问题（ＲCPSP）。Meriem Bensouyad 等介绍一种离散形式的花授粉算法来处理图形着色问题。这2种离散花授粉算法由于离散化方法的缘故，并不能解决旅行商问题，为了解决更多的组合优化问题，还需研究兼容性更好的离散化方法。
本文将介绍一种离散的花授粉算法，能有效解决对称的TSP 问题。通过对旅行商问题的求解也验证了这种离散花授粉算法的性能。
短之旅，赢得精力和时间的问题。J．K．Lenstra 和G．Ｒeinelt提出TSP 和它的变体的几个重要应用［16-17］，
x 射线晶体学、如印刷电路板的钻床、计算机线路、车
TSP 有很辆调度和调度、机器人控制等。现实表明，
大的重要性，无论是在学术界还是现实生活中。
3花授粉算法
2012年，Yang Xin-she ［15］通过模拟自然界中显花植物花朵授粉的过程提出花授粉算法（Flower Polli-nation Algorithm ，FPA ）。花授粉算法是一种新型元启发式群智能优化算法。
自然界中的花授粉过程是非常复杂的。因此，很难通过真实地模拟花授粉过程的每个细节来设计算法，即便是逼真地模拟出花授粉的过程也会导致算法特别复杂，计算量过大，降低算法的计算效率。这样的算法并不具有太大实际应用价值。因此，为了使算
FPA 对自然界中的花粉授粉过程进行了法简单易行，
简化，并根据其特点，建立了FPA 的以下规则：
规则1生物交叉授粉可以被视为是全局搜索过程，授粉生物的运动服从Levy 飞行，即跳或飞行距
［19］
离服从一个列维分布；
规则2非生物和自花授粉被视为局部搜索过程；
规则3花的常性可以被认为是繁衍概率，繁衍概率与授粉过程中参与的2朵花的相似性成比例关系；
0，1］规则4转换概率p ∈［控制全局搜索和局
部搜索之间的转换，这是由于物理上的邻近性、风等其他因素的影响。即在FPA 中，假设每朵花为求解优化问题的一个解，并且每朵花都是通过概率p 选择交叉授粉操作，或以概率1－p 选择自花授粉操作繁
p 是局部授粉的一个衍出后代。在整个授粉活动中，
非常重要的部分。
为了使以上规则公式化，需将上述更新规则转化为正确的更新方程。例如在全局搜索过程中，授粉昆虫携带着花粉配子，飞行较远距离。规则1和规则3可以表示为：
x t i +1=x t i +γL （λ）（g *－x t i ）
2旅行商问题的描述
Daven-旅行商问题可以看作是一个置换问题，dra ［18］对TSP 的规范描述如下：
c 2，．．．，c n ｝是不同的城市集，E =｛（c i ，C =｛c 1，
c j ）：i ，d c i c j 是边（c i ，j ∈｛1，．．．，n ｝｝是边集，c j ）∈E 的成c i 和c j 的距c iy ），本计量，城市c i ∈C 的坐标表示为（c ix ，离为欧几里德距离d c i c j =
π次旅行可以表示为一个循环的排列π=（π（1），（2），．．．，π（N ）），其中π（i ）表示1到N 这n 个城市
i 表示访问城市的顺序，i =1，2，．．．，N ，中的一个，旅
行的最小路程为：
f （π）=∑d π（i ）π（i +1）+d π（N ）π（1）
i =1N －1
（c ix －c jx ）+（c iy －c jy ），一
如果d c i c j =d c j c i ，则称其为欧式对称TSP ；如果至
c j ），少有一个（c i ，那么TSP 变为不对称使d c i c j ≠d c j c i ，TSP 指的是对称TSP 。欧式TSP 。在本文中，
这些年来，旅行商问题（TSP ）吸引了众多数学家的关注，他们都致力于设计一个算法，使其在合理的时间内找到对于大多数问题来说最佳的解决方案。它的特征在于它看起来十分简单，不需要数学背景的论述来了解它。它可以被看作是一个旅行商寻求最
x i 是花粉i 的第t 次迭代，g *是目前在所有的其中，
解决方案中发现的迭代最好的；γ是一个比例因子以
［20］
控制步长；L （λ）为参数，是以Levy 飞行为主步长，其与授粉强度有关。L ＞0，服从Levy 分布：
L
λΓ（λ）sin （πλ/2）1
，s s 0＞0
πs λ
t
规则2和规则3可被表示为：对于局部授粉，
x t i +1=x t i +ε（x t j －x t k ）
2016年第7期
t
t
李前等：求解旅行商问题的离散花授粉算法
t
39
其中x j 和x k 是来自相同物种不同花的花粉。如果x j
t
和x k 是来自相同的物种或在相同的群体中选择，ε
0，1］是在［间的均匀分布，那么这就等效地变成了局部随机移动。
是1号城市，第2个访问城市是3号城市，第3个访问城市是4号城市，以此类推，第10个访问城市是10号城市
。
花授粉算法的伪代码
x =（x 1，x 2，．．．，x d ）目标函数f （x ），初始化有n 朵花的种群
在这些初始种群中找出最优解g*0，1］定义转化概率p ∈［
定义最大迭代次数；
While （迭代次数＜最大迭代次数）For i =1：n
If 随机数p
绘制一个d 维步长矩阵L ，使L 服从Levy 分布全局搜索x i
t +1
图1一个解的表示
=x t i +γL （λ）（g *－x t i ）
Else 随机从种群中选择2朵花
1）取ε U （0，
进行局部搜索x i
End If
计算新解的适应度函数，并与当前最优解作比较如果新解更好，则在种群中更新它们End For
找到当前最优解g*
End While
输出当前找到的最优解
t +1
=x t i +ε（x t j －x t k ）
2）搜索空间。在二维情况下，搜索空间表示花的潜在位置。要改变一个花的位置，只需要修改其坐标的实际值。显然移动花和花的位置并没有实际的约束，而在旅行商问题中，在搜索空间中的运动，通过Levy 飞行生成的值，按照规定的方式对排列顺序进行改变，从已有的解决方案中得到新的方案。
3）全局授粉。
由于城市的坐标固定，该动作是基于旅行城市的顺序，改变旅行城市的顺序从已有的解决方案中得到新的方案，即通过改变排列的顺序来改变旅行顺序。笔者采用的方法是，在排列中每次随机选取2个位置（不相临的2个位置），这样会有4条路径交换二者，发生变化。以例中10个城市为例，交换其中第3个旅行城市（即4号城市）与第6个旅行城市（即2号
如图如图2所示。这样有4条路径发生变化，城市），
3所示
。
花授粉活动可以以任意尺度在局部和全理论上，
局中发生。但现实中，毗连的花和那些离得不遥远的花比那些距离遥远的花更容易接受局部花粉的授粉。为了模仿这个特征，转换概率（规则4）p 可有效地动
she 在参数态控制全局搜索和局部搜索。Yang Xin-研究中表明，在大多数应用中p =0．8可能更加有效。
图2
变序策略
4离散花粉算法
由于原来的FPA 被设计用于连续优化问题。笔
者通过重新定义算法中花朵、搜索空间、全局授粉、局部授粉和莱维飞行等概念，将其离散化。
1）花朵。在离散花授粉算法（DFPA ）中，一朵花代表群体中的一个体，用一种排列形式表示，其中每个元素代表预定活动，元素的索引是其中该活动将被执行的顺序。每朵花被认为是一个解决方案。例如，在旅行商问题中，每朵花表示一种旅行方案，排列中的节点表示城市编号，排列顺序即为旅行顺序。如图1所示，假设有10个城市，那么该方案表示：第1个访问城市
图3路线改变示意图1
4）局部授粉。
原始花授粉算法中的局部授粉是随机取出种群中2朵花，根据2朵花的差异程度决定花的下一代。而在旅行商问题中，其解都为遍历城市的顺序排列，要进行局部搜索，可以通过反序的策略。在连续问题中，相邻单位的意义是显而易见的。然而，对于离散性问题，就必须小量地改变相邻单位，从而得到新的
结果。这种对结论的改动必须很小。在进行局部搜索时，搜索步长应较全局搜索小。所以，本文按以下
对调其中2个连方式进行（同样取10个城市为例），
续城市的旅行顺序，如图4所示，将城市7和城市8反序。这样改变2条路径（从A 地到B 地的路程与从B 地到A 地的路程相同，所以视为同样的路径），如图5所示
。
Levy 在（0．1，0．3］→经过2次变序；Levy 在（0．3，0．6］→经过3次变序；Levy 大于0．6→经过4次变序
。
图4
反序策略
图6Levy 飞行波动图
5实验结果与分析
为了进一步验证本文所提算法的求解性能，选用
［21］
多个TSPLIB 标准库实例进行实验测试。实验环
图5
路线改变示意图2
5）Levy 飞行。
为了提高解的质量，原始FPA 所述Levy 飞行用于计算步长。
－
Levy （s ，λ） s λ，1＜λ＜3
TM
境为一台CPU 为Intel （Ｒ）Core i52．00GHz 和内存为6GB 的64位笔记本电脑，在MATLAB Ｒ2014a中编程实现。
在进行了初步实验后，本文所选择的设置参数如表1所示。
Levy 飞行具有围绕一个解决方案密集搜索的特性，但从长远来看，偶尔会有突跳现象。根据Yang Xin-she 和S．Deb ［20］的研究，在一些关于优化的问题Levy 飞行可以更有效地得到最佳方案。为了提中，
Levy 飞行所采用的步长必须与高搜索结果的质量，
标准花授粉算法中所列出的标准相关联。
在Levy 飞行移动时，经过多次绘制其波动图像，如图6所示，不难发现，其小幅跳跃的步长比较密集，随着跳跃幅度加大，其出现的频率在减少。即大多在0附近波动，越偏离0，出现的次数越少。Aziz
0，1］，Ouaarab ［14］提出的方法是将Levy 飞行控制在［
0，1］根据移动步长中的最大值n ，将［等分为n 个小
区间，根据Levy 飞行的值落在的区间段分别定义其移动步长。但这样显然在解空间搜索过程中出现突跳的可能性极小，所以容易陷入局部最优。本文采用梯度区间来限制Levy 飞行，使步长变化更加合理，保持种群多样性，避免陷入局部最优，更快找到最优解。因此，根据Levy 旅行的规则可以按如下方式确定适当的步长：
Levy 在［0，0．1］→经过1次变序；
表1
参数n p N_iter
值200．82000
参数设置
意义种群大小转换概率参数p 最大迭代次数
Bayg29、Att48、Eil51、仿真实验，采用Ulysses16、
berlin52、St70、pr76、kroA100、ch130、ch150这10个实例。每种算法独立运行40次，计算结果如表2所示。
n 表示城市的数量，Opt 其中第1列表示实例的名称，
列给出了问题的已知最优值（TSPLIB 中最优解的长
Best 列给出了本算法求解得到最优解的长度，度），
worst 列给出了本算法求得的最差解，Average 列为在40次独立运行后得出解的平均长度，PDav 列表示30
［22］
次运行中长度偏差的百分比。偏差定义如下：
PDav =
Average length －Optimal solution length
ˑ 100
Opt
通过对这10个实例的实验，结果表明本算法在维数不高的情况下，都能找到最优解，而且在多次运行过程中出现误差的情况也都不超过1%，说明本算法具有较好的稳定性。同时本算法也求得这10个实
例的最优旅行路线图，如图7 图14所示。
表2
Problem Ulysses16
Bayg29Att48Eil51berlin52St70pr76kroA100ch130ch150
n [***********]30150
FPA 标准测试问题的实验结果
Opt
[***********][***********]106528
Best [***********][***********]106528
DFPA
Worst Average 68596859
[***********]．[**************]1．80701676．[***********]21316．4761936141．0166356582．33
PDav
/%
000．0900．130．210．280．160．510．83
图10eil51旅行路线图
图7Ulysses16旅行路线图
图11Pr76旅行路线图
图8Bayg29旅行路线图
图12kroA 旅行路线图
图9Att48旅行路线图图13Ch130旅行路线图
ACS-PSOT 与表5和表6分别是DCS 和GSA-DFPA 实验结果的对比。可以清楚地看出，DFPA 模
型在解决TSP 的测试中胜过了DCS 。DFPA 在5个测ACS-PSOT 的实验结果。试问题中有4个远远小于GSA-这说明，本文提出的算法具有良好的求解性能。
表5
Problem Eil51berlin52St70
Opt 4267542675
DCS 与DFPA 的实验结果比较
DCS
Best 4267542675
Worst PDav /%459725725
3．033．903．242．835．346．5318．06
Best 4267542675
DFPA
Worst PDav /%4267570701
00．130．210．280．160．510．83
图14ch150旅行路线图
pr[***********]78
[1**********]13
[1**********]64
[***********]1106528
[1**********]35
kroA10021282Ch130Ch150
61106528
笔者选择近几年在求解旅行商问题中表现良好
的几种算法与DFPA 进行比较。DFPA 的实验结果与DPSO （Discrete Particle Swarm Optimization ）
［23］
，HDP-［24］
SO （Hybrid Discrete Particle Swarm Optimization ），
表6
Problem Eil51
GSA-ACS-PSOT 与DFPA 的实验结果比较
Opt 426
GSA-ACS-PSOT Best 4277542
Average 427．277542．00
SD 0．450．00
Best 4267542
DFPA Average 4267551．80
SD 0．002．07
ACS-PSOT DCS （Discrete Cuckoo Search ）［15］，GSA-（Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimization ）
［25］
算法的实验结果对比，
berlin527542
分别见表3 表6。这4种算法的实验数据细节直接
23-25］。引用于文献［
PDav 表表3是DPSO 与DFPA 的实验比较结果，
示30次运行中每次旅行路径长度偏差的百分比。显pr79，DPSO 并没有找到最优解，然，对测试问题Eil51，
而DFPA 找到了最优值，而且DFPA 在解决4个测试问题中的偏差百分比远远小于DPSO 。
表3
DPSO 与DFPA 的实验结果比较
PDav /%
2．57513．84583．34223．8176
DFPA
Best Worst PDav /%[**************]0．136757010．[**************]．28
kroA[***********]．47123．[1**********]6．4737．79Ch130Ch150
61106528
61416528
6205．436563．70
43．7022．45
61106528
6141．016582．33
16．5221．04
6结束语
TSP 是组合优化问题中较为著名的问题，是涉及
运筹学、图论的NP 难题，在许多行业都有广泛的应用，同时也成为检验一个算法解决组合优化问题性能的重要途径。笔者以求解TSP 问题为例，提出了一种离散花授粉算法的具体实现，拓展了花授粉算法的应用领域。该算法通过重新定义花朵、全局授粉、局部授粉等过程，将梯度分段作用于Levy 飞行，避免算法陷入局部最优。仿真实验结果表明，离散花授粉算法在收敛速度、寻优度和稳定性方面都表现良好。可以通过对该算法做适当变化，将其推广用于解决其他组合优化问题，这也是今后需要努力的方向。
参考文献：［1］Blum C ，ＲoliA．Metaheuristics in combinatorial optimiza-tion ：Overview and conceptual comparison ［J ］．ACM Com-2003，35（3）：268-308．pute Surveys （CSUＲ），［2］Lawler E L ，Lenstra J K ，ＲinnooyKan A H G ，et al．The
Traveling Salesman Problem ：A Guided Tour of Combinato-rial Optimization ［M ］．John Wiley ＆Sons ，Incorporated ，1985．［3］Papadimitriou C H．Euclidean TSP is NP-complete ［J ］．
DPSO
Problem Opt
Best Worst
Eil[1**********]berlin[1**********]362St[1**********]pr[***********]65
SD 表表4是HDPSO 与DFPA 的实验比较结果，
用以衡量每次结果值偏离平均值的程示标准方差，
DFPA 对其他测试函数的标准方差小度。除了St70，
于HDPSO 。可以发现HDPSO 并没有找到这4个测试问题的最优值，只是找到了局部值。
表4
Problem
Opt
HDPSO 与DFPA 的实验比较结果
Best
[**************]9
HDPSO Worst SD 1107011．154420．007044．4723867464．21
Best [**************]2
DFPA Worst SD 1064510．234260．007017．162159837．79
Att4810628Eil51426St70675kroA10021282
Theoretical Computer Science ，1997，4：237-244．［4］Zachariasen M ，Dam M．Tabu Search on the Geometric
Traveling Salesman Problem ［M ］．Meta-Heuristics ，Spring-er ，1996：571-587．［5］Potvin J Y．Genetic algorithms for the traveling salesman
problem ［J ］．Annals of Operations Ｒesearch，1996，63（3）：337-370．
［6］Qu Liangsheng ，Sun Ｒuixiang．A synergetic approach to
genetic algorithms for solving traveling salesman problem ［J ］．Information Sciences ，1999，117（3）：267-283．［7］Marinakis Y ，Migdalas A ，Pardalos P M．Expanding neigh-borhood GＲASPfor the traveling salesman problem ［J ］．
Computational Optimization and Applications ，2005，32（3）：231-257．
［8］Chen Yong ，Zhang Pan．Optimized annealing of traveling
salesman problem from the-nearest-neighbor distribution
［J ］．Physica A ：Statistical Mechanics and its Applica-tions ，2006，371（2）：627-632．［9］Dorigo M ，Gambardella L M．Ant colonies for the travelling
salesman problem ［J ］．Biosystems ，1997，43（2）：73-81．［10］Dorigo M ，Gambardella L M．Ant colony system ：A coop-erative learning approach to the traveling salesman problem
［J ］．IEEE Transactions on Evolutionary Computation ，1997，1（1）：53-66．［11］Li Xiangyong ，Tian Peng ，Hua Jing ，et al．A hybrid dis-crete particle swarm optimization for the traveling salesman
problem ［J ］．Lecture Notes in Computer Science ，2006，4247：181-188．
［12］Goldbarg Elizabeth F G ，Goldbarg Marco C ，Souza Givanal-do Ｒde．Particle swarm optimization algorithm for the trav-eling salesman problem ［M ］//Traveling Salesman Prob-lem．2008：75-96．［13］Jati Gilang Kusuma ，Suyanto．Evolutionary discrete firefly
algorithm for travelling salesman problem ［J ］．Adaptive and Intelligent Systems ，2011，6943：393-403．［14］Ouaarab A ，Ahiod B ，Yang Xin-she．Discrete cuckoo search
algorithm for the travelling salesman problem ［J ］．Neural Computing and Applications ，2014，24（7）：1659-1669．
［15］Yang Xin-she．Flower pollination algorithm for global opti-mization ［C ］//Proceedings of the 11th International Con-ference on Unconventional Computation and Natural Com-putation．2012，7445：240-249．［16］Lenstra J K ，ＲinnooyKan A H G．Some simple applica-tions of the travelling salesman problem ［J ］．Operational
ＲesearchQuarterly ，1975，26（4）：717-733．［17］ＲeineltG．The Traveling Salesman ：Computational Solu-tions for TSP Applications ［M ］．Springer-Verlag ，1994．［18］Davendra D．Traveling Salesman Problem ，Theory and Ap-plications ［M ］．InTech Publisher ，Ｒijeka，Croatia ，2010．［19］Pavlyukevich I．Lévyflights ，non-local search and simula-ted annealing ［J ］．Journal of Computational Physics ，
2007，226（2）：1830-1844．［20］Yang Xin-she ，Deb S．Cuckoo search via Levy flights
［C ］//Proc．of World Congress on Nature ＆Biologically Inspired Computing （NaBIC 2009）．2009：210-214．
［21］ＲeineltG．TSPLIB ：A traveling salesman problem library
［J ］．OＲSAJournal on Computing ，1991，3（4）：376-384．［22］Kirils Bibiks ，Li Jian-ping ，Hu Fun．Discrete flower polli-nation algorithm for resource constrained project scheduling
problem ［J ］．IJCSIS International Journal of Computer Sci-ence and Information Security ，2015，13（7）：8-19．［23］Shi Xiaohu ，Liang Y C ，Lee H P ，et al．Particle swarm
optimization based algorithms for TSP and generalized TSP ［J ］．Information Processing Letters ，2007，103（5）：169-176．［24］Li Xiangyong ，Tian Peng ，Hua Jing ，et al．A hybrid dis-crete particle swarm optimization for the traveling salesman
problem ［J ］．Lecture Notes in Computer Science ，2006，4247：181-188．
［25］Chen Shyi-ming ，Chien Chih-yao Y．Solving the traveling
salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization tech-nique ［J ］．Expert Systems with Applications ，2011，38
14450．（12）：14439-
檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺
（上接第36页）
［6］朱亚，GＲNN和概率统计孙冬梅，何响，等．基于EMD-J ］．计算机科学，2014，41（S1）：结合的短期风速预测［
72-75．
［7］潘学萍，史宇伟，张弛．双加权最小二乘支持向量机的
．电力系统及其自动化学报，2014，短期风速预测［J ］
17．26（1）：13-［8］Seeger M．Gaussian processes for machine learning ［J ］．
International Journal of Neural System ，2004，14（2）：69-106．［9］ＲasmussenC E ，Williams C K I．Gaussian Processes for
Machine Learning ［M ］．The MIT Press ，2006：7-31．［10］孙斌，姚海涛，刘婷．基于高斯过程回归的短期风速预
J ］．中国电机工程学报，2012，32（29）：104-109．测［
［11］Peng Kou ，Feng Gao．Sparse heteroscedastic Gaussian
process for short-term wind speed forecasting ［C ］//2012
IEEE World Congress on Computational Intelligence．Bris-bane ，Australia ，2012：1-8．［12］王富强，王东风，韩璞．基于混沌相空间重构与支持向
J ］．太阳能学报，2012，33（8）：1321-量机的风速预测［
1326．［13］Dong Lei ，Wang Lijie ，Hu Shi ，et al．Prediction of wind
power generation based on chaotic phase space reconstruc-tin models ［C ］//Power Electronics and Drive Systems 7th International Conference．Bangkok ，Thailand ，2007：744-748．［14］冬雷，王丽婕，高爽，等．基于混沌时间序列的大型风电
．电工技术学报，场发电功率预测建模与研究［J ］
129．2008，23（12）：125-［15］吕金虎，陆君安，陈士华．混沌时间序列分析及其应用
［M ］．武汉：武汉大学出版社，2002．
2016年第7期
0037-072475（2016）07-文章编号：1006-
计算机与现代化
JISUANJI YU XIANDAIHUA
总第251期
求解旅行商问题的离散花授粉算法
李
111，2
贺兴时，杨新社前，
（1．西安工程大学理学院，陕西西安710048；2．密德萨斯大学科学与技术学院，英国伦敦NW44BT ）
摘要：针对原始花授粉算法（FPA ）无法用于求解组合优化问题，提出一种离散的花授粉算法，并将其应用于求解旅行商问题（TSP ）。通过重新定义花朵、全局搜索与局部搜索等概念；并对莱维飞行用一种新的方法进行分段，有效避免算法过早陷入局部最优，增强算法的全局搜索能力。最后通过对10个国际通用的TSP 数据（TSPLIB ）进行测试，并将实验结果与离散粒子群算法（DPSO ）、混合离散粒子群算法（HDPSO ）、离散布谷鸟搜索（DCS ）算法、带有遗传模拟退火的蚁群粒子ACS-PSOT ）算法的实验结果进行对比。实验数据显示，群（GSA-该算法在求解旅行商问题中，能较快、较准确地找到最优解，在相同实验条件下，比其他算法求解偏差百分比明显降低。研究结果表明，本文提出的算法具有较好的求解性能。关键词：花授粉算法；离散花授粉算法；旅行商问题；莱维飞行；TSPLIB ；偏差百分比中图分类号：TP18
文献标识码：A
doi ：10．3969/j．issn．1006-2475．2016．07．008
A Discrete Flower Pollination Algorithm for Travelling Salesman Problem
2
LI Qian 1，HE Xing-shi 1，YANG Xin-she 1，
（1．School of Science ，Xi ’an Polytechnic University ，Xi ’an 710048，China ；2．School of Science and Technology ，Middlesex University ，NW44BT London ，UK ）
Abstract ：In view of the standard Flower Pollination Algorithm （FPA ）can not be used to solve combinatorial optimization prob-lem ，a Discrete Flower Pollination Algorithm （DFPA ）was proposed and then applied to Traveling Salesman Problem （TSP ）．By
redefining the concept of flowers ，global search and local search ，etc．，and Levy flight will be segmented by a new method ，ef-fectively avoiding premature falling into local optimum and enhancing the global search ability of the algorithm．Finally the per-formance of the proposed is tested against by some typical instances in the internationally commonly used library of TSP （TSPLIB ）and compared with Discrete Particle Swarm Optimization （DPSO ），Hybrid Discrete Particle Swarm Optimization （HDPSO ），Dis-crete Cuckoo Search （DCS ），Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimisation Technique （GSA-ACS-PSOT ）．The results of the tests show that DFPA can quickly ，accurately find the optimal solution．Under the same experi-mental conditions ，the algorithm reduces the error rate than any other algorithm．The results show that the proposed algorithm has better solving performance．
Key words ：Flower Pollination Algorithm （FPA ）；Discrete Flower Pollination Algorithm （DFPA ）；Travelling Salesman Problem （TSP ）；Levy flight ；TSPLIB ；percentage deviation
1概述
［3］
呈指数增长，搜索所有组合会使计算量迅速膨胀。
许多研究一直致力于解决TSP ，如禁忌搜索［5-6］
、（TS ）［4］、遗传算法（GA ）贪婪随机自适应搜索过［7］［8］
程（GＲASP）、模拟退火（SA ）。在过去的十几年中，基于元启发式算法或群智能的方法，比如蚁群优［9-10］［11-12］
、、化（ACO ）粒子群优化（PSO ）萤火虫算法［14］
，（FA ）［13］、布谷鸟搜索（CS ）已经被提出用于解决
［1］
旅行商问题（TSP ）是由爱尔兰数学家W．Ｒ．Hamilton 和英国数学家托马斯·柯克曼在19世纪提
hard ［2］问题。这个问题的出的，被认为是著名的NP-目的是在给定的城市列表中找到一种恰好访问每个
城市一次，然后回到出发城市的最短的巡回路线。表面上简单却十分难以解决的，因为组合数的增加会使问题
TSP 。因此，解决这一类问题具有重要的实际意义，
12-29收稿日期：2015-JM1006）基金项目：陕西省自然科学基础研究计划项目（2014，
），西安工程大学理学院硕士研究生，研究方向：智能计算与大数据理论。女，陕西商洛人，作者简介：李前（1992-
38计算机与现代化2016年第7期
因此它一直是被积极研究的一个重要课题。
旅行商问题因其简单易懂，操作过程与此同时，
复杂并具代表性，成为检验一个算法解决组合优化问题性能的重要途径。
花授粉算法是一种新型具有全局收敛的元启发
she ［15］在2012年式群智能优化算法，是由Yang Xin-通过模拟自然界中显花植物花朵授粉过程提出的。
同其他的智能优化算法相比，花授粉算法具有需要调整的参数较少、操作简单、易实现等优点。而且花授粉算法利用转换概率参数p 实现了动态控制全局搜索和局部搜索，较好地解决了全局搜索和局部搜索的平衡问题，同时采用了Levy 飞行机制，使得其具有良好的全局寻优能力。正是由于这些优点，花授粉算法引起了学术界的极大兴趣，成为启发式智能算法领域的一个新亮点。
Kirils Bibiks 等提出离散花授粉算法，解决资源受限项目调度问题（ＲCPSP）。Meriem Bensouyad 等介绍一种离散形式的花授粉算法来处理图形着色问题。这2种离散花授粉算法由于离散化方法的缘故，并不能解决旅行商问题，为了解决更多的组合优化问题，还需研究兼容性更好的离散化方法。
本文将介绍一种离散的花授粉算法，能有效解决对称的TSP 问题。通过对旅行商问题的求解也验证了这种离散花授粉算法的性能。
短之旅，赢得精力和时间的问题。J．K．Lenstra 和G．Ｒeinelt提出TSP 和它的变体的几个重要应用［16-17］，
x 射线晶体学、如印刷电路板的钻床、计算机线路、车
TSP 有很辆调度和调度、机器人控制等。现实表明，
大的重要性，无论是在学术界还是现实生活中。
3花授粉算法
2012年，Yang Xin-she ［15］通过模拟自然界中显花植物花朵授粉的过程提出花授粉算法（Flower Polli-nation Algorithm ，FPA ）。花授粉算法是一种新型元启发式群智能优化算法。
自然界中的花授粉过程是非常复杂的。因此，很难通过真实地模拟花授粉过程的每个细节来设计算法，即便是逼真地模拟出花授粉的过程也会导致算法特别复杂，计算量过大，降低算法的计算效率。这样的算法并不具有太大实际应用价值。因此，为了使算
FPA 对自然界中的花粉授粉过程进行了法简单易行，
简化，并根据其特点，建立了FPA 的以下规则：
规则1生物交叉授粉可以被视为是全局搜索过程，授粉生物的运动服从Levy 飞行，即跳或飞行距
［19］
离服从一个列维分布；
规则2非生物和自花授粉被视为局部搜索过程；
规则3花的常性可以被认为是繁衍概率，繁衍概率与授粉过程中参与的2朵花的相似性成比例关系；
0，1］规则4转换概率p ∈［控制全局搜索和局
部搜索之间的转换，这是由于物理上的邻近性、风等其他因素的影响。即在FPA 中，假设每朵花为求解优化问题的一个解，并且每朵花都是通过概率p 选择交叉授粉操作，或以概率1－p 选择自花授粉操作繁
p 是局部授粉的一个衍出后代。在整个授粉活动中，
非常重要的部分。
为了使以上规则公式化，需将上述更新规则转化为正确的更新方程。例如在全局搜索过程中，授粉昆虫携带着花粉配子，飞行较远距离。规则1和规则3可以表示为：
x t i +1=x t i +γL （λ）（g *－x t i ）
2旅行商问题的描述
Daven-旅行商问题可以看作是一个置换问题，dra ［18］对TSP 的规范描述如下：
c 2，．．．，c n ｝是不同的城市集，E =｛（c i ，C =｛c 1，
c j ）：i ，d c i c j 是边（c i ，j ∈｛1，．．．，n ｝｝是边集，c j ）∈E 的成c i 和c j 的距c iy ），本计量，城市c i ∈C 的坐标表示为（c ix ，离为欧几里德距离d c i c j =
π次旅行可以表示为一个循环的排列π=（π（1），（2），．．．，π（N ）），其中π（i ）表示1到N 这n 个城市
i 表示访问城市的顺序，i =1，2，．．．，N ，中的一个，旅
行的最小路程为：
f （π）=∑d π（i ）π（i +1）+d π（N ）π（1）
i =1N －1
（c ix －c jx ）+（c iy －c jy ），一
如果d c i c j =d c j c i ，则称其为欧式对称TSP ；如果至
c j ），少有一个（c i ，那么TSP 变为不对称使d c i c j ≠d c j c i ，TSP 指的是对称TSP 。欧式TSP 。在本文中，
这些年来，旅行商问题（TSP ）吸引了众多数学家的关注，他们都致力于设计一个算法，使其在合理的时间内找到对于大多数问题来说最佳的解决方案。它的特征在于它看起来十分简单，不需要数学背景的论述来了解它。它可以被看作是一个旅行商寻求最
x i 是花粉i 的第t 次迭代，g *是目前在所有的其中，
解决方案中发现的迭代最好的；γ是一个比例因子以
［20］
控制步长；L （λ）为参数，是以Levy 飞行为主步长，其与授粉强度有关。L ＞0，服从Levy 分布：
L
λΓ（λ）sin （πλ/2）1
，s s 0＞0
πs λ
t
规则2和规则3可被表示为：对于局部授粉，
x t i +1=x t i +ε（x t j －x t k ）
2016年第7期
t
t
李前等：求解旅行商问题的离散花授粉算法
t
39
其中x j 和x k 是来自相同物种不同花的花粉。如果x j
t
和x k 是来自相同的物种或在相同的群体中选择，ε
0，1］是在［间的均匀分布，那么这就等效地变成了局部随机移动。
是1号城市，第2个访问城市是3号城市，第3个访问城市是4号城市，以此类推，第10个访问城市是10号城市
。
花授粉算法的伪代码
x =（x 1，x 2，．．．，x d ）目标函数f （x ），初始化有n 朵花的种群
在这些初始种群中找出最优解g*0，1］定义转化概率p ∈［
定义最大迭代次数；
While （迭代次数＜最大迭代次数）For i =1：n
If 随机数p
绘制一个d 维步长矩阵L ，使L 服从Levy 分布全局搜索x i
t +1
图1一个解的表示
=x t i +γL （λ）（g *－x t i ）
Else 随机从种群中选择2朵花
1）取ε U （0，
进行局部搜索x i
End If
计算新解的适应度函数，并与当前最优解作比较如果新解更好，则在种群中更新它们End For
找到当前最优解g*
End While
输出当前找到的最优解
t +1
=x t i +ε（x t j －x t k ）
2）搜索空间。在二维情况下，搜索空间表示花的潜在位置。要改变一个花的位置，只需要修改其坐标的实际值。显然移动花和花的位置并没有实际的约束，而在旅行商问题中，在搜索空间中的运动，通过Levy 飞行生成的值，按照规定的方式对排列顺序进行改变，从已有的解决方案中得到新的方案。
3）全局授粉。
由于城市的坐标固定，该动作是基于旅行城市的顺序，改变旅行城市的顺序从已有的解决方案中得到新的方案，即通过改变排列的顺序来改变旅行顺序。笔者采用的方法是，在排列中每次随机选取2个位置（不相临的2个位置），这样会有4条路径交换二者，发生变化。以例中10个城市为例，交换其中第3个旅行城市（即4号城市）与第6个旅行城市（即2号
如图如图2所示。这样有4条路径发生变化，城市），
3所示
。
花授粉活动可以以任意尺度在局部和全理论上，
局中发生。但现实中，毗连的花和那些离得不遥远的花比那些距离遥远的花更容易接受局部花粉的授粉。为了模仿这个特征，转换概率（规则4）p 可有效地动
she 在参数态控制全局搜索和局部搜索。Yang Xin-研究中表明，在大多数应用中p =0．8可能更加有效。
图2
变序策略
4离散花粉算法
由于原来的FPA 被设计用于连续优化问题。笔
者通过重新定义算法中花朵、搜索空间、全局授粉、局部授粉和莱维飞行等概念，将其离散化。
1）花朵。在离散花授粉算法（DFPA ）中，一朵花代表群体中的一个体，用一种排列形式表示，其中每个元素代表预定活动，元素的索引是其中该活动将被执行的顺序。每朵花被认为是一个解决方案。例如，在旅行商问题中，每朵花表示一种旅行方案，排列中的节点表示城市编号，排列顺序即为旅行顺序。如图1所示，假设有10个城市，那么该方案表示：第1个访问城市
图3路线改变示意图1
4）局部授粉。
原始花授粉算法中的局部授粉是随机取出种群中2朵花，根据2朵花的差异程度决定花的下一代。而在旅行商问题中，其解都为遍历城市的顺序排列，要进行局部搜索，可以通过反序的策略。在连续问题中，相邻单位的意义是显而易见的。然而，对于离散性问题，就必须小量地改变相邻单位，从而得到新的
结果。这种对结论的改动必须很小。在进行局部搜索时，搜索步长应较全局搜索小。所以，本文按以下
对调其中2个连方式进行（同样取10个城市为例），
续城市的旅行顺序，如图4所示，将城市7和城市8反序。这样改变2条路径（从A 地到B 地的路程与从B 地到A 地的路程相同，所以视为同样的路径），如图5所示
。
Levy 在（0．1，0．3］→经过2次变序；Levy 在（0．3，0．6］→经过3次变序；Levy 大于0．6→经过4次变序
。
图4
反序策略
图6Levy 飞行波动图
5实验结果与分析
为了进一步验证本文所提算法的求解性能，选用
［21］
多个TSPLIB 标准库实例进行实验测试。实验环
图5
路线改变示意图2
5）Levy 飞行。
为了提高解的质量，原始FPA 所述Levy 飞行用于计算步长。
－
Levy （s ，λ） s λ，1＜λ＜3
TM
境为一台CPU 为Intel （Ｒ）Core i52．00GHz 和内存为6GB 的64位笔记本电脑，在MATLAB Ｒ2014a中编程实现。
在进行了初步实验后，本文所选择的设置参数如表1所示。
Levy 飞行具有围绕一个解决方案密集搜索的特性，但从长远来看，偶尔会有突跳现象。根据Yang Xin-she 和S．Deb ［20］的研究，在一些关于优化的问题Levy 飞行可以更有效地得到最佳方案。为了提中，
Levy 飞行所采用的步长必须与高搜索结果的质量，
标准花授粉算法中所列出的标准相关联。
在Levy 飞行移动时，经过多次绘制其波动图像，如图6所示，不难发现，其小幅跳跃的步长比较密集，随着跳跃幅度加大，其出现的频率在减少。即大多在0附近波动，越偏离0，出现的次数越少。Aziz
0，1］，Ouaarab ［14］提出的方法是将Levy 飞行控制在［
0，1］根据移动步长中的最大值n ，将［等分为n 个小
区间，根据Levy 飞行的值落在的区间段分别定义其移动步长。但这样显然在解空间搜索过程中出现突跳的可能性极小，所以容易陷入局部最优。本文采用梯度区间来限制Levy 飞行，使步长变化更加合理，保持种群多样性，避免陷入局部最优，更快找到最优解。因此，根据Levy 旅行的规则可以按如下方式确定适当的步长：
Levy 在［0，0．1］→经过1次变序；
表1
参数n p N_iter
值200．82000
参数设置
意义种群大小转换概率参数p 最大迭代次数
Bayg29、Att48、Eil51、仿真实验，采用Ulysses16、
berlin52、St70、pr76、kroA100、ch130、ch150这10个实例。每种算法独立运行40次，计算结果如表2所示。
n 表示城市的数量，Opt 其中第1列表示实例的名称，
列给出了问题的已知最优值（TSPLIB 中最优解的长
Best 列给出了本算法求解得到最优解的长度，度），
worst 列给出了本算法求得的最差解，Average 列为在40次独立运行后得出解的平均长度，PDav 列表示30
［22］
次运行中长度偏差的百分比。偏差定义如下：
PDav =
Average length －Optimal solution length
ˑ 100
Opt
通过对这10个实例的实验，结果表明本算法在维数不高的情况下，都能找到最优解，而且在多次运行过程中出现误差的情况也都不超过1%，说明本算法具有较好的稳定性。同时本算法也求得这10个实
例的最优旅行路线图，如图7 图14所示。
表2
Problem Ulysses16
Bayg29Att48Eil51berlin52St70pr76kroA100ch130ch150
n [***********]30150
FPA 标准测试问题的实验结果
Opt
[***********][***********]106528
Best [***********][***********]106528
DFPA
Worst Average 68596859
[***********]．[**************]1．80701676．[***********]21316．4761936141．0166356582．33
PDav
/%
000．0900．130．210．280．160．510．83
图10eil51旅行路线图
图7Ulysses16旅行路线图
图11Pr76旅行路线图
图8Bayg29旅行路线图
图12kroA 旅行路线图
图9Att48旅行路线图图13Ch130旅行路线图
ACS-PSOT 与表5和表6分别是DCS 和GSA-DFPA 实验结果的对比。可以清楚地看出，DFPA 模
型在解决TSP 的测试中胜过了DCS 。DFPA 在5个测ACS-PSOT 的实验结果。试问题中有4个远远小于GSA-这说明，本文提出的算法具有良好的求解性能。
表5
Problem Eil51berlin52St70
Opt 4267542675
DCS 与DFPA 的实验结果比较
DCS
Best 4267542675
Worst PDav /%459725725
3．033．903．242．835．346．5318．06
Best 4267542675
DFPA
Worst PDav /%4267570701
00．130．210．280．160．510．83
图14ch150旅行路线图
pr[***********]78
[1**********]13
[1**********]64
[***********]1106528
[1**********]35
kroA10021282Ch130Ch150
61106528
笔者选择近几年在求解旅行商问题中表现良好
的几种算法与DFPA 进行比较。DFPA 的实验结果与DPSO （Discrete Particle Swarm Optimization ）
［23］
，HDP-［24］
SO （Hybrid Discrete Particle Swarm Optimization ），
表6
Problem Eil51
GSA-ACS-PSOT 与DFPA 的实验结果比较
Opt 426
GSA-ACS-PSOT Best 4277542
Average 427．277542．00
SD 0．450．00
Best 4267542
DFPA Average 4267551．80
SD 0．002．07
ACS-PSOT DCS （Discrete Cuckoo Search ）［15］，GSA-（Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimization ）
［25］
算法的实验结果对比，
berlin527542
分别见表3 表6。这4种算法的实验数据细节直接
23-25］。引用于文献［
PDav 表表3是DPSO 与DFPA 的实验比较结果，
示30次运行中每次旅行路径长度偏差的百分比。显pr79，DPSO 并没有找到最优解，然，对测试问题Eil51，
而DFPA 找到了最优值，而且DFPA 在解决4个测试问题中的偏差百分比远远小于DPSO 。
表3
DPSO 与DFPA 的实验结果比较
PDav /%
2．57513．84583．34223．8176
DFPA
Best Worst PDav /%[**************]0．136757010．[**************]．28
kroA[***********]．47123．[1**********]6．4737．79Ch130Ch150
61106528
61416528
6205．436563．70
43．7022．45
61106528
6141．016582．33
16．5221．04
6结束语
TSP 是组合优化问题中较为著名的问题，是涉及
运筹学、图论的NP 难题，在许多行业都有广泛的应用，同时也成为检验一个算法解决组合优化问题性能的重要途径。笔者以求解TSP 问题为例，提出了一种离散花授粉算法的具体实现，拓展了花授粉算法的应用领域。该算法通过重新定义花朵、全局授粉、局部授粉等过程，将梯度分段作用于Levy 飞行，避免算法陷入局部最优。仿真实验结果表明，离散花授粉算法在收敛速度、寻优度和稳定性方面都表现良好。可以通过对该算法做适当变化，将其推广用于解决其他组合优化问题，这也是今后需要努力的方向。
参考文献：［1］Blum C ，ＲoliA．Metaheuristics in combinatorial optimiza-tion ：Overview and conceptual comparison ［J ］．ACM Com-2003，35（3）：268-308．pute Surveys （CSUＲ），［2］Lawler E L ，Lenstra J K ，ＲinnooyKan A H G ，et al．The
Traveling Salesman Problem ：A Guided Tour of Combinato-rial Optimization ［M ］．John Wiley ＆Sons ，Incorporated ，1985．［3］Papadimitriou C H．Euclidean TSP is NP-complete ［J ］．
DPSO
Problem Opt
Best Worst
Eil[1**********]berlin[1**********]362St[1**********]pr[***********]65
SD 表表4是HDPSO 与DFPA 的实验比较结果，
用以衡量每次结果值偏离平均值的程示标准方差，
DFPA 对其他测试函数的标准方差小度。除了St70，
于HDPSO 。可以发现HDPSO 并没有找到这4个测试问题的最优值，只是找到了局部值。
表4
Problem
Opt
HDPSO 与DFPA 的实验比较结果
Best
[**************]9
HDPSO Worst SD 1107011．154420．007044．4723867464．21
Best [**************]2
DFPA Worst SD 1064510．234260．007017．162159837．79
Att4810628Eil51426St70675kroA10021282
Theoretical Computer Science ，1997，4：237-244．［4］Zachariasen M ，Dam M．Tabu Search on the Geometric
Traveling Salesman Problem ［M ］．Meta-Heuristics ，Spring-er ，1996：571-587．［5］Potvin J Y．Genetic algorithms for the traveling salesman
problem ［J ］．Annals of Operations Ｒesearch，1996，63（3）：337-370．
［6］Qu Liangsheng ，Sun Ｒuixiang．A synergetic approach to
genetic algorithms for solving traveling salesman problem ［J ］．Information Sciences ，1999，117（3）：267-283．［7］Marinakis Y ，Migdalas A ，Pardalos P M．Expanding neigh-borhood GＲASPfor the traveling salesman problem ［J ］．
Computational Optimization and Applications ，2005，32（3）：231-257．
［8］Chen Yong ，Zhang Pan．Optimized annealing of traveling
salesman problem from the-nearest-neighbor distribution
［J ］．Physica A ：Statistical Mechanics and its Applica-tions ，2006，371（2）：627-632．［9］Dorigo M ，Gambardella L M．Ant colonies for the travelling
salesman problem ［J ］．Biosystems ，1997，43（2）：73-81．［10］Dorigo M ，Gambardella L M．Ant colony system ：A coop-erative learning approach to the traveling salesman problem
［J ］．IEEE Transactions on Evolutionary Computation ，1997，1（1）：53-66．［11］Li Xiangyong ，Tian Peng ，Hua Jing ，et al．A hybrid dis-crete particle swarm optimization for the traveling salesman
problem ［J ］．Lecture Notes in Computer Science ，2006，4247：181-188．
［12］Goldbarg Elizabeth F G ，Goldbarg Marco C ，Souza Givanal-do Ｒde．Particle swarm optimization algorithm for the trav-eling salesman problem ［M ］//Traveling Salesman Prob-lem．2008：75-96．［13］Jati Gilang Kusuma ，Suyanto．Evolutionary discrete firefly
algorithm for travelling salesman problem ［J ］．Adaptive and Intelligent Systems ，2011，6943：393-403．［14］Ouaarab A ，Ahiod B ，Yang Xin-she．Discrete cuckoo search
algorithm for the travelling salesman problem ［J ］．Neural Computing and Applications ，2014，24（7）：1659-1669．
［15］Yang Xin-she．Flower pollination algorithm for global opti-mization ［C ］//Proceedings of the 11th International Con-ference on Unconventional Computation and Natural Com-putation．2012，7445：240-249．［16］Lenstra J K ，ＲinnooyKan A H G．Some simple applica-tions of the travelling salesman problem ［J ］．Operational
ＲesearchQuarterly ，1975，26（4）：717-733．［17］ＲeineltG．The Traveling Salesman ：Computational Solu-tions for TSP Applications ［M ］．Springer-Verlag ，1994．［18］Davendra D．Traveling Salesman Problem ，Theory and Ap-plications ［M ］．InTech Publisher ，Ｒijeka，Croatia ，2010．［19］Pavlyukevich I．Lévyflights ，non-local search and simula-ted annealing ［J ］．Journal of Computational Physics ，
2007，226（2）：1830-1844．［20］Yang Xin-she ，Deb S．Cuckoo search via Levy flights
［C ］//Proc．of World Congress on Nature ＆Biologically Inspired Computing （NaBIC 2009）．2009：210-214．
［21］ＲeineltG．TSPLIB ：A traveling salesman problem library
［J ］．OＲSAJournal on Computing ，1991，3（4）：376-384．［22］Kirils Bibiks ，Li Jian-ping ，Hu Fun．Discrete flower polli-nation algorithm for resource constrained project scheduling
problem ［J ］．IJCSIS International Journal of Computer Sci-ence and Information Security ，2015，13（7）：8-19．［23］Shi Xiaohu ，Liang Y C ，Lee H P ，et al．Particle swarm
optimization based algorithms for TSP and generalized TSP ［J ］．Information Processing Letters ，2007，103（5）：169-176．［24］Li Xiangyong ，Tian Peng ，Hua Jing ，et al．A hybrid dis-crete particle swarm optimization for the traveling salesman
problem ［J ］．Lecture Notes in Computer Science ，2006，4247：181-188．
［25］Chen Shyi-ming ，Chien Chih-yao Y．Solving the traveling
salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization tech-nique ［J ］．Expert Systems with Applications ，2011，38
14450．（12）：14439-
檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺檺
（上接第36页）
［6］朱亚，GＲNN和概率统计孙冬梅，何响，等．基于EMD-J ］．计算机科学，2014，41（S1）：结合的短期风速预测［
72-75．
［7］潘学萍，史宇伟，张弛．双加权最小二乘支持向量机的
．电力系统及其自动化学报，2014，短期风速预测［J ］
17．26（1）：13-［8］Seeger M．Gaussian processes for machine learning ［J ］．
International Journal of Neural System ，2004，14（2）：69-106．［9］ＲasmussenC E ，Williams C K I．Gaussian Processes for
Machine Learning ［M ］．The MIT Press ，2006：7-31．［10］孙斌，姚海涛，刘婷．基于高斯过程回归的短期风速预
J ］．中国电机工程学报，2012，32（29）：104-109．测［
［11］Peng Kou ，Feng Gao．Sparse heteroscedastic Gaussian
process for short-term wind speed forecasting ［C ］//2012
IEEE World Congress on Computational Intelligence．Bris-bane ，Australia ，2012：1-8．［12］王富强，王东风，韩璞．基于混沌相空间重构与支持向
J ］．太阳能学报，2012，33（8）：1321-量机的风速预测［
1326．［13］Dong Lei ，Wang Lijie ，Hu Shi ，et al．Prediction of wind
power generation based on chaotic phase space reconstruc-tin models ［C ］//Power Electronics and Drive Systems 7th International Conference．Bangkok ，Thailand ，2007：744-748．［14］冬雷，王丽婕，高爽，等．基于混沌时间序列的大型风电
．电工技术学报，场发电功率预测建模与研究［J ］
129．2008，23（12）：125-［15］吕金虎，陆君安，陈士华．混沌时间序列分析及其应用
［M ］．武汉：武汉大学出版社，2002．