基于K-均值聚类的TSP演化算法

提出一种基于K-均值聚类的TSP演化算法。该算法利用K-均值聚类技术,将TSP分为一些简单的TSP问题。在寻求最短路径时,首先所有结点用其聚类中心去代替,以聚类中心为结点构造TSP演化算法;其次,对于每一聚类,可寻求其距前面的聚类和后面的聚类最近的两结点之间的最短距离,若其中的结点较多,则再次演化得到其最短路径,若结点较少,则可用warshall算法可得到最短路径;最后对获得的最短路径进行剪接操作,可得到其更优解。