推荐星级：
- 1
- 2
- 3
- 4
- 5
基于模拟退火的自适应 离散型布谷鸟算法求解旅行商问题
资料介绍
提出了一种基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题.该算法在布谷鸟搜索算法原理的基础上,构造了旅行商问题的路径求解策略.由于算法的局限性,随着算法的调整和迭代次数的增加,容易破坏已形成的路径,从而使得算法通用性不强.针对这一局限性,本文提出了一种自适应局部调整算子和全局随机扰动策略.采用简单的2-opt算子作为局部优化算子加快算法收敛速度,引入模拟退火机制防止算法陷入局部最优.采用标准TSPLIB多组数据进行测试,并与有代表性的优化算法进行结果比较.实验结果证明了该算法在精度和稳定性方面的优势.
部分文件列表
| 文件名 | 大小 |
| 基于模拟退火的自适应_离散型布谷鸟算法求解旅行商问题.pdf | 1M |
部分页面预览
（完整内容请下载后查看）8
Vol． 46 No． 8
Aug． 2018
第
期
电
子
学
报
2018
8
ACTA ELECTRONICA SINICA
年
月
基于模拟退火的自适应
离散型布谷鸟算法求解旅行商问题
1
1
1，2，3
， ，
张子成 韩 伟 毛 波
( 1．
，
南京财经大学信息工程学院 江苏南京
210046; 2．
，
现代粮食流通与全协同创新中心 江苏南京
210046;
3．
，
江苏省粮食大数据挖掘与应用重点实验室 江苏南京
210046)
:
．
提出了一种基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题 该算法在布谷鸟搜索算法原
摘
要
， ． ， ，
理的基础上 构造了旅行商问题的路径求解策略 由于算法的局限性 随着算法的调整和迭代次数的增加 容易破
， ． ，
坏已形成的路径 从而使得算法通用性不强 针对这一局限性 本文提出了一种自适应局部调整算子和全局随机扰
．
动策略 采用简单的
2-opt
，
算子作为局部优化算子加快算法收敛速度 引入模拟退火机制防止算法陷入局部最优
．
TSPLIB
采用标准
定性方面的优势
， ．
多组数据进行测试 并与有代表性的优化算法进行结果比较 实验结果证明了该算法在精度和稳
．
:
;
; 2-opt
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
布谷鸟算法 旅行商问题
算子 局部调整 全局随机扰动
0372-2112 ( 2018) 08-1849-09
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 08． 008
:
TN92
:
A
:
文章编号
文献标识码
电子学报
Adaptive Discrete Cuckoo Algorithm Based on
Simulated Annealing for Solving TSP
1
1
1，2，3
ZHANG Zi-cheng ，HAN Wei ，MAO Bo
( 1． School of Inormation Engineering，Nanjing University of Finance and Economics，Nanjing，Jiangsu 210046，China;
2． Modern Grain Circulation and Full Cooperation Innovation Center，Nanjing，Jiangsu 210046，China;
3． Key Laboratory of Large Data Mining and Spplication of Grain，，Nanjing，Jiangsu 210046，China)
Abstract: An adaptive discrete cuckoo algorithm based on simulated annealing is proposed to solve the traveling
salesman problem． The proposed algorithm constructs the path solving strategy of traveling salesman problem based on the
principle of cuckoo search algorithm． Due to the limitation of algorithm，with the increasing of the number of iterations，it is
inclined to destroy the formed paths，which makes algorithm can not be commonly used in variant applications． To overcome
this shortcoming，this paper adopt an new strategy which adjust operator locally and disturb parameters randomly ． A simple
2-opt operator is used as the local optimization operator to accelerate the convergence rate of the algorithm． The simulated
annealing mechanism is introduced to prevent the local optimum in early iterations． The algorithm is tested by the standard
TSPLIB multi-group data，comparing with several representative traveling salesman problem algorithm ，the experimental re-
sults show the advantages of the algorithm in terms of accuracy and stability．
Key words: cuckoo search algorithm; traveling salesman problem; 2-opt optimization; partial adjustment; global ran-
dom disturbance
． 、
旅行的最短路径 在物流配送 车辆路径优化等方面具
1
引言
． ，
有重要的现实意义 目前 该问题已广泛应用于物流配
( Traveling Salesman Problem，
简 称
旅 行 商 问 题
、 、 、
送路线设计 仓储货物装卸 集装箱装载 印制线路钻探
［1］
TSP)
NP-Hard
．
难题 它决定了推销员
是一个典型的
．
等多个交叉领域 考虑到
TSP
，
能在多个领域应用 许多
: 2017-07-06;
: 2018-03-13; :
责任编辑 马兰英
收稿日期
修回日期
:
基金项目 国家科技支撑计划农资物流防伪和溯源关键技术与装备研发
( No． 2015BAD18B02)
1850
2018
年
电
子
学
报
、 、 、
研究学者从数学 计算机科学 工业工程 管理科学等多
2
2-opt
优化算子
布谷鸟算法 和
［2，3］
TSP
．
并且布谷鸟搜索算法具
个学科集中研究解决
2. 1
布谷鸟算法
、 、 ，
有控制简单 收敛速度快 全局优化能力强等优点 对连
［4］
( CS)
布谷鸟搜索算法
是由杨提出的一种新型的智
CS
．
续函数优化问题具有良好的性能
许多专家学者尝
［17］
． Maribel
能优化算法
用遗传算法和
算法对比来验
TSP．
， :
一些学者将确定性算法 如
试用多种方法来求解
［4］
［5］
．
证其有效性 布谷鸟算法用莱维飞行和基于偏好的随
TSP．
，
然而 这
分枝定界法 和动态规划法 用于求解
．
机游动来平衡全局搜索和局部搜索 但该算法在后期
，
些方法的复杂度呈指数增长 对大规模
TSP
来说完全
．
仍存在收敛速度慢的缺点 优化算法参数是提高算法
． ， ，
无效 近几十年来 研究者从仿真机制中得到了启发 提
［18］
［6］
． Maribel
FCS
系统
性能的一个研究热点
提出了一个
CS
，
出了一系列智能优化算法 如遗传算法
( GA)
、
模拟
［7］
［8］
． ，
动态调整参数 实验结果表明 与传统的
，
算法相比
( SA)
、
( AC)
，
等 并用于求解
退火算法
蚁群算法
［19］
FCS
． Claudia
Sobel
结合 技术与区间
的性能有所提高
TSP．
，
随着智能优化算法的不断发展 许多新的群智能
［9］
CS，
并将改进算法应用于数字图
二型模糊逻辑来优化
． CS
，
优化算法应运而生 如布谷鸟搜索
( CS)
，
萤火虫
算法
［10］
［11］
，
模拟布谷鸟寄生习性 可有效解决优
像的边缘检测
( GSO)
，
( PSO) ．
算法 等 这些
优化
算法
粒子群优化
［11］
． CS
、 、
具有结构简单 参数少 跳出局部最优能力
化问题
TSP: Mostafa Mahi
群智能算法被广泛地用去求解
将
．
强等优点 建立理想化规则如下
: ( 1)
每只布谷鸟每次
． ( 2)
， 3-opt
粒子群算法和蚁群算法结合 用
优化算子作为局
，
只产生一个卵 随机选择一个寄生巢孵化它
在随
TSP．
，
但是 蚁群算法迭代缓慢
部优化算子并用于解决
，
机选择的寄生巢中 最好的巢将保留到下一代
． ( 3)
可
3-opt
以及
优化算子的高计算复杂性增加了算法的运行
，
用寄生巢的数目是固定的 寄生巢的主人发现外来卵
;
时间 一些研究人员利用蚁群算法求解
TSP，
对得到的
Pa．
的概率为
布谷鸟找到鸟窝路径并根据上述理想化规则更新
， ．
解进行排序 但只更新最优路径的信息素 它提高了收
［12］
，
敛速度 但在某些条件下很容易陷入局部最优
; Yong
［13］
，
位置 位置更新公式如下
:
Wang
TSP，
将遗传算法作
提出了一种混合算法求解
( t + 1)
( t)
X
= X + T Levy(
i
)
λ
( 1)
，Levy
i
．
为一种全局优化策略 他建议使用两种不同的局部优
( 1) ，T T ＞ 0，
中 代表步长 并且 ⊕是点对点乘法
式
．
化算子来优化已获得的最优路径 该算法在求解小规
［20，21］
( )
，
伪代码描述如
是搜索路径并且服从莱维分布
TSP ， TSP
时具有一定优势 但是对于大规模
模
效果不
［14］
1．
算法 自适应局部调整算子如算法
2．
． Marinakis
TSP，
基于概率分析 提出了一种
是很理想
混合粒子群优化算法
( CS)
．
1
Cuckoo Search algorithm
算法
、 、
算法具有收敛速度快 易于控制
布谷鸟搜索
，
强大的全局优化能力 在连续函数优化问题上表现出
1． Begin
2． Objective function，f( x) ，X = ( X ，X ，…，X ) d is the dimension of
［14］
T
． CS
良好的性能
算法已成功地用于优化各种组合优
1
2
d
［14］
the problem
． Aziz Ouaarab
CS
化问题
提出了一种离散型
算法用
3． Generate initial population of n host nests
TSP．
， CS
针对离散型问题 在
于解决
算法基础上设计了
X ( i = 1，2，…，n)
i
，
一种步长移动策略 使用
2-opt
和双桥算子作为局部优
( paco-
4． While ( t ＜ Max Generation) or ( stop criterion)
［15］
． Saban
化算子
3opt)
等人 引入并行协同的混合算法
5． Get a cuckoo randomly by Lévy flights evaluate its quality/fitness f( X )
i
6． Select a nest among n ( say，j) randomly.
7． If f( X ) ＞ f( X )
TSP．
，
该算法是基于蚁群算法的框架 使其避
求解
i
j
． ，
免进入局部最优 实验结果表明 该算法具有更好的性
8． replace the nest j with a new solutions
9． end
［16］
． Yassine Saji
，
提出了一种离散型的蝙蝠算法 该算
能
，
法嵌入了连续函数优化算法的机制 测 试数据 来自
10． A fraction ( Pa) of worse nests are abandoned and new ones are built
11． Keep the best solutions( or nests with quality solutions)
12． Rank the solutions and find the current best
13． end while
TSPLIB，
实验结果表明了它的有效性
．
，
因此 以上论述证明了中小型规模求解精度较高
，
． 2-opt
大规模城市的求解便会陷入局部最优
优化算子
14． Post process results and visualization
15． End
． ， 、
优化路径具有快速收敛的特点 然而 使用变异 交叉和
其他算子生成新路径可能会破坏已经形成的最佳路
． ，
径 因此 我们提出了一种自适应的局部调整算子并结
2
算法
自适应局部调整算子
2-opt
， ，
算子 并在路径上加入全局随机扰动策略 以保
合
，
持种群的多样性 避免陷入局部最优
．
1． Begin
全部评论(0)