基因重组算法设计及多目标旅行商问题求解

Gene Recombination Algorithm Designed for Solving Multi-objective Traveling Salesman Problem

遗传算法等启发式算法在求解旅行商问题时,存在收敛速度较慢、容易出现过早收敛及算法计算效率较低的问题。在模式理论基础上,提出一种新的基因重组算法。根据优良基因模式,设计模式重组算子,运用重构及进化规划的思想设计算法的个体重构算子和个体选择算子。建立一个多目标旅行商问题模型,分析每一轮计算旅行路线适应度值的差异性,采用熵值法确定路程和费用权重。系列实验表明,基因重组算法在求解多目标旅行商问题时,计算效率远高于比较的算法,收敛速度和求解精度也较一般启发式算法有明显改善。

Heuristic algorithms such as genetic algorithm have such disadvantages as low convergence speed,premature convergence,and low efficiency of computation.On the basis of schema theorem,this paper proposes a new algorithm of gene recombination.Furthermore,it designs the schema recombination operator according to the fine gene schema,and constructs the individual reconstruction operator and selection operator by means of ideas of reconstruction and evolutionary programming.Then,a model of multi-objective traveling salesman problem is established,which confirms the weights of distance and cost by using the entropy method through analyzing the fitness diversity of individuals in each generation.A series of experiments with 30 nodes show that the computation efficiency of GRA is much higher than the compared algorithms,and that the convergence speed and solution accuracy are also improved greatly.