模拟退火
算法相關參數
- 初始溫度：T0
- 目前溫度：t
- 結束溫度：Tend
- 疊代次數：Times
- 溫度衰減系數：a
- 目标函數內插補點（目前解和新解之間的函數內插補點）：δ
- 接受新解的機率 ：p = e-(δ/t)
算法效果分析
- 疊代次數越多，溫度衰減系數約大（即溫度衰減得越慢），搜尋次數越多，程式運作越慢，相對來 得到的解更可信
- “ 渣 男 ” 套 路 ： 前 期 廣 撒 網 ， 後 期 精 準 打 擊 。 \color{red}{“渣男”套路：前期廣撒網，後期精準打擊。} “渣男”套路：前期廣撒網，後期精準打擊。模拟退火算法前期要增加接受新解的機率，以便于擴大我們的搜尋範圍，避免陷入局部最優解；算法後期要減少接受新解的機率，避免丢棄目前最優解
- 目标函數內插補點越大，接受新解的機率越大；随着疊代次數的增加，溫度t逐漸減小，接受新解的機率越小
算法步驟
- 資料初始化：計算距離矩陣（dist[i][j]表示i城市與j城市之間的距離）；随機得到初始解（起點為0城市）；編寫距離計算函數
- 在每個溫度下，進行Times次疊代
- 每次疊代時：求得新路徑并計算其路徑長度（通過二次變換法和資料切片交換來求得新解）
- 若得到的新路徑長度小于目前路徑長度，則更新目前路徑和目前路徑長度，若與此同時新路徑長度還優于最優路徑長度，則同時更新最優路徑及其長度
- 模拟退火算法的核心：若得到的新路徑長度大于等于目前路徑長度，則根據相應函數計算機率，通過随機數和此時的機率相比較，進而決定是否接收新路徑（即劣解）
- 直到目前溫度小于結束溫度時，算法結束
- 調參來優化模型
# -*- coding: utf-8 -*-
import random
import matplotlib.pyplot as plt
import numpy as np
import math
import sys
import copy
import time
#解決中文顯示問題
plt.rcParams['font.sans-serif'] = ['KaiTi'] # 指定預設字型
plt.rcParams['axes.unicode_minus'] = False # 解決儲存圖像是負号'-'顯示為方塊的問題
# 初始溫度,結束溫度
T0 = 100
Tend = 1e-20
#循環控制常數,疊代次數
Times = 50000
# 溫度衰減系數
a = 0.999
#原始資料
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]])
num = coordinates.shape[0]# 城市數目
coord_x = coordinates[:,0]# 城市橫坐标
coord_y = coordinates[:,1]# 城市縱坐标
route_origin = list(range(num)) # 初始解
sumDist_origin= 0.0 # 初始距離
dist = np.zeros((num,num))# 生成距離矩陣,記錄兩個城市之間的距離
# 初始化距離矩陣
def initDist():
for i in range(num):
x_i = coord_x[i]
y_i = coord_y[i]
for j in range(i, num):
x_j = coord_x[j]
y_j = coord_y[j]
dist[i, j] = dist[j, i] = math.sqrt((x_i - x_j) ** 2 + (y_i - y_j) ** 2)# 對稱矩陣
return dist
dist = initDist()
def shuffle(my_list):
"""
對可行解進行排列組合，除去起點
:param my_list: 可行解
:return:
"""
temp_list = my_list[1:] # 資料切片，左閉右開，擷取除起點以外的所有元素
np.random.shuffle(temp_list)
shuffle_list = my_list[:1] + temp_list # 切片的拼接
return shuffle_list
#初始化初始解
def initRoute():
global num, route_origin
# route = random.sample(range(0, num), num)
route_origin = shuffle(route_origin)
# 使用上次程式運作得到的最優解：容易陷入局部7947.836346399286
# 計算總距離
def getSumDist(route, num, dist):
sumDist = 0.0
for i in range(num - 1):
sumDist += dist[int(route[i])][int(route[i + 1])]
sumDist += dist[int(route[num - 1])][int(route[0])]
return sumDist
#擷取新解
def getNewRoute(route, time, num):
route_current = copy.copy(route)
# 偶次疊代，二變換法
u = 0 # u，v，randint要去除起點終點
v = 0
if time % 2 == 0:
while u == 0 | u == num - 1 | v == 0 | v == num - 1:
u = random.randint(0, num - 1)
v = random.randint(0, num - 1)
temp = route_current[u]
route_current[u] = route_current[v]
route_current[v] = temp
# 奇次疊代，多組資料交換
else:
c1 = random.randint(1, num - 2)
c2 = random.randint(1, num - 2)
c3 = random.randint(1, num - 2)
sort_c = sorted([c1, c2, c3])
c1 = sort_c[0]
c2 = sort_c[1]
c3 = sort_c[2]
temp1 = route_current[:c1]
temp2 = route_current[c1:c2]
temp3 = route_current[c2:c3]
temp4 = route_current[c3:]
route_current = temp1 + temp3 + temp2 + temp4
return route_current
# 模拟退火核心代碼
def SACore():
# 新解，新距離
print("route_origin:", route_origin)
print("sumDist_origin:", sumDist_origin)
route_current = route_origin
sumDist_current = sumDist_origin
route_new = np.zeros(num)
sumDist_new = 0.0
route_best = np.zeros(num)
sumDist_best = sumDist_origin
t = T0
while True:
if t < Tend:
break
for time in range(Times):#疊代次數
route_new = getNewRoute(route_current, time, num)
sumDist_new = getSumDist(route_new, num, dist)
delt = sumDist_new - sumDist_current
if delt <= 0:#新路線距離更短
route_current = route_new
sumDist_current = sumDist_new
if sumDist_best > sumDist_new:#是最優距離
route_best = route_new
sumDist_best = sumDist_new
else:#模拟退火算法的核心，以一定比率接收差解
p = math.exp(-delt / t)
randomp = random.uniform(0, 1)
if randomp < p:
route_current = route_new
sumDist_current = sumDist_new
t = t * a
# print("目前溫度:", t)
# print("**********************")
print("最佳路徑：", route_best)
print("最佳距離：", sumDist_best)
if __name__ == '__main__':
start = time.time()
initRoute()
sumDist_origin = getSumDist(route_origin, num, dist)
SACore()
end = time.time()
print('Running time: %s Seconds' % (end - start))
"""
最佳路徑： [0, 21, 49, 19, 22, 29, 6, 1, 41, 20, 30, 17, 16, 2, 44, 31, 48, 34, 38, 35, 33, 36, 39, 37, 47, 23, 5, 14, 4, 3, 24, 45, 43, 15, 28, 46, 25, 26, 12, 13, 51, 10, 11, 50, 32, 42, 9, 8, 7, 40, 18, 27, 0]
最佳距離： 9636.344979299336
最佳路徑： [0, 21, 30, 22, 49, 19, 29, 1, 6, 41, 20, 16, 2, 17, 44, 31, 48, 35, 34, 33, 38, 39, 37, 36, 47, 23, 4, 14, 5, 3, 24, 45, 43, 15, 28, 46, 25, 26, 12, 13, 51, 10, 11, 50, 32, 42, 9, 8, 7, 40, 18, 27, 0]
最佳距離： 9451.034445650703
最佳路徑： [0, 21, 30, 22, 49, 19, 29, 1, 6, 41, 20, 16, 2, 17, 31, 48, 35, 34, 33, 38, 39, 36, 37, 47, 23, 4, 14, 5, 3, 24, 45, 43, 15, 28, 46, 25, 26, 12, 13, 51, 10, 11, 50, 32, 42, 9, 8, 7, 40, 44, 18, 27, 0]
最佳距離： 9378.514369030105
最佳路徑： [0, 21, 30, 22, 19, 49, 29, 1, 6, 41, 20, 16, 2, 17, 31, 48, 35, 34, 33, 38, 39, 36, 37, 47, 23, 4, 14, 5, 3, 24, 45, 43, 15, 28, 46, 25, 26, 12, 13, 51, 10, 11, 50, 32, 42, 9, 8, 7, 40, 44, 18, 27, 0]
最佳距離： 9371.600543296801
最佳路徑： [0, 21, 35, 38, 39, 36, 37, 23, 47, 14, 4, 5, 42, 3, 24, 11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 32, 9, 8, 40, 7, 18, 44, 31, 48, 34, 33, 45, 15, 28, 49, 19, 22, 16, 2, 17, 30, 20, 29, 41, 6, 1, 43, 0]
最佳距離： 8858.531529765904
最佳路徑： [0, 21, 35, 38, 39, 36, 37, 47, 23, 4, 14, 5, 3, 24, 11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 34, 33, 45, 15, 28, 49, 19, 22, 29, 16, 2, 17, 30, 20, 41, 6, 1, 43, 0]
最佳距離： 8684.306665303991
最佳路徑： [0, 21, 35, 38, 39, 36, 37, 47, 23, 4, 14, 5, 3, 24, 11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 32, 42, 9, 8, 7, 40, 18, 44, 31, 48, 34, 33, 45, 15, 28, 49, 19, 22, 29, 16, 2, 17, 30, 20, 41, 6, 1, 43, 0]
最佳距離： 8461.633757845264
最佳路徑： [0, 48, 31, 21, 30, 20, 41, 6, 1, 29, 22, 19, 49, 28, 15, 45, 43, 33, 34, 35, 38, 39, 36, 37, 47, 23, 4, 5, 3, 24, 11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 32, 42, 8, 9, 7, 40, 18, 44, 2, 16, 17, 14, 0]
最佳距離： 8398.198925957735
最佳路徑： [0, 21, 17, 30, 2, 16, 20, 41, 6, 1, 29, 22, 19, 49, 28, 15, 45, 43, 33, 34, 38, 39, 37, 4, 5, 3, 24, 11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 32, 42, 8, 9, 7, 40, 18, 44, 31, 48, 35, 36, 47, 23, 14, 0]
最佳距離： 8113.096167712638
最佳路徑： [0, 21, 17, 2, 16, 30, 20, 41, 6, 1, 29, 22, 19, 49, 28, 15, 45, 43, 33, 34, 38, 39, 37, 4, 5, 3, 24, 11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 32, 42, 9, 8, 7, 40, 18, 44, 31, 48, 35, 36, 47, 23, 14, 0]
最佳距離： 8072.726662911702
最佳路徑： [0, 21, 30, 17, 2, 16, 20, 41, 6, 1, 29, 22, 19, 49, 28, 15, 45, 43, 33, 34, 38, 39, 37, 4, 5, 3, 24, 11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 32, 42, 9, 8, 7, 40, 18, 44, 31, 48, 35, 36, 47, 23, 14, 0]
最佳距離： 7947.836346399286
GA結果:
[0, 21, 29, 22, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 36, 37, 33, 43, 45, 15, 28, 19, 49, 34, 35, 38, 39, 4, 5, 23, 47, 14, 3, 24, 42, 32, 50, 11, 10, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 21, 0]
10112.612313214102
"""
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)