计算机与现代化
計算機與現代化
계산궤여현대화
COMPUTER AND MODERNIZATION
2014年
7期
8-15
,共8页
宗德才%王康康%丁勇
宗德纔%王康康%丁勇
종덕재%왕강강%정용
旅行商问题%遗传算法%子域交叉%子域变异%Lin-Kernighan算法
旅行商問題%遺傳算法%子域交扠%子域變異%Lin-Kernighan算法
여행상문제%유전산법%자역교차%자역변이%Lin-Kernighan산법
traveling salesman problem%genetic algorithm%subregion crossover%subregion mutation%Lin-Kernighan algorithm
提出一种混合改进遗传算法的嵌套分区算法用于求解旅行商问题。该算法首先使用加权抽样法产生初始最可能域,用全局数组保存每个区域的历史最优解,设计子域交叉算子和子域变异算子,并用改进的遗传算法搜索每个子域和裙域的最好解,然后对Lin-Kernighan算法进行改进,并且在搜索裙域中最好解时,对种群中优秀个体用改进的Lin-Ker-nighan算法进行优化。对TSPLIB中问题实例的仿真结果表明,所提出的混合改进遗传算法的嵌套分区算法在求解旅行商问题时可以获得高质量的解。
提齣一種混閤改進遺傳算法的嵌套分區算法用于求解旅行商問題。該算法首先使用加權抽樣法產生初始最可能域,用全跼數組保存每箇區域的歷史最優解,設計子域交扠算子和子域變異算子,併用改進的遺傳算法搜索每箇子域和裙域的最好解,然後對Lin-Kernighan算法進行改進,併且在搜索裙域中最好解時,對種群中優秀箇體用改進的Lin-Ker-nighan算法進行優化。對TSPLIB中問題實例的倣真結果錶明,所提齣的混閤改進遺傳算法的嵌套分區算法在求解旅行商問題時可以穫得高質量的解。
제출일충혼합개진유전산법적감투분구산법용우구해여행상문제。해산법수선사용가권추양법산생초시최가능역,용전국수조보존매개구역적역사최우해,설계자역교차산자화자역변이산자,병용개진적유전산법수색매개자역화군역적최호해,연후대Lin-Kernighan산법진행개진,병차재수색군역중최호해시,대충군중우수개체용개진적Lin-Ker-nighan산법진행우화。대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 .