啟發式算法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 待更新，快遞員例子手刷