积分商城

最新搜索： 软件评估 stm8s HFBR-0310Z光纤发射和接收电路 Allegro封装库 51单片机 AP6236
您现在的位置是：首页 > 技术资料 > 基于模拟退火的自适应 离散型布谷鸟算法求解旅行商问题
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

基于模拟退火的自适应 离散型布谷鸟算法求解旅行商问题

更新时间：2019-12-24 04:48:26 大小：1M 上传用户：守着阳光1985查看TA发布的资源 标签：模拟退火 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

提出了一种基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题.该算法在布谷鸟搜索算法原理的基础上,构造了旅行商问题的路径求解策略.由于算法的局限性,随着算法的调整和迭代次数的增加,容易破坏已形成的路径,从而使得算法通用性不强.针对这一局限性,本文提出了一种自适应局部调整算子和全局随机扰动策略.采用简单的2-opt算子作为局部优化算子加快算法收敛速度,引入模拟退火机制防止算法陷入局部最优.采用标准TSPLIB多组数据进行测试,并与有代表性的优化算法进行结果比较.实验结果证明了该算法在精度和稳定性方面的优势.


部分文件列表

文件名 大小
基于模拟退火的自适应_离散型布谷鸟算法求解旅行商问题.pdf 1M

【关注视频号领20积分】   【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）
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)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号