基于演化计算的动态最短路问题

基于演化计算的动态最短路问题 Dynamic Shortest Path Problem Based on Evolutionary Computation 陈盛双 1 2 3 first-author 胡晓林 1 2 3 许万洪 1 2 3 黄樟灿 1 2 3 武汉理工大学理学院,湖北,武汉,430070 武汉理工大学理学院,湖北,武汉,430070 武汉理工大学汽车工程学院,湖北,武汉,430070 武汉理工大学汽车工程学院,湖北,武汉,430070 武汉理工大学管理学院,湖北,武汉,430070 武汉理工大学管理学院,湖北,武汉,430070 提出了一类基于时间变权的动态最短路问题 ,给出了其详细的数学描述 ,扩展了图论中关于最短路问题的概念 ;并设计了适合该问题的编码方式和杂交、变异方式 ,给出了基于演化计算的求解框架 ,其主要特点是染色体变长 ,且首尾基因固定 .最后针对一个简单实例进行了仿真和分析 ,研究结果表明 ,该算法可以获得良好的效果 . We firstly puts forward a kind of dynamic shortest path problem, represents the detailed mathematical description, and so extends the concept of the shortest path problem in graph theory. The proper coding method, crossover method and mutation method are designed to solve it. The main features of the solution framework based on Evolutionary Computation （EC） are that the lengths of chromosomes are variable, and the first and the last gene on it are both fixed already. Some simulation studies and analyses for a simple case are performed at the end of this paper. The results show that EC can be satisfied to such problems. 动态最短路 演化计算 变长染色体 TP301.6 国家自然科学基金资助项目 （ 70 0 710 42;60 0 73 0 43 ） 2001-03-01 2021-04-01 3