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

模拟退火算法原理

爬山法是一种贪婪的方法,对于一个优化问题,其大致图像(图像地址)如下图所示:

其目标是要找到函数的最大值,若初始化时,初始点的位置在CC处,则会寻找到附近的局部最大值AA点处,由于AA点出是一个局部最大值点,故对于爬山法来讲,该算法无法跳出局部最大值点。若初始点选择在DD处,根据爬山法,则会找到全部最大值点BB。这一点也说明了这样基于贪婪的爬山法是否能够取得全局最优解与初始值的选取由很大的关系。

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

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

模拟退火算法

模拟退火算法过程

模拟退火算法流程

模拟退火算法的Java实现

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


本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏语言、知识与人工智能

游戏文本关键词提取工作的尝试和探索

如何将合适的游戏文本打上正确的关键词标签,并将内容推送给恰当的用户成为一个重要的课题。

1.7K50
来自专栏深度学习自然语言处理

pyTorch基础入门练习

import导入 import torch#基本的torch函数 import torch.autograd as autograd#自动求导 import t...

424100
来自专栏大数据文摘

揭秘自编码器,一种捕捉数据最重要特征的神经网络(视频+代码)

18870
来自专栏AI研习社

神经机器翻译的编码 - 解码架构有了新进展, 具体要怎么配置?

用于循环神经网络的编码 - 解码架构,在标准机器翻译基准上取得了最新的成果,并被用于工业翻译服务的核心。 该模型很简单,但是考虑到训练所需的大量数据,以及调整模...

28340
来自专栏深度学习自然语言处理

【干货】基于注意力机制的seq2seq网络

seq2seq seq2seq的用途有很多,比如机器翻译,写诗,作曲,看图写文字等等用途很广泛!该模型最早在2014年被Cho和Sutskever先后提出,前者...

50660
来自专栏机器学习算法与Python学习

n-gram文法中数据稀疏问题解决方案之一:Good-Turing平滑

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 统计语言模型中,N元语法模型不可避免...

46340
来自专栏AI研习社

从聚合-转移框架浅谈卷积神经网络的架构设计

本次Paper Reading我们并没有关注某些特定的paper,而是用一个视角对现有的代表性的卷积神经网络设计进行总结。

16220
来自专栏机器之心

学界 | 无监督神经机器翻译:仅需使用单语语料库

39580
来自专栏机器学习算法工程师

Java 机器学习库Smile实战(二)AdaBoost

1. AdaBoost算法简介 Boost 算法系列的起源来自于PAC Learnability(PAC 可学习性)。这套理论主要研究的是什么时候一个问题是可...

37860
来自专栏利炳根的专栏

学习笔记 TF059 :自然语言处理、智能聊天机器人

自然语言处理,语音处理、文本处理。语音识别(speech recognition),让计算机能够“听懂”人类语音,语音的文字信息“提取”。

90420

扫码关注云+社区

领取腾讯云代金券