常用降維動態(tài)規(guī)劃

1、常用降維動態(tài)規(guī)劃1 逐次逼近動態(tài)規(guī)劃（ DPSA ）逐次逼近動態(tài)規(guī)劃是求解多維問題的有效方法之一， 它的基本思想是把帶有 若干決策變量的問題分解成僅帶有 1 個決策變量的若干個子問題， 每個子問題比 原來的總問題具有較少的狀態(tài)變量， 從而大大節(jié)省狀態(tài)存儲量及計算工作量， 便 于計算機求解。對于多庫聯(lián)調(diào)優(yōu)化問題，在確定初始可行調(diào)度線后采用 DPSA 求解的過程如下：（1）先假定第 2 個到最后一個水庫的調(diào)度過程全部固定，對第 1 個水庫進 行優(yōu)化，這時相當(dāng)于單庫優(yōu)化調(diào)度， 可以通過常規(guī)動態(tài)規(guī)劃找到第 1 個水庫的最 優(yōu)調(diào)度過程， 此時其它水庫僅進行簡單的水務(wù)計算即可。 計算完成后用最優(yōu)結(jié)果 替代

2、初始解中第 1 個水庫的調(diào)度過程。（2）假定第 1 個，第 3 個到最后一個水庫的調(diào)度過程全部固定，求第 2 個 水庫的最優(yōu)過程，這也相當(dāng)于單庫優(yōu)化調(diào)度，同樣通過常規(guī)動態(tài)規(guī)劃找到第 2 個水庫的最優(yōu)調(diào)度過程。并將其最優(yōu)結(jié)果替代初始解中第 2 個水庫的調(diào)度過程。（3）依次類推，直至最后一個水庫計算完成。此時初始可行解依次被各次 的單庫最優(yōu)結(jié)果替代，一輪計算完成。（4）以上一輪最優(yōu)結(jié)果為基礎(chǔ)，重新依次計算單個電站的最優(yōu)過程，并替 換總體最優(yōu)結(jié)果，反復(fù)輪流優(yōu)選，直至收斂。DPSA 的思想是通過減少每次參與計算的電站數(shù)目， 達到降維效果， 其搜索 結(jié)果精度與初始狀態(tài)序列有關(guān)， 因此它不能保證在所有情況

3、下都收斂到真正的總 體最優(yōu)解，求解過程中可以從多個不同的初始狀態(tài) （庫群初始調(diào)度過程 ）開始，求 得多個最優(yōu)值，然后選擇最好的結(jié)果。2增量動態(tài)規(guī)劃（DDDP ）DDDP是用逐次逼近方法尋優(yōu)，每次尋優(yōu)只在某個狀態(tài)序列附近的小范圍內(nèi)，用動態(tài)規(guī)劃法進行搜索。其搜索流程是先根據(jù)一般經(jīng)驗或常規(guī)方法獲得初始 狀態(tài)序列作為初始調(diào)度線，然后在該初始狀態(tài)序列的上下各變動一個小范圍， 這 個變動范圍成為增量，形成一個帶狀“廊道”，接著在該廊道內(nèi)用常規(guī)的動態(tài)規(guī) 劃尋優(yōu)，可求得一條新的更接近于最優(yōu)的狀態(tài)序列。 這樣就完成了一輪尋優(yōu)，然 后在新的狀態(tài)序列上下再變動一個增量， 并進行尋優(yōu)。依此逐次進行迭代，直到 逼近最優(yōu)

4、狀態(tài)序列為止。在迭代過程中，增量可由大變小；也可根據(jù)情況只在初始決策序列的一側(cè)選增量；在各個階段和上下兩側(cè)的增量個數(shù)也可以不同，而且3所示，各圖中同一時段增量值的大小也可以不一樣。DDDP兩個圈表示狀態(tài)的間隔即為增量。（c）第二輪尋優(yōu)it粗2）第二輪丫比詰采DDDP的思想是通過減少每次計算時的離散狀態(tài)，達到降維的效果，與DPSA 一樣不能保證所得的解是總體最優(yōu)，有可能收斂到某一局部最優(yōu)解。因此可以采用從幾個不同的初始狀態(tài)開始，求出幾個“最優(yōu)解”，然后從中選擇一個最好的解。3狀態(tài)逐密動態(tài)規(guī)劃狀態(tài)逐密動態(tài)規(guī)劃是在狀態(tài)空間內(nèi)先以較低的精度要求，取較少的狀態(tài)數(shù)目，在較稀的區(qū)間內(nèi)尋找最優(yōu)值。然后以當(dāng)前最

5、優(yōu)解為基礎(chǔ)，在附近狀態(tài)序列上 下一定范圍內(nèi)，加密搜索狀態(tài)以提高精度，再一次優(yōu)選。這樣逐步加密狀態(tài)，多 次選優(yōu)，直至滿足精度要求。4逐步優(yōu)化算法（POA）加拿大學(xué)者Howson和Sancho N G R 根據(jù)貝爾曼最優(yōu)化原理的思想提出 了逐步最優(yōu)化原理：“最優(yōu)路線具有這樣的性質(zhì)，每對決策集合相對于它的初始 值和終止值來說是最優(yōu)的”。逐步優(yōu)化算法便是根據(jù)這個原理設(shè)計的，主要用于 求解多維動態(tài)規(guī)劃問題。該算法將多階段決策問題分解成若干個子問題，子問題之間由系統(tǒng)狀態(tài)聯(lián)系，每個子問題僅考慮單個時段的狀態(tài)及相鄰兩時段的子目標(biāo) 值，逐個時段進行尋優(yōu)，直到收斂。假設(shè)對 T個時段進行求解，其尋優(yōu)過程如圖3.2所示。水庫調(diào)度優(yōu)化，如果電站數(shù)