解释

模拟退火算法是启发式算法的一种。

所谓退火，指的是固体温度越高时，其内部粒子能量越大，运动无序且越快速。而当温度降低后，内部粒子趋于稳定、有序。

模拟退火算法基于这一原理，将初始解（多个）所处状态假定为高温状态。在高温状态下，针对每一个解生成邻域解，并基于一定规则更新解。一轮更新过后，降低温度，进入下一轮更新，直到温度低于指定的最低温度。然后从所有解中选一个最好的。

实例

假设我们要在固定 $y = 0$ 的情况下，找到最小化 Rastrigin 函数的 $x$ 值（$0 \leq x \leq 100$），那么应当执行以下步骤：

1. 初始化温度为 $t$，生成随机初始解（多个）。
2. 遍历每一个当前解：
   1. 计算对应的价值（Rastrigin 函数值，$y = 0$）。
   2. 生成邻域解。
   3. 如果邻域解合法，计算对应价值。
   4. 如果价值小于原解的价值，更新解。
   5. 如果价值大于原解的价值，以概率 $p$ 更新解。
3. 降低温度
4. 重复步骤 2 - 3，直到当前温度低于指定温度。
5. 从所有解中取最好作为最优解。

代码

'''
@Auther: ArslanTu
@Email: [email protected]
@Data: 2023-03-18 15:34:15
@Description: impletation of a sample Simulated Annealing algorithm
'''

from math import cos, exp, pi
from random import random
from typing import Any

def func_z(x: float, y: float) -> float:
    """
    a function to calculate z with x and y

    Args:
        x (float): first param, which is in [0, 100]
        y (float): second param

    Returns:
        float: z value
    """
    z = 10 + (x ** 2 - 10 * cos(2 * pi * x)) + (y ** 2 - 10 * cos(2 * pi * y))
    return z

def SA(init_t: int, min_t: int, dec_rate: float, iter_turns: int, value_func: Any, fix_param: Any) -> Any:
    """
    Simulated Annealing

    Args:
        init_t (int): initial temprature
        min_t (int): min temprature
        dec_rate (float): temprature decreasing rate
        iter_turns (int): iterate turns
        value_func (Any): fuction to assess current x
        fix_param (Any): fixed parameter

    Returns:
        Any: final result
    """
    t = init_t
    x = [random() * 100] * iter_turns  # initialize the result (iter_turns)
    while t > min_t:  # as the current temprature > min temprature
        for idx in range(iter_turns):
            value_x = value_func(x[idx], fix_param)  # last value correspoding to x
            x_new = x[idx] + random() * 2 - 1
            if x_new < 0 or x_new > 100:  # out of range
                continue
            value_x_new = value_func(x_new, fix_param)
            if value_x_new < value_x:  # new x take a smaller value
                x[idx] = x_new
            else:  # replace the old with probability p
                p = 1 / (1 + exp(-(value_x_new - value_x)/(iter_turns * t)))
                if random() >= p:
                    x[idx] = x_new
        t *= dec_rate
    return min(x, key=lambda elem: value_func(elem, fix_param))

for i in range(6):
    print(f"初始温度为 10 ^ {10 * i} 时的最优解为：{SA(10 ** (10 * i), 1, 0.98, 10 ** 3, func_z, 0):0.20f}")

输出

初始温度为 10 ^ 0 时的最优解为：59.53250435927851214046
初始温度为 10 ^ 10 时的最优解为：0.00041577641466106208
初始温度为 10 ^ 20 时的最优解为：0.00323047272596399537
初始温度为 10 ^ 30 时的最优解为：0.00046046021559620343
初始温度为 10 ^ 40 时的最优解为：0.00041888395213107721
初始温度为 10 ^ 50 时的最优解为：0.00091232426549958667

可以看到，虽然存在波动（也因为参数取得比较少），但整体趋势还是朝着最优解方向的。