python实现 | 自适应大邻域搜索算法(ALNS)解决TSP问题

本文主要是介绍python实现 | 自适应大邻域搜索算法(ALNS)解决TSP问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

No.1

旅行商问题介绍

TSP解决的是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

No.2

自适应大邻域搜索算法

     自适应大邻域搜索算法(Adaptive Large Neighborhood Search)是基于邻域搜索的启发式算法，其在邻域搜索的基础上增加了的对算子作用效果的衡量，使算法能够自适应选择好的算子对解进行破坏与修复，从而加速更好的解方案的产生。

2.1 自适应大邻域搜索算法基本思想

    在邻域搜索算法中，如果邻域搜索范围较小，那么即使使用额外的元启发式技术，如模拟退火或禁忌搜索，也很难摆脱陷入局部最优的情况；在大型邻域搜索技术中(如变邻域搜索算法)，通过在当前解的多个邻域中寻找更满意的解，能够大大提高算法在解空间的搜索范围，但是它在使用算子时盲目地将每种算子形成的邻域结构都搜索一遍，缺少了一些启发式信息的指导且时间成本较高。

自适应大邻域搜索算法弥补了这种不足，首先ALNS算法允许在一次搜索中搜索多个邻域，它会根据算子的历史表现与使用次数选择下一次迭代使用的算子，通过算子间的相互竞争来生成当前解的邻域结构，而在这种结构中有很大概率能够找到更好的解。

2.2 自适应大邻域搜索算法核心设计

首先可以看看整个自适应大邻域搜索算法的伪代码（官方给的）：

     Ω^−和Ω^+分别表示destroy和repair算子的集合。第2行中的ρ^−和ρ^+分别表示各个destroy和repair算子的权重集合。一开始时，所有的算子都设置相同的权重。

     第4行根据ρ−和ρ+选择destroy和repair算子。至于选择的概率是由下面公式算出的，总的来说，权重越大，被选中的可能性越大(其实此处的选择方法就是遗传算法中的轮盘赌)。

     除此之外，每隔一定迭代次数，破坏算子和修复算子选择并计算结束后，会进行权重大小的调整。此处的权重大小是根据destroy和repair算子在搜索过程中的表现进行动态调整的（第12行）。在ALNS完成一次迭代搜索以后，我们使用下面的函数为每组destroy和repair算子的好坏进行一个评估：

其中，ω1≥ω2≥ω3≥ω4≥0。可以看出如果新的解方案改进越大，则评估级别越高。

注意，在本代码中的设计中，权重更新并不是每次选择destroy和repair算子都会更新，而是需要每隔一定迭代次数后（内循环结束后），权重才会更新。因为在本代码中只有两组破坏修复算子组合可以选，因此ALNS需要抉择出好的那组。如是每次迭代都更新权重，那么对于本身随机性较强的ALNS，每次更新这种操作会放大这种随机性，就可能会出现差的那组算子组合的选择概率会一直被提高，好的算子组合概率迟迟不被提高。因此，本文在迭代中设置有一个内循环和外循环，只有内循环结束，达到j_max时，才会进行权重更新，既降低了这种随机性，也综合多次的选择结果，不会降低算法的总体性能。

其权重更新公式如下所示：

式中，Wd为算子权重，Sd为算子分数，Ud为算子的使用次数。

在官方给的ALNS算法伪代码中，没有涉及权重更新这个步骤。因此小编重新写了一个更容易理解的算法流程，以下是本文中ALNS算法的求解流程图:

No.3

python实现ALNS算法解决TSP问题

接下来，进入到python实现阶段：

环境说明：小编的电脑系统是Windows10，python版本是3.7，编辑器是用的pycharm。在小编的代码中，需要应用到几个第三方库，numpy，matplotlib，math，time。写代码时记得先安装好这些库唷~

参数说明

破坏算子数：destory_size = 2

修复算子数：repair_size = 2  

内层迭代次数：j_max = 50

外层迭代次数：iterations = j_max * 20

新解优于最优解的分数：theta_1 = 20

新解优于当前解的分数：theta_2 = 12  

接受不优于当前解的新解分数：theta_3 = 8

相当于蚁群算法的挥发因子：alpha = 0.95  

接受概率：T = 0.2  

噪音参数：u = 0.1   

破坏算子

 小编设计的破坏算子为两个，一个是随机移除算子，另外一个是最差距离移除算子。

def destory_operators(distance, current_solution, destory_number, city_number):
    temp_solution = copy.copy(current_solution)
    ## 破坏list
    destory_list = []
    ## 随机移除算子
    if destory_number == 0: # 从0~city_number中随机取n个不重复的数，返回片段
        ## 多用于截取列表的指定长度的随机数
        temp_0 = random.sample(range(0, city_number), int(np.random.randint(2, 6)))
        for pp in temp_0:
            destory_list.append(temp_solution[pp])
        temp_0.sort()
        temp_0.reverse()
        for pp in temp_0:
            del temp_solution[pp]

    ## 最差距离移除算子
    if destory_number == 1:
        ## 将temp_distance
        temp_distance = np.zeros(city_number)
        temp_distance[0] = distance[current_solution[-1]][current_solution[0]] + distance[current_solution[0]][current_solution[1]]
        temp_distance[-1] = distance[current_solution[-2]][current_solution[-1]] + distance[current_solution[-1]][current_solution[0]]
        for h in range(1, city_number - 1):
            temp_distance[h] = distance[current_solution[h - 1]][current_solution[h]] + distance[current_solution[h]][current_solution[h + 1]]
        Inf = 0
        temp = []
        for i in range(int(np.random.randint(2, 6))):
            temp_2 = np.argmax(temp_distance)#最大索引
            ## 存储索引
            temp.append(temp_2)
            ## 存储被移除的客户点标号
            destory_list.append(temp_solution[temp_2])
            ## 避免再次被选中
            temp_distance[temp_2] = Inf
        temp.sort()
        temp.reverse()
        ## 移除操作
        for i in temp:
            del temp_solution[i]
    return temp_solution, destory_list

