基于改进郭涛算法的TSP问题求解

Based on improved GT algorithm for TSP

郭涛算法可能是目前求解TSP问题最快的演化算法[1],其算法的核心在于Inver-over算子的设计,但在城市规模超过80时,该算子寻找全局最优解的能力就会下降。将原Inver-over算子的线性逆转改为环形逆转,改进逆转方式后,被逆转的基因片段可以包括整个染色体,这样能有效地防止解的早熟。同时,在原算法的基础上,引入了映射模块,能使父代中好的基因片段得到遗传,使好的基因片段能让更多的染色体所享有,不会因为父代被替代而让好的基因模式丢失。实验表明:改进后的算法增强了原Inver-over算子对最优解的搜索能力,并且对TSPLIB中大部分实例均可搜索到最优解。

Guo Tao algorithm may be the most quickly evolution algorithm to solve the TSP issue at present. The core of this algorithm is the design ofinver-over operator, but while exceeding 80 in city size, the ability of the operator searching optimum solver will drop. The linear-reverse of the inver-over operator was changed into annular-reverse, after improving the reverse style, the reversed genetic fragment can cover the whole chromosome. This can prevent solver from early maturing. Meanwhile, the gene shine module was introduced to original algorithm, which can make parent＇s good genetic fragment get heredity, and make more chromosomes enjoy good genetic fragment. Good gene mode of parents will be not losing while their parent is substituted. The test shows that the improved algorithm has strengthened the ability of original inver-over operator searching the optimum solver. And it can search optimum solver for most instances in TSPLIB.