一种简单有效的求解TSP的混合差分进化算法  

Simple and effective hybrid differential evolution algorithm for solving traveling salesman problem

作　　者：曾宇容[1] 王林[2] 顿彩霞[2] 

机构地区：[1]湖北经济学院信息管理学院,武汉430205 [2]华中科技大学管理学院,武汉430074

出　　处：《计算机应用研究》2012年第12期4455-4458,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(70801030);湖北省教育厅重点科研资助项目(D20112201);国家教育部人文社会科学研究青年基金资助项目(11YJC630275);中央高校基本科研业务费资助项目(HUST:2012TS065)

摘　　要：设计了基于标准差分进化算法(differential evolution,DE)与遗传算法(genetic algorithm,GA)的混合差分进化算法(hybrid DE,HDE),同时用典型的测试函数对HDE进行性能测试。针对旅行商问题(traveling salesman problem,TSP)的求解难题,给出了采用位置—次序转换策略和HDE的有效求解方法,并测试了Oliver 30个城市的TSP。仿真结果表明,与DE和GA相比,HDE的优势在收敛率、平均最优解以及耗时上都很明显,证明了HDE在解决TSP问题上的有效性和稳定性。This paper designed a hybrid intelligent algorithm（HDE） by integrating advantages of DE and GA.It applied several typical test functions to test the performance of the proposed HDE.Considering the difficulty for solving the TSP,this paper proposed an effective approach using the conversion of position-order and HDE.The case of Oliver including 30 cities for TSP has been solved and analyzed.Results show the apparent advantages of the HDE on the rate of convergence,average optimal solution and CPU time compared to the DE or GA,which indicates the efficiency and stability of proposed HDE to solve the TSP.

关 键 词：旅行商问题 差分进化 遗传算法 混合智能算法 

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