论文部分内容阅读
求解N最短路径检索问题的传统算法通常比较复杂,计算量较大,针对这个问题提出了一种基于人工免疫的求解算法。借鉴免疫系统的抗体多样性机制、克隆选择、高频变异、免疫记忆以及蚁群算法的信息反馈等原理,通过抗体种群的免疫进化实现对N最短路径检索问题的求解。在多个测试图上与传统Yen方法和基于Dijkstra的方法进行了对比实验,结果表明该算法能以较高的成功率正确地求得全局最优路径集,对图的尺寸和结构以及待求路径数量较不敏感,而且具有很好的时间性能。
Traditional algorithms for solving the N shortest path search problem are usually complicated and computationally expensive. Aiming at this problem, a new artificial immune algorithm is proposed. According to immune system antibody diversity mechanism, clonal selection, high frequency mutation, immune memory and ant colony algorithm information feedback and other principles, through the immune evolution of antibody population to achieve the N shortest path retrieval problem solving. The experimental results of traditional Yen method and Dijkstra method based on multiple test graphs show that the algorithm can obtain the optimal global path set with higher success rate, and the size and structure of the graph, The number of paths is less sensitive and has good time performance.