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

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