旅行商问题(动态规划_爬山算法_遗传算法)

问题描述

​ 旅行商问题（Travelling Salesman Problem, 简记TSP，亦称货郎担问题)：设有n个城市和距离矩阵D=[dij]，其中dij表示城市i到城市j的距离，i，j=1，2 … n，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。

一、动态规划解决旅行商问题

​ 要使用动态规划，需要问题本身有最优子结构，我们需要找到要解决的问题的子问题。题目要求，从0(a)出发，经过[1(b),2©,3(d)]这几个城市，然后回到0，使得花费最少。要实现这个要求，需要从下面三个实现方案中选择花费最少的方案。

​ 从0出发，到1，然后再从1出发，经过[2,3]这几个城市，然后回到0，使得花费最少。
​ 从0出发，到2，然后再从2出发，经过[1,3]这几个城市，然后回到0，使得花费最少。
​ 从0出发，到3，然后再从3出发，经过[1,2]这几个城市，然后回到0，使得花费最少。
​ 可以发现，三个小的解决方案的最优解，构成了大的解决方案，所以这个问题具有最优子结构，可以用动态规划来实现。

​ 设置一个二维的动态规划表dp,定义符号{1,2,3}表示经过[1,2,3]这几个城市，然后回到0。
​ 设置一个二维数组l保存两个城市之间的距离。
​ 那么题目就是求dp[0][{1,2,3}]。将{1,2,3}表示成二进制，就是111，对应10进制的7，所以题目是在求dp[0][7];

​ 要求三个方案的最小值意味：

​ dp[0][{1,2,3}] = min{l[0][1]+dp[1][{2,3}] ，l[0][2]+dp[2][{1,3}] ，l[0][3]+dp[3][{1,2}]}
​ dp[1][{2,3}] = min{ l[1][2]+dp[2][{3}] ，l[1][3]+dp[3][{2}]}
​ dp[2][{3}] = l[2][3]+dp[3][{}]
​ dp[3][{}]就是从3出发，不经过任何城市，回到0的花费，所以dp[3][{}] = l[3][0]

