【算法】模拟退火

这篇具有很好参考价值的文章主要介绍了【算法】模拟退火。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.模拟退火介绍

​ 模拟退火是模拟物理上退火方法,通过N次迭代(退火),逼近函数的上的一个最值(最大或者最小值)。比如在下面函数去逼近最大值C点
模拟退火,数据结构笔记,c++,算法

1.1模拟退火的可行性

​ 模拟退火算法得益于材料统计力学的研究成果。

​ 鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减小,粒子的慢慢趋于有序,最终,当固体处于常温时,内能达到最小,此时,粒子最为稳定

​ 如果用粒子的能量定义材料的状态,退火算法用一个简单的数学模型描述了退火的过程。假设材料在状态i下的能量为E(i),那么材料在温度T时从状态i进入状态j就应该遵从以下规律:

(1)如果E(j)<=E(i),那么级接收该状态。

(2)如果E(j)>E(i),那么就以一定的概率进入该状态:exp{(E(i)-E(j))/KT}

K为物理学中的玻尔兹曼常数,T为材料的温度

1.2退火模型
  • 退火算法是一种循环算法
  • 需要先设定一个初始的问题T【需要一个高温,模拟粒子从高温向低温退火】
  • 每次循环进行一次退火
  • 然后降低的温度,我们通过让和一个“降温系数”(一个接近1的小数,比如0.999)相乘,达到慢慢降低温度的效果,直到接近于0(我们用来代表一个接近0的数(比如0.00001)。

代码架构

double T=2000;	    //表示初始的温度为0.99
double dt=0.999;	//表示降温系数
double eps=1e-14;	//相对于1的负14次方,就是最后退出循环的温度

while(T<eps)
{
    //------------------
    //进行一次退火操作
    //------------------
    T*=dt;		 //降低温度
}

2.详解退火

​ 我们要求的目标无法是两个:自变量x和对应的目标函数最值f(x)

2.1退火过程
  • 先随机找一点x0,这也是初始粒子。【注意要随机】

模拟退火,数据结构笔记,c++,算法

  • 找到对应的目标函数值

模拟退火,数据结构笔记,c++,算法

  • 进行退火操作

​ 刚才我们说了x0相当于是一个粒子,所以我们会进行一个无序运动,也就是向左或者向右随机移动:移动的幅度当前的温度T有关。

​ 温度T越大,移动的幅度越大。温度T越小,移动的幅度就越小。这是在模拟粒子无序运动的状态。

  • 接收更好的状态

模拟退火,数据结构笔记,c++,算法

​ 假设我们移动到了x1处,那么这个点对应的f(x1)很明显答案是优于(大于)当前的f(x0)。

模拟退火,数据结构笔记,c++,算法

  • 因此我们将答案进行更新。也就是将初始值进行替换:x0=x1,f(x0)=f(x1)。这是一种贪心的思想。

  • 以一定概率接受(Accept)更差的状态

为什么需要按照一定的概率接受更差的状态。因为可能在一个较差的状态旁边会出现一个更加高的山峰

模拟退火,数据结构笔记,c++,算法

如果我们鼠目寸光,只盯着右半区,很容易随着温度的下降、左右跳转幅度的减小迷失自己,最后困死在小山丘中。

而我们如果找到了左边山峰的低点,以一定的概率接受了它(概率大小和温度以及当前的值的关键程度有关),会在跳转幅度减少之前,尽可能找到最优点

那么我们以多少的概率去接受它呢?我们用一个公式表示:exp{ Δf / KT }

注意

- 如果随机后的函数值如果结果更好,我们一定选择它(即x0=x1,f(x0)=f(x1));
- 随机后的函数值如果结果更差,我们以exp{ Δf /  KT }的概率接受它
- e是自然对数,约等于2.71。我们可以把右上角这一坨 Δf /  KT值看成一个整体x:

而exp{x}的函数图像为:

模拟退火,数据结构笔记,c++,算法

而如果需要用exp{x}表示一个概率,那么x【Δf / KT】的取值范围只能为负数。

负数部分的值域是在(0,1)开区间内,x越小,越接近0,越大越靠近1。

2.2各变量说明

K其实是个物理学玻尔兹曼常数,我们在代码中不会用到

T就是当前的温度。所以实际上这个分母就是T,K当做1使用。

Δf:

  • 我们想要函数来代表一个概率值,一定要让它的值域属于(0,1),所以Δf / KT必须是个负数。但是在我们的模拟中KT一定是正数,那么Δf必须是个负数
  • Δf 就是当前解的函数值与目标解函数值之差
  • 现在我们求一个函数的最大值,如果f(x0)<f(x1),那就说明结果变好了,我们肯定选择它
  • 如果f(x0)>f(x1),那就说明结果变差了,我们需要概率选择它,因此Δf=-(f(x0)-f(x1));

模拟退火,数据结构笔记,c++,算法

2.2.1关于接收概率

关于接受概率e{x}和KT以及Δf的关系:

当T越大时(温度越高),由于是Δf一个负数,所以Δf / KT算出来的值会越大。比如-1 / 1000 等于 -0.001,很明显-0.001 > -1,由于e{x}是个单调递增函数,所以温度越高时,接受的概率就越大。

Δf越小【负的越多】,说明答案越糟糕,那么接受的概率就越小。

①对rand()函数

  1. rand()函数可以默认拿到[0,32767]内的随机整数
  2. RAND_MAX = 32767,可以看作常量。本质是宏定义: #define RAND_MAX 32767
  3. rand() * 2 的范围是[0,32767 * 2]
  4. rand() * 2 - RAND_MAX 的范围是[-32767, 32767]

②对exp()函数

  1. exp(x)代表e的x次方

③关于exp((df - f) / T) * RAND_MAX > rand()

  1. 目的是要概率接受,但是exp{x}是个准确值,所以从理论上我们可以生成一个(0,1)的随机数,如果exp{x}比(0,1)这个随机数要大,那么我们就接受。
  2. 但是由于rand()只能产生[0,32767]内的随机整数,化成小数太过麻烦。所以我们可以把左边乘以RAND_MAX(也就是把概率同时扩大32767倍),效果就等同exp{x}于比(0,1)了。
double T = 20000; //代表开始的温度
double dT = 0.999; //代表系数delta T
double eps = 1e-14; //相当于0.0000000000000001

//用自变量计算函数值,这里可能存在多个自变量对应一个函数值的情况,比如f(x,y)
double func(int x, ... ) {
    //这里是对函数值进行计算
    double ans = .......
    return ans;
}
//原始值
double x = rand(); //x0取随机值
double f = func(x,...); //通过自变量算出f(x0)的值
while(T > eps) {
    //--------------
    //这里是每一次退火的操作
    
    //x1可以左右随机移动,幅度和温度T正相关,所以*T
    //注意这里移动可以左右移动,但是也可以单向移动
    //关于rand()详细见开头注的①
    double dx = x+(2*rand() - RAND_MAX) * T; 
    
    //让x落在定义域内,如果没在里面,就重新随机。
    // ================
    while(x > ? || x < ? ...) { //保证x在作用域中
        double dx = (2*rand() - RAND_MAX) * T; 
    }
    // ================
    
    //求出f(x1)的值
    double df = func(dx);
    //这里需要具体问题具体分析,我们要接受更加优秀的情况。可能是df < f(比如求最小值)
    if(f < df) {
        f = df; x = dx;  [...,y = dy;] // 接受,替换值,如果多个自变量,那么都替换
    }
    //否则概率接受,注意这里df-f也要具体问题具体分析。
    //详细见开头注的②③
    else if(exp((df - f) / T) * RAND_MAX > rand()) {
        f = df; x = dx;  [...y = dy;] // 接受,替换值,如果多个自变量,那么都替换
    }
 //--------------
    T = T * dT; //温度每次下降一点点, T * 0.999
}
//最后输出靠近最优的自变量x值,和函数值f(x)
cout << x << " " << f << endl;

3.退火模拟求根号n的值

我们试图通过退火找出一个值x0,使得x0的平方的值更加接近于n

所以我们的目标函数就可以知道:f(x)=|x0^2-n|;

//n代表我们最后函数要逼近的值
double n;
//x表示我们随机产生的那个数的平方和n的靠近程度
double func(double x) {
    return fabs(x * x - n);
}

退火函数SA()

double T = 20000; //初始温度,初始温度主要是看题目开始需要跳转的幅度。
double dT = 0.995; //变化率,这里需要速度稍微慢一点,写0.999 或者 0.997都可以,但是越靠近1速度就越慢 
const double eps = 1e-14; //10的-14次方已经非常小了,写这个大概率没问题
void SA() {
    //首先随机生成一个点x0,这里我用0代替。
    double x = 0;
    //算出x平方和n的差距f(x0)
    double f = func(x);
    while(T > eps) {
        //这里x0既可以变小,也可以变大,所以我们正负都要进行一个跳转,算出变换后的点dx
        double dx = x + (2 * rand() - RAND_MAX) * T;
        //但是请注意,dx很明显要保证 >= 0才行,因为算术平方根的定义域是>=0,因此小于0就重新随机
        while(dx < 0) 
        {
            dx = x + (2 * rand() - RAND_MAX) * T;
        }
        //算出变换后的点dx的平方和n的差距,f(dx)
        double df = func(dx);
        //这里就是关键的地方了,很明显我们需要算出来的function值越小,自变量x更加接近那个根号值。
        //所以如果新来的值df 比 f更小,我们百分百接受
        if(df < f) {
            //注意更新所有变量
            f = df; x = dx;
        }
        //否则我们概率接受,这里的需要写 f - df了,因为这样才是负值。负值说明我们并不是贪心接受的,他是不太好的值。
        else if(exp((f - df)/T) * RAND_MAX > rand()) {
            //注意更新所有变量
            f = df; x = dx;
        }
        //温度下降一下
        T *= dT;
    }
    printf("%.8lf",x);
}

4.洛谷POJ-2420

题目描述

给出平面上N(N<=100)个点,你需要找到一个这样的点,使得这个点到N个点的距离之和尽可能小。输出这个最小的距离和(四舍五入到最近的整数)。

Input输入

第一行N,接下来N行每行两个整数,表示N个点

Output输出

一行一个正整数,最小的距离和。

Sample Input样例输入
4
0 0
0 10000
10000 10000
10000 0
Sample Output样例输出
28284

模拟退火,数据结构笔记,c++,算法

将所有的点存放入一个结构体point数组中

const int N = 1e5 + 5;
struct Point {
    double x, y;
}e[N];

//main函数中输入N个点
int main() 
{
    cin >> n;
    for(int i = 1; i <= n; i++) 
        scanf("%lf%lf", &e[i].x, &e[i].y);
}

关键的函数

//输入我们随机生成的点A 坐标 x0, y0
double func(double x, double y) {
    double ans = 0;
    for(int i = 1; i <= n; i++) {
        double xx = e[i].x, yy = e[i].y; // xx 就是 xi ,yy 就是 yi
        double p = fabs(e[i].x - x); // x0 - xi
        double q = fabs(e[i].y - y); // y0 - yi
        ans += (sqrt((p * p + q * q))); // ans加上到随机点A到点i的距离
    }
    return ans;
}

然后套用上面的公式,我们写出SA()模拟退火文章来源地址https://www.toymoban.com/news/detail-660674.html

double T = 2000; //初始温度
double dT = 0.993; //变化率,这里需要速度稍微慢一点,写0.995 或者 0.997都可以,但是越靠近1速度就越慢 
const double eps = 1e-14; //10的-14次方已经非常小了,写这个大概率没问题
void SA() {
    //随机生成点A(x0,y0),这里我直接赋值为了0。当然也可以写rand(),差别都不大。
    double x = 0, y = 0;
    //生成的点A(x0,y0)对应的函数值f(x0, y0)
    double f = func(x, y);
    while(T > eps) {
        //这里对x和y同时进行一个偏移,很明显在一个平面中,上下左右都可以移动,所以我们选择了rand() * 2 - RAND_MAX
        //对于每个点,我们的偏移幅度都要 * T,温度越高,偏移量越大
        double dx = x + (rand() * 2 - RAND_MAX) * T;
        double dy = y + (rand() * 2 - RAND_MAX) * T;
        //算出偏移后的点B(dx, dy)对应的函数值f(dx, dy)
        double df = func(dx, dy);
        //这里就是关键的地方了,很明显我们需要算出来的function值越小,就更加优秀
        //所以如果新来的值df 比 f更小,我们百分百接受
        if(df < f) {
            //注意更新所有变量
            f = df; y = dy; x = dx;
        }
        //否则我们概率接受,这里的需要写 f - df了,因为这样才是负值
        else if(exp((f - df) / T) * RAND_MAX > rand()) {
            //注意更新所有变量
            f = df; y = dy; x = dx;
        }
        //降低温度
        T = T * dT;
    }
    //输出答案
    printf("%.f\n", f);
}

到了这里,关于【算法】模拟退火的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(62)
  • 数据结构之树与二叉树——算法与数据结构入门笔记(五)

    本文是算法与数据结构的学习笔记第五篇,将持续更新,欢迎小伙伴们阅读学习。有不懂的或错误的地方,欢迎交流 前面章节介绍的都是线性存储的数据结构,包括数组、链表、栈、队列。本节带大家学习一种非线性存储的数据结构,即树(tree)。 不管是在面试时,还是日

    2024年02月08日
    浏览(43)
  • 数据结构和算法笔记1:滑动窗口

    在一些数组或者字符串我们需要遍历子序列,可能要用到两个指针(我们称为起始指针和终止指 针)进行双层遍历,内层终止指针满足条件时跳出内层循环,然后起始指针前进,回溯终止指针到起始指针,以此继续进行遍历,然而这样效率比较低,我们可能进行了很多不必要

    2024年02月07日
    浏览(30)
  • 【王道考研】王道数据结构与算法详细笔记(全)

    目录 第一章 数据结构绪论  1.1 数据结构的基本概念 1.2 数据结构的三要素 1.2.1. 数据的逻辑结构 1.2.2. 数据的存储结构(物理结构) 1.2.3. 数据的运算 1.2.4. 数据类型和抽线数据类型 1.3 算法的基本概念 1.4 算法的时间复杂度 1.5 算法的空间复杂度 第二章 线性表 2.1 线性表的定

    2024年02月08日
    浏览(50)
  • 【学习笔记】数据结构算法文档(类C语言)

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(42)
  • 读书笔记-《数据结构与算法》-摘要4[插入排序]

    核心:通过构建有序序列,对于未排序序列,在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历),找到相应位置并插入。实现上通常使用in-place排序(需用到O(1)的额外空间) 从第一个元素开始,该元素可认为已排序 取下一个元素,对已排序数组从后往前扫描 若从

    2024年02月04日
    浏览(35)
  • 读书笔记-《数据结构与算法》-摘要8[桶排序]

    桶排序和归并排序有那么点点类似,也使用了归并的思想。大致步骤如下: 设置一个定量的数组当作空桶。 Divide - 从待排序数组中取出元素,将元素按照一定的规则塞进对应的桶子去。 对每个非空桶进行排序,通常可在塞元素入桶时进行插入排序。 Conquer - 从非空桶把元素

    2024年01月18日
    浏览(42)
  • 【软考程序员学习笔记】——数据结构与算法基础

    目录  🍊一、数据结构概念和分类 🍊二、数组特点存储方式 🍊三、矩阵 特殊矩阵 非特殊矩阵 🍊四、栈和队列 🍊 五、二叉树的性质 🍊六、二叉树的遍历 (1)前序遍历(先根遍历,先序遍历) (2)中遍历(中根遍历) (3)后序遍历(后根遍历,后序遍历) 🍊七、二叉排序树 🍊八、

    2024年02月12日
    浏览(60)
  • 【零基础】学python数据结构与算法笔记14-动态规划

    学习python数据结构与算法,学习常用的算法, b站学习链接 动态规划在基因测序、基因比对、hmm 有应用场景。 从斐波那契数列看动态规划 练习: 使用递归和非递归的方法来求解斐波那契数列。 这种非递归求斐波那契数,可以看成是一个动态规划思想,每次都会把重复子问

    2023年04月09日
    浏览(42)
  • 读程序员的制胜技笔记02_算法与数据结构

    3.1.1.1. 根据你的需要,可以有更智能的算法 3.1.3.1. 算法本身并不意味着它很聪明 3.2.1.1. public static bool Contains(int[] array, int lookFor) { for (int n = 0; n < array.Length; n++) {        if (array[n] == lookFor) {            return true;        }    }    return false; } 3.3.1.1. public sta

    2024年02月06日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包