《随机算法介绍》PPT课件

《《随机算法介绍》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、智能优化算法研究1引言在复杂系统的优化计算过程中，传统的确定性算法（如梯度法、共轭梯度法、牛顿法、拟牛顿法等）往往容易陷入局部极值点（如下图）。为了有效地进行全局搜索，得到问题的全局最优解或次优解，人们受自然界、或具体问题的启发提出了一些启发式的随机优化算法。模拟退火算法；遗传算法等进化计算方法；神经网络算法；蚁群算法等等。2一、模拟退火算法模拟退火算法最早由Metropolis于1953年提出，1983年Kirkpatrick等将其应用于优化问题。1.算法步骤(1)给定初温t=t0，随机产生初始

2、状态X(1)，令k=0;(2)Repeat(2.1)Repeat(2.1.1)产生新的状态X(2)=Generate(X(1));(2.1.2)ifrandom[0,1]≤min{1,exp[C(X(1))-C(X(2))]/tk}X(1)=X(2);//这里C(X(1))为状态X(1)的目标函数值(2.2)Until抽样稳定准则满足(2.3)退温tk+1=update(tk),并令k=k+1;(3)Until算法终止准则满足;(4)输出结果3一、模拟退火算法2、三函数、二准则（新状态产生函数，新

3、状态接受函数，退温函数，抽样稳定准则和退火结束准则）①新状态产生函数：通常用领域函数，并且尽可能使候选解遍布全部解空间。②状态接受函数：通常用概率的方式给出，遵循以下三原则：1）在固定温度下，接受使目标函数值下降的候选解的概率要大于使用目标函数值上升的候选解的概率；2）随着温度的下降，接受使目标函数值上升的解的概率要逐渐减少；3）当温度趋于零时，只能接受目标函数值下降的解。模拟退火算法通常采用min{1,exp[C(X(1))-C(X(2))/tk]}作为状态接受函数。4一、模拟退火算法③退温函数

4、：tk+1=λtk(0<λ<1);④抽样稳定规则：通常有三种方法:1)检验目标函数的均值是否稳定;2)连续若干步的目标值变化较小;3)按一定的步数抽样.⑤退火结束准则：三种方法：1)设置终止温度;2)设置外循环迭代次数;3)算法搜索到的最优值连续若干步保持不变。5二、势能曲面变平算法1.势能曲面变平（ELP）算法描述给定一个初始状态X(1)，令t=1，初始化直方图函数H(E,t)，设置温度T，计算E(X(1),t)，令最优解E’=E(X(1),t)，计算；(2)更新当前状态X(1)，产生新的状态X

5、（2）＝Generate(X(1))；(3)计算和，令(4)如果，则接受X(2)，判断E(X(2))106，则停止迭代，输出E’；否则，令t=t+1，转(2).2.对算法的理解关键是：通过增加惩罚项，对目标函数进行修改，尽量避免重复访问曾经访问过的状态。7二、势能曲面

6、变平算法3.对算法的改进1）提出好的状态更新机制：怎样产生新的状态？最好具有搜索整个状态空间的能力。具体来说：可以针对具体问题提出一些启发式策略；或考虑与遗传算法相结合；或采用与禁忌搜索相结合的方法。2）局部搜索：一旦产生一个新的状态，就用某一确定性的算法（如梯度法）进一步搜索该状态附近目标函数值更低的状态。3）将退温机制加入算法4）增加补充搜索过程：即以搜索到的最优解为初始状态，再次执行势能曲面变平法，或进行局部搜索。8三、吸引盘填充算法吸引盘填充算法是势能曲面变平法与梯度法的结合。1.自适应步

7、长的梯度算法X2=X1-▽E(X1)•h其中h是自适应步长。9三、吸引盘填充算法2.吸引盘填充(BasinFilling,BF)算法BF算法是一种将随机算法（ELP）与确定性算法（如梯度法）很好地结合起来的混合算法，其中随机算法ELP用来进行全局搜索，提高采样的多样性和跳出局部极值点，梯度法则用来进行局部搜索，以便快速得到全局最优或新的能量更低的状态。BF算法是一种高性能的全局优化方法。10四.应用：圆形packing问题1.问题提法问题1：给定一个大小确定的圆形闭区域，以及M个可互不重叠地放进圆

8、形区域中的小圆，这些小圆的半径分别为R1,R2,…,RM，问如何将这些小圆互不重叠地放进圆形区域中?问题2：给定M个半径分别是R1,R2,…,RM的小圆，问如何将这M个小圆摆放在直角坐标系平面上，使得所有M个小圆形成的包络圆(即圆形闭区域)的面积最小？11四.圆形packing问题一个实例：12四.圆形packing问题一个实例的布局结果13四.圆形packing问题2.问题背景圆形Packing问题是NP难度问题，在玻璃、钢板、木材、纸张和制衣等工程领域中有着广泛的应用，在这些工