演化算法求解TSP问题的最新进展  

Latest progress of evolutionary algorithm to TSP

作　　者：张伟民[1] 刘松虎[2] 李程俊[1] 

机构地区：[1]中国地质大学计算机学院,湖北武汉430074 [2]中国建设银行武汉审计分部六处,湖北武汉430015

出　　处：《计算机工程与设计》2008年第20期5247-5249,共3页Computer Engineering and Design

基　　金：中国地质大学(武汉)2006年度优秀青年教师资助计划基金项目(CUGQNL0633)

摘　　要：TSP是一个著名的NP-hard问题。对近期出现的一些新的求解TSP问题的演化算法进行了比较全面的综述。其中有一类算法属于郭涛算法及其相应的改进算法,能够得到比传统演化算法更好的解,还有一类采用了实数编码的染色体表示方式,对求解TSP问题的新的染色体表示方式进行了尝试,还有的属于并行演化算法,通过增加并行进程的方式能够在原有算法的基础上得到更好的解。在综述这些算法的同时,还对比了它们的求解能力。最终的目的是希望通过对上述算法的研究,得到更合理的算法,推动演化算法研究TSP问题的进程。TSP is a famous NP-hard problem. Recently, some newly evolutionary algorithms （EAs） to TSP are proposed. Some of these algorithms which belong to GT algorithm or improved algorithm based on it can get better answer than traditional EAs. Some adopt new chromosome representation-real number coding representation. Some belong to parallel EA and can get better answer than original EA by adding parallel processes. They are all introduced and compared. The ultimatc aim is to get better algorithms through study the above mentioned algorithms to impulse research of EA to TSP.

关 键 词：演化计算 郭涛算法 染色体 实数编码 并行 

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