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

优化算法——模拟退火算法模拟退火算法原理模拟退火算法模拟退火算法过程模拟退火算法流程模拟退火算法的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)
blank

相关推荐

  • VAR模型_trophymanager

    VAR模型_trophymanager本作品采用知识共享署名-非商业性使用-相同方式共享4.0国际许可协议进行许可。本作品(李兆龙博文,由李兆龙创作),由李兆龙确认,转载请注明版权。文章目录引言PercolatorTiKV中的应用ColumnFamily读放大Latches缺陷总结引言TiKV是GoogleSpanner的一个开源实现,其作为HTAP(HybridTransactionalandAnalyticalProcessing)数据库TiDB的行存储引擎,以支持对OLTP(On-LineTrans

  • 十天学会PHP_十天学会php教程

    十天学会PHP_十天学会php教程以前写了十天学会asp,十天学会asp.net什么的,现在想想再写个php吧,也算比较全了。PHP的调试方法我这里就不说了,外面很多文章都有介绍,也有很多不同的组合。我这里暂时是以Apachew

  • RelativeLayout.LayoutParams.addRule()方法

    RelativeLayout.LayoutParams.addRule()方法1、应用场景

  • swagger @ApiParam 参数设置为可为空却还是要求输入参数

    swagger @ApiParam 参数设置为可为空却还是要求输入参数

  • Pycharm调试_pycharm 远程调试

    Pycharm调试_pycharm 远程调试动机一些bug由于本地环境和线上环境的不一致可能导致本地无法复现本地依赖和线上依赖版本不一致也可以导致一些问题有时一些bug跟数据相关,本地数据无法和线上数据一致有些三方平台会验证服务器的合法性或者异步回调结果,如微信支付,这时候本地无法测试如上所诉,要是有一个很方便调试远程服务器的方法,岂不美哉。通过PyCharm我们可以很方便地实现远程调试,下面详细介绍下PyCharm这个牛叉的功能。添加远程…

    2022年10月29日
  • POJ 2478 Farey Sequence

    POJ 2478 Farey Sequence

    2021年11月29日

发表回复

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

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