推荐星级:
  • 1
  • 2
  • 3
  • 4
  • 5

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

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

资料介绍

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


部分文件列表

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

部分页面预览

(完整内容请下载后查看)
8
Vol. 46 No. 8  
Aug. 2018  
2018  
8
ACTA ELECTRONICA SINICA  
基于模拟退的自适应  
谷鸟问题  
1
1
123  
, ,  
张子成 韩 伟 毛 波  
( 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
123  
ZHANG Zi-cheng HAN Wei MAO Bo  
( 1. School of Inormation EngineeringNanjing University of Finance and EconomicsNanjingJiangsu 210046China;  
2. Modern Grain Circulation and Full Cooperation Innovation CenterNanjingJiangsu 210046China;  
3. Key Laboratory of Large Data Mining and Spplication of GrainNanjingJiangsu 210046China)  
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 algorithmwith the increasing of the number of iterationsit is  
inclined to destroy the formed pathswhich makes algorithm can not be commonly used in variant applications. To overcome  
this shortcomingthis 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 datacomparing 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  
优化算子  
布谷鸟算法 和  
23]  
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,  
法  
优化已最优规  
2021]  
( )  
描述如  
搜索布  
TSP TSP  
具有于大规模  
效果不  
14]  
1.  
法 自适应调整法  
2.  
. Marinakis  
TSP,  
基于率分提出了一种  
是很想  
优化法  
( CS)  
1
Cuckoo Search algorithm  
算法  
、 、  
具有制  
谷鸟搜索  
大的全优化能力 在数优化问题出  
1. Begin  
2. Objective functionf( x) X = ( X X X ) d is the dimension of  
14]  
T
. CS  
能  
地用优化各合优  
1
2
d
14]  
the problem  
. Aziz Ouaarab  
CS  
问题  
提出了型  
用  
3Generate initial population of n host nests  
TSP.  
CS  
问题 在  
解决  
法基了  
X ( i = 12n)  
i
一种策略 使用  
2-opt  
作为优  
( paco-  
4While ( t < Max Generation) or ( stop criterion)  
15]  
. Saban  
子  
3opt)  
入并法  
5Get a cuckoo randomly by Lévy flights evaluate its quality/fitness f( X )  
i
6. Select a nest among n ( sayj) randomly.  
7If f( X ) f( X )  
TSP.  
基于法的框架 使避  
解  
i
j
,  
最优 实验结果表明 该具有更好性  
8. replace the nest j with a new solutions  
9end  
16]  
. Yassine Saji  
提出了一种蝙蝠算  
优化自  
10A 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  
13end while  
TSPLIB,  
实验结果表明了它有效性  
因此 度较高  
. 2-opt  
大规市的便最优  
优化子  
14Post process results and visualization  
15End  
、  
优化具有快速收点 然使变异 交叉和  
生成路  
,  
因此 我们提出了一种自适应调整结  
2
算法  
适应算子  
2-opt  
, ,  
策略 保  
多样避免最优  
1Begin  

全部评论(0)

暂无评论

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

  • 打赏
  • 30日榜单

推荐下载