Computer Science ›› 2017, Vol. 44 ›› Issue (7): 215-220.doi: 10.11896/j.issn.1002-137X.2017.07.038

Previous Articles     Next Articles

Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm

MAN Zhen-zhen, YU Shi-ming and HE De-feng   

  • Online:2018-11-13 Published:2018-11-13

Abstract: Through the analysis of shortest path problem on network routing,we built the network model of the shortest path routing problem by using ITO algorithm to get the lowest cost route optimization target.To speed up ITO lowest routing algorithm’s convergence speed,the proposed algorithm involves cost inspired factor in the state transition strategy,and hence improves path weight updating rules.The convergence speed and optimization capability are enhanced simultaneously by introducing the method of population cross and using the information exchange between populations.A 2-opt operator-based inversion operator is adopted to optimize the algorithm and to avoid falling into local optimal solution.The astringency of the algorithm was also analyzed systematically.The case study illustrates that the improved algorithm is effective to speed up the convergence speed and enhance optimization capability.

Key words: Route optimization,Shortest path,ITO algorithms,Network optimization

[1] ZOU E,LIU Z H,FANG S Y,et al.Research on Multicast Routing Optimization Based on Chaos Genetic Algorithm[J].Computer Engineering,2011,7(3):155-157.(in Chinese) 邹恩,刘泽华,方仕勇,等.基于混沌遗传算法的组播路由优化研究[J].计算机工程,2011,7(3):155-157.
[2] FLEISCHER M.The Measure of Pareto Optima:Applications to Multiobjective Metaheuristics[M]∥Evolutionary Multiobjective Optimization.Berlin,Germany:Springer-Verlag,2003:519-533.
[3] WHILE L,HINGSTON P,BARONE L,et al.A Faster algo-rithm for calculating hypervolume[J].IEEE Transactions on Evolutionary Computation,2006,10(1):29-38.
[4] BEUME N,RUDLOPH G.Faster Smetric Calculation by Considering Dominated Hyper volume as Klee’s Measure problem[C]∥Proc.of the 2nd IASTED Conference on Computational Intelligence.Anaheim,USA:ACTA Press,2006.
[5] ZHANG Y,ZHANG M,LIANG Y C.Application of an Improved Dijkstra Algorithm in Multicast Routing Problem[J].Computer Science,2009,6(8):205-207.(in Chinese) 张毅,张猛,梁艳春.改进的最短路径算法在多点路由上的应用[J].计算机科学,2009,6(8):205-207.
[6] DONG W,ZHANG D,WEICHENG Z,et al.The Simulation Optimization Algorithm Based on the Ito Process[C]∥Advanced Intelligent Computing Theories and Applications with Aspects of Contemporary Intelligent Computing Techniques.2007:115-124.
[7] DONG W,LEI M,YU R.A New Evolutionary Algorithms for Global Numerical Optimization Based on Ito Process[M]∥Computational Intelligence and Intelligent Systems:5th International Symposium(ISICA 2010).Wuhan,China,Springer,Berlin,Heidelberg,2010.
[8] DONG W,YU R,LEI M.Merging the Ranking and Selection into ITO Algorithm for Simulation Optimization[C]∥5th International Symposium Computational Intelligence and Intelligent Systems(ISICA 2010).Wuhan,China,Springer,2010.
[9] DONG W Y,ZHANG W S,YU R G.Convergence and Runtime Analysis of ITO Algorithm for One Class of Combinatorial Optimization[J].Chinese Journal of Computers,2011,4(4):636-646.(in Chinese) 董文永,张文生,于瑞国.求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J].计算机学报,2011,4(4):636-646.
[10] YI Y F,CAI Y L,DONG W Y,et al.Improved ITO Algorithm for Multiobjective Real-time Vehicle Routing Problem with Customers’ Satisfaction[J].Acta Electronica Sinica,2015,3(10):2053-2061.(in Chinese) 易云飞,蔡永乐,董文永,等.求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J].电子学报,2015,3(10):2053-2061.
[11] YI Y F,DONG W Y,LIN X D,et al.The Improved ITO Algorithm to Solve the Vehicle Routing Problem with Soft Time Windows and Its Convergence Analysis[J].Acta Electronica Sinica,2015,3(4):658-664.(in Chinese) 易云飞,董文永,林晓东,等.求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J].电子学报,2015,43(4):658-664.
[12] WANG H G,YU S M.Improved ITO Algorithm for SolvingVRP[J].Computer Science,2015,2(9):253-256.(in Chinese) 王浩光,余世明.求解车辆路径问题的改进伊藤算法[J].计算机科学,2015,2(9):253-256
[13] ZHAO Z Y,LI Y X,YU F.Artificial Bee Colony Algorithm Based on ITO Algorithm[J].Computer Science,2014,1(6A):29-32.(in Chinese) 赵志勇,李元香,喻飞.基于伊藤算法的改进人工蜂群算法[J].计算机科学,2014,1(6A):29-32.
[14] YI Y F,CAI Y L,DONG W Y,et al.Improved ITO Algorithm for Solving the CVRP[J].Computer Science,2013,0(5):213-216.(in Chinese) 易云飞,蔡永乐,董文永,等.求解带容量约束的车辆路径问题的改进伊藤算法[J].计算机科学,2013,0(5):213-216.
[15] MUNEMOTO M,TAKAI Y,SATO Y.A Migration Scheme for the Genetic Adaptive Routing Algorithm[C]∥IEEE International Conference on Systems,Man,and Cybernetics.1998:2774-2779.
[16] INAGAKI J,HASEYAMA M,KITAJIMA H.A Genetic Algorithm for Determining Multiple Routes and Its Applications[C]∥Proceedings of IEEE International Symposium on Circuits and Systems.1999:137-140.
[17] AHN C W,RAMAKRISHNA R S.A Genetic Algorithm forShortest Path Routing Problem and the Sizing of Populations[J].IEEE Transactions on Evolutionary Computation,2002,6(6):566-579.
[18] SUN B L,LI L Y,CHEN H.Shortest Path Routing Optimization Algorithms Based on Genetic Algorithms[J].Computer Engineering,2005,1(6):142-144.(in Chinese) 孙宝林,李腊元,陈华.基于遗传算法的最短路径路由优化算法[J].计算机工程,2005,1(6):142-144.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .