|本期目录/Table of Contents|

[1]林 敏*,刘必雄,林晓宇. 带Metropolis准则的混合离散布谷鸟算法求解旅行商问题[J].南京大学学报(自然科学),2017,53(5):972.[doi:10.13232/j.cnki.jnju.2017.05.017]
 Lin Min*,Liu Bixiong,Lin Xiaoyu. Hybrid discrete cuckoo search algorithm with metropolis criterion for traveling salesman problem[J].Journal of Nanjing University(Natural Sciences),2017,53(5):972.[doi:10.13232/j.cnki.jnju.2017.05.017]
点击复制

 带Metropolis准则的混合离散布谷鸟算法求解旅行商问题()
     

《南京大学学报(自然科学)》[ISSN:0469-5097/CN:32-1169/N]

卷:
53
期数:
2017年第5期
页码:
972
栏目:
出版日期:
2017-09-30

文章信息/Info

Title:
 Hybrid discrete cuckoo search algorithm with metropolis criterion for traveling salesman problem
作者:
 林 敏*刘必雄林晓宇
 福建农林大学计算机与信息学院,福州,350002
Author(s):
 Lin Min*Liu BixiongLin Xiaoyu
 School of Computer and Information Science,Fujian Agriculture and Forestry University,Fuzhou,350002,China
关键词:
 布谷鸟搜索旅行商问题Metropolis接受准则Levy飞行
Keywords:
 cuckoo searchtraveling salesman problemMetropolis acceptance criterionLevy flight
分类号:
TP183
DOI:
10.13232/j.cnki.jnju.2017.05.017
文献标志码:
A
摘要:
 布谷鸟算法(Cuckoo Search,CS)在求解连续问题方面得到较好的结果,但在处理离散问题方面解决方案较少且收敛速度过慢,针对此不足,以求解旅行商问题为代表,结合基于学习的混合邻域结构和概率接受准则,提出了一种新颖的改进的混合离散布谷鸟(Hybrid Discrete Cuckoo Search,HDCS)算法.HDCS算法通过向最佳个体学习和从问题学习来搜索解空间,将反序、插入、块移动、交换和双桥等多种算子组合构造不同的混合邻域,通过Levy飞行选择相应的邻域结构进行寻优,并引入模拟退火算法的Metropolis接受准则,能够以一定的概率接受劣质解,使算法不易陷入局部最优.为了验证算法的性能,将HDCS算法分别与其他基于CS算法、经典智能优化算法和新型群智能优化算法的3类方法进行比较,实验结果表明,HDCS算法不但优于其他基于CS的算法,同时也优于一些其他最新的群智能优化算法.
Abstract:
 The cuckoo search(CS)algorithm is a new metaheuristic method which is proposed by Yang and Deb in 2009,inspired by the brood parasitism behavior of cuckoos.The cuckoos find the optima by the Levy flight.Levy flight has a heavy-tailed which make it search in the short area most time and jump to the long distance occasionally.Such characteristics of CS can enlarge the search areas,guarantee the diversity of solution,and make it not easy to fall into the local optimum.As a result,CS shows better performance in solving continuous problems,but there are few researches applying it to the discrete problems,at the same time those existing discrete strategies converges slowly in the search processes.In order to solve this deficiency,a novel discrete hybrid Cuckoo Search(HDCS)algorithm,which combines learning-based hybrid neighborhood structure and probability acceptance criteria,is proposed for traveling salesman problem.Specifically,the HDCS algorithm searches the solution space by learning from the best and learning from problem at hand.HDCS uses reverse,insertion,block moving,swap and double bridge operator to generate different hybrid neighborhood structures,and levy flight is used to select those neighborhood structures.Furthermore,the Metropolis acceptance criterion of simulated annealing algorithm is introduced to allow accepting inferior solutions with certain probability,so the algorithm will not be strapped into local optima easily.In order to test the performance of HDCS,the paper chooses some benchmark instances which city quantity varies from 51 to 13509,and compares it with three types of algorithms.They are another improved CS algorithm,the classical intelligent optimization algorithms,and the other new swarms intelligence algorithms.The experimental results show that HDCS algorithm is not only better than other cuckoo search based algorithms,but is better than some state-of-the-art swarm intelligence algorithms also.

参考文献/References:

