[發(fā)明專利]一種多維多階段復(fù)雜決策問題的均勻動態(tài)規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201410723960.0
• 申請日: 2014-12-02
• 公開（公告）號: CN104408531B
• 公開（公告）日: 2018-04-10
• 發(fā)明（設(shè)計）人: 程春田;馮仲愷;牛文靜;廖勝利;武新宇;李剛;申建建;曾筠
• 申請（專利權(quán)）人: 大連理工大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/06
• 代理公司: 大連理工大學(xué)專利中心21200
• 代理人: 梅洪玉

技術(shù)領(lǐng)域

本發(fā)明涉及水電系統(tǒng)決策優(yōu)化領(lǐng)域，特別涉及一種多維多階段復(fù)雜決策問題的均勻動態(tài)規(guī)劃方法。

技術(shù)背景

多維多階段決策問題普遍存在于水利、交通、經(jīng)濟等復(fù)雜巨系統(tǒng)的最優(yōu)控制及生產(chǎn)調(diào)度中，通常涉及到龐大復(fù)雜的目標(biāo)和約束條件，很難對目標(biāo)和約束條件分解，因此大多無法選擇解析式優(yōu)化方法，通常選用對目標(biāo)函數(shù)和約束條件無嚴(yán)格要求的動態(tài)規(guī)劃進行求解。動態(tài)規(guī)劃將復(fù)雜高維決策問題通過分段降維轉(zhuǎn)化為一系列結(jié)構(gòu)相似的簡單低維子問題，利用各階段之間的關(guān)聯(lián)關(guān)系遞歸求解，能夠同時獲得全局最優(yōu)解及各子過程的最優(yōu)解，有利于對結(jié)果進行分析。然而隨著狀態(tài)變量與決策變量維數(shù)的增加，動態(tài)規(guī)劃計算量與存儲量均呈指數(shù)增長，受限于現(xiàn)有計算機存儲容量和計算速度，常常無法解算。

為克服這一問題，國內(nèi)外學(xué)者對動態(tài)規(guī)劃開展多方面的探索，提出一系列以逐次漸進逼近理論為核心的改進方法，如旨在減少維數(shù)的動態(tài)規(guī)劃逐次逼近算法，旨在減少離散狀態(tài)數(shù)的離散微分動態(tài)規(guī)劃，旨在減少優(yōu)化階段數(shù)的逐步優(yōu)化算法。這些方法在不同程度上提高了動態(tài)規(guī)劃計算效率，但在求解大規(guī)模復(fù)雜決策問題時存在仍會面對“維數(shù)災(zāi)”問題，難以保證在合理時間內(nèi)獲得高質(zhì)量的優(yōu)化解。

均勻試驗設(shè)計是我國數(shù)學(xué)家方開泰和王元利用數(shù)論在多維數(shù)值積分中的應(yīng)用原理創(chuàng)立的多因素多水平試驗設(shè)計方法。它著重考慮試驗點在試驗范圍內(nèi)的充分均衡分布，力求通過最少的試驗次數(shù)獲得最多的信息，通過合理安排試驗實現(xiàn)各因素每個水平僅做一次試驗，在大幅減少試驗次數(shù)的同時保證所選試驗點具有良好的代表性，從而提高試驗結(jié)果的精確性與可靠性。

均勻試驗設(shè)計采用精心設(shè)計的均勻設(shè)計表安排試驗方案，記為U_m(q^s)，其中U表示均勻設(shè)計，q為設(shè)計水平數(shù)，s為設(shè)計因素數(shù)，m為試驗次數(shù)，m＝q。均勻設(shè)計表為q行s列的矩陣，即各行分別表示一種均勻試驗設(shè)計方案；各列涵蓋相應(yīng)因素所有可能水平；a_i,j表示第i項試驗方案中因素j相應(yīng)水平，a_i,j∈{1,2,…,q}。

從表1可以看出，均勻設(shè)計表具有以下特點：(1)各列不同數(shù)字只出現(xiàn)一次，即各因素的不同水平僅做一次試驗。(2)任意兩因素相應(yīng)水平有且僅需開展一次試驗。(3)均勻設(shè)計將試驗次數(shù)降至水平數(shù)的一次方數(shù)量級，即試驗次數(shù)與試驗水平數(shù)相同，工作量大幅減少且具有良好的連續(xù)性。由此可知，采用均勻設(shè)計表安安排試驗，僅需極少數(shù)試驗即能反映客觀事物的主要特征。

表1均勻設(shè)計表

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問題是：提供一種均勻動態(tài)規(guī)劃方法解決動態(tài)規(guī)劃求解多維多階段復(fù)雜決策問題中存在的維數(shù)災(zāi)問題。

本發(fā)明首先對動態(tài)規(guī)劃時空復(fù)雜度進行分析。假設(shè)系統(tǒng)涉及N座水電站(N維，即單個水電站視為一維)的T個階段(多階段)的優(yōu)化計算，階段j狀態(tài)向量為V_j＝(V_1,j,V_2,j,…,V_N,j)^T需要一個單位的存儲空間，其中V_i,j表示第i個電站在第j個階段的狀態(tài)。若各水電站在所有T個階段狀態(tài)變量均在可行域內(nèi)離散q份，則時段j的狀態(tài)向量總數(shù)為顯然，各狀態(tài)向量分別需要一個單位存儲空間，同時均需從前一時段q^N個狀態(tài)向量中優(yōu)選最優(yōu)狀態(tài)向量，共計q^N次計算；階段j所有狀態(tài)向量共需q^N個存儲空間、涉及q^N×q^N＝q^2N次計算。動態(tài)規(guī)劃一次計算中T個階段合計需要T×q^N個存儲空間、T×q^2N次計算。由此可知，動態(tài)規(guī)劃空間復(fù)雜度和時間復(fù)雜度分別為O(Tq^N)和O(Tq^2N)。顯然，單階段各維離散狀態(tài)的全面組合是動態(tài)規(guī)劃時空復(fù)雜度隨電站規(guī)模和狀態(tài)離散數(shù)目呈指數(shù)增長的根本原因。假設(shè)單一水電站狀態(tài)離散數(shù)目取為100，則N座水電站開展全面組合，狀態(tài)變量總數(shù)高達100^N，每增加一座電站，狀態(tài)變量數(shù)目便增加100倍，“維數(shù)災(zāi)”凸顯。因此，若能采取一定的方法手段避免各維離散狀態(tài)的全面組合，可以節(jié)省計算工作量和存儲量，有效緩解動態(tài)規(guī)劃維數(shù)災(zāi)問題。