【遗传算法】求解TSP问题

本专栏将会重点围绕车辆路径规划问题进行讲解，会涵盖车辆路径规划中的很多常见问题，如TSP问题，CVRP问题，VRPTW问题，VRPCTW-MultiDepot问题，EVRPTW问题，PDVRP问题，Mul-ObjVRP问题，M2-2E-VRP双层网络模型，将会逐步为大家进行梳理与整理。本将小节内容将会讲解第一个问题：TSP问题。

前言：在【01路径规划问题的相关理论】这一小节的内容中，有讲述到TSP问题是车辆路径规划问题的基础模型，我们在系统性的学习VRP问题时，首先来讲解TSP问题，文章将会包含TSP问题的各种算法，会从不同的维度、利用不同的算法来讲解，TSP问题后续也会整理成一个系列文章，分别会从遗传算法、粒子群优化算法、模拟退火算法、蚁群算法、分支定界法以及动态规划等不同算法维度来讲解，目的在于：

①为大家铺垫不同的算法模型，为后续更多更复杂的规划问题打基础；

②后续将不会重点介绍算法的理论框架，会直接根据问题给出解决的代码模型。

1、TSP问题介绍

        根据百度百科的解释：

        旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

 2、遗传算法介绍

        我们系列文章将会轻理论，重实践，重代码，不会和你长篇大论关于算法的原理内容，若想比较详细的了解关于原理内容，请自行百度学习。

        遗传算法（Genetic Algorithm，GA）起源于达尔文进化论，是一种随机全局搜索优化方法，模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，通过一代一代的进化，最后收敛到一群最适应环境的个体，从而求得问题的优质解的一种方法。

在执行遗传算法前，有两个东西必须提前实现设定好；

1. 可行解的表示方法，即编码方式，目前路径规划领域中常用的编码方式为实数编码，除此以外，还有二进制编码、浮点编码等，这些不做为我们的重点。
2. 适应度函数，也就是计算子代适应度的函数，这个函数一般是目标函数，如要最大化某个函数，则将这个函数作为目标函数即可，反之最小化的时候加个负号即可。

遗传算法是一个迭代算法，在进行初始化后按照 “选择，交叉，变异” 的顺序进行迭代，当满足设定的结束条件(例如达到一定的代数)，便将得到的解作为问题的解。其流程如下所示 ：
     

 说明：案例中的TSP问题，我们不需要过多的纠结说，车辆有无限制，编码后如何解码的问题，这可能是初学者对这个算法模型最大的疑问，我们后续在讲解VRP问题时，会提及到车辆限制以及遗传算法中如何解码的问题，其中我相信绝大数同学对于整个算法理解不会有问题，但就一直没有弄明白整数编码的情况下，求出的线路，算法是如何解码的。

我们得明白这样一个问题：

旅行商问题TSP与装箱问题Packing problem的混合问题=车辆路径规划问题VRP

3、代码实验

3.1、随即初始化

    def random_init(self, num_total, num_city):
        tmp = [x for x in range(num_city)]
        result = []
        for i in range(num_total):
            random.shuffle(tmp)
            result.append(tmp.copy())
        return result

 随即初始化一个个体的方法。其中通过rang函数生成一个所有城市节点数量的序列，然后使用shuffle函数将这个序列打乱，就是我们模拟的一种随即路线。

3.2、贪心初始化

