计算机与现代化

• 人工智能 • 上一篇    下一篇

一种混合改进遗传算法的嵌套分区算法

  

  1. (1.常熟理工学院计算机科学与工程学院,江苏 常熟 215500; 2.江苏科技大学数理学院,江苏镇江 212003; 3.南京理工大学泰州科技学院计算机科学与技术系,江苏泰州 225300)
  • 收稿日期:2014-05-20 出版日期:2014-07-16 发布日期:2014-07-17
  • 作者简介:宗德才(1979-),男,江苏常熟人,常熟理工学院计算机科学与工程学院讲师,硕士,研究方向:智能优化算法,概率论和信息论; 王康康(1980-),男,江苏科技大学数理学院副教授,博士,研究方向:智能优化算法,概率论和信息论; 丁勇(1980-),男,南京理工大学泰州科技学院计算机科学与技术系讲师,研究方向:数据库理论与数据挖掘。
  • 基金资助:
    江苏省高校自然科学基础研究项目(13KJB110006)

Combined Nested Partitions Method Based on Improved Genetic Algorithm

  1. (1. College of Computer Science and Engineering, Changshu Institute of Technology, Changshu 215500, China;
    2. School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang 212003, China;
    3. Taizhou Institute of Technology, Nanjing University of Science and Technology, Taizhou 225300, China)
  • Received:2014-05-20 Online:2014-07-16 Published:2014-07-17

摘要: 提出一种混合改进遗传算法的嵌套分区算法用于求解旅行商问题。该算法首先使用加权抽样法产生初始最可能域,用全局数组保存每个区域的历史最优解,设计子域交叉算子和子域变异算子,并用改进的遗传算法搜索每个子域和裙域的最好解,然后对Lin-Kernighan算法进行改进,并且在搜索裙域中最好解时,对种群中优秀个体用改进的Lin-Kernighan算法进行优化。对TSPLIB中问题实例的仿真结果表明,所提出的混合改进遗传算法的嵌套分区算法在求解旅行商问题时可以获得高质量的解。

关键词: 旅行商问题, 遗传算法, 子域交叉, 子域变异, Lin-Kernighan算法

Abstract: This paper puts forward an improved nested partitions method using improved genetic algorithm to solve the small and medium scale traveling salesman problem. The algorithm adopts weighted sampling method to generate the initial most promising region, uses the global array to record the historical optimal solution of every region and designs the crossover operator and mutation operator of subregion. Then our algorithm uses an improved genetic algorithm to search the optimal solution of each subregion and surrounding region. In the search for the best solution of surrounding region, some excellent individual is improved by modified Lin-Kernighan algorithm. The simulation results for the 16 problems in TSPLIB show that the proposed improved nested partitions method using improved genetic algorithm can find solutions of high quality when applied to the traveling salesman problem.

Key words: traveling salesman problem, genetic algorithm, subregion crossover, subregion mutation, Lin-Kernighan algorithm

中图分类号: