隨著信息科學技術(shù)的迅猛發(fā)展和廣泛應用,出現(xiàn)了大量的復雜隨機動態(tài)系統(tǒng),比如在通訊網(wǎng)絡(Internet及無線網(wǎng)絡),柔性制造,智能機器人,交通管理等領(lǐng)域。目前,該類系統(tǒng)的性能優(yōu)化問題逐漸成為很多領(lǐng)域的研究熱點。這些領(lǐng)域包括控制系統(tǒng)領(lǐng)域,運籌學領(lǐng)域,計算機科學領(lǐng)域以及人工智能領(lǐng)域等等。不同領(lǐng)域采用不同的方法來解決該問題,如控制系統(tǒng)領(lǐng)域的離散事件動態(tài)系統(tǒng)的攝動分析方法,運籌學領(lǐng)域的Markov決策過程理論,計算機科學和人工智能領(lǐng)域的強化學習(或神經(jīng)元動態(tài)規(guī)劃)方法。雖然這些方法對系統(tǒng)結(jié)構(gòu)有著不同的描述,但這些方法都是圍繞著同一個目的展開,即尋找一個“最好的策略”來優(yōu)化系統(tǒng)的性能。 近幾年來,一種基于靈敏度觀點的優(yōu)化方法將以上不同領(lǐng)域的不同方法有機的統(tǒng)一起來。該方法以性能勢理論為基礎(chǔ),通過兩種性能靈敏度公式:性能差公式和性能導數(shù)公式,將攝動分析方法,Markov決策過程理論以及強化學習方法統(tǒng)一在同一框架下。該方法不僅可以基于模型采用理論計算的方法來尋找系統(tǒng)的最優(yōu)策略,而且可以在系統(tǒng)模型參數(shù)未知的情況下基于一條樣本軌道在線地改進系統(tǒng)性能。因而在某種程度上它解決了該類系統(tǒng)的“維數(shù)災”和“模型災”問題。到目前為止,該方法在自適應Markov報酬過程上的應用還沒有被研究,本文在該方法的基礎(chǔ)上,研究了自適應Markov報酬過程的靈敏度分析,得到了性能差和性能導數(shù)公式,以及在單樣本軌道上性能導數(shù)的估計式。 基于仿真的梯度逼近方法是基于一種可以基于單樣本軌道在線的改進系統(tǒng)性能的梯度逼近方法。這個方法首先參數(shù)化策略。然后根據(jù)仿真出來的樣本軌道估計出性能測度關(guān)于參數(shù)向量的梯度;最后再沿梯度的方向改進參數(shù)。利用參數(shù)化策略,減少了未知參數(shù)的個數(shù),避開了“維數(shù)災”的問題;通過仿真避開了“模型災”的問題。參數(shù)的更新時刻的不同,這個方法分為兩個傳統(tǒng)的算法。再生環(huán)梯度逼近算法是每到更新點時,即更新一次參數(shù),每步梯度逼近算法是每次狀態(tài)轉(zhuǎn)移都更新一次參數(shù)。這兩個算法雖然很好的避開了“維數(shù)災”和“模型災”的問題,但它們也有其局限的地方:在再生環(huán)梯度逼近算法中,狀態(tài)空間比較大時,再生環(huán)相應增大,更新緩慢,導致較低的計算效率,同時帶來比較大的方差;在每步梯度逼近算法中,由于每做一次轉(zhuǎn)移,算法進行一次更新,這洋計算量就會比較大,甚至有些實際系統(tǒng)是無法實現(xiàn)的。本文為了解決現(xiàn)有方法的這些不足,提出了Markov報酬過程、自適應Markov報酬過程以及隨機策略的Markov決策過程的雙時間尺度梯度逼近算法。算法主要思想是,在給定的更新周期上更新參數(shù),而這個給定的更新周期序列是由兩個時間尺度通過計算獲得的,并且是個遞增序列。算法的特點是開始更新較快,隨后更新頻率慢慢降低。這個特點帶來的好處就是,在最初的更新中,算法結(jié)合了每步逼近算法的優(yōu)點,更新較快,并且方差很小,有助于參數(shù)較快地收斂到最優(yōu)值附近,同時將方差降低到一個很小的范圍內(nèi);在隨后的更新中,算法更新頻率降低,經(jīng)過很多次的狀態(tài)轉(zhuǎn)移參數(shù)才會更新一次,一次更新中獲得的信息量比較多,有助于估值準確性的提高,提高了收斂精度,同時降低了計算量。并且在較弱的假設(shè)下,從理論上證明了算法的收斂性。 無線多媒體通信網(wǎng)絡問題是近期的研究熱點,目前仍存在大量瓶頸問題。本文在上述理論研究的基礎(chǔ)上,研究OVSF-CDMA系統(tǒng)中動態(tài)編碼分配的呼叫容許接入控制問題和有QoS指標約束下的CDMA系統(tǒng)的呼叫容許接入控制問題的建模和優(yōu)化。通過將問題建模為Markov決策過程,提出一種在線學習估計策略梯度,隨機逼近優(yōu)化容許接入策略的在線算法,利用雙時間尺度的技術(shù)降低計算復雜度,提高收斂速度。并且這個算法不依賴于系統(tǒng)的具體參數(shù),具有較強的適應性,可以適用于復雜應用環(huán)境中的無線多媒體通信網(wǎng)的呼叫容許接入控制的在線優(yōu)化,具有較高的應用價值。
【學位單位】：中國科學技術(shù)大學
【學位級別】：博士
【學位年份】：2009
【中圖分類】：N941.4
【部分圖文】：

{13!基于性能勢和實現(xiàn)因子可以在線估計的特性，給出了性能勢，實現(xiàn)因子，性能梯度的幾種估計方法。對于基于靈敏度觀點的優(yōu)化，我們可以引用文獻{ls]中的圖1一1來概括。由圖1一1可見，強化學習為性能勢的在線估計提供了方法，性能勢為兩個靈敏度公式莫定了基礎(chǔ)，基于性能差公式可以得到Markov決策過程的策略迭代算法以及在線的策略迭代算法，還可以得到隨機控制中的最優(yōu)性方程與在線優(yōu)化算法�；谛阅軐�(shù)公式，可以得到策略梯度估計方法以及攝動分析的一些結(jié)果，進而設(shè)計在線的梯度優(yōu)化算法。圖1一1基于靈敏度觀點的優(yōu)化思路1.3神經(jīng)元動態(tài)規(guī)劃目前比較成熟的Markov系統(tǒng)的優(yōu)化控制方法是傳統(tǒng)的動態(tài)規(guī)劃方法。這個方法首先利用Bellman方程建立最優(yōu)性方程，再通過迭代計算求出最優(yōu)性能{7}。尋優(yōu)的過程依賴狀態(tài)空間中每個狀態(tài)的報酬函數(shù)和行動值函數(shù)，以及Markov系統(tǒng)的精確模型。而在某些實際問題中，系統(tǒng)的狀態(tài)空間往往非常大，并且系統(tǒng)運行機制也往往很難精確描述

SuboPtimal tWOtime一sCals圖5一1雙時間尺度策略梯度CAC算法與傳統(tǒng)的四個算法的出較可以看出這個算法得到的值最接近最優(yōu)算法得到的值。圖5一2演示了再生環(huán)梯度逼近算法、每步梯度逼近算法和雙時間尺度梯度逼近算法的區(qū)別，可以看出我們的算法能夠達到更快的收斂速度，更小的樣本方差。為了比較三種梯度逼近算法的計算復雜度，我們計算每個算法的迭代次數(shù)，考慮到對于再生環(huán)梯度逼近算法，每條樣本軌道上的再生環(huán)個數(shù)并不相同，所以我們仿真30個樣本軌道，選擇迭代次數(shù)的平均值，作為比較的依據(jù)。每步梯度逼近算法、再生環(huán)梯度逼近算法和雙時間尺度梯度逼近算法的迭代次數(shù)分別是20，000，000、375
【參考文獻】

相關(guān)期刊論文 前1條

1 ;Performance Potential-based Neuro-dynamic Programming for SMDPs[J];自動化學報;2005年04期

相關(guān)博士學位論文 前1條

1 李衍杰;擴展Markov決策過程的性能靈敏度分析與優(yōu)化[D];中國科學技術(shù)大學;2006年

本文編號：2866380