隨機走步法

隨機走步法(random walk method)是利用隨機數確定搜尋方向的方法。隨機走步法是一種直接的識別方法，它的原理類似於單純形法，但並不藉助於單純形，而是通過用隨機的方式對上一次的近似值加以改進來達到最小誤差函式值。

基本介紹

• 中文名：隨機走步法
• 外文名：random walk method
• 所屬學科：數學
• 簡介：利用隨機數確定搜尋方向的方法

基本介紹

隨機走步法是以產生一系列逐步改善的極小值的近似點為基礎的，其中每一個近似點都是由前一近似點推導得到的。如果是在第級(或第步或第次)得到的一個近似極小點，則第i級新的改進的近似極小點可由下面關係式求得

式中，為規定的標量步長，為第i級產生的單位隨機向量。

方法步驟

隨機走步法的疊代過程如下：

①開始選一初始點和一相對於最終要求精度充分大的標量步長。計算函式值。

②置疊代序號。

③產生一組n個隨機數，並建立單位隨機向量u。

④求目標函式的新值為

⑤比較函式值f與。若，則使，並重複步驟③到⑤。若，直接重複步驟③到⑤。

⑥若疊代次數N已充分大，但還不能產生一個較好的點，則減小標量步長，返回步驟③繼續進行。

⑦若值已減小到小於某一給定的足夠小的數後，仍然不能得到一個改進點，則取當前點為最優點，並結束疊代。

帶一維搜尋的隨機走步法

以上討論的隨機走步法，在某一固定步長下，一旦求得函式值減小的方向後即開始生成新的單位隨機向量。然而，如果可以期望當沿方向取的步長大一些，函式值有可能進一步下降。這樣將能充分利用對每一f值有可能改善的方向，隨機走步法可以得到改進。採用所討論過的任一種一維極小化方法都可以達到此目的。按照這種方法，新點可按下式求得：

式中，為沿方向使

為極小所求得的最優步長。

具有這種特點的搜尋方法稱帶一維搜尋的隨機走步法。