基于定向变异布谷鸟算法的配送路径问题

doi:10.11896/j.issn.1002-137X.2019.07.026

计算机科学 ›› 2019, Vol. 46 ›› Issue (7): 165-171.doi: 10.11896/j.issn.1002-137X.2019.07.026

基于定向变异布谷鸟算法的配送路径问题

刘晓珍¹,刘景森^1,2

(河南大学软件学院河南开封475004)¹
(河南大学智能网络系统研究所河南开封475004)²

收稿日期:2018-08-05 出版日期:2019-07-15 发布日期:2019-07-15
作者简介:刘晓珍(1992-),女,硕士,主要研究方向为智能算法,E-mail:liuzxhenu@163.com;刘景森(1968-),男,博士,教授,CCF会员,主要研究方向为智能算法、网络与信息安全等,E-mail:ljs@henu.edu.cn(通信作者)。
基金资助:
河南省重点研发与推广专项(182102310886),河南省科技攻关重点项目(162102110109)资助

Distribution Routing Problem Based on Cuckoo Search Algorithm with Directional Mutation

LIU Xiao-zhen¹,LIU Jing-sen^1,2

(College of Software,Henan University,Kaifeng,Henan 475004,China)¹
(Institute of Intelligent Networks System,Henan University,Kaifeng,Henan 475004,China)²

Received:2018-08-05 Online:2019-07-15 Published:2019-07-15

摘要/Abstract

摘要： 在货物配送路径规划问题中,为了保持基本布谷鸟算法中莱维飞行机制与偏好随机游动策略的特点,文中提出了基于定向变异的布谷鸟算法和求解配送路径问题的完整有效方法。首先采用快速排序法将实数编码个体的每一维元素映射成问题的城市编号,从而建立算法与问题模型之间的联系;然后运用邻域搜索法决定城市访问的次序,即通过各城市之间的距离寻找当前城市的邻近城市,以增强算法的收敛速度。同时,在算法局部搜索机制中,通过平均适应度函数将算法划分为双子群,然后针对不同的子群体采用相应的定向变异机制,从而使算法搜索具有目的性,以增强算法的局部搜索能力。对标准TSP数据库中测试算例的求解实验结果表明,所提算法在各个算例中的求解偏差率均有明显降低,无论在最优值还是平均值的偏差率上都小于其他几种对比算法,对于路径规划问题的求解效果较优。

关键词: 变异策略, 布谷鸟算法, 快速排序法, 邻域搜索法, 路径规划问题

Abstract: In order to maintain the characteristics of the Lévy flight mechanism and the preference of the random walk strategy in the basic cuckoo search algorithm,this paper proposed a cuckoo search algorithm based on directional mutation to solve the distribution routing problem.Firstly,the quick sort method is used to map each dimensional element of a real-coded individual into the city numberthus to establish the connection between the algorithm and the problem mo-del.Then the neighboring-region search method is used to determine the city access order.In other words,it is to find the neighboring cities of the current city by the distance between cities so as to enhance the convergence speed of the algorithm.Meanwhile,in the algorithm local search mechanism,the average fitness function is used to divide the algorithm into two subgroups.Then the corresponding directional mutating mechanism is adopted according to different subgroups,so that the algorithm has purpose to search and the local search ability of the algorithm is enhanced.The experimental results of solution to the test case of the standard TSP database show that the deviation rate of the proposed algorithm has been significantly reduced in each case.The deviation rate of the algorithm is smaller than that of other comparison algorithms in both the optimal value and the average value,and its solution effect is better in the path planning problem.

Key words: Cuckoo search algorithm, Local search method, Mutation strategy, Path planning problem, Quick sort method

中图分类号:

TP301.6

刘晓珍,刘景森. 基于定向变异布谷鸟算法的配送路径问题[J]. 计算机科学, 2019, 46(7): 165-171. https://doi.org/10.11896/j.issn.1002-137X.2019.07.026

LIU Xiao-zhen,LIU Jing-sen. Distribution Routing Problem Based on Cuckoo Search Algorithm with Directional Mutation[J]. Computer Science, 2019, 46(7): 165-171. https://doi.org/10.11896/j.issn.1002-137X.2019.07.026

参考文献