1.1 相关代码：

    def prepare(self):

        Max = 1000
        temp = []
        tmp = []
        for i in range(Max):
            for j in range(Max):
                temp.append(0x7ffff)
                tmp.append(0)

            self.dp.append(copy.deepcopy(temp))
            self.value.append(copy.deepcopy(tmp))
            temp.clear()
            tmp.clear()

        self.value[0][1] = self.value[1][0] = 2
        self.value[0][2] = self.value[2][0] = 5
        self.value[0][3] = self.value[3][0] = 7
        self.value[1][2] = self.value[2][1] = 8
        self.value[1][3] = self.value[3][1] = 3
        self.value[2][3] = self.value[3][2] = 1

    '''
    dp[0][{1,2,3}] = min{l[0][1]+dp[1][{2,3}] ，l[0][2]+dp[2][{1,3}] ，l[0][3]+dp[3][{1,2}]}
    dp[1][{2,3}] = min{ l[1][2]+dp[2][{3}] ，l[1][3]+dp[3][{2}]}
    dp[2][{3}] = l[2][3]+dp[3][{}] = l[2][3]+ l[3][0]
    '''
    def dp_method(self):

        for i in range(self.n):
            self.dp[i][0] = self.value[i][0]
        col = 1<< self.n - 1
        print(col)
        for j in range(1,col):
            for i in range(self.n):

                if i != 0 and j >> (i-1) & 1:
                    continue
                '''
                从2出发，要去{1,3}。
                先看去1的路，去了1集合{1,3}中只剩下{3} ,{3}对应4,所以要求的dp表就是dp[1][4],这个4可以通过(101) ^ (1)得到,(1) = 1<>(2-1)) &1==1。而且也由于从2出发，就更不能去了。
                最后看去3的路，去了3集合{1,3}中只剩下{1},{1}对应这1，所以要求的dp表就是dp[3][1],1通过(101) ^ (100)得到。(100) = 1<
                for k in range(1,col):

                    if j>>(k-1)&1 == 0:
                        continue
                    if self.dp[i][j] > self.value[i][k] + self.dp[k][j ^ (1 << (k-1))]:
                        self.dp[i][j] = self.value[i][k] + self.dp[k][j ^ (1 << (k - 1))]

1.2 运行结果：

; 二、爬山法解决旅行商问题

​ 爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。属于人工智能算法的一种。

​ 爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。

#爬山算法思路
#1、随机生成一个城市排序，计算该顺序下所耗总路程,并假设为最短距离
#2、设定爬山算法总代数
#3、若当前代数小于总次数，则随机交换两个城市的顺序，计算总路程，否则第5步
#4、若该次总路程小于假设的最短距离，则更新最短距离，否则继续第3步
#5、输出此时的最短距离，和城市访问顺序

2.1 相关代码：

    def prepare_for_hill_climbing_and_genetic_algorithm(self):

        data = xlrd.open_workbook('中国省会城市坐标.xlsx')
        table = data.sheets()[0]
        row = table.nrows

        self.num = row
        self.citys = {}
        self.citys_name = []
        for i in range(row):
            self.citys[table.cell_value(i,0)] = (table.cell_value(i,1),table.cell_value(i,2))
            self.citys_name.append(table.cell_value(i,0))

    def distance(self,city_a,city_b):

        x = city_a[0] - city_b[0]
        y = city_a[1] - city_b[1]
        dist = (x**2 + y**2)**0.5
        return dist

    def all_distance(self,citys_num):

        sum = self.distance(self.citys[self.citys_name[citys_num[0]]],self.citys[self.citys_name[citys_num[len(citys_num)-1]]])
        for i in range(len(citys_num)-1):
            citys_a = self.citys[self.citys_name[citys_num[i]]]
            citys_b = self.citys[self.citys_name[citys_num[i+1]]]
            sum += self.distance(citys_a,citys_b)
        return sum

    def hill_climbing(self):

        citys_num = list(range(self.num))

        shuffle(citys_num)

        ans = copy.deepcopy(citys_num)

        generation = 0

        shortest_distance = self.all_distance(citys_num)
        print("初始距离:{}".format(self.all_distance(citys_num)))

        generations = 100000

        x = []
        x.append(0)

        y = []
        y.append(shortest_distance)
        a = 0

        while a < generations:
            a += 1

            c1 = random.randint(0, 10)
            c2 = random.randint(0, 10)

            temp = citys_num[c1]
            citys_num[c1] = citys_num[c2]
            citys_num[c2] = temp
            dist = self.all_distance(citys_num)
            if dist < shortest_distance:
                x.append(a)
                y.append(dist)
                shortest_distance = dist
                print(shortest_distance)
                ans = copy.deepcopy(citys_num)
                generation = a
        print("最短距离:{}".format(shortest_distance))
        print("最短访问顺序:{}".format(ans))
        print("最短访问顺序出现的代数:{}".format(generation))
        plt.title("hill_climbing")
        plt.xlabel("generations")
        plt.ylabel("distance")
        plt.plot(x, y, "ob")
        plt.show()

        self.drawPic(ans)

    def drawPic(self,citys_num):
        dots = []
        for i in range(len(citys_num)):
            temp = []
            temp.append(self.citys[self.citys_name[citys_num[i]]][0])
            temp.append(self.citys[self.citys_name[citys_num[i]]][1])
            dots.append(temp)
        temp = []
        temp.append(self.citys[self.citys_name[citys_num[0]]][0])
        temp.append(self.citys[self.citys_name[citys_num[0]]][1])
        dots.append(temp)
        plt.figure(figsize=(10, 6))
        plt.xlim(85.00000, 130, 0.002)
        plt.ylim(15, 50, 0.001)
        plt.xlabel('城市经度', fontproperties="simhei")
        plt.ylabel('城市纬度', fontproperties="simhei")

        for i in range(len(dots) - 1):
            plt.text(dots[i][0], dots[i][1], self.citys_name[citys_num[i]], color='#0085c3', fontproperties="simhei")
            plt.plot(dots[i][0], dots[i][1], 'o', color='#0085c3')

        for i in range(len(dots) - 1):
            start = (dots[i][0], dots[i + 1][0])
            end = (dots[i][1],dots[i + 1][1])
            plt.plot(start, end, color='#000000')
        plt.show()

2.2 运行结果：

城市数据：

City(116.41667, 39.91667, “北京”),

City(121.43333, 34.50000, “上海”),

City(113.00000, 28.21667, “长沙”),

City(106.26667, 38.46667, “银川”),

City(109.50000, 18.20000, “三亚”),

City(112.53333, 37.86667, “太原”),

City(91.00000, 29.60000, “拉萨”),

City(102.73333, 25.05000, “昆明”),

City(126.63333, 45.75000, “哈尔滨”),

City(113.65000, 34.76667, “郑州”),

City(113.50000, 22.20000, “澳门”)));

; 三、遗传算法解决旅行商问题

​ 遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。遗传算法是从首先是初始化一个种群，然后根据适应性函数确定个体的适应度，由适应度来选择个体进行交叉，以某种概率让个体进行变异，从而不断选出适应度高的个体，进而更新种群。

​ 算法流程如下所示。

#遗传算法
    #1、确定种群规模，迭代次数，变异概率等
    #2、初始化种群（初始化城市序列）
    #3、计算个体适应度
    #4、选择个体进行交叉
    #5、选择个体进行变异
    #6、用产生的新个体更新种群
    #7、如果达到迭代次数则输出适应度最高的个体，否则回到第（3）步
    #8、结束

3.1 相关代码:

    def select(self,fitness,generation,population_size):
        original_fitness = copy.deepcopy(fitness)
        fitness.sort(reverse=True)
        new_generation = []
        for i in range(population_size):
            index = original_fitness.index(fitness[i])
            new_generation.append(copy.deepcopy(generation[index]))
        return new_generation

    def genetic_algorithm(self):

        population_size = 10
        generations = 100000
        mutation_probability = 0.01
        fitness = []
        x = []
        y = []
        coordinate = []

        generation = []

        citys_num = list(range(self.num))
        for i in range(population_size):

            shuffle(citys_num)
            generation.append(copy.deepcopy(citys_num))

        a = 0
        while a < generations:
            a += 1

            fitness.clear()
            for i in range(len(generation)):
                fitness.append(1/self.all_distance(generation[i]))

            max_fitness = max(fitness)
            print(max_fitness)
            print(1/max_fitness)
            x.append(a)
            y.append(1/max_fitness)

            generation = copy.deepcopy(self.select(fitness,generation,population_size))

            parent1_list = []
            parent2_list = []

            for i in range(int(population_size/2)):
                tmp = random.randint(0, population_size - 1)

                while tmp in parent1_list:
                    tmp = random.randint(0, population_size - 1)
                parent1_list.append(tmp)

            for i in range(population_size):
                if i not in parent1_list:
                    parent2_list.append(i)

            children = []
            index = []
            for i in range(int(population_size/2)):
                children.clear()
                parent1 = generation[parent1_list[i]]
                parent2 = generation[parent2_list[i]]

                tmp = random.randint(1,self.num)
                index.clear()
                for j in range(tmp):
                    temp = random.randint(0, self.num - 1)

                    while temp in index:
                        temp = random.randint(0, self.num - 1)
                    index.append(temp)

                for j in range(len(index)):
                    children.append(parent1[index[j]])

                for j in range(self.num):
                    if parent2[j] not in children:
                        children.append(parent2[j])

                if random.randint(1,100) == 100*mutation_probability:
                    print("发生变异")
                    print("变异前:{}".format(children))

                    c1 = random.randint(0, self.num-1)
                    c2 = random.randint(0, self.num-1)
                    temp = children[c1]
                    children[c1] = children[c2]
                    children[c2] = temp
                    print("变异后:{}".format(children))

                generation.append(copy.deepcopy(children))

        print("最终适应度：{}".format(max_fitness))
        print("最短距离：{}".format(1/max_fitness))
        print("最短访问顺序:{}".format(generation[0]))

        plt.title("genetic_algorithm")
        plt.xlabel("generations")
        plt.ylabel("distance")
        plt.scatter(x, y, 1,)

        for i in range(len(x) - 1):
            start = (x[i], x[i+1])
            end = (y[i],y[i+1])
            plt.plot(start, end, color='#000000',linewidth=0.5)
        plt.show()
        self.drawPic(generation[0])

    def prepare_for_hill_climbing_and_genetic_algorithm(self):

        data = xlrd.open_workbook('中国省会城市坐标.xlsx')
        table = data.sheets()[0]
        row = table.nrows

        self.num = row
        self.citys = {}
        self.citys_name = []
        for i in range(row):
            self.citys[table.cell_value(i,0)] = (table.cell_value(i,1),table.cell_value(i,2))
            self.citys_name.append(table.cell_value(i,0))

    def distance(self,city_a,city_b):

        x = city_a[0] - city_b[0]
        y = city_a[1] - city_b[1]
        dist = (x**2 + y**2)**0.5
        return dist

    def all_distance(self,citys_num):

        sum = self.distance(self.citys[self.citys_name[citys_num[0]]],self.citys[self.citys_name[citys_num[len(citys_num)-1]]])
        for i in range(len(citys_num)-1):
            citys_a = self.citys[self.citys_name[citys_num[i]]]
            citys_b = self.citys[self.citys_name[citys_num[i+1]]]
            sum += self.distance(citys_a,citys_b)
        return sum

    def drawPic(self,citys_num):
        dots = []
        for i in range(len(citys_num)):
            temp = []
            temp.append(self.citys[self.citys_name[citys_num[i]]][0])
            temp.append(self.citys[self.citys_name[citys_num[i]]][1])
            dots.append(temp)
        temp = []
        temp.append(self.citys[self.citys_name[citys_num[0]]][0])
        temp.append(self.citys[self.citys_name[citys_num[0]]][1])
        dots.append(temp)
        plt.figure(figsize=(10, 6))
        plt.xlim(85.00000, 130, 0.002)
        plt.ylim(15, 50, 0.001)
        plt.xlabel('城市经度', fontproperties="simhei")
        plt.ylabel('城市纬度', fontproperties="simhei")

        for i in range(len(dots) - 1):
            plt.text(dots[i][0], dots[i][1], self.citys_name[citys_num[i]], color='#0085c3', fontproperties="simhei")
            plt.plot(dots[i][0], dots[i][1], 'o', color='#0085c3')

        for i in range(len(dots) - 1):
            start = (dots[i][0], dots[i + 1][0])
            end = (dots[i][1],dots[i + 1][1])
            plt.plot(start, end, color='#000000')
        plt.show()

3.2 运行结果:

城市数据:

北京 116.46 39.92
天津 117.2 39.13
上海 121.48 31.22
重庆 106.54 29.59
拉萨 91.11 29.97
乌鲁木齐 87.68 43.77
银川 106.27 38.47
呼和浩特 111.65 40.82
南宁 108.33 22.84
哈尔滨 126.63 45.75
长春 125.35 43.88
沈阳 123.38 41.8
石家庄 114.48 38.03
太原 112.53 37.87
西宁 101.74 36.56
济南 117 36.65
郑州 113.6 34.76
南京 118.78 32.04
合肥 117.27 31.86
杭州 120.19 30.26
福州 119.3 26.08
南昌 115.89 28.68
长沙 113 28.21
武汉 114.31 30.52
广州 113.23 23.16
台北 121.5 25.05
海口 110.35 20.02
兰州 103.73 36.03
西安 108.95 34.27
成都 104.06 30.67
贵阳 106.71 26.57
昆明 102.73 25.04
香港 114.1 22.2
澳门 113.33 22.13

; 四、总结

​ 动态规划求解旅行商问题在解决城市数量较少时有着非常好的效果，可以求得准确解，但是当城市数量增多，比如遗传算法解决旅行商问题中的34个城市求最短路径问题，使用动态规划就需要大量的内存空间，dp数组大小将为34*(2^34)，显然这时再使用动态规划就不太现实。

​ 爬山算法容易陷入局部最优解，这时可以采用

​ 1、随机爬山法,它在上山移动中随机地选择下一步;选择的概率随上山移动的陡峭程度而变化。这种算法通常比最陡上升算法的收敛速度慢很多,但是在某些状态空间地形图上能找到更好的解。

​ 2、首选爬山法,它在实现随机爬山法的基础上,采用的方式是随机地生成后继结点,直到生成一个优于当前结点的后继。这个算法在有很多后继结点的情况下有很好的效果。到现在为止,我们描述的爬山法算法还是不完备的—它们经常会在目标存在的情况下因为被局部极大值卡住而找不到该目标。还有一种值得提出的方法

​ 3、随机重新开始的爬山法,它通过随机生成的初始状态进行一系列的爬山法搜索,找到目标时停止搜索。这个算法是完备的概率接近于1,原因是它最终会生成一个目标状态作为初始状态。

​ 相对于爬山算法来说，遗传算法拥有更高的效率，能够解决更多城市的旅行商问题，并且很快就能收敛，求得近似解。

五、参考文章

用遗传算法求解旅行商问题
基于爬山算法求解TSP问题（JAVA）
旅行商问题（TSP）

六、完整代码

Original: https://blog.csdn.net/sgsx11/article/details/121482958
Author: 骑行去看海
Title: 旅行商问题(动态规划_爬山算法_遗传算法)