必经点最短路径问题模型及相应遗传算法研究

Models and genetic algorithm for designated-points shortest path problem

根据军事运输在路径寻优方面的特殊需求,将必经点最短路径问题分为三类,建立各类问题的数学模型。以分类保序最短路径为例,设计相应的改进遗传算法。该遗传算法构造了独特的适应度函数,使包含较多必经点的染色体能够优先被选择进入下一代种群。通过节点保序算子的引入,保证相关节点之间存在特定的先后次序,并提出一种新的引入必经点变异算子,提高算法的全局搜索能力,加快收敛速度。仿真结果验证了算法的有效性。

On the basis of the special requirements of military transportation in routing, the designated- points shortest paths problem is divided into three categories and their mathematics models are established. The improved genetic algorithm for the grouped and order-preserving designated-points shortest paths problem is presented. The algorithm constructs a unique fitness function, which makes that a chromosome with shorter distance and more designated-points would be selected to rebirth into next generation more easily. An order-pre- serving operation is proposed to ensure that some particular points are connected based on the determined order. By using novel mutation, the global search capability and convergence speed are improved. The experimental re- suits show the effectiveness of the proposed algorithm.