修复算子

修复算子同样为两个，一个是贪婪插入算子，另外一个是带扰动的贪婪插入算子。

def repair_operators(distance,temp_solution,destory_list,city_number,u,repair_number):
    ## 贪婪插入，找到适应度最小的
    if repair_number == 0:
        for temp_1 in destory_list:
            temp_value = 100000000000000  # 用于记录邻域操作后最好的邻域解
            for f in range(len(temp_solution) + 1):
                temp_route = temp_solution.copy()
                temp_route.insert(f, temp_1)  # 将城市编号插入
                if f == 0:
                    temp1 = distance[temp_route[-1]][temp_route[0]] + distance[temp_route[0]][temp_route[1]] - distance[temp_route[-1]][temp_route[1]]
                elif f == len(temp_solution):
                    temp1 = distance[temp_route[-2]][temp_route[-1]] + distance[temp_route[-1]][temp_route[0]] - distance[temp_route[-2]][temp_route[0]]
                else:
                    temp1 = distance[temp_route[f-1]][temp_route[f]] + distance[temp_route[f]][temp_route[f+1]] -  distance[temp_route[f-1]][temp_route[f+1]]
                if temp1 < temp_value:
                    temp_value = temp1
                    temp_route_new = temp_route.copy()
            temp_solution = temp_route_new.copy()

    ## 扰动+贪婪修复
    if repair_number == 1:
        temp_max = 0
        for i in range(city_number+1):
            for j in range(city_number + 1):
                if distance[i][j] > temp_max:
                    temp_max = distance[i][j]
        for temp_1 in destory_list:
            temp_value = 100000000000000  # 用于记录邻域操作后最好的邻域解
            for f in range(len(temp_solution) + 1):
                temp_route = temp_solution.copy()
                temp_route.insert(f, temp_1)  # 将城市编号插入
                if f == 0:
                    temp1 = distance[temp_route[-1]][temp_route[0]] + distance[temp_route[0]][temp_route[1]] -  distance[temp_route[-1]][temp_route[1]] + temp_max*u*np.random.uniform(-1,1)
                elif f == len(temp_solution):
                    temp1 = distance[temp_route[-2]][temp_route[-1]] + distance[temp_route[-1]][temp_route[0]] - distance[temp_route[-2]][temp_route[0]] + temp_max*u*np.random.uniform(-1,1)
                else:
                    temp1 = distance[temp_route[f-1]][temp_route[f]] + distance[temp_route[f]][temp_route[f+1]] - distance[temp_route[f-1]][temp_route[f+1]] + temp_max*u*np.random.uniform(-1,1)
                if temp1 < temp_value:
                    temp_value = temp1
                    temp_route_new = temp_route.copy()
            temp_solution = temp_route_new.copy()
    temp_value = get_total_distance(temp_solution)
    return temp_solution, temp_value

权重更新

 根据权重更新规则，其中Wd为算子权重，Sd为算子分数，Ud为算子的使用次数。

# ---------更新权值概率---------
        if j == j_max:
            for o in range(destory_size):
                if time_destory[o] == 0:
                    destory_weight[o] = destory_weight[o]*alpha
                else:
                    destory_weight[o] = destory_weight[o]*alpha + (1-alpha)*score_destory[o]/time_destory[o]

            sum_destory_weight = np.sum(destory_weight)
            P_destory = destory_weight/sum_destory_weight

            # 修复算子的权重参数
            for o in range(repair_size):
                if time_repair[o] == 0:
                    repair_weight[o] = repair_weight[o] * alpha
                else:
                    repair_weight[o] = repair_weight[o] * alpha + (1 - alpha) * score_repair[o] / time_repair[o]

        运行程序，迭代1000次后，最终的路线图和迭代过程图都如下所示，可以看到ALNS算法在迭代60次左右的时候就已经收敛了。经过多次的实验可以发现，在求解tsp问题中，ALNS收敛速度较快，且收敛的适应度值相比于遗传算法、禁忌搜索算法会更加稳定。

小结

        ALNS算法有一个动态调整即自适应的过程，以获得更好的邻域和解。它允许在一次搜索中搜索多个邻域（在一个ALNS算法中，有很多个邻域，每个邻域都可以看做是一组destroy和repair算子生成的，那么多个邻域就是使用多组不同的destroy和repair算子）。

        至此，ALNS算法解决TSP问题的介绍就到此结束了。

这篇关于python实现 | 自适应大邻域搜索算法(ALNS)解决TSP问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！