改进量子蚁群算法在动态路径诱导中的应用

Application of an improved quantum ant colony algorithm in dynamic route guidance

针对动态路径诱导中寻优算法收敛速度慢,易陷入局部最优解的不足,提出了一种改进的量子蚁群算法(IQACA)。首先,建立了考虑交叉口和路段耗费的动态路网模型,并建立了时间最优路径模型。借鉴量子蚁群算法的寻优策略,改进的量子蚁群算法通过将量子比特相位取值范围缩小的方法,提高概率幅的密度;采用Hadamard门变异机制,实现量子比特概率幅值的位置和大小的变化,扩大了种群多样性,增加了全局最优解搜索的概率。将IQACA算法应用到实际路网的动态路径诱导中,并与蚁群算法、量子蚁群算法进行对比分析,实验结果表明,改进的IQACA算法适用于求解时间最优路径问题,不仅具有很好的收敛性能还能够较快的得出时间最优路径。

To solve the problems of slow convergence speed, easily falling into local optimal solution in optimizationalgorithm of dynamic route guidance, an improved quantum ant colony algorithm （IQACA） is proposed in this pa-per. Firstly, a dynamic road network model considering road intersection and road-consuming and a time optimalpath model are established. Taking the quantum ant colony optimization algorithm strategy as reference, the im-proved quantum ant colony algorithm increases the probability amplitude density by narrowing the range of the qubitphase. Hadamard gate mutation mechanism is introduced to make the changes of the qubit probability amplitude＇ sposition and size, which expands population diversity and increases the searching probability of globally optimal so-lution. IQACA is applied to the dynamic route guidance of an actual road network, and is analyzed comparing withthe ant-colony algorithm and quantum ant colony algorithm. The simulation shows that IQACA is applicable to sol-ving the problem of time optimal path, which not only has good convergence performance but also obtains the timeoptimal route quickly.