|
经典优化算法——模拟退火 各路参考资料上的模拟退火算法都太晦涩难懂了，刚刚简单的学习了一下，希望可以以一种简单的方式说明模拟退火的作用
模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
简单来说，就是通过设置迭代次数（即退火时温度下降的速度）来达到不断优化结果，计算全局最优解的过程。 下面将从一道题目入手，大致讲解算法：  那么首先，我们需要先计算出任意两位置之间的举例，由于给定值为经纬度，将过建立三维直角坐标系的方式，计算任意两点间的劣弧长度记作两点之间的距离。 即：  化简可得 下面进行算法实现部分
##库的引入
from random import*
import numpy as np
from math import*
from matplotlib import pyplot as plt
points=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 |