压缩搜索空间的遗传算法在TSP中的应用

Application of genetic algorithm with space contraction in TSP

旅行商问题的可能解与城市规模n是成指数型增长的,因此规模越大解决越困难。通过设计能够对搜索空间进行压缩的遗传算法,依靠搜索过程中已得到的近优解的信息,可以降低随机搜索的盲目性并加速算法收敛速度。首先利用不完全演化得到一组近优解,然后通过比较近优解获得解的相同模式,将搜索空间划分为一个或多个最优解域,再进行局部的优化,来提高求解速度和解的质量,并用TSP问题进行了验证。

The possible solution of traveling salesman problem and the scale of the cities have the exponential relation, so the more bigger of the scale, the more difficult of the solution. By designing the genetic algorithm which can compress the search space, and use the information of the suboptimal solution we get, we can reduce the blindness of random search and accelerate convergence of the al- gorithm. First a suboptimal solution is gotten using incomplete evolution, and the same mode of the suboptimal solution is gotten by comparison, then the search space is divided into one or more optimal solution domain, then do partial optimization, to improve the quality and speed of the solution. And use TSP problems to verify the validity.