[1] 刘荷花,崔 超,陈 晶.一种改进的遗传算法求解旅行商问题.北京理工大学学报,2013,33(4):390-393.(Liu H H,Cui C,Chen J.An improved genetic algorithm for solving travel salesman problem.Transactions of Beijing Institute of Technology,2013,33(4):390-393.)
[2]  于莹莹,陈 燕,李桃迎.改进的遗传算法求解旅行商问题.控制与决策,2014,29(8):1483-1488.(Yu Y Y,Chen Y,Li T Y.Improved genetic algorithm for solving TSP.Control and Decision,2014,29(8):1483-1488.)
[3]  吴 斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法.计算机学报,2001,24(12):1328-1333.(Wu B,Shi Z Z.An ant colony algorithm based partition algorithm for TSP.Chinese Journal of Computers,2001,24(12):1328-1333.)
[4]  冀俊忠,黄 振,刘椿年等.基于多粒度的旅行商问题描述及其蚁群优化算法.计算机研究与发展,2010,47(3):434-444.(Ji J Z,Huang Z,Liu C N,et al.An ant colony algorithm based on multiple-grain representation for the traveling salesman problems.Journal of Computer Research and Development,2010,47(3):434-444.)
[5]  杜占玮,杨永健,孙永雄等.基于互信息的混合蚁群算法及其在旅行商问题上的应用.东南大学学报(自然科学版),2011,41(3):478-481.(Du Z W,Yang Y J,Sun Y X,et al.Hybrid ant colony algorithm based on mutual information and its application to traveling salesman problem.Journal of Southeast University(Natural Science Edition),2011,41(3):478-481.)
[6]  Shi X H,Liang Y C,Lee H P,et al.Particle swarm optimization-based algorithms for TSP and generalized TSP.Information Processing Letters,2007,103(5):169-176.
[7]  易云飞,林郭隆,董文永等.一种基于粒子优势分析的异步混合粒子群算法.小型微型计算机系统,2015,36(6):1379-1383.(Yi Y F,Lin G L,Dong W Y,et al.A Hybrid particle swarm optimization algorithm based on asynchronous advantage analysis of particle.Journal of Chinese Computer Systems,2015,36(6):1379-1383.)
[8]  刘 波,蒙培生.采用基于模拟退火的蚁群算法求解旅行商问题.华中科技大学学报(自然科学版),2009,37(11):26-30.(Liu B,Meng P S.Simulated annealing-based ant colony algorithm for traveling salesman problems.Journal of Huazhong University of Science and Technology (Nature Science Edition),2009,37(11):26-30.)
[9]  Chen S M,Chien C Y.Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques.Expert Systems with Applications,2011,38(12):14439-14450.
[10]  于宏涛,高立群,韩希昌.求解旅行商问题的离散人工萤火虫算法.华南理工大学学报(自然科学版),2015,43(1):126-131.(Yu H T,Gao L Q,Han X C.Discrete artificial firefly algorithm for solving traveling salesman problems.Journal of South China University of Technology(Natural Science Edition),2015,43(1):126-131.)
[11]  罗雪晖,杨 烨,李 霞.改进混合蛙跳算法求解旅行商问题.通信学报,2009,30(7):130-135.(Luo X H,Yang Y,Li X.Modified shuffled frog-leaping algorithm to solve traveling salesman problem.Journal on Communications,2009,30(7):130-135.)
[12]  吴新杰,王静文,黄国兴等.一种求解旅行商问题的改进蛙跳算法.小型微型计算机系统,2015,36(5):1078-1081.(Wu X J,Wang J W,Huang G X,et al.Improved shuffled frog leaping algorithm for solving traveling salesman problems.Journal of Chinese Computer Systems,2015,36(5):1078-1081.)
[13]  Osaba E,Yang X S,Diaz F,et al.An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems.Engineering Applications of Artificial Intelligence,2016,48:59-71.
[14]  王勇臻,陈 燕,张金松.用于求解旅行商问题的多策略离散型和声搜索算法.华南理工大学学报(自然科学版),2016,44(1):131-138.(Wang YZ,Chen Y,Zhang JS.Multi-strategy discrete harmony search algorithm for solving traveling salesman problem.Journal of South China University of Technology(Natural Science Edition),2016,44(1):131-138.)
[15]  张鑫龙,陈秀万,肖 汉等.一种求解旅行商问题的新型帝国竞争算法.控制与决策,2016,31(4):586-592.(Zhang X L,Chen X W,Xiao H,et al.A new imperialist competitive algorithm for solving TSP problem.Control and Decision,2016,31(4):586-592.)
[16]  Ouaarab A,Ahiod B,Yang X S.Discrete cuckoo search algorithm for the travelling salesman problem.Neural Computing & Applications,2014,24(7-8):1659-1669.
[17]  Ouaarab A,Ahiod B,Yang X S.Random-key cuckoo search for the travelling salesman problem.Soft Computing,2015,19(4):1099-1106. 
[18]  Yang X S,Deb S.Cuckoo search via Lévy flights.In:World Congress on Nature & Biologically Inspired Computing.Coimbatore,India:IEEE,2009:210-214.
[19]  王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法.软件学报,2013,24(11):2687-2698.(Wang LJ,Yin YL,Zhong YW.Cuckoo search algorithm with dimension by dimension improvement.Journal of Software,2013,24(11):2687-2698.)
[20]  张永韡,汪 镭,吴启迪.动态适应布谷鸟搜索算法.控制与决策,2014,29(4):617-622.(Zhang Y W,Wang L,Wu Q D.Dynamic adaptation cuckoo search algorithm.Control and Decision,2014,29(4):617-622.)
[21]  王李进,钟一文,尹义龙.带外部存档的正交交叉布谷鸟搜索算法.计算机研究与发展,2015,52(11):2496-2507.(Wang L J,Zhong Y W,Yin Y L.Orthogonal crossover cuckoo search algorithm with external archive.Journal of Computer Research and Development,2015,52(11):2496-2507.)
[22]  贾云璐,刘 胜,宋颖慧.基于种群特征反馈的布谷鸟搜索算法.控制与决策,2016,31(6):969-975.(Jia Y L,Liu S,Song Y H.Cuckoo search algorithm based on swarm feature feedback.Control and Decision,2016,31(6):969-975.)
[23]  马 卫,孙正兴.采用搜索趋化策略的布谷鸟全局优化算法.电子学报,2015,43(12):2429-2439.(Ma W,Sun Z X.A global cuckoo optimization algorithm using coarse-to-fine search.Acta Electronica Sinica,2015,43(12):2429-2439.)
[24]  Escario J B,Jimenez J F,Giron-Sierra J M.Ant colony extended:Experiments on the travelling salesman problem.Expert Systems with Applications,2015,42(1):390-410.
[25]  Zhang H G,Zhou J.Dynamic multiscale region search algorithm using vitality selection for traveling salesman problem.Expert Systems with Applications,2016,60:81-95.

相似文献/References:

备注/Memo

备注/Memo:
 基金项目:福建省自然科学基金(2015J01233),福建省教育厅项目(JAT160143,JA12105)
收稿日期:2017-07-30
*通讯联系人,E-mail:linmin@fafu.edu.cn
更新日期/Last Update: 2017-09-25