启发式算法Python实现（一） 模拟退火

文章目录

• • • • 语言感知描述
      • 伪代码
      • python实现

不懂为什么网上各种把很简单的模拟退火讲的那么复杂，感觉好像英文版的讲的总比中文的简单。之后的启发式算法全以英文维基百科 + Python实例代码为基础作为讲解和总结。

语言感知描述

1. 选初始点
2. 选邻居点，计算初始点和邻居点谁离我最终目标更近，更近的话就更新，否则以一定的概率取邻居点。类似贪心算法，我又感觉像DQN了，maxQ的意味了，强化学习荼毒太深。
3. 更新温度，同时更新的是以一定概率的这个概率

伪代码

官方原话需要注意的点

• When T \displaystyle T T tends to zero, the probability P ( e , e ′ , T ) \displaystyle P(e,e&#x27;,T) P(e,e′,T) must tend to zero if e ′ &gt; e \displaystyle e&#x27;&gt;e e′>e and to a positive value otherwise. The probability P ( e , e ′ , T ) \displaystyle P(e,e&#x27;,T) P(e,e′,T) was equal to 1 when e ′ &lt; e \displaystyle e&#x27;&lt;e e′<e
• To be precise, for a large T \displaystyle T T , the evolution of s \displaystyle s s is sensitive to coarser energy variations, while it is sensitive to finer energy variations when T \displaystyle T T is small.

其中temperature()可理解为温度改变的function，neighbour(s)可理解为选择邻居的function。

假设 P ( E ( s ) , E ( s n e w ) , T ) = e x p − ( E ( s ) − E ( s n e w ) ) / T P(E(s),E(s_{new}),T)=exp^{-(E(s)-E(s_{new}))/T} P(E(s),E(snew​),T)=exp−(E(s)−E(snew​))/T，则可以理解 E ( s ) − E ( s n e w ) E(s)-E(s_{new}) E(s)−E(snew​)为loss，这个要为正值。

python实现

求解10sin(5x)+7cos(4x)的最小值，由于迭代次数的原因，这边最终取到的可能是局部极小值

# SA(simulated annealing)
import math
import random

# 求解10sin(5x)+7cos(4x)的最小值
def function(x):
    return 10*math.sin(5*x) + 7*math.cos(4*x)

def SA(f):
	# 初始x值
    x = 2
    # 初始温度
    T = 10
    # 冷却系数
    cool = 0.9
    # 迭代终止规则
    while T > 0.1:
        f_old = f(x)
        x_n = x + random.random()
        f_new = f(x_n)
        # loss值
        delta = f_new - f_old
		# 模拟退火算法
        if delta <= 0 or math.exp(-delta/T) >= random.random():
            x = x_n

        T *= cool

        print(x, f(x))


SA(function)


           

TODO 待更新，快递员例子手刷