智能优化系列|第六期：VNS变邻域搜索算法求解TSP问题 (附python代码和详细注释)

变邻域搜索算法（VNS）是一种改进的爬山算法。变邻域搜索（VNS）主要是利用多个邻域对当前解进行搜索。它分为两个阶段，即变邻域下降阶段（variable neighborhood descent）-即VND阶段和扰动阶段（shaking phase）-即邻域动作阶段。这两个阶段都会改变搜索的邻域。

Miracle_lucy

1181人浏览 · 2024-09-03 09:00:00

Miracle_lucy · 2024-09-03 09:00:00 发布

1.变邻域搜索算法（VNS）简介

变邻域搜索算法（VNS）是一种改进的爬山算法。变邻域搜索（VNS）主要是利用多个邻域对当前解进行搜索。它分为两个阶段，即变邻域下降阶段（variable neighborhood descent）-即VND阶段和扰动阶段（shaking phase）-即邻域动作阶段。这两个阶段都会改变搜索的邻域。

2.变邻域搜索算法的核心步骤

上一节我们知道了变邻域搜索算法的核心步骤有2个：下降阶段和扰动阶段。下面我们看看怎么实现这2个阶段

2.1 VND阶段流程：

1) 假设初始解为S；定义n个邻域，记为N_k(k = 1, 2, 3......n)；k = 1。

2) 对邻域结构N_k（即 N_k(S)）进行局部搜索，找更优解S′；

3) 如果在N_k(S)里找到一个比S更优的解S′，则令S=S′, k=1 。如果搜遍邻域N_k仍找不到比S更优的解，则令k++。

4) 如果k≤n ,转步骤2。

5) 输出最优解S。

2.2 VND阶段图解：

2.3 扰动阶段：

shaking phase，看起来很高大上的名词，扰动、抖动、邻域动作，这些名词本质上还是没有什么区别的。都是通过一定的规则，将一个解变换到另一个解而已。

2.4 VNS伪代码：

下面我们看看最终形成的VNS伪代码：

选择一个邻域结构N_k，k = 1, 2, 3......n
S<-生成初始解
while termination conditions not met do 
    k = 1
    while k < n do
        # 扰动阶段
        S′ = ShakeMethod(N_k(S)) # 在邻域中产生随机解
        # VND阶段
        S′′ = LocalSearch(S′) # 首先用局部搜索算法，找更优解S′′
        if(f(S′′) <f(S′)) then  # 然后判断是否move on
            S = S′′
            k = 1
        else
            k = k + 1
        endif
    endwhile
endwhile

3.变邻域搜索算法求解TSP问题

我们这里用python实现

算例使用的是tsplib上的数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628（取整的伪欧氏距离）。tsplib地址：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

第1行数据说明：

城市索引	城市X坐标	城市Y坐标
1	6734	1453

算例文件如下：

1 6734 1453
2 2233 10
3 5530 1424
4 401 841
5 3082 1644
6 7608 4458
7 7573 3716
8 7265 1268
9 6898 1885
10 1112 2049
11 5468 2606
12 5989 2873
13 4706 2674
14 4612 2035
15 6347 2683
16 6107 669
17 7611 5184
18 7462 3590
19 7732 4723
20 5900 3561
21 4483 3369
22 6101 1110
23 5199 2182
24 1633 2809
25 4307 2322
26 675 1006
27 7555 4819
28 7541 3981
29 3177 756
30 7352 4506
31 7545 2801
32 3245 3305
33 6426 3173
34 4608 1198
35 23 2216
36 7248 3779
37 7762 4595
38 7392 2244
39 3484 2829
40 6271 2135
41 4985 140
42 1916 1569
43 7280 4899
44 7509 3239
45 10 2676
46 6807 2993
47 5185 3258
48 3023 1942

部分python代码如下：

import copy
import random
import math