def greedy_init(self, dis_mat, num_total, num_city):
        start_index = 0
        result = []
        for i in range(num_total):
            rest = [x for x in range(0, num_city)]
            # 所有起始点都已经生成了
            if start_index >= num_city:
                start_index = np.random.randint(0, num_city)
                result.append(result[start_index].copy())
                continue
            current = start_index
            rest.remove(current)
            # 找到一条最近邻路径
            result_one = [current]
            while len(rest) != 0:
                tmp_min = math.inf
                tmp_choose = -1
                for x in rest:
                    if dis_mat[current][x] < tmp_min:
                        tmp_min = dis_mat[current][x]
                        tmp_choose = x
 
                current = tmp_choose
                result_one.append(tmp_choose)
                rest.remove(tmp_choose)
            result.append(result_one)
            start_index += 1
        return result

 3.3、计算路径长度

    # 计算路径长度
    def compute_pathlen(self, path, dis_mat):
        try:
            a = path[0]
            b = path[-1]
        except:
            import pdb
            pdb.set_trace()
        result = dis_mat[a][b]
        for i in range(len(path) - 1):
            a = path[i]
            b = path[i + 1]
            result += dis_mat[a][b]
        return result

 3.4、计算种群的适应度

    # 计算种群适应度
    def compute_adp(self, fruits):
        adp = []
        for fruit in fruits:
            if isinstance(fruit, int):
                import pdb
                pdb.set_trace()
            length = self.compute_pathlen(fruit, self.dis_mat)
            adp.append(1.0 / length)
        return np.array(adp)

3.5、选择操作

    def swap_part(self, list1, list2):
        index = len(list1)
        list = list1 + list2
        list = list[::-1]
        return list[:index], list[index:]

3.6、交叉操作

  def ga_cross(self, x, y):
        len_ = len(x)
        assert len(x) == len(y)
        path_list = [t for t in range(len_)]
        order = list(random.sample(path_list, 2))
        order.sort()
        start, end = order
 
        # 找到冲突点并存下他们的下标,x中存储的是y中的下标,y中存储x与它冲突的下标
        tmp = x[start:end]
        x_conflict_index = []
        for sub in tmp:
            index = y.index(sub)
            if not (index >= start and index < end):
                x_conflict_index.append(index)
 
        y_confict_index = []
        tmp = y[start:end]
        for sub in tmp:
            index = x.index(sub)
            if not (index >= start and index < end):
                y_confict_index.append(index)
 
        assert len(x_conflict_index) == len(y_confict_index)
 
        # 交叉
        tmp = x[start:end].copy()
        x[start:end] = y[start:end]
        y[start:end] = tmp
 
        # 解决冲突
        for index in range(len(x_conflict_index)):
            i = x_conflict_index[index]
            j = y_confict_index[index]
            y[i], x[j] = x[j], y[i]
 
        assert len(set(x)) == len_ and len(set(y)) == len_
        return list(x), list(y)

3.7、变异操作

    def ga_mutate(self, gene):
        path_list = [t for t in range(len(gene))]
        order = list(random.sample(path_list, 2))
        start, end = min(order), max(order)
        tmp = gene[start:end]
        # np.random.shuffle(tmp)
        tmp = tmp[::-1]
        gene[start:end] = tmp
        return list(gene)

 3.8、程序执行

    def run(self):
        BEST_LIST = None
        best_score = -math.inf
        self.best_record = []
        for i in range(1, self.iteration + 1):
            tmp_best_one, tmp_best_score = self.ga()
            self.iter_x.append(i)
            self.iter_y.append(1. / tmp_best_score)
            if tmp_best_score > best_score:
                best_score = tmp_best_score
                BEST_LIST = tmp_best_one
            self.best_record.append(1./best_score)
            print(i,1./best_score)
        print(1./best_score)
        return self.location[BEST_LIST], 1. / best_score

3.9、图形展示

fig, axs = plt.subplots(2, 1, sharex=False, sharey=False)
axs[0].scatter(Best_path[:, 0], Best_path[:,1])
Best_path = np.vstack([Best_path, Best_path[0]])
axs[0].plot(Best_path[:, 0], Best_path[:, 1])
axs[0].set_title('规划结果')
iterations = range(model.iteration)
best_record = model.best_record
axs[1].plot(iterations, best_record)
axs[1].set_title('收敛曲线')
plt.show()

 最终运行的结果如下：

模型收敛图如下：

 

若读者朋友需要全部的案例数据以及完整的代码，可以自行点击案例链接下载，但其实如果您能看懂上述的代码结构，我相信不用作者提供完整的代码也是可以自行进行测试完成的，也希望朋友们在实在没办法的情况下，才去下载完整资源，这样的学习效果会最好。