启发式搜索之模拟退火

• 一，问题描述
• 二，算法实现
• 三，例题
• • 1，二维费马点

一，问题描述

在实际日常中，人们会经常遇到如下问题：在某个给定的定义域X内，求函数 f ( x ) f(x) f(x) 对应的最优值。此处以最小值问题举例（最大值问题可以等价转化成最小值问题），形式化为： min ⁡ x ∈ C f ( x ) \min _{x \in C }f(x) minx∈C​f(x)

如果X是离散有限取值，那么可以通过穷取法获得问题的最优解；如果X连续，但 f ( x ) f(x) f(x)是凸的，那可以通过梯度下降等方法获得最优解；如果X连续且 f ( x ) f(x) f(x)非凸，虽说根据已有的近似求解法能够找到问题解，可解是否是最优的还有待考量，很多时候若初始值选择的不好，非常容易陷入局部最优值。

所以为了更有效的跳转最优解，模拟退火应运而生

• 不过模拟退火算法到底是如何模拟金属退火的原理？
  1，主要是将热力学的理论套用到统计学上，将搜寻空间内每一点想象成空气内的分子；
  2，分子的能量，就是它本身的动能；
  3，搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。
  4，演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
  5，若概率大于给定的阈值，则跳转到“邻居”；若概率较小，则停留在原位置不动。
  6，随着温度的降低，跳跃越来越不随机，最优解也越来越稳定
  （gif全程需10s，引用自wiki）

二，算法实现

根据热力学的原理，在温度为T时，出现能量差为 d E dE dE 的降温的概率为 p ( d E ) p(dE) p(dE)，表示为 p ( d E ) = e x p ( d E k T ) p(dE)=exp(\frac{dE}{kT}) p(dE)=exp(kTdE​)

量化的抽出exp和自变量

一次模拟退火中温度tt需要覆盖数据范围的3倍，我觉得是因为这符合正态分布 3 δ 3δ 3δ 覆盖的绝大部分(大概 96 96% 96)数据范围.

因为是随机化的算法，整个计时函数，有时间的话就多跑跑，最优解还是很好搞的

三，例题

1，二维费马点

在二维平面上有 n 个点，第 i 个点的坐标为 (xi,yi)，请你找出一个点，使得该点到这 n 个点的距离之和最小，该点可以选择在平面中的任意位置，甚至与这 n 个点的位置重合。

#include<iostream>
#include<cmath>
#include<ctime>
#include<cstring>
#include<algorithm>

#define x first
#define y second
using namespace std;

typedef pair<double ,double >pdd;
double ans;
int n;
pdd q[109];

inline int read ()
{
    int x; bool flag = 1; char ch = getchar();
    while(ch>'9'&&ch<'0')if(ch=='-')flag = 0,ch= getchar();
    while(ch<='9'&&ch>='0')x=(x<<1)+(x<<3)+ch-'0',ch = getchar ();
    if(!flag)return ~(x-1);
    else return x;
}

inline double  randx (double l , double r)
{
    return (double)rand() / RAND_MAX * (r - l ) + l;
}

inline double dis(pdd a, pdd b)
{
    return sqrt((a.x - b.x)*(a.x - b.x ) + (a.y - b.y ) * (a.y - b.y ));
}

double clac (pdd k)
{
    double res=0;
    for(int i= 1;i<=n;i ++)res+=dis(k,q[i]);
    ans =min(ans,res);
    return res;
}
void simulate_anneal()
{
    pdd dx (randx(0,10000),randx (0,10000));
    for(double  t = 1e4; t >1e-4 ; t*=0.99)
    {
        pdd dt  (randx (dx.x -t,dx.x + t) , randx (dx.y-t,dx.y+t));
        double dlata= clac(dt)- clac(dx);
        if (exp(-dlata/t) > randx(0, 1) ) dx =dt ;
    }
}

signed main(void)
{
    ans = 1e8+9;
    n=read();
    for(int i = 1 ; i <=n; i ++ )cin>>q[i].x>>q[i].y;
    for(int i= 1; i<=100;i++)simulate_anneal();
    printf ("%.0lf",ans);
}