1. 大規(guī)模鄰域搜索算法

參考《Handbook of Metaheuristics (Third Edition)》中的Large neighborhood search章節(jié), 建議直接閱讀英文原版

1.1. LNS定義

大規(guī)模鄰域搜索(LNS) 屬于超大鄰域搜索(Very Large-Scale Neighborhood Search, VLNS)的一類，隨著算例規(guī)模的增大，鄰域搜索算法的鄰域規(guī)模呈指數(shù)增長或者當鄰域太大而不能在實際中明確搜索時 (the neighborhood it searches grows exponentially with the instance size or if the neighborhood is simply too large to be searched explicitly in practice)，我們把這類鄰域搜索算法(Neighborhood Search, NS)歸類于VLNS;

1.2. LNS鄰域

• 鄰域搜索算法關(guān)鍵在于鄰域結(jié)構(gòu)的選擇，即鄰域定義的方式。通常來講，鄰域越大，局部最優(yōu)解就越好，獲得的全局最優(yōu)解就越好。同時，鄰域越大，每次迭代搜索鄰域所需的時間也越長。

• 在大規(guī)模鄰域搜索算法中，鄰域由一種破壞（destroy）和一種修復(fù)（repair）算子隱式定義（the neighborhood is de?ned implicitly by a destroy and a repair method）。destroy算子會破壞當前解的一部分（變成不可行解），repair算子會對被破壞的解進行重建（重新變成可行解），相當于一個鄰域動作變換動作。破壞算子通常包含隨機性的元素，以便在每次調(diào)用destroy方法時破壞解的不同部分（The destroy method typically contains an element of stochasticity such that different parts of the solution are destroyed in every invocation of the method）。

• 解$x$的鄰域$N(x)$就可以定義為：首先利用destroy算子破壞解$x$，然后利用repair算子重建解$x$，從而得到的一系列解的集合（The neighborhood N(x) of a solution x is then de?ned as the set of solutions that can be reached by ?rst applying the destroy method and then the repair method）。

• LNS算法不會搜索一個解的整個鄰域（entire neighborhood），而只是對該鄰域進行采樣(samples)搜索; (按照算法流程，只定義一種detory和repair方式，雖然detory里有隨機部分，但也不包含整個鄰域)

1.3. LNS框架

• 偽代碼

在LNS中只定義一種破壞和修復(fù)算子，所以破壞和修復(fù)算子的定義很重要，直接決定了能搜索到的當前解x的鄰域。如果鄰域太小，那么局部最優(yōu)解的質(zhì)量就一般，因為有些空間沒搜索到。如果鄰域太大，又缺少帶點啟發(fā)式信息方向搜索。所以Ropke在論文《An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows》定義了多種破壞和修復(fù)算子，提出來自適應(yīng)大規(guī)模鄰域搜索（Adaptive Large Neighborhood Search, ALNS）的框架，有空總結(jié)寫一篇關(guān)于ALNS的文章。

2. 旅行商問題TSP

• 旅行商問題（Travelling Salesman Problem, TSP），通俗而言它是指對于給定的一系列城市和每對城市之間的距離，找到訪問每一座城市僅一次并回到起始城市的最短回路。建立不同的建模方式會有不同的求解方式，比如Dantzig-Fulkerson-Johnson模型、Miller-Tucker-Zemlin模型、Commodity Flow、最短路徑等；(這里不再贅述，注意TSP問題各種形式的變種)

3. python代碼示例及結(jié)果

• python代碼

import random
import numpy as np
from copy import deepcopy
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']

class Solution:
    # 使用符號編號表示一個訪問路徑route
    def __init__(self):
        self.route = []
        self.cost = 0  # 解對應(yīng)的總成本

class Lns_tsp(object):
    def __init__(self, distance, num_node):
        self.distance = distance
        self.num_node = num_node

    def get_route_cost(self, route):
        # 計算成本的函數(shù)
        cost = 0
        for i in range(1, len(route)):
            cost += self.distance[route[i-1]][route[i]]
        return cost

    def destroy_operator(self, solution, num_destroy):
        # 破壞算子: 隨機選擇num_destroy個不重復(fù)的破壞點（即刪除num_destroy個城市）
        destroy_node_bank = []  # 保存被刪除的城市節(jié)點
        while len(destroy_node_bank) < num_destroy:
            n = random.randint(0, self.num_node-1)
            while n in destroy_node_bank:
                n = random.randint(0, self.num_node-1)
            destroy_node_bank.append(n)
            solution.route.remove(n)
        return solution, destroy_node_bank

    def repair_operator(self, solution, destroy_node_bank):
        # 修復(fù)算子: 貪婪插入，插入到成本最小的位置
        for n in destroy_node_bank:
            #計算將n插入各個位置的成本
            insert_list = np.full(len(solution.route), 0)
            for i in range(0, len(solution.route)):
                insert_list[i] = self.distance[solution.route[i-1]][n] + self.distance[n][solution.route[i]] - self.distance[solution.route[i]][solution.route[i-1]]

            greedy_index = np.where(insert_list == min(insert_list))[0][0]

            solution.route.insert(greedy_index, n)
        return solution