class VSN_TSP:

    def __init__(self):
        self.dist_mat = None  # 城市的距离矩阵
        self.cities = []  # 城市的坐标数据，用二维数组表示
        self.cities_num = 0  # 城市的个数

    # 读取城市的坐标数据和个数
    def read_data(self):
        cities = []
        cities_num = 0
        with open("./data/vsn.txt", 'r') as file:  # 更换了算例
            for line in file:  # 把客户数据存在字典customers中，字典的长度是101
                line = line.split()
                city = [int(line[1]), int(line[2])]
                cities.append(city)
                cities_num += 1
        self.cities = cities
        self.cities_num = cities_num

    # 计算两点之间的取整的伪欧式距离
    def calc_distance(self, p1, p2):
        return math.ceil(math.sqrt((math.pow(p1[0] - p2[0], 2) + math.pow(p1[1] - p2[1], 2)) / 10))

    # 计算距离矩阵
    def calc_dist_mat(self):
        cities_num = self.cities_num  # 城市个数
        dist_mat = [[0 for _ in range(cities_num)] for _ in range(cities_num)]
        for i in range(len(dist_mat)):
            for j in range(i + 1, len(dist_mat)):
                # i到j等于j到i
                dist_mat[i][j] = self.calc_distance(self.cities[i], self.cities[j])
                dist_mat[j][i] = dist_mat[i][j]
        self.dist_mat = dist_mat

    # 计算路径总长度
    def calc_path_dist(self, path):
        """
        适应度函数，计算目标函数值.
        :param path: 一个解
        :return: 目标函数值，即总距离
        """
        distance = 0
        for i in range(len(path) - 1):
            distance += self.dist_mat[path[i]][path[i + 1]]
        distance += self.dist_mat[path[-1]][path[0]]  # 从最后一个城市回到出发城市
        return distance

    # 随机交换两个城市,产生邻域
    def change_neighborhood_0(self, path):
        exchange = random.sample(range(1, len(path) - 1), 2)
        temp_path = copy.deepcopy(path)
        temp_path[exchange[0]] = path[exchange[1]]
        temp_path[exchange[1]] = path[exchange[0]]
        return temp_path

    # 随机翻转某个区间,产生邻域
    def change_neighborhood_1(self, path):
        # 随机选择两个端点, 不改变先后顺序
        endpoints = random.sample(range(1, len(path) - 1), 2)
        endpoints.sort()
        temp_path = copy.deepcopy(path)
        temp_path[endpoints[0]:endpoints[1]] = list(reversed(temp_path[endpoints[0]:endpoints[1]]))
        return temp_path

    # 随机找两个城市放到序列最前面,产生邻域
    def change_neighborhood_2(self, path):
        # 随机选择两个city, 不改变先后顺序
        endpoints = random.sample(range(1, len(path) - 1), 2)
        endpoints.sort()
        temp_path = copy.deepcopy(path)
        temp_path.pop(endpoints[0])
        temp_path.pop(endpoints[1] - 1)
        temp_path.insert(1, path[endpoints[0]])
        temp_path.insert(2, path[endpoints[1]])
        return temp_path

    # 扰动函数
    def shake_method(self, k, path):
        if k == 0:
            temp_path = self.change_neighborhood_0(path)
        elif k == 1:
            temp_path = self.change_neighborhood_1(path)
        elif k == 2:
            temp_path = self.change_neighborhood_2(path)
        else:
            temp_path = self.change_neighborhood_0(path)
        dis = self.calc_path_dist(temp_path)
        # print("超出shake邻域集合长度: " + str(k))
        return temp_path, dis

    # 变邻域搜索核心
    def variable_neighborhood_search(self, iter_cnt, local_search_cnt, kmax=3):
        """
        :param iter_cnt: 迭代次数
        :param local_search_cnt: 局部搜索次数
        """
        first_path = [i for i in range(0, len(self.dist_mat))]
        # first_path.append(0)
        first_path_dist = self.calc_path_dist(first_path)
        cur_solution = [first_path, first_path_dist]
        self.print_result(first_path, first_path_dist)
        best_solution = copy.deepcopy(cur_solution)

        for it in range(iter_cnt):
            k = 0
            while k < kmax:
                # 扰动阶段
                solution1 = self.shake_method(k, cur_solution[0])
                # VND阶段
                # 首先用局部搜索算法，找更优解s1_1
                solution1_1 = self.variable_neighborhood_descent(solution1, kmax, local_search_cnt)
                # 然后判断是否move on
                if solution1_1[1] < cur_solution[1]:
                    cur_solution = solution1_1
                    k = 1
                    if cur_solution[1] < best_solution[1]:
                        best_solution = copy.deepcopy(cur_solution)
                else:
                    k += 1
        self.print_result(best_solution[0], best_solution[1])
        return best_solution

    # 打印结果
    def print_result(self, path_list, path_dist):
        print("best cost:%.2f" % (path_dist))
        path = ""
        for i, point in enumerate(path_list):
            if i < len(path_list) - 1:
                path += str(point) + "->"
            else:
                path += str(point)
        print("best path:" + path)


if __name__ == "__main__":
    VSN = VSN_TSP()
    VSN.read_data()  # 读取城市坐标和城市数量
    VSN.calc_dist_mat()  # 计算城市的距离矩阵
    VSN.variable_neighborhood_search(iter_cnt=20000, local_search_cnt=30)

4.结果输出

best cost:49840.00
best path:0->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->25->26->27->28->29->30->31->32->33->34->35->36->37->38->39->40->41->42->43->44->45->46->47
best cost:11505.00
best path:0->7->8->37->30->43->17->6->27->5->36->18->26->16->42->29->35->45->32->19->11->14->39->21->15->40->33->2->22->10->46->20->12->13->24->38->31->23->9->44->34->3->25->41->1->28->4->47

局部搜索：变邻域搜索(Variable Neighbourhood Search, VNS)解决TSP问题的python案例

干货 | 变邻域搜索算法(Variable Neighborhood Search,VNS)超详细一看就懂