改进型遗传算法求解TSP问题

An improved genetic algorithm to solve TSP problem

旅行商问题(TSP)是一个典型的NP难题,优化TSP求解问题有着重要的意义。遗传算法(GA)是解决这类问题的有效方法之一。标准遗传算法有一定的局限性,该文对遗传算法选择算子改进而引入了精英保留策略,保证选择的质量;在变异操作中采用自适应算法选择变异算子,提高变异质量和算法的搜索效果;在个体进化后再引入单向进化逆转操作,使子代继承亲代优质基因机会提高,提高算法搜索最优解的能力。经过国际公认的TSPLIB的实验数据的验证,优化后的遗传算法搜索最优解能力提高。

The TSP is a typical NP problem .The optimization of vehicle routing problem （VRP） and city pipeline optimization can use TSP to solve ;therefore it is very important to the optimization for solving TSP problem .The genetic algorithm （GA） is one of ideal methods in solving it .The standard genetic algorithm has some limitations .Improving the selection operator of genetic algorithm ,and importing elite retention strategy can ensure the select operation of quality .In mutation operation ,using the adaptive algorithm selection can improve the quality of search results and variation .after the chromosome evolved ,one-way evolution reverse operation is added ,which can make the offspring inherit gene of parental quality improvement opportunities , and improve the ability of searching the optimal solution algorithm .After the experimental data of international recognized TSPLIB verification ,the genetic algorithm optimization has better probability of finding the optimal solution .