基于遗传算法的离散时间动态网络最短路径求解(英文)

Genetic Algorithm-Based Computation of the Shortest Path in Discrete-Time Dynamic Networks

采用遗传算法来求解不满足先进先出原则的动态网络中的最短路径问题,并采用所提出的随机A*算法解决了利用遗传算法求解最短路径问题时的最大障碍——初始种群的产生.最后以广州市电子地图为基础随机产生了一个不满足先进先出原则的动态网络(包括20000个节点,40000条边和144个时间间隔),来对所提出的算法进行验证.试验结果表明,遗传算法适合求解非常态且不满足先进先出原则的动态网络中的路径诱导问题.

In this paper, the genetic algorithm is adopted to compute the shortest path in the dynamic networks unsatisfying the first-in-first-out （FIFO） principle, and a random A^＊ algorithm is proposed to overcome the difficulty in obtaining the initial generation of the genetic algorithm. Then, based on the electronic map of Guangzhou city, a dynamic network containing 20000 nodes, 40000 links and 144 time intervals, which does not satisfy the FIFO principle, is proposed to test the proposed algorithm. Experimental results indicate that the genetic algorithm is suitable for the solving of transportation guidance problem in the dynamic networks unsatisfying the FIFO principle and possessing unstable states.