一种基于免疫遗传的多路搜索蚁群动态路径诱导算法

An Ant Colony Dynamic Route Guidance of Multi-route Searching Based on Immune Genetic

在交通路径诱导过程中,为了优化出行者的路径选择,提出一种用免疫遗传算法与蚁群系统算法相互融合的算法,主要利用了蚁群系统算法的动态性、正反馈性和分布式计算的优点;同时兼容了免疫遗传算法的全局搜索能力以及容易和其他算法相结合等特点.蚁群系统算法的动态性能够满足交通道路动态变化的各种因素,但是蚁群系统算法固有的缺点是容易陷入局部最优和进化速度缓慢,为了改善蚁群系统算法陷入局部最优的缺点,采用免疫遗传算法的全局搜索的思想来对蚁群系统算法进行改进,避免了蚁群系统算法陷入局部最优的缺点.为了提高算法的进化速度,本文提出了基于多路搜索的蚁群系统算法,能够更好地加快收敛速度,满足交通动态变化的需要,并且满足出行者的需要.在算法的研究过程中,进行了两部分实验对算法进行了论证,在eil51问题中,算法与其它算法相比证明可以得到更优的解;在MapX环境下模拟现实交通状况,运用算法寻找最佳路径,证明了本文提出的算法能够在实际的道路状况中找到满足出行者需求的道路.

In the process of traffic route guidance,in order to optimize the traveler′s route choice,This paper presents a genetic algorithm with immune system algorithm and ant colony algorithm for merging,mainly making use of the advantage of the dynamic nature of ant colony system algorithm,positive feedback and distributed computing;Meanwhile compatible with the global search capability of the immune genetic algorithm and conmbine with other algorithms easily.The dynamics of ant colony system algorithm can meet the dynamic changes of the various factors of traffic roads,However,the inherent disadvantage of ant colony system algorithm is easy to fall into local optimization and evolve slowly,in order to improve the shortcoming of the local optimum of ant colony system algorithm,using the global search of immune genetic to avoid the shortcoming of the local optimum of ant colony system algorithm.In order to improve the speed of algorithm evolution,this paper presents ant system algorithm based on multi-search,to speed up the convergence better and met the needs of dynamic changes of traffic,meet the needs of travelers.In the research process of the algorithm,the paper has carried out two experiments on the algorithm.In the eil51 problem,algorithm compared with other algorithms can find out a better path.Menwhile,using MapX simulate real traffic environment to use of algorithm to look for a better path,show that the proposed algorithm can find a better path that can satisfied travelers′s needs in the actual road condition.