經典優化演算法——模擬退火
各路參考資料上的模擬退火演算法都太晦澀難懂了，剛剛簡單的學習了一下，希望可以以一種簡單的方式說明模擬退火的作用
- 模擬退火演算法來源于固體退火原理，是一種基于概率的演算法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小，
簡單來說，就是通過設定迭代次數（即退火時溫度下降的速度）來達到不斷優化結果，計算全域最優解的程序，
下面將從一道題目入手，大致講解演算法：
那么首先，我們需要先計算出任意兩位置之間的舉例，由于給定值為經緯度，將過建立三維直角坐標系的方式，計算任意兩點間的劣弧長度記作兩點之間的距離，
即：
化簡可得
下面進行演算法實作部分
##庫的引入
from random import*
import numpy as np
from math import*
from matplotlib import pyplot as pltpoints=np.loadtxt(r'填寫csv檔案路徑',delimiter=',')##進行檔案的讀寫
number_of_points=points.shape[0]
points=np.array(points)
R=1##地球半徑，對優化程序無影響故只設為1
def dis(i,j):
temp=np.cos(points[i][0]-points[j][0])*np.cos(points[i][1])*np.cos(points[j][1])+np.sin(points[i][1])*np.sin(points[j][1])
return R*np.arccos(temp)T0=100000000##初始溫度
Tf=1##降溫停止溫度
alpha=0.95##降溫比例
wbest=[]
fbest=0
##初始化距離矩陣
distance=np.zeros((number_of_points,number_of_points))
'''
for i in range(number_of_points):
for j in range(number_of_points):
distance[i][j]=dis(i,j)
'''
for i in range(number_of_points):
for j in range(number_of_points):
distance[i][j] = sqrt((points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2)
##初始化初解
p=[]
for i in range(number_of_points):
p.append(i)
np.random.shuffle(p)##亂序排列points
print(p)
p=np.array(p)
for i in range(len(p)-1):
fbest+=distance[p[i]][p[i+1]]
fbest+=distance[p[0]][p[-1]]##初始化最佳長度
wbest=p.copy()##初始化最佳路徑
f_now=fbest
w_now=wbest.copy()
##開始進行優化
while T0>Tf:
for i in range(10):
x1 = [0 for q in range(number_of_points)]
p1,p2=randint(0,number_of_points-1),randint(0,number_of_points-1)##進行隨機取址操作
n = [p1, p2]
n.sort()
p1, p2 = n
##更新路徑
if p1>0:
x1[0:p1]=w_now[0:p1]
x1[p1:p2+1]=w_now[p2:p1-1:-1]
x1[p2+1:number_of_points]=w_now[p2+1:number_of_points]
else:
x1[0:p1] = w_now[0:p1]
x1[p1:p2 + 1] = w_now[p2::-1]
x1[p2 + 1:number_of_points] = w_now[p2 + 1:number_of_points]
##更新距離
f=0
for j in range(number_of_points-1):
f+=distance[w_now[j]][w_now[j+1]]
f+=distance[w_now[0]][w_now[-1]]
if f_now>=f:
f_now=f
w_now=x1.copy()
if f_now<f:
t=f_now-fbest
if random() < exp(-t/T0):
f_now = f
w_now = x1.copy()
if f < fbest:
fbest = f
wbest = x1.copy()
T0*=alpha
print(wbest)
print(fbest)
plt.title('SA_TSP')
plt.xlabel('x')
plt.ylabel('y')
plt.scatter(points[...,0],points[...,1])
plt.plot(points[wbest,0],points[wbest,1])
plt.plot([points[wbest[-1],0],points[wbest[0],0]],[points[wbest[-1],1],points[wbest[0],1]],ms = 2)
plt.show()
最后運行就是這樣啦（因為資料太多了，所以偷懶只采集的一部分）
模擬退火的本質其實只是一個貪心演算法，通過邏輯抽象，模擬固體退火的物理情景，不斷的隨機取位進行計算，使得答案靠近全域最優
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/249487.html
標籤：python
上一篇：PyQt5入門（七）常用控制元件
下一篇：python中四舍五入的講解