| 启发式交叉求解TSP问题的混合遗传算法 |
| |
| 引用本文： | 宋海洲.启发式交叉求解TSP问题的混合遗传算法[J].系统工程学报,2005,20(6):625-629. |
| |
| 作者姓名： | 宋海洲 |
| |
| 作者单位： | 华侨大学数学系,福建,泉州,362021 |
| |
| 基金项目： | 福建省自然科学基金计划资助项目（Z0511028）. |
| |
| 摘 要： | 在给出度约束最小生成树的快速生成方法的基础上，设计了一种启发式交叉求解TSP问题的混合遗传算法．该算法在交叉操作的设计上，与其他遗传算法有本质的不同，该交叉操作是在不违反度约束和不形成圈的前提下，每次从父代基因所拥有的边中加入权最小的边，从而形成子代．利用该算法得到了TSP CHN144问题迄今为止最好的解．
|
| 关 键 词： | TSP 遗传算法 初始种群 度约束最小生成树 |
| 文章编号： | 1000-5781（2005）06-0625-05 |
| 收稿时间： | 2004-05-20 |
| 修稿时间： | 2004-05-202005-01-21 |
Hybrid genetic algorithm with developmental crossover operator for solving TSP |
| |
| SONG Hai-zhou.Hybrid genetic algorithm with developmental crossover operator for solving TSP[J].Journal of Systems Engineering,2005,20(6):625-629. |
| |
| Authors: | SONG Hai-zhou |
| |
| Institution: | Department of Mathematics, Huaoqiao University, Quanzhou 362021, China |
| |
| Abstract: | 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. |
| |
| Keywords: | TSP genetic algorithm initial population degree-constrained minimum spanning tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
