CTSP问题稳态小生境算法的研究及仿真实现  

SNGA Algorithm for Solving the China Traveling Salesman Problem (CTSP) and Simulation Implementing

作　　者：张贵军[1] 吴惕华[1] 叶蓉[2] 

机构地区：[1]上海交通大学电子信息学院自动化系,上海200030 [2]河北省科学院,石家庄050081

出　　处：《系统仿真学报》2004年第8期1692-1696,共5页Journal of System Simulation

基　　金：河北省科技厅重点项目(01213553)

摘　　要：提出了一种求解中国旅行商问题(CTSP)的稳态小生境遗传算法SNGA。SNGA算法在稳态遗传算法的基础上采用物种保存小生境替换策略,在改善算法的在线性能、离线性能和计算量的同时,有效的维持了群体的多样性,从而可避免群体出现早熟现象,增强群体在进化后期产生优良模式的能力。在具体实现中,SNGA算法采用链表染色体编码,这样就可以对染色体进行快速的基本遗传算子以及倒位算子的遗传操作,进一步提高算法的实现性能。此外采用C++语言和基于COM的MapObjects组件技术实现了基于上述算法的仿真软件GISCTSP,并对国家基础地理信息系统(NFGIS)1400万中国行政中心数据文件res1_4m进行了仿真分析。Steady Niche Genetic Algorithm (SNGA) is presented for solving the China Traveling Salesman Problem. In the framework of Steady Genetic Algorithm, the species conserving niche replacement policy is adopted for individual抯 replacement. Thus, no mention the computation reducing, we can dramatically improve the on-line performance and the off-line performance of SNGA. Further more, the Niche technology can maintains the diversity in population, so that the premature can be avoid during evolving. In implementation, a bi-list structure is used to describe the chromosome, as a result of it, operations such as basic genetic operators and inverse operator can be applied to individuals rapidly. At last, simulation software 揋ISCTSP?is developed which uses C++ programming language and ESRI抯 MapObjects Component as development tools. By using this software, we have analyzed the GIS shapefile 搑es1_4m?that downloaded from the National Foundation Geographic Information System (NFGIS) and made some approving results.

关 键 词：中国旅行商问题 稳态遗传算法 物种保存 小生境 链表染色体 地理信息系统 C++ 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]