您现在的位置是:首页 >技术交流 >智能优化算法——下山单纯型算法网站首页技术交流

智能优化算法——下山单纯型算法

非妃是公主 2024-06-17 10:13:44
简介智能优化算法——下山单纯型算法

在这里插入图片描述

作者:非妃是公主
专栏:《智能优化算法》
博客地址https://blog.csdn.net/myf_666
个性签:顺境不惰,逆境不馁,以心制境,万事可成。——曾国藩
在这里插入图片描述

专栏推荐

专栏名称专栏地址
软件工程专栏——软件工程
计算机图形学 专栏——计算机图形学
操作系统专栏——操作系统
软件测试专栏——软件测试
机器学习专栏——机器学习
数据库专栏——数据库
算法专栏——算法

下山单纯型法是一种智能优化算法,对于一个 n 维问题,主要通过先产生 n+1 个可行解,然后通过反射、收缩、膨胀、压缩 4 个操作,不断逼近最优解的过程。

给定 n+1 个顶点 x i , i = 1 , . . . , n + 1 x_i,i=1,...,n+1 xi,i=1,...,n+1,这些点对应的函数值为 f ( x i ) f(x_i) f(xi)

定义如下相关参数

参数名称参数值
反射(reflection) α = 1 alpha = 1 α=1
膨胀(expansion) γ = 2 gamma = 2 γ=2
收缩(contration) β = 0.5 eta = 0.5 β=0.5
压缩(shrinkage) δ = 0.5 delta = 0.5 δ=0.5

一、算法流程

1. 反射

  1. 按照目标函数对n+1个点进行从好到差排序,确定最坏点,第二坏点和最好点的下表 h , s , l h,s,l h,s,l

  2. 计算除去最差点外其它点的中心点: c = 1 n ∑ j = 1 n x j c=frac{1}{n}sum_{j=1}^n x_j c=n1j=1nxj;

  3. 反射操作: x r = c + α ( c − x h ) , f r = f ( x r ) x_r=c+alpha(c-x_h),f_r=f(x_r) xr=c+α(cxh),fr=f(xr)。如果 f l < = f r < = f s f_l<=f_r<=f_s fl<=fr<=fs,则接受 x r x_r xr

这里要注意反射操作时,对 c − x h c-x_h cxh 的理解,可以理解其为一个向量,从 c c c 点加上一个由 x h x_h xh 指向 c c c 的向量。

如下图所示:

在这里插入图片描述


2. 膨胀

如果我们上面的反射取得了很好的效果,我们还要再膨胀一下,因为也许可能取得更好的效果,因此,在 f r < f l f_r<f_l fr<fl的条件下,即反射后比之前三角形的最优位置还小,那么我们就要进一步向这个方向移动,计算膨胀点为:

x e = c + γ ( x r − c ) x_e=c+gamma (x_r-c) xe=c+γ(xrc)

从上面可以看出,之前的系数 α = 1 alpha=1 α=1,现在的系数 γ = 2 gamma=2 γ=2,是膨胀的。


3. 收缩

如果 f r > = f s f_r>=f_s fr>=fs,则利用 x h x_h xh(最坏点)和 x r x_r xr(反射点)中较好的一个点来计算收缩点 x c x_c xc

这里可能发生的情况就是,我们反射时候波动的范围较大,因此我们需要进一步缩小一定的范围。

如果 x h x_h xh好一些的话,我们就向 x h x_h xh方向走,但是,注意是收缩,少走一些。

如果 x r x_r xr好一些的话,同理,我们就像 x r x_r xr方向走,但是,同样注意要少走一些。


Ⅰ. x r x_r xr好一些的情况

f s < = f r < f h f_s<=f_r<f_h fs<=fr<fh,向外收缩,计算 x c = c + β ( x r − c ) , f c = f ( x c ) x_c=c+eta(x_r-c),f_c=f(x_c) xc=c+β(xrc),fc=f(xc)。如果 f c < = f r f_c<=f_r fc<=fr(证明有效果),则接受 x c x_c xc

在这里插入图片描述


Ⅱ. x h x_h xh好一些的情况

f r > = f h f_r>=f_h fr>=fh,计算 x c = c + β ( x h − c ) , f c = f ( x c ) x_c=c+eta(x_h-c),f_c=f(x_c) xc=c+β(xhc),fc=f(xc)。如果 f c < f h f_c<f_h fc<fh(证明有效果),接受 x c x_c xc

在这里插入图片描述

注意:这里的 β = 0.2 eta=0.2 β=0.2,不是上面的 α = 1 alpha=1 α=1操作,因此,叫做收缩。


4. 压缩

最后,如果 f r > f h f_r>f_h fr>fh,这个时候,证明结果已经很坏了。进行压缩操作,怎么压缩呢?整体向最好的点的方向压缩,如下:

x j = x l + δ ( x j − x i ) , f j = f ( x j ) , j = 1 , . . . , n + 1 且 j ≠ l x_j=x_l+delta(x_j-x_i),f_j=f(x_j),j=1,...,n+1且j eq l xj=xl+δ(xjxi),fj=f(xj),j=1,...,n+1j=l

在这里插入图片描述


二、一个求解的实例

在这里插入图片描述

公式太多了,打不出来,附上手稿,如有纰漏,欢迎指正!手动推演了 3 代,具体如下图:

在这里插入图片描述

the end……

下山单纯型算法到这里就要结束啦~~到此既是缘分,欢迎您的点赞评论收藏关注我,不迷路,我们下期再见!!

??? 我是Cherries,一位计算机科班在校大学生,写博客用来记录自己平时的所思所想!
??? 内容繁杂,又才疏学浅,难免存在错误,欢迎各位大佬的批评指正!
??? 我们相互交流,共同进步!

:本文由非妃是公主发布于https://blog.csdn.net/myf_666,转载请务必标明原文链接:https://blog.csdn.net/myf_666/article/details/129072785

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。