遗传算法在网络最短路径问题上的应用

将网络最短路径问题抽象为求最小生成树问题,分析了最小生成树在解决实际问题时的局限性,引入了节点的度的概念;针对一般遗传算法在求解某些工程问题时存在的一些不足,提出了用量化约束条件来改进适应值函数、节点与度约束相结合编码的二进制编码方式、基于节点域的交叉和变异运算的策略.通过对公路交通网络的仿真表明,采用一般遗传算法与普通遗传算法分别求解,数值计算结果证明了改进后的遗传算法的可行性.

The Application of Genetic Algorithm on the Shortest Path Problem of Networks

The shortest path problem of network is abstracted to a minimum spanning tree problem and the limitations of the minimum spanning tree are analyzed.The notion of the node degree is introduced.To overcome the shortcomings of simple genetic algorithm in some engineering projects,the quantitative constraint rule is used to improve the fitness function,the binary coding mode,and the crossover and mutation operation strategy based on the node field.Through the modeling and simulation of a road transportation network,the simple algorithm and improved algorithm are used respectively to solve road transportation network problems and the results show the feasibility of the improved genetic algorithm.