071. 编写一个函数，实现简单的模拟退火算法

模拟退火算法（Simulated Annealing, SA）是一种通用的概率算法，用于在大搜索空间内寻找问题的近似最优解。它通过模拟物理中的退火过程，允许算法在搜索过程中接受劣解，从而避免陷入局部最优解。以一个简单的优化问题为例：最小化一个函数 f(x) 的值。

示例

假设我们要最小化函数 f(x)=x2，其中 x 是一个实数，范围在 [−10,10] 之间。

模拟退火算法的基本步骤

初始化：随机生成一个初始解。
计算适应度：计算当前解的适应度（目标函数值）。
生成新解：通过某种方式生成一个新的解。
接受准则：根据 Metropolis 准则决定是否接受新解。
降温：逐渐降低温度，重复上述步骤，直到满足终止条件（如温度足够低或达到最大迭代次数）。

代码

import random
import math

# 目标函数
def objective_function(x):
    return x ** 2

# 模拟退火算法
def simulated_annealing(initial_x, initial_temp, cooling_rate, stopping_temp, stopping_iter):
    """
    模拟退火算法

    :param initial_x: 初始解
    :param initial_temp: 初始温度
    :param cooling_rate: 降温速率
    :param stopping_temp: 停止温度
    :param stopping_iter: 停止迭代次数
    :return: 最优解和最优值
    """
    current_temp = initial_temp
    current_solution = initial_x
    current_cost = objective_function(current_solution)
    best_solution = current_solution
    best_cost = current_cost

    iteration = 0

    while current_temp > stopping_temp and iteration < stopping_iter:
        # 生成新解（在当前解附近随机扰动）
        new_solution = current_solution + random.uniform(-1, 1)
        new_solution = max(-10, min(10, new_solution))  # 限制解的范围
        new_cost = objective_function(new_solution)

        # Metropolis 准则
        if new_cost < current_cost or random.uniform(0, 1) < math.exp((current_cost - new_cost) / current_temp):
            current_solution = new_solution
            current_cost = new_cost

            # 更新最优解
            if new_cost < best_cost:
                best_solution = new_solution
                best_cost = new_cost

        # 降温
        current_temp *= cooling_rate
        iteration += 1

        # 打印当前状态
        print(f"Iteration {iteration}: Best Cost = {best_cost:.4f}, Current Temp = {current_temp:.4f}")

    return best_solution, best_cost

# 示例用法
if __name__ == "__main__":
    initial_x = random.uniform(-10, 10)  # 初始解
    initial_temp = 100.0  # 初始温度
    cooling_rate = 0.99  # 降温速率
    stopping_temp = 1e-8  # 停止温度
    stopping_iter = 1000  # 停止迭代次数

    best_solution, best_cost = simulated_annealing(initial_x, initial_temp, cooling_rate, stopping_temp, stopping_iter)
    print(f"Best Solution: {best_solution:.4f}")
    print(f"Best Cost: {best_cost:.4f}")

代码说明

目标函数：定义了一个简单的目标函数 f(x)=x2。
初始化：随机生成一个初始解 initial_x，范围在 [−10,10] 之间。
生成新解：通过在当前解附近随机扰动生成新解。这里使用 random.uniform(-1, 1) 生成一个小的扰动值。
接受准则：使用 Metropolis 准则决定是否接受新解。如果新解更优，或者以一定概率接受劣解，从而避免陷入局部最优。
降温：每次迭代后，温度乘以 cooling_rate 逐渐降低。
终止条件：当温度低于 stopping_temp 或达到最大迭代次数 stopping_iter 时，停止迭代。

示例输出

Iteration 1: Best Cost = 1.2345, Current Temp = 99.0000
Iteration 2: Best Cost = 0.9876, Current Temp = 98.0100
...
Iteration 1000: Best Cost = 0.0001, Current Temp = 0.0000
Best Solution: 0.0001
Best Cost: 0.0001

注意事项

参数调整：初始温度、降温速率、停止温度和停止迭代次数等参数对算法性能有重要影响，需要根据具体问题进行调整。
解的范围：在生成新解时，需要确保解在合法范围内。可以通过 max 和 min 函数限制解的范围。
接受准则：Metropolis 准则允许接受劣解，从而增加算法跳出局部最优解的机会。
多样性保持：通过适当的降温速率和接受准则，可以保持搜索过程中的多样性，避免过早收敛。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)