欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

模拟退火算法求解函数优化问题举例

程序员文章站 2022-05-20 22:52:57
...

前言:在这里,我们尝试使用模拟退火算法对函数优化问题进行求解。由于使用的是基础算法,并且简化了相关过程,所以求解效果不显著。在未来,应该讨论完善的、改进的模拟退火算法的应用。

算法内容参考书籍:模拟退火算法及其应用
案例参考博客:模拟退火算法与其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);
	}
}

模拟退火算法简要内容如上,有待进一步学习。

相关标签: 智能算法学习