計算機設計大賽國獎作品_5. 模擬退火求解旅行商問題

本系列是2021年中國大學生計算機設計大賽作品“環境監測無人機航線優化”的相關文檔，獲得2021年西北賽區一等獎，國賽三等獎。學生習作，只供大家參考。

計算機設計大賽國獎作品_1. 項目概要
計算機設計大賽國獎作品_2. 報名材料
計算機設計大賽國獎作品_3. 需求分析
計算機設計大賽國獎作品_4. 界面設計
計算機設計大賽國獎作品_5. 核心算法
[計算機設計大賽國獎作品_6. 測試報告]
[計算機設計大賽國獎作品_7. 安裝使用]
[計算機設計大賽國獎作品_8. 項目總結]
[計算機設計大賽國獎作品_9. PPT]

作品名稱：環境監測無人機航線優化

第三章 詳細設計

3.2 模擬退火求解旅行商問題

3.2.1 模擬退火算法概述

模擬退火算法是解決大規模組合優化問題的常用方法，可以解決無人機飛行路線的路徑優化問題。

模擬退火算法結構簡單，由溫度更新函數、狀態產生函數、狀態接受函數和內循環、外循環終止準則構成。
溫度更新函數是指退火溫度緩慢降低的實現方案，也稱冷卻進度表；狀態產生函數是指由當前解隨機產生新的候選解的方法；狀態接受函數是指接受候選解的機制，通常采用Metropolis準則。
外循環是由冷卻進度表控制的溫度循環；內循環是在每一溫度下循環迭代產生新解的次數，也稱Markov鏈長度。

模擬退火算法的基本步驟如下：

（1） 隨機產生初始解 X_0；

