您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

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

• • 上一篇    下一篇

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

王峰1,2,曼媛3,王幸乐4   

  1. 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 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)

1011

摘要： 求解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
[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] 陈晶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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发