JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (9): 35-40.doi: 10.6040/j.issn.1671-9352.1.2015.048

Previous Articles     Next Articles

N-shortest paths retrieval algorithm based on artificial immunity

WANG Feng1,2, MAN Yuan3, WANG Xing-le4   

  1. 1. College of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, Henan, China;
    2. College of Engineering, The Ohio State University, Columbus 43210, Ohio State, USA;
    3. China Family News, Beijing 100054, China;
    4. Henan Radio Transmitting Center, Zhengzhou 450001, Henan, China
  • Received:2015-11-14 Online:2017-09-20 Published:2017-09-15

PDF (PC)

1012

Abstract: To solve the N-shortest paths retrieval problem, the implementations of traditional approaches are complicated and often cost large computational resources. To address these concerns, a novel retrieval algorithm based on artificial immunity was proposed. The problem was solved through the immune evolutionary process of antibody population, by borrowing the diversity of antibody, clone selection, hyper-mutation, immune memory from immune system and information feedback mechanism from ant colony algorithm. Experiments were conducted on different data sets, compared with traditional Yen method and Dijkstra-based method. Experimental results show that the proposed algorithm can obtain the global best paths set with high success rate and good time performance. It is insensitive to the size and structure of graphs as well as the number of paths to be solved.

Key words: artificial immunity, path optimization, N-shortest paths retrieval

CLC Number: 

  • TP301
