Samxander's home

You shall see the difference now that we are back again!

0%

模拟退火算法

发表于

模拟退火算法

模拟退火思想(以寻找山的最高峰为例)

  • 显然，此时朴素贪心算法会失效

  • 首先在可见范围内，随机选择一点

  • 若该点比当前位置更高，就直接去该点
  • 如果该点更低，那么有一定概率去该点
  • 在刚才的局部最优解的峰，会有一定概率走下了当前山峰，从而发现另一个山峰的上坡
  • 从而就有可能走上新的更高峰

算法关键点

  • 时间有限，需要设置终止条件 (“退火”过程中温度不断降低，剩余时间不多时就别乱跑)
  • 若当前所处的山峰越高，前往低点的概率越低 (概率的表达式)

适用赛题

  • 可行解过多
    • 有些规划类问题的可行解过多，传统算法运算时间过长
    • 能够列出可行解的任意排列
  • NP-hard问题
    • 旅行推销员问题 (TSP)：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路
    • TSP问题是组合优化中的一个NP-hard问题，该问题的可行解是所有顶点的全排列，随着点数的增加，会产生组合爆炸，传统算法难以求解
    • 此时就适合用模拟退火等启发式算法求近似解

原理与求解思路

例题：

  • 已知全国34个省会城市（包括直辖市、自治区首府和港澳台）的经纬度坐标（第一个为北京）
  • 现在需要从北京出发，到所有城市视察
  • 要求每个城市只能到达一次，并最终回到北京
  • 求视察路线方案，使得总路径最短

令北京为1号城市 $x_1$，剩下33个城市依次设为 $x_2,x_3,…,x_{34}$；

设第 $i$ 号城市 $x_i$ 与第 $i+1$ 号城市 $x_{i+1}$ 之间的路径长度为 $d_{x_i x_{i+1}}$，则目标函数： $min \ f(x_1,x_2,…,x_{35}) = \sum_{i=1}^{34} d_{x_i x_{i+1}}$

1.初始化

  • 在最开始，需设定一个初始温度 $T_0$ 和问题的一个初始解 $x(0)$
  • 也可用蒙特卡洛法求一个较好的初始解

2.随机产生新解

  • 在当前温度 $T_i$ 下随机求一个解 $x’$，制定产生新解的准则 (准则不唯一，能确保随机即可)
  • 假设上一步的解为： $x_1x_2…x_{u-1} x_{u} x_{u+1} … x_{v-1} x_{v} x_{v+1}…x_{35}$
  • 随机选序号 $u,v$ ，将 $u$ 到 $v$ 这部分转为逆序，得到解： $x_1x_2…x_{u-1} x_{v} x_{v-1} … x_{u+1} x_{u} x_{v+1}…x_{35}$

3.计算目标函数差值

  • 随机得到的解 $x’$ 和当前解 $x(i)$ ，两种方案总路径的差值记为 $\Delta f$ :

    $ \Delta f = (d_{x_{u-1} x_{v}} + d_{x_{u} x_{v+1}}) - (d_{x_{u-1} x_{u}} + d_{x_{v} x_{v+1}})$

4.是否接受新解

  • 接受准则：

  • 显然，$\Delta f$ 越小，意味着随机解的总路径比原解的总路径短更多，那么接受 $x’$ 的概率就越大

5.马尔科夫过程

  • 在当前温度 $T_i$ 下，重复2、3、4步
  • 新解 $x(i+1)$ 只与 $x(i)$ 有关，而与更早的 $x(i-1),x(i-2),…,x(0)$无关
  • 这是个马尔科夫过程，$x’$ 在原解 $x(i)$ 的邻域中符合均匀分布

6. 退火过程

  • 选定降温系数 $\alpha$，求得新温度 $T_{i+1} = \alpha T_i$，此处设为0.999
  • 再重复2、3、4、5步；然后继续降低温度

7.结束条件

  • 直到温度足够小，设终止温度为 $ e = 10^{-30}$，当 $T < e$ 时终止迭代，输出最终解
  • 退火过程足够慢、每个温度下寻找新解的次数足够多，则最终解是全局最优解的概率越大

理论上，模拟退火可以找到全局最优

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>

// 假设的目标函数 f(x)，我们要最小化该函数
double objective_function(double x) {
    return x * x - 4 * x + 4; // 例如 f(x) = x^2 - 4x + 4
}

// 模拟退火算法
double simulated_annealing(double (*obj_func)(double), double start, double end, double temp, double cooling_rate, int iterations) {
    double current_solution = start + (end - start) * ((double) rand() / RAND_MAX); // 随机初始解
    double current_energy = obj_func(current_solution);
    double best_solution = current_solution;
    double best_energy = current_energy;

    for (int i = 0; i < iterations; i++) {
        // 生成一个邻域解
        double neighbor = current_solution + (rand() % 2 == 0 ? 1 : -1) * ((double) rand() / RAND_MAX) * 0.1; // 邻域解

        double neighbor_energy = obj_func(neighbor);
        
        // 计算接受概率
        if (neighbor_energy < current_energy || exp((current_energy - neighbor_energy) / temp) > ((double) rand() / RAND_MAX)) {
            current_solution = neighbor;
            current_energy = neighbor_energy;
        }

        // 更新最优解
        if (current_energy < best_energy) {
            best_solution = current_solution;
            best_energy = current_energy;
        }

        // 降温
        temp *= cooling_rate;
    }

    return best_solution; // 返回最优解
}

int main() {
    srand(time(0)); // 随机数种子

    // 设置模拟退火的参数
    double start = -10.0;         // 搜索空间的起始点
    double end = 10.0;            // 搜索空间的结束点
    double initial_temperature = 1000.0;  // 初始温度
    double cooling_rate = 0.99;   // 降温速率
    int iterations = 10000;       // 迭代次数

    // 执行模拟退火算法
    double result = simulated_annealing(objective_function, start, end, initial_temperature, cooling_rate, iterations);

    std::cout << "最优解: " << result << std::endl;
    std::cout << "最优目标函数值: " << objective_function(result) << std::endl;

    return 0;
}
Insist on writing original high-quality articles. Your support is my biggest motivation.