爬山法
在介绍模拟退火算法之前，先介绍一下爬山法。爬山法是一种贪心算法。其目标是要找到函数的最大值，若初始化时，初始点的位置在C处，则会寻找到附近的局部最大值A点处，由于A点出是一个局部最大值点，故对于爬山法来讲，该算法无法跳出局部最大值点。若初始点选择在D处，根据爬山法，则会找到全部最大值点B。这一点也说明了这样基于贪婪的爬山法是否能够取得全局最优解与初始值的选取由很大的关系。
模拟退火算法(Simulated Annealing Algorithm, SAA)的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。
模拟退火算法从某一较高的温度出发，这个温度称为初始温度，伴随着温度参数的不断下降，算法中的解趋于稳定，但是，可能这样的稳定解是一个局部最优解，此时，模拟退火算法中会以一定的概率跳出这样的局部最优解，以寻找目标函数的全局最优解。如上图中所示，若此时寻找到了A点处的解，模拟退火算法会以一定的概率跳出这个解，如跳到了D点重新寻找，这样在一定程度上增加了寻找到全局最优解的可能性。
模拟退火算法过程
(1)随机挑选一个单元k，并给它一个随机的位移，求出系统因此而产生的能量变化ΔEk。
(2)若ΔEk⩽0，该位移可采纳，而变化后的系统状态可作为下次变化的起点；
若ΔEk>0，位移后的状态可采纳的概率为
式中T为温度，然后从(0,1)区间均匀分布的随机数中挑选一个数R，若R<Pk，则将变化后的状态作为下次的起点；否则，将变化前的状态作为下次的起点。
(3)转第(1)步继续执行，知道达到平衡状态为止。
(3)转第(1)步继续执行，知道达到平衡状态为止。
模拟退火算法流程
模拟退火算法MATLAB实现
计算-x^2-4x+3的最大值：
主函数：
|
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 |
clc; clear; k = 0.1; r = 0.9; T = 2000; T_min = 20; glb = -4.0; lub = 4.0; gen = 100000; best = func(rnd(glb,lub)); best_min = 9999; while(T>T_min) for i=1:gen current = func(rnd(glb,lub)); dE = current - best; if(dE>=0) best = current; best_min = current; else if(exp(dE/(T*k))>rnd(0,1)) best = current; end end end T = r * T; end |
随机数生成函数：
|
1 2 3 |
function y = rnd(glb, lub) y = glb + (lub-glb)*rand(); end |
目标函数：
|
1 2 3 |
function y = func(x) y = -x*x-4*x+3; end |
模拟退火算法C语言实现
计算-x^2-4x+3的最大值：
|
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 |
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> #define num 1000000 //迭代次数 double k=0.1; double r=0.9; //用于控制降温的快慢 double T=2000; //系统的温度，系统初始应该要处于一个高温的状态 double T_min =2;//温度的下限，若温度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-4*x+3; } int main() { double best=func(rnd(-4,4)); double dE,current; double gbest=0; int i; while( T > T_min ) { for(i=0;i<num;i++) { //用当前时间点初始化随机种子，防止每次运行的结果都相同 time_t tm; time(&tm); unsigned int nSeed=(unsigned int)tm; srand(nSeed); current=func(rnd(-4,4)); dE = current - best ; if ( dE >= 0 ) //表达移动后得到更优解，则总是接受移动 best = current ; gbest = current; } T = r * T ;//降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快 } printf("最大值是 %f\n",best); printf("gbest为：%f\n",gbest); return 0; } |
结果
best和best_min是求出的最大值。
