基本介紹
- 中文名:隨機走步法
- 外文名:random walk method
- 所屬學科:數學
- 簡介:利用隨機數確定搜尋方向的方法
基本介紹,方法步驟,帶一維搜尋的隨機走步法,
基本介紹
隨機走步法是以產生一系列逐步改善的極小值的近似點為基礎的,其中每一個近似點都是由前一近似點推導得到的。如果
是在第
級(或第
步或第
次)得到的一個近似極小點,則第i級新的改進的近似極小點可由下面關係式求得
![](/img/6/a4a/038c379261fe8b8a5ff37c2f6925.jpg)
![](/img/0/7e3/f2a38b00addf3b0191926e049d3c.jpg)
![](/img/0/7e3/f2a38b00addf3b0191926e049d3c.jpg)
![](/img/0/7e3/f2a38b00addf3b0191926e049d3c.jpg)
![](/img/1/eea/079255f72374d39b48a958f46934.jpg)
![](/img/c/e8c/500ff5304c90618f7a2dfc42821d.jpg)
![](/img/2/376/152e6efc4bb9ac2e2603ebe58ade.jpg)
方法步驟
隨機走步法的疊代過程如下:
①開始選一初始點
和一相對於最終要求精度充分大的標量步長
。計算函式值
。
![](/img/2/3ac/9cbd9db03777d0ab59779655adf4.jpg)
![](/img/c/e8c/500ff5304c90618f7a2dfc42821d.jpg)
![](/img/2/961/d31f6940e9d8ee41fe4ecfc40259.jpg)
②置疊代序號
。
![](/img/c/f09/20fcf2dc2bbc94edd523ba02d817.jpg)
③產生一組n個隨機數,並建立單位隨機向量u。
④求目標函式的新值為
![](/img/1/6b6/09cc4d2baddc7e461f1149164d6c.jpg)
⑤比較函式值f與
。若
,則使
,並重複步驟③到⑤。若
,直接重複步驟③到⑤。
![](/img/8/389/b9b2cce77cb7dee1ba1a2680efd9.jpg)
![](/img/3/a27/5aece81627e74c87618957506060.jpg)
![](/img/b/028/d45e670520531baa97c95e114303.jpg)
![](/img/8/1fc/a3e931d91cfd35d22bb47f069347.jpg)
⑥若疊代次數N已充分大,但還不能產生一個較好的點
,則減小標量步長
,返回步驟③繼續進行。
![](/img/4/0b5/8dcd15b60585cf6067956fe6419c.jpg)
![](/img/c/e8c/500ff5304c90618f7a2dfc42821d.jpg)
⑦若
值已減小到小於某一給定的足夠小的數
後,仍然不能得到一個改進點,則取當前點
為最優點,並結束疊代。
![](/img/c/e8c/500ff5304c90618f7a2dfc42821d.jpg)
![](/img/c/eca/1477504912619332a759116b82b0.jpg)
![](/img/1/0e4/291faacf881e8f44b88d95aedb3a.jpg)
帶一維搜尋的隨機走步法
以上討論的隨機走步法,在某一固定步長
下,一旦求得函式值減小的
方向後即開始生成新的單位隨機向量
。然而,如果可以期望當沿
方向取的步長大一些,函式值有可能進一步下降。這樣將能充分利用對每一f值有可能改善的方向,隨機走步法可以得到改進。採用所討論過的任一種一維極小化方法都可以達到此目的。按照這種方法,新點可按下式求得:
![](/img/c/e8c/500ff5304c90618f7a2dfc42821d.jpg)
![](/img/c/262/d70b3dd4c960bae16d586d2e5eeb.jpg)
![](/img/9/660/bdb50709d765641b28adff539c92.jpg)
![](/img/c/262/d70b3dd4c960bae16d586d2e5eeb.jpg)
![](/img/3/3bf/d7b6185c648cf79909673f5b1200.jpg)
![](/img/0/953/60258a7674967562c5c01f8bfdf7.jpg)
![](/img/c/262/d70b3dd4c960bae16d586d2e5eeb.jpg)
![](/img/6/fe4/6a1249b2d95cb2e1f9776e912ee0.jpg)
具有這種特點的搜尋方法稱帶一維搜尋的隨機走步法。