摸拟退火算法 Simualtea Annealing AIirthm（SAA）

1：固体退火过程

固体退火是将固体加热到熔化，在冷却使之凝固成规整晶体的热力学过程。

文献原文描述：

固体加热时, 固体粒子的热运动不断增强,随着温度的升高 , 粒子与其平衡位置的偏离越来越大 , 固体的规则性逐渐被破 坏 . 当粒子排列从较有序的结晶态变为无序的液态时便完成熔解过程 . 熔解过程的目的是消出系统中原先可能存在的非均匀状态 , 该过程中系统的能量随着温度的升高而增大 .

冷却时, 液体粒子的热运动渐渐减弱 , 随着温度的徐徐降低, 粒子运动渐趋规则 (有 序 ) , 当温度降至结晶温度后 ,粒子运动变为围绕晶体格点的微小振动 . 当液体凝固成固体的晶态时完成退火过程. 退火过程中系统的能量随着温度的降低趋于最小值 .

2：准则

初始状态i，其能量是Ei；新状态为j，其能量是Ej。

当Ej

当Eim，则接受。否 则不接受。（k是波尔兹曼常数，T是当前温度。）

3：算法描述 1：退火与最优解联系

状态i对应组合解i，能量Ei对应目标函数f（x），能量最小值对应最优解。

2：算法步骤

重复一下步骤，知道停止准则。

随机产生新解；

计算f（x）；

比较与上一次的解的大小，根据准则进行取舍。

取一张他人博客的图片：

通常SAA可用于多种组合优化问题及相关问题 , 它不会因为问题实例的不同而使实验性能脱变, 从而具有较好的稳健性 .

C语言代码实现：

#include 
#include 
#include 
#include
#define num 30000 //迭代次数double k=0.1;
double r=0.9; //用于控制降温的快慢
double T=2000; //系统的温度，系统初始应该要处于一个高温的状态
double T_min =10;//温度的下限，若温度T达到T_min，则停止搜索//返回指定范围内的随机浮点数
double rnd(double dbLow,double dbUpper)
{double dbTemp=rand()/((double)RAND_MAX+1.0);return dbLow+dbTemp*(dbUpper-dbLow);
}double func(double x)//目标函数
{return x*(x-1)+1;
}
int main()
{double best=func(rnd(0.0,10));double dE,current;int i;while( T > T_min ){for(i=0;i rnd( 0.0 , 1.0 ) )best = current ;}}T = r * T ;//降温退火 ，0