优化算法——模拟退火算法

优化算法——模拟退火算法模拟退火算法原理模拟退火算法模拟退火算法过程模拟退火算法流程模拟退火算法的Java实现Java代码最后的结果模拟退火算法原理爬山法是一种贪婪的方法,对于一个优化问题,其大致图像(图像地址)如下图所示:其目标是要找到函数的最大值,若初始化时,初始点的位置在CC处,则会寻找到附近的局部最大值AA点处,由于AA点出是一个局部最大值点,故对于爬山法来讲,该算法无法跳出局部最大值点。若初始

大家好,又见面了,我是你们的朋友全栈君。

模拟退火算法原理

爬山法是一种贪婪的方法,对于一个优化问题,其大致图像(图像地址)如下图所示:
图片来自大白话解析模拟退火算法
其目标是要找到函数的最大值,若初始化时,初始点的位置在 C C C处,则会寻找到附近的局部最大值 A A A点处,由于 A A A点出是一个局部最大值点,故对于爬山法来讲,该算法无法跳出局部最大值点。若初始点选择在 D D D处,根据爬山法,则会找到全部最大值点 B B B。这一点也说明了这样基于贪婪的爬山法是否能够取得全局最优解与初始值的选取由很大的关系。

模拟退火算法(Simulated Annealing, SA)的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减小,粒子的慢慢趋于有序,最终,当固体处于常温时,内能达到最小,此时,粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。

模拟退火算法从某一较高的温度出发,这个温度称为初始温度,伴随着温度参数的不断下降,算法中的解趋于稳定,但是,可能这样的稳定解是一个局部最优解,此时,模拟退火算法中会以一定的概率跳出这样的局部最优解,以寻找目标函数的全局最优解。如上图中所示,若此时寻找到了 A A A点处的解,模拟退火算法会以一定的概率跳出这个解,如跳到了 D D D点重新寻找,这样在一定程度上增加了寻找到全局最优解的可能性。

模拟退火算法

模拟退火算法过程

(1)随机挑选一个单元 k k k,并给它一个随机的位移,求出系统因此而产生的能量变化 Δ E k \Delta E_k ΔEk
(2)若 Δ E k ⩽ 0 \Delta E_k\leqslant 0 ΔEk0,该位移可采纳,而变化后的系统状态可作为下次变化的起点;
Δ E k > 0 \Delta E_k> 0 ΔEk>0,位移后的状态可采纳的概率为
P k = 1 1 + e − Δ E k / T P_k=\frac{1}{1+e^{-{\Delta E_k}/{T}}} Pk=1+eΔEk/T1
式中 T T T为温度,然后从 ( 0 , 1 ) \left ( 0,1 \right ) (0,1)区间均匀分布的随机数中挑选一个数 R R R,若 R < P k R< P_k R<Pk,则将变化后的状态作为下次的起点;否则,将变化前的状态作为下次的起点。
(3)转第(1)步继续执行,知道达到平衡状态为止。

模拟退火算法流程

这里写图片描述

模拟退火算法的Java实现

求解函数最小值问题:
F ( x ) = 6 x 7 + 8 x 6 + 7 x 3 + 5 x 2 − x y F\left ( x \right )=6x^7+8x^6+7x^3+5x^2-xy F(x)=6x7+8x6+7x3+5x2xy
其中, 0 ≤ x ≤ 100 0\leq x\leq 100 0x100,输入任意 y y y值,求 F ( x ) F\left ( x \right ) F(x)的最小值。

##Java代码

package sa;

/** * 实现模拟退火算法 * @author zzy *Email:zhaozhiyong1989@126.com */
public class SATest { 
   
	public static final int T = 100;// 初始化温度
	public static final double Tmin = 1e-8;// 温度的下界
	public static final int k = 100;// 迭代的次数
	public static final double delta = 0.98;// 温度的下降率

	public static double getX() { 
   
		return Math.random() * 100;
	}

	/** * 求得函数的值 * * @param x目标函数中的一个参数 * @param y目标函数中的另一个参数 * @return函数值 */
	public static double getFuncResult(double x, double y) { 
   
		double result = 6 * Math.pow(x, 7) + 8 * Math.pow(x, 6) + 7
				* Math.pow(x, 3) + 5 * Math.pow(x, 2) - x * y;

		return result;
	}
	
	/** * 模拟退火算法的过程 * @param y目标函数中的一个参数 * @return最优解 */
	public static double getSA(double y) { 
   
		double result = Double.MAX_VALUE;// 初始化最终的结果
		double t = T;
		double x[] = new double[k];
		// 初始化初始解
		for (int i = 0; i < k; i++) { 
   
			x[i] = getX();
		}
		// 迭代的过程
		while (t > Tmin) { 
   
			for (int i = 0; i < k; i++) { 
   
				// 计算此时的函数结果
				double funTmp = getFuncResult(x[i], y);
				// 在邻域内产生新的解
				double x_new = x[i] + (Math.random() * 2 - 1) * t;
				// 判断新的x不能超出界
				if (x_new >= 0 && x_new <= 100) { 
   
					double funTmp_new = getFuncResult(x_new, y);
					if (funTmp_new - funTmp < 0) { 
   
						// 替换
						x[i] = x_new;
					} else { 
   
						// 以概率替换
						double p = 1 / (1 + Math
								.exp(-(funTmp_new - funTmp) / T));
						if (Math.random() < p) { 
   
							x[i] = x_new;
						}
					}
				}
			}
			t = t * delta;
		}
		for (int i = 0; i < k; i++) { 
   
			result = Math.min(result, getFuncResult(x[i], y));
		}
		return result;
	}

	public static void main(String args[]) { 
   
		// 设置y的值
		int y = 0;
		System.out.println("最优解为:" + getSA(y));
	}

}

最后的结果

最优解为:1.733360963664572E-16


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/161428.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号