[科普中國]-策略迭代法

策略迭代法（policy iteration method）是動態(tài)規(guī)劃中求最優(yōu)策略的基本方法之一。它借助于動態(tài)規(guī)劃基本方程，交替使用“求值計算”和“策略改進”兩個步驟，求出逐次改進的、最終達到或收斂于最優(yōu)策略的策略序列。

計算例如，在最短路徑問題中，設(shè)給定M個點1，2，…，M。點M是目的點，сij>0是點i到點j的距離i≠j，сij=0，i,j=1,2,…,M,要求出點i到點M的最短路。記?(i)為從i到M的最短路長度。此問題的動態(tài)規(guī)劃基本方程為：

其策略迭代法的程序如下：選定一初始策略u0(i)，在這問題中，策略u(i)的意義是從點i出發(fā)走一步后到達的點，而且作為策略，它是集{1,2,…,M-1}上的函數(shù)。由u0(i)解下列方程組求出相應(yīng)的值函數(shù)?0(i)：

再由?0(i)求改進的一次迭代策略u1(i)，使它是下列最小值問題的解：

然后，再如前面一樣，由u1(i)求出相應(yīng)的值函數(shù)?1(i)，并由?1(i)求得改進的二次迭代策略u2(i)，如此繼續(xù)下去。

步驟可見求解(1)的策略迭代法的程序由下列兩個基本步驟組成：

①求值計算 由策略 un(i)求相應(yīng)的值函數(shù)?n(i)，即求下列方程的解：

②策略改進 由值函數(shù)?n(i)求改進的策略，即求下列最小值問題的解：

式中規(guī)定，如un(i)是上一問題的解，則取un+1(i)=un(i)。

在一定條件下，由任選的初始策略出發(fā)，輪換進行這兩個步驟, 經(jīng)有限步N后將得出對所有i，uN+1(i)=uN(i)這樣求得的uN(i)就是最優(yōu)策略，相應(yīng)的值函數(shù)?N(i)。是方程(1)的解。

對于更一般形式的動態(tài)規(guī)劃基本方程

這里?，H，φ為給定實函數(shù)。上述兩個步驟變成：

①求值計算 由策略un(x)求相應(yīng)的值函數(shù) ?n(x)，即求方程 之解，n=0，1，2…。

②策略改進 由值函數(shù)?n(x)求改進的策略un+1(x)，即求最優(yōu)值問題（圖8）的解。

對于滿足適當(dāng)條件的方程(2)和初始策略，上述兩個步驟的解存在，并且在一定條件下，當(dāng)n→ 時，所得序列{?n(x)}與{un(x)}在某種意義下分別收斂于(2)的解和最優(yōu)策略。

策略迭代法最初是由R.貝爾曼提出的。1960年，R.A.霍華德對于一種馬爾可夫決策過程模型，提出了適用的策略迭代法，給出了相應(yīng)的收斂性證明。后來，發(fā)現(xiàn)策略迭代法和牛頓迭代法在一定條件下的等價性，于是，從算子方程的牛頓逼近法的角度去研究策略迭代法，得到了發(fā)展。

對于范圍很廣的一類馬爾可夫決策過程，其動態(tài)規(guī)劃基本方程可以寫成

式中?∈V，對所有 γ∈Γ:r(γ)∈V，γ為 V→V的線性算子，Γ為這種算子的族，而V 則是由指標(biāo)值函數(shù)所構(gòu)造的函數(shù)空間。

假設(shè) 當(dāng) ?(γ)是方程 r(γ)+γ?=0 的解時，它是對應(yīng)于策略γ的指標(biāo)值函數(shù)。

最優(yōu)策略，定義為最優(yōu)值問題的解。

這時由策略迭代法所求得的序列{fn}和{γn}滿足下列關(guān)系 ，其中的逆算子。1

當(dāng)σ是加托可微時, γn+1是σ在?n處的加托導(dǎo)數(shù)。于是，上面的關(guān)系恰好表達了牛頓迭代法在算子方程中的推廣。

解決問題利用迭代算法解決問題，需要做好以下三個方面的工作：

一、確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。

二、建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。

三、對迭代過程進行控制。在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要進一步分析出用來結(jié)束迭代過程的條件。

動態(tài)規(guī)劃動態(tài)規(guī)劃是旦澤和貝爾曼提出的，他們關(guān)于這一定量化方法的重要著作發(fā)表于50年代。最初動態(tài)規(guī)劃指的是不確定性的線性規(guī)劃問題，而現(xiàn)在它已發(fā)展成為一個解決范圍廣泛的工商業(yè)務(wù)問題的定量技術(shù)了。

動態(tài)規(guī)劃的理論基礎(chǔ)為“最優(yōu)化原則”。它是說一個最優(yōu)策略是由最優(yōu)子策略構(gòu)成的。它可以定義為這樣的一個數(shù)學(xué)方法：它解決一串序貫決策問題，而這些決策中的每一個都又影響著未來的決策，且后面的決策對前面決策所決定的初始狀態(tài)來說總是最優(yōu)的。這是非常重要的，因為我們很難遇到一個運行中的情況；其中的決策不影響未來的決策。經(jīng)理們面對著的問題是要他們作出一系列決策，這些決策中的每一個都依賴于先前決策的結(jié)果。例如，一個生產(chǎn)經(jīng)理可能為了得到眼前的高產(chǎn)量不顧未來的高產(chǎn)量而忽視工廠的維修工作。若每一決策只考慮它本身最優(yōu)化，那么由全部決策所得到的收益可能不是最優(yōu)的。相反如果在制定第1個或后續(xù)的決策時在收益上作些犧牲，雖然使各決策次優(yōu)化了，但總的收益可能更高些。這就是動態(tài)規(guī)劃的目標(biāo)。

一般說來，動態(tài)規(guī)劃處理的問題都含有時間變量。但是，它可以用來處理一些本來與時間無關(guān)的問題，這只要在靜態(tài)模型中人為地引進“時間”因素，分成時段，把它看作多階段的動態(tài)模型就能用動態(tài)規(guī)劃的方法來解決了。

在很多領(lǐng)域中都有動態(tài)規(guī)劃的應(yīng)用。如資源分配、貨物裝運、設(shè)備更新、生產(chǎn)計劃和存貯、排序、確定利息策略及評價投資機會等。

動態(tài)規(guī)劃可以看成是一個把復(fù)雜的大問題分成一系列較易解決的小問題的方法。它沒有標(biāo)準(zhǔn)的格式。

動態(tài)規(guī)劃模型有4個基本概念：(1)階段。它是所給問題中被劃分成若干個相互聯(lián)系的時期或區(qū)間。(2)狀態(tài)變量。是表示某段的出發(fā)位置。這些狀態(tài)變量的值把制定決策需要了解的所有有關(guān)系統(tǒng)的情況都顯示出來。狀態(tài)變量數(shù)目可能很大，對于一定的計算能力，應(yīng)盡能減少狀態(tài)變量的數(shù)目。(3)決策變量。表示狀態(tài)給定以后，從該狀態(tài)到下一階段某狀態(tài)的選擇。(4)目標(biāo)函數(shù)。各個不同階段的決策能力，可能是距離、利潤、成本等。2

本詞條內(nèi)容貢獻者為:

王海俠 - 副教授 - 南京理工大學(xué)