一个网站的制作步骤,直播视频,酒店手机网站首页设计,网站建设价格标准报价以下均假设最优解是在最低点。
爬山法
爬山算法是一种局部择优的方法#xff0c;采用启发式方法#xff0c;是对深度优先搜索的一种改进#xff0c;它利用反馈信息帮助生成解的决策。
直白地讲#xff0c;就是当目前无法直接到达最优解#xff0c;但是可以判断两个解哪…以下均假设最优解是在最低点。
爬山法
爬山算法是一种局部择优的方法采用启发式方法是对深度优先搜索的一种改进它利用反馈信息帮助生成解的决策。
直白地讲就是当目前无法直接到达最优解但是可以判断两个解哪个更优的时候根据一些反馈信息生成一个新的可能解。
因此爬山算法每次在当前找到的最优方案 xxx 附近寻找一个新方案。如果这个新的解 x′xx′ 更优那么转移到 x′xx′否则不变。
这种算法对于单峰函数显然可行。 Q既然都知道是单峰函数了为什么不三分呢? A你说的对直接三分好了。 B我要是知道是单峰函数我还在这里骗分 爬山算法会引入『温度参数』 TTT。
类比的说爬山就是一个醉汉喝得狂醉然后再山上裸奔蹦迪。
他知道该回家了不然就要跪搓衣板然后每次会往他认为最低的地方狂奔过去中途不刹车。
显然他可能一次恰好奔到山脚然后下山回家也有可能奔过了到另一座山顶上去了。
不过没关系醉汉奔过头了还会存在奔回来的可能。
但显然这个过程很没用。仿佛醉汉回家全靠天公作美。
所以在暴走过程中他会经受山顶寒风的摧残酒精作用渐渐消减他变得越发清晰。
他就变得谨慎一点每次少奔一点以达到山脚最低点位置。
这就要引入『降温参数』来起到缓缓冷静的作用。
关于『降温参数』一般是 [0.985,0.999][0.985,0.999][0.985,0.999] 中选这样才能做到慢慢消减。
显然如果存在多个”转折“时爬山就很容易进入局部最优解而非全局最优解。
随着头脑逐渐清醒醉汉蹦出局部最优解的期望就会更小很有可能一直跳不过去某个坡。 模拟退火
为什么会有上面情况的产生呢
其实是因为爬山法的写法只有在新解优于当前解的时候我们才会接受新解并移动到相应位置。
根据这种情况我们知道其实偶尔新解不好我们也要去接受这样才会存在跳出这个坡的可能。
这就是模拟退火了。
模拟退火相较于爬山就只是多了一个随机接受非最优解的部分大大增加了找到全局最优解得可能。 以下是追根溯源由物理和化学知识迁移到信息学上应用 我们知道在分子和原子的世界中能量越大意味着分子和原子越不稳定当能量越低时原子越稳定。 『退火』是物理学术语指对物体加温在冷却的过程。 模拟退火算法来源于晶体冷却的过程如果固体不处于最低能量状态给固体加热再冷却随着温度缓慢下降固体中的原子按照一定形状排列形成高密度、低能量的有规则晶体即全局最优解。 而如果温度下降过快可能导致原子缺少足够的时间排列成晶体的结构结果产生了具有较高能量的非晶体即局部最优解。 因此就可以根据退火的过程给其再增加一点能量然后再冷却如果增加能量跳出了局部最优解那么本次退火就是成功的。 模拟退火由两个部分组成Metropolis\text{Metropolis}Metropolis 算法和退火过程。
Metropolis\text{Metropolis}Metropolis 算法就是如何在局部最优解的情况下让其跳出来是退火的基础。
Metropolis\text{Metropolis}Metropolis 提出的以概率来接受新状态的重要性采样方法而非使用完全确定的规则称为Metropolis\text{Metropolis}Metropolis 准则计算量较低。 假设我们从 AAA 开始求解。先跳到 BBB然后发现 BBB 更优绝对接受。BBB 又跳到 CCC绝对接受。CCC 跳到 DDD 哎呀更差了呢此时我们以一定的概率选择是否接受假设接受DDD 又跳到 EEE 发现比之前跳到的所有位置都优直接接受EEE 继续跳……\dots\dots…… 不接受就还停在 CCC 又开始随机下一个解。
至于这个接受概率是多少呢已经有前人计算出来了。x:x:x: 当前最优解x′:x:x′: 产生的新解 P{1E(x′)E(x)e−E(x′)−E(x)TE(x′)≥E(x)P\begin{cases}1\quad\quad\quad\quad\quad\quad E(x)E(x)\\e^{-\frac{E(x)-E(x)}{T}}\quad\quad\ E(x)\ge E(x)\end{cases} P{1E(x′)E(x)e−TE(x′)−E(x) E(x′)≥E(x) 从这个式子我们可以看出如果新解更优那么百分之百绝对接受否则我们会以 PPP 的概率接受。
Metropolis\text{Metropolis}Metropolis 算法虽然说是模拟退火算法的基础但直接使用的话可能导致寻找解得速度太慢以至于无法过题。
为了确保在有限的时间收敛必须设定控制算法收敛的参数。
在上面的公式中可以调节的参数就是『温度参数』TTT。
TTT 如果过大就会导致退火太快迭代次数不够最后停留在局部最优值就会结束迭代。TTT 如果较小则计算时间会增加。
实际应用中采用退火温度表在退火初期采用较大的 TTT 值随着退火的进行逐步降低 初始的温度 T0T_0T0 应选的足够高使的所有转移状态都被接受。初始温度越高获得高质量的解的概率越大但耗费的时间也越长。 退火速率。 指数式下降TnλTn,n1,2,3,...T_n\lambda T_n,n1,2,3,...TnλTn,n1,2,3,...。λ\lambdaλ 即是爬山算法里面的『降温参数』选取的值同样遵守 111 又逼近 111 原则。 这种方式最常见且对每一温度有足够的转移尝试但其收敛速度比较慢。 其它方式 TnT0log(1t)T_n\frac{T_0}{\log(1t)}Tnlog(1t)T0。TnT01tT_n\frac{T_0}{1t}Tn1tT0。 终止温度。当 T0T_0T0 迭代到终止温度时就会结束退火。一般设为 eps1e-kk∈Zk\in \Z^k∈Z。
一般针对数据进行『温度参数』TTT『降温参数』Δ\DeltaΔ 的调参在本地手造大数据跑自己抉择。
对时间和正确性的平衡选取。
有的时候可以用 #include ctime 库里面自带的 clock() 函数计时也可以自己定一个跑的次数。
( clock() / (1.0 * CLOCKS_PER_SEC) ) TIME
//返回的是多少秒 所以TIME是个 1 的浮点数需要注意是
初始温度 T0T_0T0 的选取对算法结果有一定的影响最好是多次运行对结果进行综合判断。在算法运行初期温度下降快避免接受过多的差结果。当运行时间增加温度下降减缓以便于更快稳定结果。当迭代次数增加到一定次数时结果可能已经达到稳定但是距离算法结束还有一段时间。在设计程序时应该加入适当的输出条件满足输出条件即可结束程序。
最后给出流程图总结又淘了一张好图 显然模拟退火也不一定是对的这个概率接受就很概率。但对比爬山得到最优解的概率肯定是大大增加的。
例题
Strange function
hdu2899
TTT 次询问每次给定 yyy。
求 f(x)6x78x67x35x2−yx(0≤x≤100)f(x)6x^78x^67x^35x^2-yx\quad(0\le x\le 100)f(x)6x78x67x35x2−yx(0≤x≤100) 的最小值。
#include bits/stdc.h
using namespace std;
double y;
const double eps 1e-8; //终止温度
const double delta 0.997; //温度变化率
mt19937 wwl(time(0));
uniform_real_distribution double range( 0, 100 );double f( double x ) {return 6 * pow(x, 7) 8 * pow(x, 6) 7 * pow(x, 3) 5 * pow(x, 2) - y * x;
}double solve() {double T 100, x range( wwl ); //初始温度 以及初始随机解double now f(x), ans now;int Time 8e5; //防止超时的卡点次数while( T eps and Time -- ) { //要么降温完成 要么被卡时double tx x (rand() * 2 - RAND_MAX) * T; //随机扰动产生新解if( 0 tx and tx 100 ) {double nxt f(tx);ans min( ans, nxt );if( nxt now ) //新状态更小 直接接受x tx, now nxt;else if( rand() exp( ( now - nxt ) / T ) * RAND_MAX ) //在一定概率内仍接受这个解x tx, now nxt;}T * delta; //降温}return ans;
}int main() {int T;scanf( %d, T );while( T -- ) {scanf( %lf, y );printf( %.4f\n, solve() );}return 0;
}[JSOI2004]平衡点 / 吊打XXX
洛谷链接
#include bits/stdc.h
using namespace std;
#define delta 0.996
#define maxn 1005
#define eps 1e-15
struct node { int x, y, w; }g[maxn];
int n;double energy( double x, double y ) {double ans 0, dx, dy;for( int i 1;i n;i ) {dx x - g[i].x, dy y - g[i].y;ans sqrt( dx * dx dy * dy ) * g[i].w;}return ans;
}double ansx, ansy, ans, x, y, now;
void Simulate_Anneal() {double T 5e4;while( T eps ) {double tx x (rand() * 2 - RAND_MAX) * T;double ty y (rand() * 2 - RAND_MAX) * T;double tw energy( tx, ty );if( tw ans ) ans tw, ansx tx, ansy ty;if( tw now ) x tx, y ty, now tw;else if( rand() exp( ( now - tw ) / T ) * RAND_MAX )x tx, y ty;T * delta;}
}signed main() {scanf( %d, n );for( int i 1;i n;i )scanf( %d %d %d, g[i].x, g[i].y, g[i].w );for( int i 1;i n;i ) x g[i].x, y g[i].y;x / n, y / n;ansx x, ansy y;now ans energy( x, y );Simulate_Anneal();Simulate_Anneal();Simulate_Anneal();Simulate_Anneal();printf( %.3f %.3f\n, ansx, ansy );return 0;
}Haywire
洛谷链接
#include bits/stdc.h
using namespace std;
#define TIME 0.9
#define eps 1e-10
#define delta 0.998
#define maxn 15
int n;
int p[maxn];
int f[maxn][5];int energy() {int ans 0;for( int i 1;i n;i )for( int j 1;j 3;j )ans fabs( p[i] - p[f[i][j]] );return ans;
}int main() {mt19937 wwl(time(NULL));scanf( %d, n );uniform_int_distribution int id( 1, n );for( int i 1;i n;i )for( int j 1;j 3;j )scanf( %d, f[i][j] );iota( p 1, p n 1, 1 );int ans energy();while( ( clock() / (1.0 * CLOCKS_PER_SEC) ) TIME ) {for( int i 1;i n;i ) p[i] i;double T 1e5; int x, y;while( T eps ) {do { x id( wwl ), y id( wwl ); }while( x y );swap( p[x], p[y] );int now energy();if( now ans ) ans now;else if( rand() exp( ( now - ans ) / T ) * RAND_MAX )swap( p[x], p[y] );T * delta;}}printf( %d\n, ans / 2 );return 0;
}学习参考博客 https://www.cnblogs.com/flashhu/p/8884132.html https://blog.csdn.net/weixin_42398658/article/details/84031235 https://zhuanlan.zhihu.com/p/266874840?utm_sourceqq
