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

N-shortest paths retrieval algorithm based on artificial immunity

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

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 infor- mation 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 ob- tain 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.