模式搜索法.doc

模式搜索法这是虎克—吉夫斯(Hook-Jeeves)于1962年提出的,故又称虎克—吉夫斯法,根据方法本身特点,也称为步长加速法。,首先在某一点的四周探索出一个能使目标函数有所被改进的方向;然后沿着这个方向逐步加速前进。当发现继续沿此方向再爬不利时,便停止前进,而重新探索有利方向;就这样,“探”与“爬”交替进行直至最优点位置。这个方法的特点是一直拿着函数的等值线(面)的局部主轴方向进行探索,已达到加快收敛的目的。或者形象地说,是沿着曲折的山脊前进。可以认为,整个迭代过程是由两类移动所组成:一类是“探索性”的,一类是“模式性”的。下面以二元函数为例进行说明。,有两个分量和。作探索性移动时,先选定初始点,计算。步长根据预给的精度来选择,如为二元函数即选择为精度若干倍的两个正数和。从点出发,分别沿和方向做探索。可以先沿方向以为步长水平移动(或左或右),只要移动成功(即目标函数沿优化的方向有所改进),就记移动后的点为。若左右移动均失败,便令。然后再沿方向以为步长作垂直移动(或上或下),只要移动成功,就记移动后的点为,如图10-22。对于二元函数,探索至此暂告结束;但对于元变量的情形,就要沿个座标方向做类似的探索,直至完成一个周期。点若优于点,就把它改记作,即。此时已知点和的连线方向是有利方向。接着进行模式移动,就是将从到的移动无条件地依同一方向延伸一倍。用表示延伸后得到的点,点称为参考点。成为基点;是初始点,因此既是基点又是参考点。从参考点开始作探索性移动,找到的是基点,从基点沿至的方向延伸一倍得参考点,这就是模式移动。这里也表现出步长加速法的基本过程。但进到一定阶段,会遇到下面情形:不但点比点没有改进,而且从出发作探索所得到的点(如和)仍不优于点,迭代过程无法继续。这说明原来的走向失败,应将步长和缩小,重新探索有利方向并重复上述步骤。如此循环直至得到满意结果或步长和达到给定的精度以内。图10--23表示一个模式搜索法的局部过程。图10-23模式搜索法示意图从初始点x(0)(即参考点y(0))作探索移动,得到新的基点x(0)。延伸一倍距离得到新的参考点y(0)(作模式移动)。从y(1)再作探索移动,目的是进行一次局部探测,以校验所探索的走向是否正确。当该方向被认为是成功的,则得到新的基点x(2)。再从x作模式移动得到新的参考点y(2)。从图中可以看出x(2)到y(2)的距离等于x(1)到x(2)的距离,已是原模式移动步长的二倍。这是因为已从探索证明目标函数在同一方向上得到了改进,所以步长可以大些,而由于每次新的移动都考虑到前面几次移动的累积作用,所以也能够大些。由此把这种方法称为步长加速法。从y(2)作探索,垂直方向失败,则得y2(2)=y1(1)=x(3),即得新的基点x(3)。从x(3)延伸x(2)x(3)方向一倍的距离得y(3)。在y(3)作探索,垂直方向和水平向左移动均失败,则得y1(3)=y2(3)=x(4),于是求得新的基点x(4),此时f(x(4))优于(小于)f(x(3))。从基点x(4)作模式移动求得参考点y(4),如自y(4)作探索各方向均失败且f(y(4))>f(y(3)),即从基