Simulated Annealing

模拟退火最大值算法：

• 初始化起始解 $x_0$ 、温度$t_0$ 以及迭代次数 steps，计算初始值 $y_0$
• 扰动产生新解 $x_1$, 计算对应函数值 $y_1$
• 依据 $\Delta y=y_1-y_0$ 决策是否接受新解，具体决策方式依据以下概率公式：

$$p=\{\begin{array}{rlr}1& & \Delta y>0\\ e^{\Delta y/T}& & \Delta y<0\end{array}$$

• 更新温度 $T_1=T_0/ln(1+t)=T_0/ln(1+1)$
• 重复以上步骤直至达到退出条件

以求解函数 $F(x)=x\cdot cos(x)+x，x\in (0,15)$ 最大值为例 :

import math
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt


def F(x):
    return np.power(x, 0.5) * np.cos(x) + x


num_of_samples = 64
X = np.linspace(0, 15, num_of_samples).reshape(-1, 1)
Y = F(X)
plt.plot(X, Y, label='F(x)')

算法实验如下：

def max_by_simulated_annealing(t0, steps):
    x0 = np.random.uniform(0, 15, 1)
    y0 = F(x0)
    
    x_max = x0
    y_max = y0
    
    for t in range(1, steps + 1):
        xt = np.random.normal(x0, 1, 1)
        while xt < 0 or xt > 15:
            xt = np.random.normal(x0, 1, 1)
        
        yt = F(xt)
        y_delta = yt - y0
        if y_delta > 0:
            x0 = xt
            y0 = yt
        else :
            p = math.exp(y_delta / t0)
            if np.random.uniform(0, 1) < p:
                x0 = xt
                y0 = yt
        if y0 > y_max:
            x_max = x0
            y_max = y0
            
        t0 = t0 / math.log(1 + t)
        
    return x_max, y_max

首先尝试初始温度$T_0=5$, 迭代次数 $steps=1000$ :

row = 4
line = 4
plt.figure(figsize=(16, 12), dpi=80)
for i in range(1, row * line + 1):
    plt.subplot(row,line,i)
    x_hat, y_hat = max_by_simulated_annealing(5, 1000)
    plt.plot(X, Y, label='F(x)')
    plt.scatter([x_hat], [y_hat], marker='+', label='maximum')
    plt.legend()

16 次模拟中有 9次得到最大值，7次得到次优解：

尝试初始温度$T_0=10$, 迭代次数 $steps=1000$

row = 4
line = 4
plt.figure(figsize=(16, 12), dpi=80)
for i in range(1, row * line + 1):
    plt.subplot(row,line,i)
    x_hat, y_hat = max_by_simulated_annealing(10, 1000)
    plt.plot(X, Y, label='F(x)')
    plt.scatter([x_hat], [y_hat], marker='+', label='maximum')
    plt.legend()

16 次模拟中有 6次得到最大值，10次得到次优解：

原文地址：https://blog.csdn.net/gaofeipaopaotang/article/details/140243075

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！