[1] BERCLAZ J, FLEURET F, TURETKEN E, et al. Multiple object tracking using k-shortest paths optimization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(9): 1806-1819.
[2] 叶金平, 朱征宇, 王丽娜, 等. 智能交通中的高效多准最短路径混合算法[J]. 计算机应用研究, 2011, 28(9): 3301-3304. YE Jinping, ZHU Zhengyu, WANG Lina, et al. Efficient hybrid algorithm for multi-shorter-path searching in ITS[J]. Application Research of Computers, 2011, 28(9): 3301-3304.
[3] XU Wangtu, HE Shiwei, SONG Rui, et al. Finding the k shortest paths in a schedule-based transit network[J]. Computers & Operations Research, 2012, 39(8): 1812-1826.
[4] 吴晓倩, 胡学钢. 基于N-最短路径的中文分词技术研究[J]. 安徽理工大学学报(自然科学版), 2014, 34(1): 72-75. WU Xiaoqian, HU Xuegang. Research on Chinese word segmentation based on N-shortest path[J]. Journal of Anhui University of Science and Technology(Natural Science), 2014, 34(1): 72-75.
[5] YEN J Y. Finding the k shortest loopless paths in a network[J]. Management Science, 1971, 17: 712-716.
[6] HADJICONSTANTINOU E, CHRISTOFIDES N. An efficient implementation of an algorithm for finding k shortest simple paths[J]. Networks, 1999, 34(2): 88-101.
[7] MARTINS E Q V, PASCOAL M M B. A new implementation of Yens ranking loopless paths[J]. 4OR-Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2003, 1(2): 121-134.
[8] 王峰, 游志胜, 曼丽春, 等. Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用[J]. 计算机应用研究, 2006, 23(9): 203-208. WANG Feng, YOU Zhisheng, MAN Lichun,et al. Application of Dijkstra and Dijkstra-based N-shortest-paths algorithm to intelligent transportation systems[J]. Application Research of Computers, 2006, 23(9): 203-208.
[9] RODITTY L. On the k-simple shortest paths problem in weighted directed graphs[C] //Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms(SODA). Philadelphia: SIAM, 2007: 920-928.
[10] HERSHBERGER J, MAXEL M, SURI S. Finding the K shortest simple paths: a new algorithm and its implementation[J]. ACM Transactions on Algorithms, 2007, 3(4): 45:1-45:19.
[11] 高松, 陆锋. K则最短路径算法效率与精度评估[J]. 中国图象图形学报, 2009, 14(8): 1677-1683. GAO Song, LU Feng. The Kth shortest path algorithms: accuracy and efficiency evaluation[J]. Journal of Image and Graphics, 2009, 14(8): 1677-1683.
[12] CHAUHAN P, SINGH N, CHANDRA N. A review on intrusion detection system based on artificial immune system[J]. International Journal of Computer Applications, 2013, 63(20): 36-40.
[13] DASGUPTA D, YU S H, NINO F. Recent advances in artificial immune systems: models and applications[J]. Applied Soft Computing, 2011, 11(2): 1574-1587.
[14] 刘大有, 谷方明, 王生生. 基于人工免疫核聚类的支持向量数据描述方法[J]. 吉林大学学报(工学版), 2011, 41(5): 1369-1373. LIU Dayou, GU Fangming, WANG Shengsheng. Support vector data description based on artificial immune kernel clustering[J].Journal of Jilin University(Engineering and Technology Edition),2011, 41(5): 1369-1373.
[15] 戚玉涛, 刘芳, 常伟远, 等. 求解多目标问题的Memetic免疫优化算法[J]. 软件学报, 2013, 24(7): 1529-1544. QI Yutao, LIU Fang, CHANG Weiyuan, et al. Memetic immune algorithm for multiobjective optimization[J]. Journal of Software, 2013, 24(7): 1529-1544.
[16] YANG Hua, LI Tao, HU Xinlei, et al. A survey of artificial immune system based intrusion detection[J]. The Scientific World Journal, 2014, 2014: 1-11.
[17] 张韬, 丁永生, 郝矿荣, 等. 基于人工免疫系统的故障诊断方法及其应用[J]. 系统仿真学报, 2014, 26(4): 830-835. ZHANG Tao, DING Yongsheng, HAO Kuangrong. Artificial immune system based fault detection approach with application to carbon fiber stretching process[J]. Journal of System Simulation, 2014, 26(4): 830-835.
[18] DORIGO M, BLUM C. Ant colony optimization theory: a survey[J]. Theoretical Computer Science, 2005, 344(2-3): 243-278.
[19] CHAKRABORTY S. Ant colony system: a new concept to robot path planning[J]. International Journal of Hybrid Information Technology, 2013, 6(6): 11-30.
[20] YAN Q. An implementation of k-shortest path algorithm[CP/OL].[2015-05-25]. http://code.google.com/p/k-shortest-paths/.
[1] LIU Li-zhao, YU Jia-ping, LIU Jian, LI Jun-yi, HAN Shao-bing, XU Hua-rong, LIN Huai-chuan, ZHU Shun-zhi. Secure storage addressing algorithm for large data based on quantum radiation field [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 65-74.
[2] SONG Xing-shen, YANG Yue-xiang, JIANG Yu. Efficient multiple sets intersection using SIMD instructions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(3): 54-62.
[3] . Graph model based trustworthy resource scheduling algorithm in cloud environment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 63-74.
[4] ZHU Dan, XIE Xiao-yao, XU Yang, XIA Meng-ting. Evaluation method for network security level based on cloud model and Bayesian feedback [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 53-62.
[5] SHI Pei-yun, GAO Xing-bao. Individual strength-based multi-objective immune algorithm with adaptive differential evolution [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(11): 1-10.
[6] WANG Xia, ZHANG Qian, LI Jun-yu, LIU Qing-feng. Triadic concept analysis based on rough set theory [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(7): 37-43.
[7] MA Lan, LI Wei-an, YIN Tian-yi. Improved particle swarm optimization for flight conflict resolution based on variable neighborhood search [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(1): 23-28.
[8] DU Hong-le, ZHANG Yan, ZHANG Lin. Intrusion detection on imbalanced dataset [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(11): 50-57.
[9] XIE Jian-min, YAO Bing, ZHAO Ting-gang. An algorithm and its implementation for odd-elegant labeling of general sun graph Sm,n [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 79-85.
[10] QIN Li-zhen, LI Jin-hai, WANG Yang-yang. Concept lattice based knowledge discovery and its application to analysis of employment data in universities [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(12): 58-64.
[11] LI Jing-wen, JIA Xi-bei, DONG Wei, LI Xiao-hui, YAN Guang-hui. The algorithm for adjacent-vertex-distinguishing total coloring of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 14-21.
[12] ZHANG Chun-ying, WANG Li-ya, LIU Bao-xiang. Dynamic reduction theory for interval concept lattice based on covering and its realization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 15-21.
[13] LIU Jing-Lei, WANG Ling-Ling, ZHANG Wei. Generation algorithm for the role assigning lattice [J]. J4, 2009, 44(11): 52-56.
[14] QU Shouning, FU Aifang, LI Jing, LIU Jing. Forecasting stock market risks based on the flexible neural tree [J]. J4, 2009, 44(11): 44-47.
[15] YANG Yu-Zhen, LIU Pei-Yu, SHU Zhen-Fang, QIU Ye. Research of an improved information gain methodusing distribution information of terms [J]. J4, 2009, 44(11): 48-51.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd