堆优化模拟退火（List-Based Simulated Annealing） 算法
引入
堆优化模拟退火（List-Based Simulated Annealing，简称 LBSA） 是一种对 模拟退火 的优化算法。由 Shi-hua Zhan,, Juan Lin, Ze-jun Zhang, Yi-wen Zhong, 提出。（以下我们以求最小值为例）
解释
我们定义当前温度为 \(t\) ，已知状态为 \(x\) ，新状态为 \(y\)， 能量（值）的计算函数为 \(f\)。根据 模拟退火 可以得到发生状态转移（修改最优解）的概率 \(p\) 为（公式1）：
\[p=\begin{cases}
1 & \text{if}\ f(y)\le f(x) \\
e^{\frac{-(f(y)-f(x))}{t}} & \text{otherwise}
\end{cases}
\]
相反，如果我们知道发生状态转移的概率 \(p\)， 那么我们就可以计算出相应的温度 \(t\)。
证明过程
-
首先，将等式两边取对数，得到 \(\ln(p)=\frac{-(f(y)-f(x))}{t}\)。
-
然后，将等式两边相乘得到 \(t\ln(p)=-(f(y)-f(x))\)。
-
最后，将等式两边除以 \(\ln(p)\) 得到 \(t=\frac{-(f(y)-f(x))}{\ln(p)}\)。
可以得到相应的温度 \(t\) 为（公式2）：
\[t=\frac{-(f(y)-f(x))}{\ln(p)}
\]
生成初始温度堆
顾名思义，堆优化，那肯定有堆！其实我们是要生成一个初始的温度堆，里面存储了大量的温度。温度堆怎么生成呢？下图表对此进行了解释：
graph TD
a(温度堆生成开始) --> b[定义初始状态 $x$<br/>创建空的温度堆 $L$<br/>定义温度堆长度 $L$<sub>$max$</sub><br/>定义初始发生状态转移的概率 $p$<br/>$i=0$] --> c[创建新状态 $y$] --> d{"$f(y)＜f(x)$ （解更优）"} --NO--> f["计算温度 $t=(-(f(y)-f(x)))/\ln(p)$（公式2）    <br/>将温度 $t$ 插入温度堆 $L$ 中<br/>$i++$"] --> g{"$i < L$<sub>$max$</sub>"} --Yes-->c
d --Yes--> e["$x=y$（更新状态）"] --> f
g --NO--> h[结束]
（做图表真的累）
我们一般定义 \(p=0.1\)。
这个温度堆为大根堆，即温度越高，优先级越高。重复相同的程序，直到填满。
温度控制
对于第 \(i\) 次模拟退火，我们会跑 \(M\) 次。定义当前温度堆最大值为 \(t_{max}\) ，已知状态与新状态的值差为 \(d_i\)，那么发生状态转移的概率 \(p_i\) 为（公式3）：
\[p_i=e^{-d_i/t_{max}}
\]
以上可以通过公式 1 得出（应该是一毛一样）。
根据Metropolis算法（Metropolis acceptance criterion），每次遇到一个较差的新状态，生成一个从0到1的随机小数 \(r\)。如果 \(r\) 小于发生状态转移的概率 \(p\)，则将接受较差的新状态，同时通过以下公式算出新的温度 \(t_i\)（公式4）：
\[t_i=\frac{-d_i}{\ln(r_i)}
\]
证明可参见公式 2 的证明。
更新列表
对于第 \(i\) 次模拟退火，我们跑完 \(M\) 次后，将最大值 \(t_{max}\) 从堆里删去，插入上述 \(t_i\) 的平均值，然后进行下一次模拟退火。
下图表对此进行了详细解释：
graph TD
a(LBSA开始) --> b[生成温度堆<br/>生成状态 $x$<br/>$k=0$] --> c[从温度堆 $L$ 堆顶取出最大值 $T$<sub>$max$</sub><br/>$k++,t=0,c=0,m=0$] --> d[创建新状态 $y$<br/>$m++$] --> e{"$f(y)＜f(x)$ （解更优）"} --No--> f["定义$d_i=−(f(y)-f(x))$<br/>$p=exp(-d_i/t$<sub>$max$</sub>$)$（公式3）<br/>生成从0到1的随机数 $r$"] --> g{"$r\le p$"} --Yes--> h["$t=t+(-d_i/\ln(r))$     <br/>c++"] --> i["$x=y$     "] --> j[$m\le M$] --No--> k{"$c==0?$     "} --No--> l["弹出温度堆 $L$ 堆顶<br/>插入 $t/c$"] --> m{$k\le K$} --No--> n(LBSA结束)
e --Yes--> i
g --No--> j
j --Yes--> d
k --Yes--> m
m --Yes--> c