快捷導(dǎo)航

Python數(shù)學(xué)建模學(xué)習(xí)模擬退火算法旅行商問(wèn)題示例解析

更新時(shí)間：2021年10月18日 14:36:29 作者：youcans

模擬退火算法不僅可以解決連續(xù)函數(shù)優(yōu)化問(wèn)題，KIRKPATRICK在1983年成功將其應(yīng)用于求解組合優(yōu)化問(wèn)題,現(xiàn)已成為求解旅行商問(wèn)題的常用方法，通常采用反序、移位和交換等操作算子產(chǎn)生新解

1、旅行商問(wèn)題(Travelling salesman problem, TSP)

旅行商問(wèn)題是經(jīng)典的組合優(yōu)化問(wèn)題，要求找到遍歷所有城市且每個(gè)城市只訪問(wèn)一次的最短旅行路線，即對(duì)給定的正權(quán)完全圖求其總權(quán)重最小的Hamilton回路：設(shè)有 n個(gè)城市和距離矩陣 D=[dij]，其中dij表示城市i到城市j的距離（i,j = 1,2 … n），則問(wèn)題是要找出遍訪每個(gè)城市恰好一次的一條回路并使其路徑長(zhǎng)度為最短。旅行商問(wèn)題屬于NP完全問(wèn)題，其全局優(yōu)化解的計(jì)算量以問(wèn)題規(guī)模的階乘關(guān)系增長(zhǎng)。旅行商問(wèn)題不僅作為一類典型的組合優(yōu)化問(wèn)題經(jīng)常被用作算法研究和比較的案例，許多實(shí)際應(yīng)用問(wèn)題如路徑規(guī)劃、交通物流、網(wǎng)絡(luò)管理也可轉(zhuǎn)化為旅行商問(wèn)題。
　　目前，旅行商問(wèn)題的研究主要集中于探索和發(fā)展各種高效近似最優(yōu)解的優(yōu)化方法，包括基于問(wèn)題特征信息（如城市位置、距離、角度等）構(gòu)造的各種啟發(fā)式搜索算法，以及通過(guò)模擬或解釋自然規(guī)律而發(fā)展的模擬退火算法、遺傳算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)算法等智能優(yōu)化算法或?qū)⒍呦嘟Y(jié)合的混合算法。

2、模擬退火算法求解旅行商問(wèn)題

模擬退火算法要從當(dāng)前解的鄰域中產(chǎn)生新的候選解，解的表達(dá)形式和鄰域結(jié)構(gòu)對(duì)算法收斂非常重要。組合優(yōu)化問(wèn)題不同于函數(shù)優(yōu)化，其自變量不是連續(xù)變化的，目標(biāo)函數(shù)不僅依賴于自變量的數(shù)值，而且與變量的排列次序有關(guān)。極端地，旅行商問(wèn)題的路徑長(zhǎng)度僅取決于排列次序，因此常用城市編號(hào)的序列來(lái)表示解。
　　新解的產(chǎn)生機(jī)制是在當(dāng)前解序列的基礎(chǔ)上進(jìn)行變換操作，隨機(jī)改變序列中某些點(diǎn)的排列次序，常見(jiàn)的基本變換操作有交換算子(Swap Operator)、反序算子（Inversion Operator）、移位算子(Move Operator)等。交換算子將當(dāng)前路徑 S_now 中的第 i 個(gè)城市 Ci 與第 j 個(gè)城市 Cj 的位置交換；反序算子也稱2-opt，將當(dāng)前路徑 S_now 中從第 i 個(gè)城市 Ci 到第 j 個(gè)城市 Cj 之間的城市排列順序反向翻轉(zhuǎn)；移位算子相當(dāng)于 Or-opt 操作t，將當(dāng)前路徑 S_now 中的第 i 個(gè)城市 Ci 移動(dòng)到第 j 個(gè)城市 Cj 之后的位置。

3、程序說(shuō)明

下段給出了模擬退火算法求解旅行商問(wèn)題的 Python程序。對(duì)于程序中的一些細(xì)節(jié)處理，說(shuō)明如下：

數(shù)據(jù)的獲取。為了避免讓讀者下載數(shù)據(jù)文件，程序中采用直接賦值方式讀取旅行城市位置的坐標(biāo)。實(shí)際上，通常是使用數(shù)據(jù)文件給出城市位置的參數(shù)，程序中已經(jīng)給出了讀取 TSPLib（旅行商問(wèn)題國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集）的子程序和調(diào)用方法。