（2）在溫度 $T_k$下進行 $L_k$ 次循環迭代：由當前解 $X_{old}$ 產生新的候選解 $X_{new}$，并按 Metropolis 接受準則以一定的概率接受候選解 $X_{new}$ 作為當前解：
$$?E=E(X_{new})?E(X_{old})$$
$$P=\{\begin{array}{l}1,?E<0\\ exp((??E)/T_k),?E\ge 0\end{array}$$

這里 $E_{old}$、$E_{new}$分別是當前解 $X_{old}$、新解 $X_{new}$ 的目標函數值。

（3）按照冷卻進度表控制退火溫度，從溫度初值緩慢降低，直到達到溫度終值結束。

模擬退火算法要從當前解的鄰域中產生新的候選解。新解的產生機制是在當前解序列的基礎上進行變換操作，隨機改變序列中某些點的排列次序，常見的基本變換操作有交換算子(Swap Operator)、反序算子（Inversion Operator）、移位算子(Move Operator)等。

交換算子將當前路徑 S_now 中的第 i 個城市 C_i 與第 j 個城市 C_j 的位置交換，得到新路徑 S_swap ：

• S_now = C_1?C_(i-1)?(C_i)?C_(i+1)?C_(j-1)?(C_j)?C_(j+1)?C_n
• S_swap= C_1?C_(i-1)?(C_j)?C_(i+1)?C_(j-1)?〖(C〗i)?C(j+1)?C_n

反序算子也稱2-opt，將當前路徑 S_now 中從第 i 個城市 C_i 到第 j 個城市 C_j 之間的城市排列順序反向翻轉，得到新路徑 S_inv ：

• S_now = C_1?C_(i-1)?(C_i?C_(i+1)?C_(j-1)?C_j)?C_(j+1)?C_n
• S_inv = C_1?C_(i-1)?〖(C〗j?C(j-1)?C_(i+1)?C_i)?C_(j+1)?C_n

以下兩節因涉及待發表論文，暫不公開。

3.2.2 操作算子的等價關系

（略）

3.2.3 聯合算子改進算法

（略）

3.3 模擬退火求解旅行商問題 Python 程序

# SATSP_demo_V1_20201212.py # 模擬退火算法求解旅行商問題 DEMO 程序 # v1.0: # 模擬退火求解旅行商問題（TSP）基本算法 # (1) 直接讀取城市坐標數據（CTSP31） # (2) 僅采用2-交換方式產生新解 # (3) 圖形輸出：最優路徑圖，優化過程圖 # (4) 城市間距離取整 # Copyright 2020 YouCans, XUPT # Crated：2020-12-15# -*- coding: utf-8 -*- import math # 導入模塊 math import random # 導入模塊 random import pandas as pd # 導入模塊 pandas 并簡寫成 pd import numpy as np # 導入模塊 numpy 并簡寫成 np import matplotlib.pyplot as plt # 導入模塊 matplotlib.pyplot 并簡寫成 pltnp.set_printoptions(precision=4) pd.set_option('display.max_rows', 20) # youcans pd.set_option('expand_frame_repr', False) pd.options.display.float_format = '{:,.2f}'.format# 子程序：初始化模擬退火算法的控制參數 def initParameter():# custom function initParameter():# Initial parameter for simulated annealing algorithmtInitial = 100.0 # 設定初始退火溫度(initial temperature)tFinal = 1 # 設定終止退火溫度(stop temperature)alfa = 0.985 # 設定降溫參數，T(k)=alfa*T(k-1)nMarkov = 500 # Markov鏈長度，也即內循環運行次數return alfa,nMarkov,tInitial,tFinal# 子程序：計算各城市間的距離，得到距離矩陣 def getDistMat(nCities, coordinates):# custom function getDistMat(nCities, coordinates):# computer distance between each 2 CitiesdistMat = np.zeros((nCities,nCities)) # 初始化距離矩陣for i in range(nCities):for j in range(i,nCities):# np.linalg.norm 求向量的范數（默認求 二范數），得到 s1、s2 間的距離distMat[i][j] = distMat[j][i] = round(np.linalg.norm(coordinates[i]-coordinates[j]))return distMat # 城市間距離取整（四舍五入）# 子程序：計算 TSP 路徑長度 def caltourMileage(tour, nCities, distMat):# custom function caltourMileage(nCities, tour, distMat):# compute mileage of the given tourmileageTour = 0.0 # 路徑長度 置 0for i in range(nCities-1): # dist(0,1),...dist((n-2)(n-1))mileageTour += distMat[tour[i], tour[i+1]]mileageTour += distMat[tour[nCities-1], tour[0]] # dist((n-1),0)return round(mileageTour) # 路徑總長度取整（四舍五入）# 子程序：交換操作算子 def mutateSwap(tour, 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) 產生 2個不相等的隨機整數 s1,s2s1 = np.random.randint(nCities) # 產生第一個 [0,n) 區間內的隨機整數while True:s2 = np.random.randint(nCities) # 產生一個 [0,n) 區間內的隨機整數if s1!=s2: break # 保證 s1, s2 不相等tourSwap = tour.copy() # 將給定路徑復制給新路徑 tourSwap#tourSwap[s1] = tour[s2] # 交換 城市 s1 和 s2 的位置#tourSwap[s2] = tour[s1]# 交換 城市 s1 和 s2 的位置————簡潔的實現方法# 特別注意：深入理解深拷貝和淺拷貝的區別，注意內存中的變化，謹慎使用tourSwap[s1],tourSwap[s2] = tour[s2],tour[s1]return tourSwap# 子程序：繪制 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') # 繪制城市坐標點 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') # 繪制城市坐標點 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 xupt of TSP{:d}".format(num)) # 設置圖形標題plt.show()def main():# 主程序# 讀取旅行城市位置的坐標"""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]"""coordinates = np.array([[1164.6,399.2],[1172.0,391.3],[1214.8,312.2],[1065.4,295.9],[911.1,299.7],[876.8,437.7],[1062.7,384.7],[1116.5,408.2],[1083.3,228.4],[1266.3,457.5],[1253.5,438.8],[1233.8,418.0],[1144.8,380.3],[1125.3,378.7],[1017.4,365.6],[1170.0,366.5],[1136.0,347.6],[1187.8,320.4],[1172.7,318.6],[1201.9,302.6],[1193.0,260.8],[1158.9,286.8],[1130.0,282.1],[1143.1,305.2],[1132.3,231.6],[1103.5,200.2],[1037.3,360.3],[1089.5,342.7],[1040.6,306.7],[1067.1,265.7],[1027.3,250.4]]) # CTSP31nCities = coordinates.shape[0] # 根據輸入的城市坐標 獲得城市數量 nCitiesdistMat = getDistMat(nCities,coordinates) # 調用子程序，計算城市間距離矩陣tourNow = np.arange(nCities) # 產生初始路徑，返回一個初值為0、步長為1、長度為n 的排列tourBest = tourNow.copy() # 初始化最優路徑，將 tourNow 復制給 tourBestvalueNow = caltourMileage(tourNow,nCities,distMat) # 計算當前路徑的總長度valueBest = valueNow # 初始化最優路徑的總長度alfa,nMarkov,tInitial,tFinal = initParameter() # 調用子程序，獲得模擬退火算法的設置參數# 開始模擬退火優化過程iter = 0 # 外循環迭代次數計數器recordBest = [] # 初始化 最優路徑記錄表recordNow = [] # 初始化 最優路徑記錄表tNow = tInitial # 初始化 當前溫度(current temperature)while tNow >= tFinal: # 外循環，直到當前溫度達到終止溫度時結束# 在當前溫度下，進行充分次數(nMarkov)的狀態轉移以達到熱平衡for k in range(nMarkov): # 內循環，循環次數為Markov鏈長度# 產生新解：通過在當前解附近隨機擾動而產生新解，新解必須在 [min,max] 范圍內tourNew = mutateSwap(tourNow,nCities) # 通過 交換操作 產生新路徑valueNew = caltourMileage(tourNew,nCities,distMat) # 計算當前路徑的總長度# 接受判別：按照 Metropolis 準則決定是否接受新解if valueNew < valueNow: # 更優解：如果新解的目標函數好于當前解，則接受新解accept = Trueelse: # 容忍解：如果新解的目標函數比當前解差，則以一定概率接受新解deltaE = valueNew - valueNowpAccept = math.exp(-deltaE/tNow) # 計算容忍解的狀態遷移概率if pAccept > random.random():accept = Trueelse:accept = False# 保存新解if accept == True: # 如果接受新解，則將新解保存為當前解tourNow[:] = tourNew[:]valueNow = valueNewif valueNew < valueBest: # 如果新解的目標函數好于最優解，則將新解保存為最優解tourBest[:] = tourNew[:]valueBest = valueNew# 完成當前溫度的搜索，保存數據和輸出recordBest.append(valueBest) # 將本次溫度下的最優路徑長度追加到 最優路徑記錄表recordNow.append(valueNow) # 將當前路徑長度追加到 當前路徑記錄表print('i:{}, t(i):{:.2f}, valueNow:{:.1f}, valueBest:{:.1f}'.format(iter,tNow,valueNow,valueBest))# 緩慢降溫至新的溫度，降溫曲線：T(k)=alfa*T(k-1)tNow = tNow * alfaiter = iter + 1# 結束模擬退火過程print("Best xupt: \n", tourBest)print("Best value: {:.1f}".format(valueBest))# 圖形化顯示優化結果figure1 = plt.figure() # 創建圖形窗口 1plot_tour(tourBest,valueBest,coordinates)figure2 = plt.figure() # 創建圖形窗口 2plt.title("Optimization youcans of TSP{:d}".format(nCities)) # youcans@xuptplt.plot(np.array(recordBest),'b-', label='Best') # 繪制 recordBest曲線plt.plot(np.array(recordNow),'g-', label='Now') # 繪制 recordNow曲線plt.xlabel("iter") # 設置 x軸標注plt.ylabel("mileage of tour") # 設置 y軸標注plt.legend() # 顯示圖例plt.show()exit()if __name__ == '__main__':main()

版權聲明：

youcans@xupt 原創作品，轉載必須標注原文鏈接：(https://blog.csdn.net/youcans/article/details/124004941)

Copyright 2022 youcans, XUPT
Crated：2022-4-15

計算機設計大賽國獎作品_1. 項目概要
計算機設計大賽國獎作品_2. 報名材料
計算機設計大賽國獎作品_3. 需求分析
計算機設計大賽國獎作品_4. 界面設計
計算機設計大賽國獎作品_5. 核心算法
[計算機設計大賽國獎作品_6. 測試報告]
[計算機設計大賽國獎作品_7. 安裝使用]
[計算機設計大賽國獎作品_8. 項目總結]
[計算機設計大賽國獎作品_9. PPT]

總結

以上是生活随笔為你收集整理的计算机设计大赛国奖作品_5. 模拟退火求解旅行商问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。