启发式交叉求解TSP问题的混合遗传算法  

Hybrid genetic algorithm with developmental crossover operator for solving TSP

作　　者：宋海洲[1] 

机构地区：[1]华侨大学数学系,福建泉州362021

出　　处：《系统工程学报》2005年第6期625-629,共5页Journal of Systems Engineering

基　　金：福建省自然科学基金计划资助项目(Z0511028)

摘　　要：在给出度约束最小生成树的快速生成方法的基础上,设计了一种启发式交叉求解TSP问题的混合遗传算法.该算法在交叉操作的设计上,与其他遗传算法有本质的不同,该交叉操作是在不违反度约束和不形成圈的前提下,每次从父代基因所拥有的边中加入权最小的边,从而形成子代.利用该算法得到了TSP CHN144问题迄今为止最好的解.Based on a fast approximation algorithm proposed by the author for the degree-constrained minimum spanning tree problem, a hybrid genetic algorithm with heuristic crossover operator for solving Traveling Salesman Problem （TSP） is given. This algorithm is different from other one on designing crossover operator. The kernel idea of the crossover operator of the algorithm is given as follows ： The edge which has the minimal weight is added form parents if the added edge will not disobey degree-constraint and will not form a circle, these added edges form child. The algorithm is applied to solving the TSP CHN144 problem.

关 键 词：TSP 遗传算法 初始种群 度约束最小生成树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]