当前位置：首页 > news >正文

模拟退火算法

news 2024/10/27 22:20:49

一、优化问题

经典（传统）优化算法：动态（线性）规划、排序
离散：通过对解空间进行枚举，缺点：解空间太大，很难求解出结果。
连续：目标函数微分，缺点：如果不是凸优化问题，容易得出局部最优解，不是全局最优解。
求解优化问题时，大多数问题只能求解近似解：近似算法、随机算法、启发式算法。

1.1、启发式算法

启发式算法：通过对过去经验的归纳推理以及实验分析来解决问题的方法，以求得问题的次优解或以一定的概率求其最优解（不能确定得到的解就是最优解，但通常得到的解比局部最优解要好），所以可以认为启发式算法一种基于经验或者实验算法的统称。
元启发式算法：从自然界的一些现象取得灵感(模拟退火、遗传算法)，通过这些现象获取的求解过程来解决实际的一些问题。元启发式算法看成构造启发式算法的一些基础方法，而启发式算法就是利用元启发式算法，结合被求解问题的特征，设计出来的面向特定问题的算法。
启发式算法 =元启发式算法+问题特征

1.2、经典启发式算法（元启发式算法）

模拟退火算法、遗传算法、蚁群算法。

1.2.1、传统梯度下降算法（贪心算法）的缺陷。

（1）算法只会往梯度下降的方向走，因此，起始随机点没选择好，模型只会达到局部最优，达不到全局最优。（启发：如果随机生成足够多均匀分布的点，是否可以解决缺陷，答案：取决于求解函数的复杂程度或者理解足够多的点是否能覆盖到全局最低点附近）
（2）梯度算法核心理念：当求解最小（大）值时，生成的随机点随机走一步，如果是向梯度下降（上升）的方向前进，100%接受，如果是向梯度上升的方向前进，不接受，回到起始位置。模拟退火算法理念是如果随机点是向梯度下降的方向前进，100%接受，如果随机点是向梯度上升的方向前进，会以p的概率接受，那么就可能绕开局部最优点，从而找到全局最优点。

1.2.2、模拟退火算法原理

模拟退火算法源于固体退火原理，是一种基于概率的贪心算法。当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。
在这里插入图片描述
图左：在初始状态，固体内部的粒子存在非均匀状态。
图中：加热到一定温度，增强其粒子的热运动，使粒子偏离其平衡位置，消除原来的非均匀状态。
图右：让温度慢慢降低，达到热平衡状态，粒子逐渐均匀有序，最终达到内能（粒子越散乱内能越高，越整齐内能越低）最小的状态。

1.2.3、模拟退火算法流程

在这里插入图片描述
针对第四点拓展：若目标函数f在第i+1步移动后比第i步更优，即f(Y(i+1))<=f(Y(i))，则总是接受该移动;若f( Y(i+1))>f( Y(i))(即移动后的解比当前解要差)，则以一定的概率接受移动而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)。
Metroplis准则:温度越高，算法接受新解的概率越高。这个根据一定概率选择是否接受新解的方法叫做Metropolos准则。温度越高，接受“错误解”的概率越高，步长越大；温度越低，接受“错误解”的概率越低，步长越小（前期找到更多的区域，后期找到局部区域）
在这里插入图片描述

模拟退火算法中重要的两个循环：内循环（Metroplis算法），外循环（退火算法）。
内循环：每个温度下多次迭代，寻找最小值
外循环：从高温按照冷却步长（降温系数）使温度逐渐下降，最终达到终止温度的过程。

二、案例

#求解：p=x**2+2*x+32*y+4*y**2-15,x,y在[-5,5]之间，求p的最小值。
import math
from random import random
import matplotlib.pyplot as pltdef func(x,y):res=x**2+2*x+32*y+4*y**2-15return resclass SA:def __init__(self,func,iter=100,T0=1000,Tf=0.01,alpha=0.99):self.func=funcself.iter=iter   # 迭代次数self.T0=T0       # 初始温度self.Tf=Tf       # 终止温度self.T=T0        # 当前温度self.alpha=alpha # 退火系数(冷却步长)self.x=[random()*11-5 for i in range(iter)] #随机生成100个xself.y=[random()*11-5 for i in range(iter)] #随机生成100个yself.most_best=[]self.history={'f':[],'T':[]}def generate_new(self,x,y):  #扰动生成新解while True:new_x=x+self.T*(random()-random()) #random()-random()保证x值向左或者向右new_y=y+self.T*(random()-random())if (new_x>=-5 and new_x<=5) and (new_y>=-5 and new_y<=5):break               # 在[-5,5]之间重复得到新解，直到新解满足条件return new_x,new_ydef Metroplis(self,f,f_new):  #Metroplis准则if f_new <= f:return 1else:p=math.exp((f-f_new)/self.T)if random()<p:return 1else:return 0def best(self):     #获得最优目标函数值f_list=[]       #保存每次迭代之后的值for i in range(self.iter):f=self.func(self.x[i],self.y[i])f_list.append(f)f_best=min(f_list)idx=f_list.index(f_best)return f_best,idx  #返回最优值和最优值对应的索引def run(self):count=0#外循环迭代，当前温度小于终止温度的阈值while self.T>self.Tf:#内循环迭代100次for i in range(self.iter):f=self.func(self.x[i],self.y[i])   #迭代一次后的值new_x,new_y=self.generate_new(self.x[i],self.y[i]) #产生新解f_new=self.func(new_x,new_y)       #新解对应的值if self.Metroplis(f,f_new):         #判断是否接受新解self.x[i]=new_xself.y[i]=new_y#迭代L次后，更新最优解f_best,idx=self.best()self.history['f'].append(f)self.history['T'].append(self.T)#温度按照一定比例下降（冷却）self.T=self.alpha*self.Tcount+=1#得到最优解f_best,idx=self.best()print(f"F={f_best},x={self.x[idx]},y={self.y[idx]}")sa=SA(func)
sa.run()
plt.plot(sa.history['f'],sa.history['T'])
plt.title('SA')
plt.xlabel('f')
plt.ylabel('T')
plt.gca().invert_xaxis()
plt.show()