城市間距的計(jì)算。按照 TSPLib 的處理規(guī)范，一是城市間距按歐式距離計(jì)算，不要說(shuō)地球是圓的要算球面間距了；二是對(duì)計(jì)算的城市間距離取整（四舍五入），而不是用實(shí)數(shù)表示城市間距離，這會(huì)導(dǎo)致一些優(yōu)化結(jié)果的差異。

新路徑的產(chǎn)生。為便于理解，本程序只給出了交換算子(Swap Operator)的子程序。交換操作非常容易理解，但實(shí)際上優(yōu)化效率和效果并不好，反序操作的性能顯著優(yōu)于交換算子。

4、模擬退火算法求解旅行商問(wèn)題 Python 程序

# 模擬退火算法求解旅行商問(wèn)題 Python程序
# Program: SimulatedAnnealing_v6.py
# Purpose: Simulated annealing algorithm for traveling salesman problem
# v1.0: = 關(guān)注 Youcans，分享原創(chuàng)系列 https://blog.csdn.net/youcans =
#   模擬退火求解旅行商問(wèn)題（TSP）基本算法
# Copyright 2021 YouCans, XUPT
# Crated：2021-05-01
#  -*- coding: utf-8 -*-
import math                         # 導(dǎo)入模塊 math
import random                       # 導(dǎo)入模塊 random
import pandas as pd                 # 導(dǎo)入模塊 pandas 并簡(jiǎn)寫成 pd
import numpy as np                  # 導(dǎo)入模塊 numpy 并簡(jiǎn)寫成 np YouCans
import matplotlib.pyplot as plt     # 導(dǎo)入模塊 matplotlib.pyplot 并簡(jiǎn)寫成 plt
np.set_printoptions(precision=4)
pd.set_option('display.max_rows', 20)
pd.set_option('expand_frame_repr', False)
pd.options.display.float_format = '{:,.2f}'.format
# 子程序：初始化模擬退火算法的控制參數(shù)
def initParameter():
    # custom function initParameter():
    # Initial parameter for simulated annealing algorithm
    tInitial = 100.0                # 設(shè)定初始退火溫度(initial temperature)
    tFinal  = 1                     # 設(shè)定終止退火溫度(stop temperature)
    nMarkov = 1000                # Markov鏈長(zhǎng)度，也即內(nèi)循環(huán)運(yùn)行次數(shù)
    alfa    = 0.98                 # 設(shè)定降溫參數(shù)，T(k)=alfa*T(k-1)
    return tInitial,tFinal,alfa,nMarkov
# 子程序：讀取TSPLib數(shù)據(jù)
def read_TSPLib(fileName):
    # custom function read_TSPLib(fileName)
    # Read datafile *.dat from TSPlib
    # return coordinates of each city by YouCans, XUPT
    res = []
    with open(fileName, 'r') as fid:
        for item in fid:
            if len(item.strip())!=0:
                res.append(item.split())
    loadData = np.array(res).astype('int')      # 數(shù)據(jù)格式：i Xi Yi
    coordinates = loadData[:,1::]
    return coordinates
# 子程序：計(jì)算各城市間的距離，得到距離矩陣
def getDistMat(nCities, coordinates):
    # custom function getDistMat(nCities, coordinates):
    # computer distance between each 2 Cities
    distMat = np.zeros((nCities,nCities))       # 初始化距離矩陣
    for i in range(nCities):
        for j in range(i,nCities):
            # np.linalg.norm 求向量的范數(shù)（默認(rèn)求 二范數(shù)），得到 i、j 間的距離
            distMat[i][j] = distMat[j][i] = round(np.linalg.norm(coordinates[i]-coordinates[j]))
    return distMat                              # 城市間距離取整（四舍五入）
# 子程序：計(jì)算 TSP 路徑長(zhǎng)度
def calTourMileage(tourGiven, nCities, distMat):
    # custom function caltourMileage(nCities, tour, distMat):
    # to compute mileage of the given tour
    mileageTour = distMat[tourGiven[nCities-1], tourGiven[0]]   # dist((n-1),0)
    for i in range(nCities-1):                                  # dist(0,1),...dist((n-2)(n-1))
        mileageTour += distMat[tourGiven[i], tourGiven[i+1]]
    return round(mileageTour)                     # 路徑總長(zhǎng)度取整（四舍五入）
