Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (27): 59-61.DOI: 10.3778/j.issn.1002-8331.2009.27.019

• 研究、探讨 • Previous Articles     Next Articles

Genetic algorithm for optimal design of machining route

WANG Mei-hua,TIAN Xu-hong,LIAO Hong-xiang   

  1. College of Information,South China Agricultural University,Guangzhou 510642,China
  • Received:2008-05-21 Revised:2008-09-04 Online:2009-09-21 Published:2009-09-21
  • Contact: WANG Mei-hua

求解广义旅行商问题的混合染色体遗传算法

王美华,田绪红,廖鸿翔   

  1. 华南农业大学 信息学院,广州 510642
  • 通讯作者: 王美华

Abstract: A genetic algorithm of hybrid chromosome(HCGA) is proposed for solving generalized traveling sales man problem(GTSP).Generalized chromosome genetic algorithm has been the most effective method for GTSP since it is proposed,but its global searching capacity needs to be improved.In HCGA algorithm,the chromosome is updated with a hybrid one of binary and integer codes,and the crossover and mutation operators are renewed accordingly.The theoretical analysis and experimental results indicates HCGA performs better than GCGA and other methods in global searching.

Key words: genetic algorithm, hybrid chromosome, generalized traveling sales man problem(GTSP), optimal routing

摘要: 提出了针对广义旅行商问题(GTSP)的混合染色体遗传算法(HCGA)。目前,广义染色体遗传算法(GCGA)是求解GTSP问题的最好方法,但这种方法在编码设计上存在不足,使得算法全局搜索能力较差。在GCGA算法基础上,设计了二进制和整数混合编码的染色体,并更新了交叉和变异算子设计,得到改进算法HCGA。理论和实验结果都说明:HCGA比GCGA等多种算法具有更强的全局搜索能力。

关键词: 遗传算法, 混合染色体, 广义旅行商, 最优化路线

CLC Number: