改进的紧致遗传算法求解族状旅行商问题  

An Improvement of the Compact Genetic Algorithm for Solving Clustering Traveling Salesman Problem

作　　者：叶苗[1] 程小辉[1] 

机构地区：[1]桂林理工大学信息科学与工程学院,广西桂林541004

出　　处：《微电子学与计算机》2013年第8期7-12,共6页Microelectronics & Computer

基　　金：国家自然科学基金(61063001/F020207;61262075/F020702);广西自然科学基金项目(桂科自0832264);广西高等学校重大科研项目(201201ZD012)

摘　　要：相比经典的标准遗传算法求解旅行商问题,紧致遗传算法对存储的要求较少,但可行解的产生需要花费大量的时间.针对城市节点成族状分布的旅行商问题,在紧致遗传算法中设计"轮盘赌"的个体编码产生方式以避免时间耗费的缺点,并在基于节点聚类分析的基础上设计出符合问题特点的概率矩阵初始化方法和更新方法,以提高算法搜索最优解的准确性和搜索速度.最后通过对公开数据集TSPLib的测试证实设计的改进紧致遗传算法确实能提高问题求解的效率.Compared with classical genetic algorithm for solving traveling salesman problem（TSP）, compact genetic algorithm （CGA） exploited without significantly increasing memory requirements, but the computational cost of generation of feasible Tours increased. Facing the characteristic of city nodes distributing as cluster in clustering TSP,the roulette wheel is applied in generating individuals chromosomes of CGA to overcome the drawbacks of expensive computation. Based on the cluster analysis of city nodes in clustering TSP, the initialization operator and update protocol of the probability matrix corresponding to the characteristic of clustering TSP is proposed to improve the speed of convergence efficiently and capacity of global optimization. The results of experiments conducted on TSP instances in open datasets TSPLib shows the efficacy of the improved compact genetic algorithm.

关 键 词：紧致遗传算法 概率模型 聚类分析 族状旅行商问题 

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