def plot_best_vales_iteration(best_values_record):
    # 繪制最優(yōu)解隨著迭代變化的趨勢
    plt.figure()
    plt.plot([i+1 for i in range(len(best_values_record))], best_values_record)
    plt.xlabel('迭代次數(shù)')
    plt.ylabel('最優(yōu)值')
    plt.show()

def plot_route(route, city_location):
    plt.figure()
    # 繪制散點
    x = np.array(city_location)[:, 0]  # 橫坐標
    y = np.array(city_location)[:, 1]  # 縱坐標
    plt.scatter(x, y, color='r')
    # 繪制城市編號
    for i, txt in enumerate(range(1, len(city_location) + 1)):
        plt.annotate(txt, (x[i], y[i]))
    # 繪制方向
    x0 = x[route]
    y0 = y[route]
    for i in range(len(city_location) - 1):
        plt.quiver(x0[i], y0[i], x0[i + 1] - x0[i], y0[i + 1] - y0[i], color='b', width=0.005, angles='xy', scale=1,
                   scale_units='xy')
    plt.quiver(x0[-1], y0[-1], x0[0] - x0[-1], y0[0] - y0[-1], color='b', width=0.005, angles='xy', scale=1,
               scale_units='xy')

    plt.xlabel('橫坐標')
    plt.ylabel('縱坐標')
    plt.show()

if __name__ == '__main__':
    ############## 算例和參數(shù)設(shè)置 ############################
    # 城市節(jié)點的位置信息，一行代表一個城市的橫坐標及縱坐標
    city_location = [[ 94,  99],
           [ 66,  67],
           [ 14,  78],
           [ 95,  56],
           [ 68,   9],
           [ 26,  20],
           [ 51,  67],
           [ 39,  39],
           [  5,  55],
           [ 12,  33],
           [ 55,  85],
           [ 98,  46],
           [ 36,  39],
           [ 65, 100],
           [ 57,  89],
           [ 88,  24],
           [ 53,  96],
           [ 91,  41],
           [ 32,  69],
           [ 38,  38],
           [ 38,  39],
           [ 85, 100],
           [  7,  37],
           [ 85,  96],
           [ 89,  48],
           [ 85,  35],
           [ 32,  29],
           [ 31,  25],
           [ 20,  17],
           [ 75,  21],
           [ 74,  29],
           [  6,  32],
           [ 20,  81],
           [ 62,   1],
           [ 11,  48],
           [  1,  69],
           [ 99,  70],
           [ 20,  27],
           [ 25,  42],
           [  6,  31],
           [ 78,  24],
           [ 42,  39],
           [ 83,  30],
           [ 94,  10],
           [ 90,  37],
           [ 76,  73],
           [  9,  56],
           [ 39,  33],
           [ 74,  15],
           [ 77,  14]]

    num_node = len(city_location)  # 城市節(jié)點的數(shù)量
    iter_num = 300  # 迭代次數(shù)
    random.seed(3)  # 隨機種子
    num_destroy = int(num_node*0.2) # 破壞程度

    # 計算距離成本矩陣 distance, 直接使用歐式距離
    distance = np.full((num_node, num_node), 0)
    for i in range(num_node):
        for j in range(num_node):
            distance[i][j] = ((city_location[i][0]-city_location[j][0])**2+(city_location[i][1]-city_location[j][1])**2)**0.5

    ############## 產(chǎn)生初始解 ############################
    solution = Solution()
    solution.route = [i for i in range(num_node)]  # 按照節(jié)點編號依次相連構(gòu)成初始解也可隨機產(chǎn)生
    lns = Lns_tsp(distance, num_node)
    solution.cost = lns.get_route_cost(solution.route) # 計算初始解對應(yīng)的目標成本
    best_solution = deepcopy(solution)  # 初始化最優(yōu)解=初始解
    best_values_record = [0 for i in range(iter_num)]  # 初始化保存最優(yōu)解的集合

    ############## 執(zhí)行LNS ############################
    for n_gen in range(iter_num):
        tem_solution = deepcopy(solution)
        # 執(zhí)行破壞修復(fù)算子，得到臨時解
        tem_solution, destroy_node_bank = lns.destroy_operator(tem_solution, num_destroy)
        tem_solution = lns.repair_operator(tem_solution, destroy_node_bank)
        # 計算臨時解的目標值
        tem_solution.cost = lns.get_route_cost(tem_solution.route)

        # 接受標準：如果臨時解比當前解好，直接接受；且更新最優(yōu)解
        if tem_solution.cost < best_solution.cost:
            solution = deepcopy(tem_solution)
            best_solution = deepcopy(tem_solution)
        best_values_record[n_gen] = best_solution.cost

    ############## 繪制結(jié)果 ############################
    plot_best_vales_iteration(best_values_record)
    plot_route(best_solution.route, city_location)

• 結(jié)果
  

文章來源地址http://www.zghlxwxcb.cn/news/detail-480215.html

到了這里，關(guān)于python實現(xiàn)大規(guī)模鄰域搜索(LNS)求解旅行商問題(TSP)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！