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

Combined Nested Partitions Method Based on Improved Genetic Algorithm

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

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 muta -tion 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 modi-fied Lin-Kernighan algorithm .The simulation results for the 16 problems in TSPLIB show that the proposed improved nested parti-tions method using improved genetic algorithm can find solutions of high quality when applied to the traveling salesman problem .