基于人工免疫的N最短路径检索算法

doi:10.6040/j.issn.1671-9352.1.2015.048

山东大学学报（理学版） ›› 2017, Vol. 52 ›› Issue (9): 35-40.doi: 10.6040/j.issn.1671-9352.1.2015.048

基于人工免疫的N最短路径检索算法

王峰^1,2,曼媛³,王幸乐⁴

1. 河南工业大学信息科学与工程学院, 河南郑州 450001;2.俄亥俄州立大学工程学院, 俄亥俄州哥伦布 43210;3. 中国家庭报社, 北京 100054;4.河南省无线发射传输管理中心, 河南郑州 450001

收稿日期:2015-11-14 出版日期:2017-09-20 发布日期:2017-09-15
作者简介:王峰(1975— ),男,博士,副教授,研究方向为智能信息处理、模式识别、智能交通、人工智能等. E-mail: wangfeng_-scu@aliyun.com
基金资助:
国家自然科学基金资助项目(U1204617);国家留学基金资助项目(201309895002);河南省科技攻关计划重点项目(122102310303);河南省教育厅科学技术研究重点项目(14B520026);河南省高等学校青年骨干教师资助项目(2014GGJS-060);郑州市科技局自然科学项目(20141364);河南工业大学青年骨干教师培育计划项目;河南工业大学博士基金资助项目(2010BS009)

N-shortest paths retrieval algorithm based on artificial immunity

WANG Feng^1,2, MAN Yuan³, WANG Xing-le⁴

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

摘要/Abstract

摘要： 求解N最短路径检索问题的传统算法通常比较复杂,计算量较大,针对这个问题提出了一种基于人工免疫的求解算法。借鉴免疫系统的抗体多样性机制、克隆选择、高频变异、免疫记忆以及蚁群算法的信息反馈等原理,通过抗体种群的免疫进化实现对N最短路径检索问题的求解。在多个测试图上与传统Yen方法和基于Dijkstra的方法进行了对比实验,结果表明该算法能以较高的成功率正确地求得全局最优路径集,对图的尺寸和结构以及待求路径数量较不敏感,而且具有很好的时间性能。

关键词: N最短路径检索, 路径优化, 人工免疫

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

中图分类号:

TP301

王峰,曼媛,王幸乐. 基于人工免疫的N最短路径检索算法[J]. 山东大学学报（理学版）, 2017, 52(9): 35-40.

WANG Feng, MAN Yuan, WANG Xing-le. N-shortest paths retrieval algorithm based on artificial immunity[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(9): 35-40.

参考文献

[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/.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于人工免疫的N最短路径检索算法

N-shortest paths retrieval algorithm based on artificial immunity

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

多维度评价

本文评价

推荐阅读 0

[1]	陈晶1, 刘亚斌2, 刘建东2, 赵黎1, 林青云1, 杜瑞颖1. 无线Mesh网络中基于人工免疫的容错拓扑控制[J]. J4, 2012, 47(9): 38-44.
[2]	郭晨1,梁家荣2,罗超3,彭硕1. 基于TLR异常检测系统的DC算法研究[J]. J4, 2012, 47(5): 93-97.
[3]	胡选子1, 谢存禧2. 基于人工免疫网络的机器人局部路径规划[J]. J4, 2010, 45(7): 122-126.