# 子程序：繪制 TSP 路徑圖
def plot_tour(tour, value, coordinates):
    # custom function plot_tour(tour, nCities, coordinates)
    num = len(tour)
    x0, y0 = coordinates[tour[num - 1]]
    x1, y1 = coordinates[tour[0]]
    plt.scatter(int(x0), int(y0), s=15, c='r')      # 繪制城市坐標(biāo)點(diǎn) C(n-1)
    plt.plot([x1, x0], [y1, y0], c='b')             # 繪制旅行路徑 C(n-1)~C(0)
    for i in range(num - 1):
        x0, y0 = coordinates[tour[i]]
        x1, y1 = coordinates[tour[i + 1]]
        plt.scatter(int(x0), int(y0), s=15, c='r')  # 繪制城市坐標(biāo)點(diǎn) C(i)
        plt.plot([x1, x0], [y1, y0], c='b')         # 繪制旅行路徑 C(i)~C(i+1)
    plt.xlabel("Total mileage of the tour:{:.1f}".format(value))
    plt.title("Optimization tour of TSP{:d}".format(num))  # 設(shè)置圖形標(biāo)題
    plt.show()
# 子程序：交換操作算子
def mutateSwap(tourGiven, nCities):
    # custom function mutateSwap(nCities, tourNow)
    # produce a mutation tour with 2-Swap operator
    # swap the position of two Cities in the given tour
    # 在 [0,n) 產(chǎn)生 2個(gè)不相等的隨機(jī)整數(shù) i,j
    i = np.random.randint(nCities)          # 產(chǎn)生第一個(gè) [0,n) 區(qū)間內(nèi)的隨機(jī)整數(shù)
    while True:
        j = np.random.randint(nCities)      # 產(chǎn)生一個(gè) [0,n) 區(qū)間內(nèi)的隨機(jī)整數(shù)
        if i!=j: break                      # 保證 i, j 不相等
    tourSwap = tourGiven.copy()             # 將給定路徑復(fù)制給新路徑 tourSwap
    tourSwap[i],tourSwap[j] = tourGiven[j],tourGiven[i] # 交換 城市 i 和 j 的位置————簡(jiǎn)潔的實(shí)現(xiàn)方法
    return tourSwap
