模拟退火算法求解函数优化问题举例
前言:在这里,我们尝试使用模拟退火算法对函数优化问题进行求解。由于使用的是基础算法,并且简化了相关过程,所以求解效果不显著。在未来,应该讨论完善的、改进的模拟退火算法的应用。
算法内容参考书籍:模拟退火算法及其应用
案例参考博客:模拟退火算法与其python实现(一)
详细内容请移步上述博客,内容十分有用。
1.固体退火过程
固体退火是先将固体加热至熔化,再通过冷却凝固成规整晶体的热力学过程。
2.固体退火现象
在加热固体时,固体粒子的热运动不断增强,随着温度的升高,粒子预期平衡位置的偏离越来越大。当温度升至溶解温度后,固体的规则性被彻底破坏,从有序转变为无序状态,即固体转变为液体。相反,当温度降低时,则从无序转变为有序状态。
3.模拟退火算法
模拟退火算法来源于固体退火过程,使对象粒子从无序到有序的状态的转变。在高温条件下,粒子的能量较高,处于无序状态;在低温条件下,粒子能量较低,相对处于有序状态。当温度慢慢降低时,粒子的能量减小,粒子由无序趋于有序。最终,当粒子处于特定温度时,能量达到最小,此时,粒子处于稳定状态。
由此,假设函数优化问题当中,通过模拟退火的过程使函数变量趋向于稳定状态时,变量逐渐趋向于某个取值范围,在这个范围当中函数取得相对较优的值。
4.适应值函数
与其他算法相同,适应值函数为目标函数,如下:
double Fitness(double x) {
double fit = 0;
fit = pow(x, 3) - 60 * pow(x, 2) - 4 * x + 6;
return fit;
}
5.状态更新
5.1 步长搜索
相对于当前解,算法需要对其领域进行搜索,以达到该区域中的最优状态。一般,一当前解为中心,随机产生均匀分布的步长,从而更新当前解。在这里,使用简单的随机数进行更新步长。
double delta_x = (rand() % 10)/10.0;
if (delta_x > 0.5) {
delta_x -= 1;
}
x_tem = x_best + delta_x;
5.2 界限判断
对于更新的变量值,需要检查变量是否超出界限,若超出界限,对其重新分配一个随机变量值。
if ((x_tem < x_low) || (x_tem > x_high)) {
x_tem= ((rand() % (10000 + 1))) / 100.0;
}
5.3函数值更新
Metropolis准则
模拟退火算法使用Metropolis准则产生组合优化问题解的序列,并使用对应的转移概率P确定是否接受当前解到新解的转移。
if (y_tem < y_best) {
y_best = y_tem;
x_best = x_tem;
}
else {
double principle = exp(-1*(y_tem - y_best) / iter_temperature);
srand((unsigned)time(NULL));
double random = (rand() % (10 + 1)) / 10.0;
if(random < principle) {
y_best = y_tem;
x_best = x_tem;
}
6.冷却进度表
冷却进度表是指从某一高温状态T向低温状态冷却时的降温函数,在这里,表示如下:
7.模拟退火算法
void SA() {
Init();//初始化函数值
x_best=x_tem;
y_best= Fitness(x_tem);
iter_temperature = init_temperature;
int count = 0;
while (iter_temperature > min_temperature) {
int iter_time = 0;//初始搜索次数
srand((unsigned)time(NULL));
while (iter_time<circul_time) {
//邻域函数选取步长
double delta_x = (rand() % 10)/10.0;
if (delta_x > 0.5) {
delta_x -= 1;
}
//cout << delta_x << endl;
x_tem = x_best + delta_x;
Update();
iter_time++;
//cout << iter_time << endl;
}
cout << iter_temperature << "温度下函数值为:" << y_best << endl;
count++;
iter_temperature = init_temperature / (1 + count);
}
}
模拟退火算法简要内容如上,有待进一步学习。
上一篇: 头顶标数法
下一篇: 迷宫问题(广搜 POJ 3984)