最近在做华为的一个比赛,用到了退火算法来实现设备的最大资源利用率的分配问题,先来说下具体问题吧,这个问题是个典型的装箱问题,比如你有5个设备种类,每个种类需要占用一定量的资源1和一定量的资源2,现在你有很多箱子,每个箱子可以容纳一定的资源1和资源2,现在要保证用最少的箱子装配所有的设备,你要如何分配?


这就是一个典型的装箱问题,解决思路有很多,典型的贪心算法或者动态规划都可以对其求解,但是贪心算法不能保证是最优解,动态规划倒是可以高效的解决这个问题,刚好最近接触了退火算法,退火也是可以解决这个问题的,下面就先来简单的介绍一下退火算法:

先说下退火算法的由来,
在热力学上,退火(annealing)现象指物体逐渐降温的物理现象,温度愈低,物体的能量状态会低;够低后,液体开始冷凝与结晶,在结晶状态时,系统的能量状态最低。大自然在缓慢降温(亦即,退火)时,可“找到”最低能量状态:结晶。但是,如果过程过急过快,快速降温(亦称「淬炼」,quenching)时,会导致不是最低能态的非晶形。


从退火的由来就可以看出,退火方法就是尽可能的去寻找全局最优解的,退火方法试用用哪些场景呢?先来思考下面这个问题,对于下面这条曲线,要怎么去寻找它的全局最小值呢?

                                                


你可能觉得,这很简单嘛,遍历这个线上的所有点,然后取最小值就行了嘛,但是考虑这种情况,这条线非常非常长,就只有几个比较靠近的波谷位置,就像下图这样





再去遍历这条曲线就显得很浪费了,怎么去优化这个算法呢?最直观的感受就是可以先尝试下贪心算法,当一个点的前面一个点和后面一个点都比这个点的值大时,这个点肯定是这附近的最小值了嘛,但是这也出现了很明显的问题,最小值的点可能不是全局最优解,怎么办呢?这个时候,就引入了退火算法,退火算法本质上就是一个贪心算法,它在贪心算法的基础上
针对刚才我们遇到的问题做了改进,来看看是怎么改进的呢?


传统贪心算法中,当我们找到了局部最低点的时候,我们就不动了,但在退火中,无论这个点是不是满足局部最低点的特性,我们还是会往后走,如果后面这个点比前一个点小,我们就接受这个点为最低值,如果这个点比前一个点大,我们依然以一定的概率接受这个最低点作为最小值,这就是这个算法的精髓所在了。

我们记变化后的值为V_new,变化前的值为V_old;

那么接受V_new为新的最小值的概率p表达式为

if(V_new < V_old)

        p = 1;


if(V_new > V_old)

        p = exp((V_old - V_new)/T);(公式为)


公式中的T就是退火过程中的温度,实际上呢就是一个你自己设定的迭代系统,正常的退火步骤会设定一个初值T,一个温度下降率alpha(0
<alpha<1),每一次迭代,T都会更新值:T = T * alpha.

分析下这个过程,开始时T很大,exp((V_old - V_new)/T)值会趋近与1,大概率向后移动,随着不停的迭代,T会越来越小,导致
exp((V_old -
V_new)/T)越来越趋近于0,值得波动概率越来越小,最后达到最优解。可以看出,退火算法也是不是100%给出最优解,但它能在确定的时间(迭代次数确定)大概率得到最优解。


再来看看退火怎么解决装箱的这个问题,在这个问题上,我们开始先随机打乱设备的顺序,然后将其用贪心的方式放入箱子,然后每次迭代稍微做一点设备的顺序改变,然后根据每个箱子资源1和资源2的使用率来决定是否接受这个方案或者是以概率接受这个方案。

发一个伪代码(实际代码由于有很多其他东西在里面,不太好看懂)
double T = 500; double alpha = 0.99; double T_min = 1; while(T > T_min) {
随机交换设备的顺序(); 贪心放入箱子(); 计算最后一个箱子的资源利用率(); if(新的分配方案资源利用率 > 旧的分配方案资源利用率) {
旧的分配方案资源利用率 = 新的分配方案资源利用率 旧的分配方案 = 新的分配方案 } else { if(exp(旧的分配方案资源利用率 -
新的分配方案资源利用率) / T) > rand()%RAND_MAX) { 旧的分配方案资源利用率 = 新的分配方案资源利用率; 旧的分配方案 =
新的分配方案 } } T = T * alpha; }