最大字段和 模拟退火算法 题解
2025-01-25 10:23:18 #模拟退火算法 #算法

最大字段和 使用模拟退火算法的题解

原题解来自洛谷

最大字段和 题目
原题解

一、模拟退火算法原理
概览：

模拟退火算法是一种基于概率的启发式搜索算法，可以有效的避免局部最优解。该算法模拟了金属的退火过程，将金属加热到高温，再缓慢冷却，以此来找最优解，避免局部最优解。

如何 以及 为何模拟金属退火过程？

物理退火过程分为三个阶段

  1. 加热： 材料被加热到高温状态，原子处于高度活跃状态，能量较高
  2. 冷却： 材料冷却，原子逐渐稳定，能量降低
  3. 平衡： 温度足够低的时候，材料到达能量最低的稳定状态

启发：

  • 试想如果让我们用肉眼算出一个迷宫的走法，我们会一步步计算概率还是随机选取一个方向走走看。
  • 试想如果走走看之后，发现无法抵达，我们是选择从头开始选取路线，还是回到上一步之前的某个随机的位置重新走一遍。

在求解时，我们可以像肉眼走迷宫一样随机多次的选择初始路线，然后慢慢基于当前路线随机改动。
在这个过程中最重要的一点是肉眼走迷宫时其实并非完全的随机改动路线，而是我们结合了迷宫大小、当前路线等等的因素，在脑内生成的一个感官上较为合理的路线(我不可能直接选一个看起来走不通的路)
模拟退火算法正是解决了怎么“选取”一个较为合理的解,这里的合理并非是指距离迷宫终点最近，而是有可能在最短路上，哪怕他看起来距离迷宫终点更远了。

模拟退火算法求解迷宫问题的阶段：

  1. 初始阶段：算法随机选择一个初始解(可以是完全的随机)
  2. 扰动阶段：对初始解添加一个随机扰动，生成一个新解，如果新解更优就接受新解，如果新解更劣，就条件接受劣解。
    扰动阶段分为两个阶段：
    2.1. 高温阶段：较高概率接受劣解，以便算法可以更广阔的探索迷宫
    2.2. 低温阶段：已经广阔的探索了迷宫，此时较低的概率接受劣解，以便得到一个当前路线的最优解

注意算法需要多次运行，也就是多次退火，因为要多次的选取初始解。

那么条件接受劣解是什么条件呢？

算法会根据Metropolis准则来决定是否接受这个劣解。具体来说，接受劣解的概率由以下公式决定：

1
P(接受新解)=e^{-ΔE/T}

其中：
ΔE=f(新解)−f(旧解) 是新解与当前解的目标函数值之差
T 是当前温度
当新解更优时ΔE<0, P>1, 则100%接受新解
当新解更劣时ΔE>0, p<1, 就以P条件接受新解
T温度一直降低，若为劣解，则P一直减小，所以接受劣解的概率以这个公式降低

所以只要确定目标函数后，就可以简单的应用模拟退火算法。目标函数是计算当前解优劣的函数，需要自己设计。

下面将用样例来具体的说明如何取目标函数和应用模拟退火算法

二、模拟退火算法解决最大子段和问题

最大字段和 题目

首先对于模拟退火算法，设置退火操作次数fire、初始温度T、终止温度eps、降温系数A。

1
2
const double T = 2e4,A=0.98,eps=1e-5;
const int fire = 15000;

退火过程伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 多次退火
for(int i = 1 ; i<= fire; i++){
        //生成初始解
        //定义中间温度
        double t = T
        //如果t大于最低温度
        while(t>eps){
            //添加随机扰动，生成新解
            //计算新解与旧解目标函数的差值 delta
            if(delta <= 0) 
                //劣解，以概率接受新解
            else 
                //优解，接受新解
            t=T*A // 降温
        }
       
}

下面介绍该题目如何生成新解、设计目标函数、概率接受新解

根据题意有4个操作

  1. 左移子段左端点
  2. 右移子段左端点
  3. 左移子段右端点
  4. 右移子段右端点

所以： 随机选取一个操作，再随机选取移动的距离dis, dis的范围最好和T成正比，这样温度下降时搜索范围也减小，便于选取到最优值。
然后判断新子段是否合法,合法继续
再判断新解是否要接受(delta = 新子段和 - 旧子段和)，为了快速计算子段和需要用前缀和优化。
接受新解的概率就是上述的公式
具体代码请移步
最大字段和

2025-01-25 10:23:18 #模拟退火算法 #算法