def main():
    # 主程序 = 關(guān)注 Youcans，分享原創(chuàng)系列 https://blog.csdn.net/youcans =
    # # 讀取旅行城市位置的坐標(biāo)
    coordinates = np.array([[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0, 655.0],
                            [880.0, 660.0], [25.0, 230.0], [525.0, 1000.0], [580.0, 1175.0], [650.0, 1130.0],
                            [1605.0, 620.0], [1220.0, 580.0], [1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0],
                            [725.0, 370.0], [145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],
                            [300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0], [975.0, 580.0],
                            [1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0], [660.0, 180.0], [410.0, 250.0],
                            [420.0, 555.0], [575.0, 665.0], [1150.0, 1160.0], [700.0, 580.0], [685.0, 595.0],
                            [685.0, 610.0], [770.0, 610.0], [795.0, 645.0], [720.0, 635.0], [760.0, 650.0],
                            [475.0, 960.0], [95.0, 260.0], [875.0, 920.0], [700.0, 500.0], [555.0, 815.0],
                            [830.0, 485.0], [1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0],
                            [1340.0, 725.0], [1740.0, 245.0]])
    # fileName = "../data/eil76.dat"                      # 數(shù)據(jù)文件的地址和文件名
    # coordinates = read_TSPLib(fileName)                 # 調(diào)用子程序，讀取城市坐標(biāo)數(shù)據(jù)文件
    # 模擬退火算法參數(shù)設(shè)置
    tInitial,tFinal,alfa,nMarkov = initParameter()      # 調(diào)用子程序，獲得設(shè)置參數(shù)
    nCities = coordinates.shape[0]              # 根據(jù)輸入的城市坐標(biāo) 獲得城市數(shù)量 nCities
    distMat = getDistMat(nCities, coordinates)  # 調(diào)用子程序，計(jì)算城市間距離矩陣
    nMarkov = nCities                           # Markov鏈 的初值設(shè)置
    tNow    = tInitial                          # 初始化 當(dāng)前溫度(current temperature)
    # 初始化準(zhǔn)備
    tourNow   = np.arange(nCities)   # 產(chǎn)生初始路徑，返回一個(gè)初值為0、步長(zhǎng)為1、長(zhǎng)度為n 的排列
    valueNow  = calTourMileage(tourNow,nCities,distMat) # 計(jì)算當(dāng)前路徑的總長(zhǎng)度 valueNow
    tourBest  = tourNow.copy()                          # 初始化最優(yōu)路徑，復(fù)制 tourNow
    valueBest = valueNow                                # 初始化最優(yōu)路徑的總長(zhǎng)度，復(fù)制 valueNow
    recordBest = []                                     # 初始化 最優(yōu)路徑記錄表
    recordNow  = []                                     # 初始化 最優(yōu)路徑記錄表
    # 開始模擬退火優(yōu)化過(guò)程
    iter = 0                        # 外循環(huán)迭代次數(shù)計(jì)數(shù)器
    while tNow >= tFinal:           # 外循環(huán)，直到當(dāng)前溫度達(dá)到終止溫度時(shí)結(jié)束
        # 在當(dāng)前溫度下，進(jìn)行充分次數(shù)(nMarkov)的狀態(tài)轉(zhuǎn)移以達(dá)到熱平衡
        for k in range(nMarkov):    # 內(nèi)循環(huán)，循環(huán)次數(shù)為Markov鏈長(zhǎng)度
            # 產(chǎn)生新解：
            tourNew = mutateSwap(tourNow, nCities)      # 通過(guò) 交換操作 產(chǎn)生新路徑
            valueNew = calTourMileage(tourNew,nCities,distMat) # 計(jì)算當(dāng)前路徑的總長(zhǎng)度
            deltaE = valueNew - valueNow
            # 接受判別：按照 Metropolis 準(zhǔn)則決定是否接受新解
            if deltaE < 0:                          # 更優(yōu)解：如果新解的目標(biāo)函數(shù)好于當(dāng)前解，則接受新解
                accept = True
                if valueNew < valueBest:            # 如果新解的目標(biāo)函數(shù)好于最優(yōu)解，則將新解保存為最優(yōu)解
                    tourBest[:] = tourNew[:]
                    valueBest = valueNew
            else:                                   # 容忍解：如果新解的目標(biāo)函數(shù)比當(dāng)前解差，則以一定概率接受新解
                pAccept = math.exp(-deltaE/tNow)    # 計(jì)算容忍解的狀態(tài)遷移概率
                if pAccept > random.random():
                    accept = True
                else:
                    accept = False
            # 保存新解
            if accept == True:                      # 如果接受新解，則將新解保存為當(dāng)前解
                tourNow[:] = tourNew[:]
                valueNow = valueNew
        # 平移當(dāng)前路徑，以解決變換操作避開 0,（n-1）所帶來(lái)的問(wèn)題，并未實(shí)質(zhì)性改變當(dāng)前路徑。
        tourNow = np.roll(tourNow,2)                # 循環(huán)移位函數(shù)，沿指定軸滾動(dòng)數(shù)組元素
        # 完成當(dāng)前溫度的搜索，保存數(shù)據(jù)和輸出
        recordBest.append(valueBest)                # 將本次溫度下的最優(yōu)路徑長(zhǎng)度追加到 最優(yōu)路徑記錄表
        recordNow.append(valueNow)                  # 將當(dāng)前路徑長(zhǎng)度追加到 當(dāng)前路徑記錄表
        print('i:{}, t(i):{:.2f}, valueNow:{:.1f}, valueBest:{:.1f}'.format(iter,tNow,valueNow,valueBest))
        # 緩慢降溫至新的溫度，
        iter = iter + 1
        tNow = tNow * alfa                              # 指數(shù)降溫曲線：T(k)=alfa*T(k-1)
    # 結(jié)束模擬退火過(guò)程
    # 圖形化顯示優(yōu)化結(jié)果
    figure1 = plt.figure()     # 創(chuàng)建圖形窗口 1
    plot_tour(tourBest, valueBest, coordinates)
    figure2 = plt.figure()     # 創(chuàng)建圖形窗口 2
    plt.title("Optimization result of TSP{:d}".format(nCities)) # 設(shè)置圖形標(biāo)題
    plt.plot(np.array(recordBest),'b-', label='Best')           # 繪制 recordBest曲線
    plt.plot(np.array(recordNow),'g-', label='Now')             # 繪制 recordNow曲線
    plt.xlabel("iter")                                          # 設(shè)置 x軸標(biāo)注
    plt.ylabel("mileage of tour")                               # 設(shè)置 y軸標(biāo)注
    plt.legend()                                                # 顯示圖例
    plt.show()
    print("Tour verification successful!")
    print("Best tour: \n", tourBest)
    print("Best value: {:.1f}".format(valueBest))
    exit()
if __name__ == '__main__':
    main()

5、運(yùn)行結(jié)果

程序的運(yùn)行結(jié)果只供參考，顯然這并不是最優(yōu)結(jié)果。

Tour verification successful!
Best tour: 
 [18  7 40  2 16 17 31 38 39 36 24 27 26 11 50  3  5  4 23 47 37 14 42  9
  8 32 10 51 13 12 25 46 28 29  1  6 41 20 30 21  0 48 35 34 33 43 45 15
 49 19 22 44]
Best value: 9544.0

在這里插入圖片描述