本文目錄一覽：
模擬退火求tsp問題可以用python編程嗎
模擬退火求tsp問題可以用python編程
也許最初設計 Python 這種語言的人並沒有想到今天Python 會在工業和科研上獲得如此廣泛的使用。著名的自由軟件作者Eric Raymond 在他的文章《如何成為一名黑客》中，將Python 列為黑客應當學習的四種編程語言之一，並建議人們從Python 開始學習編程。這的確是一個中肯的建議，對於那些從來沒有學習過編程或者並非計算機專業的編程學習者而言，Python 是最好的選擇之一。Python 第一次學習Python，我只用了不到二十分鐘的時間，站在書店裡把一本教初學編程的人學習Python 的書翻了一遍。也是從那時起，我開始被這種神奇的語言吸引。 Python 可以用來開發symbian 上的東西。 易用與速度的完美結合Python 是一種用起來很方便的語言，很多初學Java 的人都會被 Java 的CLASSPATH 搞得暈頭轉向，花上半天的時間才搞明白原來是CLASSPATH 搞錯了自己的 Hello World 才沒法運行。
python實現TSP問題的案例
import math
from os import path
import numpy as np
import matplotlib.pyplot as plt
class TSPInstance:
”’
設計一個類，實現從文件讀入一個旅行商問題的實例
文件格式為：
city number
best known tour length
list of city position (index x y)
best known tour (city index starts from 1)
以文件01eil51.txt為例：
第一行51為城市數
第二行426為最優解的路徑長度
第三行開始的51行為各個城市的序號、x坐標和y坐標
最後是最優解的訪問城市系列（注意裏面城市序號從1開始，而python的sequence是從0開始）
Eil51Tour.png是最優解的城市訪問順序圖
”’
def __init__(self, file_name):
”’
從文件file_name讀入旅行商問題的數據
”’
self.file_name=file_name
a= open(file_name)
# 城市數量
self.city_num = a.readline()
# 返回坐標 51行，3列
self.city = np.zeros((int(self.city_num), 3))
# x坐標
self.x = np.zeros(int(self.city_num))
# y坐標
self.y = np.zeros(int(self.city_num))
# 城市ID
self.id = np.zeros(int(self.city_num))
b = a.readlines()
for i, content in enumerate(b):
if i in range(1, 52 ):
# 單行賦值
self.city[i-1] = content.strip(‘\n’).split(‘ ‘)
self.x[i-1] = self.city[i-1][1]
self.y[i-1] = self.city[i-1][2]
for i, content in enumerate(b):
if i in range(53, 104):
self.id[i – 53] = content.strip(‘\n’)
@property
def citynum(self):
”’
返回城市數
”’
return self.city_num
@property
def optimalval(self):
”’
返回最優路徑長度
”’
c = 0
i = 1
s = open(self.file_name)
str = s.readlines()
for content in str:
if i == 2:
c = content
i = i + 1
return c
@property
def optimaltour(self):
”’
返回最優路徑
”’
tour = np.array(self.id)
return tour
def __getitem__(self, n):
”’
返回城市n的坐標,由x和y構成的tuple:(x,y)
”’
(x, y) = (self.x[n-1], self.y[n-1])
return (x, y)
def get_distance(self, n, m):
”’
返回城市n、m間的整數距離（四捨五入）
”’
u=int(self.x[n-1] – self.x[m-1])
v=int(self.y[n-1] – self.y[m-1])
dis = math.sqrt(pow(u,2) + pow(v,2))
return int(dis+0.5)
def evaluate(self, tour):
”’
返回訪問系列tour所對應的路徑程度
”’
dis = 0
for i in range(50):
dis += self.get_distance(int(tour[i]), int(tour[i + 1]))
dis += self.get_distance(int(tour[50]), int(tour[0]))
return dis
def plot_tour(self, tour):
”’
畫出訪問系列tour所對應的路徑路
”’
for i in range(51):
x0,y0 = self.__getitem__(i)
plt.scatter(int(x0),int(y0),s=10,c=’c’)
#記住坐標點的畫法
for i in range(len(tour)-1):
x1,y1 = self.__getitem__(int(tour[i]))
x,y = self.__getitem__(int(tour[i+1]))
plt.plot([x1,x],[y1,y],c=’b’)
x2,y2 = self.__getitem__(int(tour[0]))
x3,y3 = self.__getitem__(int(tour[len(tour)-1]))
plt.plot([x2,x3],[y2,y3],c=’b’)
plt.xlabel(‘x label’)
plt.ylabel(‘y label’)
plt.title(“City access sequence diagram”)
plt.plot()
plt.show()
if __name__ == “__main__”:
file_name = path.dirname(__file__) + “/1.txt”
instance = TSPInstance(file_name)
print(instance.citynum)
print(instance.evaluate(instance.optimaltour))
print(instance.optimaltour)
print(instance.__getitem__(2))
print(instance.get_distance(0, 1))
instance.plot_tour(instance.optimaltour)
”’
output:
51
426
[ 1. 22. 8. 26. 31. 28. 3. 36. 35. 20. 2. 29. 21. 16. 50.
34. 30. 9. 49. 10. 39. 33. 45. 15. 44. 42. 40. 19. 41. 13.
25. 14. 24. 43. 7. 23. 48. 6. 27. 51. 46. 12. 47. 18. 4.
17. 37. 5. 38. 11. 32.]
(49.0, 49.0)
14
”’
其實解決TSP問題有很多方法，比如模擬退火算法，貪心算法，回溯算法等等。希望各位博友可以把你們的解決方法出現在評論區。
Python怎麼做最優化
一、概觀scipy中的optimize子包中提供了常用的最優化算法函數實現。我們可以直接調用這些函數完成我們的優化問題。optimize中函數最典型的特點就是能夠從函數名稱上看出是使用了什麼算法。下面optimize包中函數的概覽：1.非線性最優化fmin — 簡單Nelder-Mead算法fmin_powell — 改進型Powell法fmin_bfgs — 擬Newton法fmin_cg — 非線性共軛梯度法fmin_ncg — 線性搜索Newton共軛梯度法leastsq — 最小二乘2.有約束的多元函數問題fmin_l_bfgs_b —使用L-BFGS-B算法fmin_tnc —梯度信息fmin_cobyla —線性逼近fmin_slsqp —序列最小二乘法nnls —解|| Ax – b ||_2 for x=03.全局優化anneal —模擬退火算法brute –強力法4.標量函數fminboundbrentgoldenbracket5.擬合curve_fit– 使用非線性最小二乘法擬合6.標量函數求根brentq —classic Brent (1973)brenth —A variation on the classic Brent（1980）ridder —Ridder是提出這個算法的人名bisect —二分法newton —牛頓法fixed_point7.多維函數求根fsolve —通用broyden1 —Broyden』s first Jacobian approximation.broyden2 —Broyden』s second Jacobian approximationnewton_krylov —Krylov approximation for inverse Jacobiananderson —extended Anderson mixingexcitingmixing —tuned diagonal Jacobian approximationlinearmixing —scalar Jacobian approximationdiagbroyden —diagonal Broyden Jacobian approximation8.實用函數line_search —找到滿足強Wolfe的alpha值check_grad —通過和前向有限差分逼近比較檢查梯度函數的正確性二、實戰非線性最優化fmin完整的調用形式是：fmin(func, x0, args=(), xtol=0.0001, ftol=0.0001, maxiter=None, maxfun=None, full_output=0, disp=1, retall=0, callback=None)不過我們最常使用的就是前兩個參數。一個描述優化問題的函數以及初值。後面的那些參數我們也很容易理解。如果您能用到，請自己研究。下面研究一個最簡單的問題，來感受這個函數的使用方法：f(x)=x**2-4*x+8，我們知道，這個函數的最小值是4，在x=2的時候取到。from scipy.optimize import fmin #引入優化包def myfunc(x):return x**2-4*x+8 #定義函數x0 = [1.3] #猜一個初值xopt = fmin(myfunc, x0) #求解print xopt #打印結果運行之後，給出的結果是：Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]程序準確的計算得出了最小值，不過最小值點並不是嚴格的2，這應該是由二進制機器編碼誤差造成的。除了fmin_ncg必須提供梯度信息外，其他幾個函數的調用大同小異，完全類似。我們不妨做一個對比：from scipy.optimize import fmin,fmin_powell,fmin_bfgs,fmin_cgdef myfunc(x):return x**2-4*x+8×0 = [1.3]xopt1 = fmin(myfunc, x0)print xopt1printxopt2 = fmin_powell(myfunc, x0)print xopt2printxopt3 = fmin_bfgs(myfunc, x0)print xopt3printxopt4 = fmin_cg(myfunc,x0)print xopt4給出的結果是：Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 531.99999999997Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 12Gradient evaluations: 4[ 2.00000001]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 15Gradient evaluations: 5[ 2.]我們可以根據給出的消息直觀的判斷算法的執行情況。每一種算法數學上的問題，請自己看書學習。個人感覺，如果不是純研究數學的工作，沒必要搞清楚那些推導以及定理云云。不過，必須了解每一種算法的優劣以及能力所及。在使用的時候，不妨多種算法都使用一下，看看效果分別如何，同時，還可以互相印證算法失效的問題。在from scipy.optimize import fmin之後，就可以使用help(fmin)來查看fmin的幫助信息了。幫助信息中沒有例子，但是給出了每一個參數的含義說明，這是調用函數時候的最有價值參考。有源碼研究癖好的，或者當你需要改進這些已經實現的算法的時候，可能需要查看optimize中的每種算法的源代碼。在這裡：https:/ / github. com/scipy/scipy/blob/master/scipy/optimize/optimize.py聰明的你肯定發現了，順着這個鏈接往上一級、再往上一級，你會找到scipy的幾乎所有源碼！
模擬退火算法每次的解為什麼不一樣?
模擬退火每次的解不同是很正常的，因為模擬退火本身是一種隨機算法，轉移向更差的解不是必然而是概率性的，也就是說每次執行算法時，執行過程轉移到的解可能都是完全不一樣的。
至於TSP問題，本身屬於NP-hard問題，找不到存在多項式時間複雜度的解。
如果要求精確的解，目前可行的方法有枚舉、分支限界、動態規劃等，但這些方法適用的數據範圍都很小，一旦數據規模變大，它們都將無能為力。
所以目前廣泛使用的大都是一些隨機算法，比如蟻群、遺傳等，模擬退火就是其中的一種，這些算法的一大特點就是通過隨機去逼近最優解，但也有可能得到錯解。
只有窮舉法可以保證得到最優解，但是窮舉法在數據量比較大的時候運行時間通常是不能接受的，所以用了各種近似方法。
模擬退火算法新解的產生和接受可分為如下四個步驟：
第一步是由一個產生函數從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。
第三步是判斷新解是否被接受,判斷的依據是一個接受準則，最常用的接受準則是Metropolis準則: 若ΔT0則接受S′作為新的當前解S，否則以概率exp(-ΔT/T)接受S′作為新的當前解S。
第四步是當新解被確定接受時，用新解代替當前解，這隻需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時，則在原當前解的基礎上繼續下一輪試驗。
原創文章，作者：VANKI，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/329185.html
微信掃一掃 
支付寶掃一掃 