[1]GOLDBERG D E.Genetic algorithm in search,optimization and machine learning [M].Boston: Addison-Wesley Longman Publishing Co.Inc.,1989.
[2]DORIGO M,MANIEZZO V,COLORNI A.Ant System:opti- mization by a colony of cooperating agents [J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics a Publication of the IEEE Systems Man & Cybernetics Society,1996,26(1):29-41.
[3]EBERHART R,KENNEDY J.A new optimizer using particle swarm theory[C]∥Proceedings of the Sixth International Symposium on Micro Machine and Human Science.1995:39-43.
[4]KENNEDY J,EBERHART R.Particle swarm optimization[C]∥ roceedings of IEEE International Conference on Neural Networks.1995:1942-1948.
[5]KIRKPATRICK S,GELATT C,VECCHI M.Optimization by simulated anealing [J].Science,1983,220:671-680.
[6]GLOVER F.Future Paths for integer programming and links to artificial intelligence [J].Computers and Operations Research,1986,13(5):535-549.
[7]YANG X S,DEB S.Cuckoo search via levy flight[C]∥Procee- dings of World Congress on Nature & Biologically Inspired Computing.India,Washington:IEEE Publications,2009:210-214.
[8]YANG X S,Deb S.Engineering optimization by cuckoo search [J].Int’l Journal of Mathematical Modeling and Numerical Optimization,2010,1(4):330-343.
[9]LI Y,MA L.A new metaheuristic cuckoo search algorithm [J].Systems Engineering,2012,30(8):64-69.(in Chinese)
李煜,马良.新型元启发式布谷鸟搜索算法[J].系统工程,2012,30(8):64-69.
[10]SURESH S,LAL S.An efficient cuckoo search algorithm based multilevel thresholding for segmentation of satellite images using different objective functions [J].Expert Systems with Applications,2016,58(C):184-209.
[11]CHAKRABORTY S,CHATTERJEE S,DEY N,et al.Modified cuckoo search algorithm in microscopic image segmentation of hippocampus [J].Microscopy Research & Technique,2017(10):1051-1072.
[12]ABD-ELAZIM S M,ALI E S.Optimal location of STATCOM in multimachine power system for increasing load ability by cuckoo search algorithm[J].International Journal of Electrical Power &Energy Systems,2016,80:240-251.
[13]CHITARA D,NIAZI K R,SWARNKAR A,et al.Cuckoo search optimization algorithm for designing of multimachine power system stabilizer[C]∥IEEE International Conference on Power Electronics,Intelligent Control and Energy Systems.IEEE,2017:1-6.
[14]NAIK M K,PANDA R.A novel adaptive cuckoo search algorithm for intrinsic discriminant analysis based face recognition [J].Applied Soft Computing,2016,38(C):661-675.
[15]MOHANTY P K,PARHI D R.Optimal path planning for a mobile robot using cuckoo search algorithm [J].Journal of Experimental & Theoretical Artificial Intelligence,2016,28(1／2):35-52.
[16]SANTILLAN J H,TAPUCAR S,MANLIGUEZ C,et al.Cuc- koo search via lévy flights for the capacitated vehicle routing problem [J].Journal of Industrial Engineering International,2017(1):1-12.
[17]PAULINE O,SIN H C,SHENG D D C V,et al.Design optimization of structural engineering problems using adaptive cuckoo search algorithm[C]∥International Conference on Control,Automation and Robotics.IEEE,2017:745-748.
[18]OUAARAB A,AHIOD B,YANG X S.Discrete cuckoo search algorithm for the travelling salesman problem [J].Neural Computing & Applications,2014,24(7／8):1659-1669.
[19]OUAARAB A,AHIOD B,YANG X S.Random-key cuckoo search for the travelling salesman problem [J].Soft Computing,2015,19(4):1099-1106.
[20]MA C,LIU J,YU F P.Research on cuckoo algorithm with simulated annealing [J].Journal of Chinese Computer Systems,2016,37(9):2029-2034.(in Chinese)
马灿,刘坚,余方平.混合模拟退火的布谷鸟算法研究[J].小型微型计算机系统,2016,37(9):2029-2034.
[21]LIN M,ZHONG Y W,LIU B X,et al.Genotype-phenotype cuckoo search algorithm for traveling salesman problem [J].Computer Engineering and Applications,2017,53(24):172-181.(in Chinese)
林敏,钟一文,刘必雄,等.基因-表现型的布谷鸟算法求解旅行商问题[J].计算机工程与应用,2017,53(24):172-181.
[22]JAFARZADEH H,MORADINASAB N,ELYASI M.An enhanced genetic algorithm for the generalized traveling salesman problem[J].Engineering,Technology & Applied Science Research,2017,7(6):2260-2265.
[23]LIU J.Applied research of hybrid genetic algorithm and simulated annealing algorithm in traveling salesman problem [D].Guangzhou:South China University of Technology,2014.(in Chinese)
刘锦.混合遗传算法和模拟退火算法在TSP中的应用研究[D].广州:华南理工大学,2014.
[24]BEAN J C.Genetic algorithms and random keys for sequencing and optimization[J].Informs Journal on Computing,1994,6: 154-160.
[25]WU H S,ZHANG F M,LI H,et al.Discrete wolf pack algorithm for traveling salesman problem [J].Control and Decision,2015(10):1861-1867.(in Chinese)
吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015(10):1861-1867.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于定向变异布谷鸟算法的配送路径问题

Distribution Routing Problem Based on Cuckoo Search Algorithm with Directional Mutation

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 0

[1]	臧睿, 刘笑笑. 分段加权布谷鸟算法及其应用 Segment Weighted Cuckoo Algorithm and Its Application 计算机科学, 2020, 47(6A): 119-123. https://doi.org/10.11896/JsJkx.190400036
[2]	张贵军, 王文, 周晓根, 王柳静. 基于动态策略的差分进化柔性车间优化调度 Dynamic Strategy-based Differential Evolution for Flexible Job Shop Scheduling Optimization 计算机科学, 2018, 45(10): 240-245. https://doi.org/10.11896／j.issn.1002-137X.2018.10.044
[3]	周雅兰,徐志. 多变异策略的自适应差分演化算法 Self-adaptive Differential Evolution with Multi-mutation Strategies 计算机科学, 2015, 42(6): 247-250. https://doi.org/10.11896/j.issn.1002-137X.2015.06.052
[4]	傅嗣鹏,乔俊飞,韩红桂. 基于锦标赛选择变异策略的改进差分进化算法及函数优化 Improved Differential Evolution Algorithm Based on Mutation Strategy of Tournament Selection for Function Optimization 计算机科学, 2013, 40(Z6): 15-18.
[5]	王丛佼,王锡淮,肖健梅. 基于动态自适应策略的改进差分进化算法 Improved Differential Evolution Algorithm Based on Dynamic Adaptive Strategies 计算机科学, 2013, 40(11): 265-270.