論基于NSGA-II算法的目標(biāo)參數(shù)優(yōu)化的主動隊列管理新策略.doc

基于NSGA-II算法的多目標(biāo)參數(shù)優(yōu)化的主動隊列管理新策略收稿日期：基金項目：國家自然科學(xué)基金（60474076）, 江蘇省“六大人才高峰”項目（07-E-013）,南通市應(yīng)用研究計劃項目（K2007004）陸錦軍1,2李志權(quán)2王執(zhí)銓1 (1南京理工大學(xué)自動化學(xué)院 南京 210094;2南通職業(yè)大學(xué)現(xiàn)代教育技術(shù)中心 南通 226007)摘 要 本文推導(dǎo)了基于流體流理論的網(wǎng)絡(luò)簡化模型，基于該模型將NSGA-II與PGA相結(jié)合的優(yōu)化算法應(yīng)用于PID控制器參數(shù)優(yōu)化，提出了一種多目標(biāo)PID優(yōu)化設(shè)計方法在滿足系統(tǒng)魯棒性的前提下，以超調(diào)量、上升時間和調(diào)整時間最小作為多目標(biāo)優(yōu)化的子目標(biāo)，并將NSGA-與PGA相結(jié)合對其求解。該算法求得的Pareto最優(yōu)解分布均勻，收斂性和魯棒性好，根據(jù)網(wǎng)絡(luò)主動隊列管理控制系統(tǒng)的要求在Pareto解集中選擇最終的滿意解。仿真結(jié)果表明，在大時滯和突發(fā)業(yè)務(wù)流的沖擊兩種情況下,該方法設(shè)計的控制器的動靜態(tài)性能優(yōu)于RED、GA、SPSO、QDPSO算法的優(yōu)化結(jié)果。關(guān)鍵詞 主動隊列管理 網(wǎng)絡(luò)擁塞 PID控制 NSGA-II中圖分類號 TP273 文獻(xiàn)標(biāo)志碼 A 國家標(biāo)準(zhǔn)學(xué)科分類代碼 120.30A New Tactics of Multi-Object Parameter Optimization for Active Queue Management Based on NSGA-II AlgorithmLU Jin-jun1,2 LI Zhi-quan2 WANG Zhi-quan1 （1School of Automation, Nanjing University of Science and Technology,Nanjing210094, China;2 Center of Education and Technology, Nantong Vocational College, Nantong 226007,China）Abstract: Simplified network model based on fluid flow theory is derived in this paper, and based on this model, an improved algorithm, i.e. optimization algorithm combining NSGA-II and PGA is applied to optimization of PID controller parameters. In the following, a multi-object PID optimization design method is put forward, i.e. when robustness of the system is satisfied, the minimum of overshoot, rise time and adjusting time is taken as the sub-object of multi-object optimization, and solve it by combining NSGA-II and PGA. The Pareto optimal solution got by this algorithm distributes even, and has good convergence and robustness. According to request of networked Active Queue Management control system, a satisfying solution is chosen in Pareto solution set. The simulation experimental results show that under the two conditions of large time delay and sudden business flow, the dynamic state and steady state performances of the proposed algorithm are obviously superior to those of the existing RED, GA, SPSO and QDPSO algorithms.Key words: active queue management; network congestion; PID control; NSGA-II1 引言IP網(wǎng)絡(luò)擁塞控制是人們一直著力解決但未能很好解決的問題，相繼產(chǎn)生了不少有影響力的算法，如RED1、ARED2、SRED3、BLUE4等，同時也出現(xiàn)了許多基于網(wǎng)絡(luò)流量的控制模型，但較具影響力的是V Misra等人于2000年基于流體流理論提出的網(wǎng)絡(luò)模型5，該模型較為恰當(dāng)?shù)孛枋隽薚CP傳輸流的行為6，為研究人員廣為采用，根據(jù)該模型，產(chǎn)生了PID7等主動隊列管理算法和相應(yīng)的PID參數(shù)優(yōu)化算法8-11，增強(qiáng)了對隊列長度的控制能力，但這些方法難以兼顧系統(tǒng)對快速性、穩(wěn)定性和魯棒性的要求。針對這些缺陷，本文提出了一種多目標(biāo)PID設(shè)計方法在滿足系統(tǒng)魯棒性的前提下，以系統(tǒng)輸出的超調(diào)量、上升時問和調(diào)整時間作為多目標(biāo)優(yōu)化的子目標(biāo)，并將帶精英策略的快速非支配排序遺傳算法(NSGA-II)12和并行遺傳算法(PGA)13相結(jié)合，提出基于偽并行NSGA-II算法的多目標(biāo)魯棒PID優(yōu)化設(shè)計方法，并且將得到的優(yōu)化PID目標(biāo)參數(shù)應(yīng)用于網(wǎng)絡(luò)主動隊列管理系統(tǒng)中。仿真結(jié)果表明,在大時滯和突發(fā)業(yè)務(wù)流的沖擊兩種情況下,該方法設(shè)計的控制器的動靜態(tài)性能優(yōu)于RED、GA、SPSO、QDPSO算法的優(yōu)化結(jié)果。2 TCP/AQM簡化模型及其AQM控制V Misra等人在分析網(wǎng)絡(luò)連續(xù)數(shù)據(jù)流和隨機(jī)微分方程的基礎(chǔ)上，建立了TCP的動態(tài)模型6，用如下一組非線性微分方程來描述。 （1） 式中：W為預(yù)期的TCP擁塞窗口的大?。ò籷為預(yù)期的隊列長度（包）；為往返時間；（秒），為傳輸延時（秒）；C為鏈路容量（包/秒）；N為激活TCP連接數(shù)；P為分組的丟棄概率，P的取值范圍為0，1；q和W滿足。其中，、分別表示緩存容量和最大窗口尺寸。式（1）中第一個方程描述的是TCP的窗口控制動態(tài)特性，其中式右端的1/R項模擬了窗口的加性增加，W/2項對應(yīng)于包丟失概率p的窗口大小乘性降低。第二個方程描述的是瓶頸隊列長度，它等于包到達(dá)率NW/R和鏈路容量C之間的差值。分析穩(wěn)態(tài)工作點各參數(shù)之間的關(guān)系，主要研究低頻性能，在W1時，忽略高頻性能,加入AQM控制，最終可得到如圖1所示的基于簡化模型AQM控制系統(tǒng)框圖。q(t)AQM控制p(t)e(t)q0圖1 基于簡化模型的AQM控制系統(tǒng)框圖令Gp(s)為AQM系統(tǒng)簡化模型，即Gp(S)= （2）其中，T1=，。若鏈路容量C、往返時間和連接數(shù)N分別為105packet/s、0.03s和30，則Gp(S)= （3）PID控制是一種具有負(fù)反饋的閉環(huán)控制系統(tǒng)，能夠較好的根據(jù)系統(tǒng)實時狀態(tài)快速作出控制反應(yīng)，故不妨假設(shè)圖5中的AQM控制器仍具有PID形式，它引入微分環(huán)節(jié)來增強(qiáng)系統(tǒng)的快速響應(yīng)的能力，克服其他控制算法響應(yīng)遲緩的弱點，根據(jù)偏差的變化趨勢調(diào)節(jié)，具有超前作用，對系統(tǒng)的時滯具有補(bǔ)償能力。即Gc（S）=Kp+Kds （4）其中Kp、Ki、Kp分別為PID控制器的比例、積分、微分增益系數(shù)，其離散的表達(dá)形式為（5）其中是第k時刻的隊列長度采樣值，q0為期望隊列長度，p(k)為k時刻的丟包概率。其增量形式為（6）其中，T=0.00625s（7）分組丟包概率 （8）3 多目標(biāo)魯棒PID設(shè)計與Pareto解集3.1 多目標(biāo)魯棒PID優(yōu)化模型 為了兼顧系統(tǒng)對快速性、穩(wěn)定性和魯棒性的要求，這里以系統(tǒng)輸出的超調(diào)量、上升時間和調(diào)節(jié)時間作為優(yōu)化目標(biāo)，以頻域魯棒性為約束(當(dāng)然也可以把它作為目標(biāo)函數(shù)處理)，建立如下的多目標(biāo)優(yōu)化模型: （9）式中：為超調(diào)量；為上升時間(由終值2第一次上升到終值98%的時間)；為調(diào)整時間(誤差帶取2)；GM、PM為幅值裕度和相角裕度，下標(biāo)min為約束下限。3.2 Pareto解集 多目標(biāo)優(yōu)化問題可以用函數(shù)來定義，該函數(shù)把決策向量映射到目標(biāo)向量，其數(shù)學(xué)描述為： （10）式中：X=(,)由m個決策變量構(gòu)成，由n個需同時優(yōu)化的目標(biāo)構(gòu)成；約束g(X)由r個等式、不等式gi(X)0構(gòu)成。多目標(biāo)優(yōu)化問題(2)中的各目標(biāo)往往處于沖突狀態(tài)，因而不存在使所有目標(biāo)同時達(dá)到最優(yōu)的絕對最優(yōu)解，只能獲得滿意解即Pareto解。對于極小值多目標(biāo)優(yōu)化問題，Pareto最優(yōu)解定義為：在設(shè)計變量的可行域內(nèi)，對于變量X，當(dāng)且僅當(dāng)不存在其他變量，在不違背約束的條件下滿足，至少存在一個i使得成立，則稱變量為非支配解，即Pareto最優(yōu)解。Pareto最優(yōu)解不是唯一的，多個Pareto最優(yōu)解構(gòu)成Pareto最優(yōu)解集(也稱Pareto前沿或非支配解集)。4 基于偽并行NSGA-II算法的PID優(yōu)化4.1 NSGA-算法12 NSGA是由Srinivas和Deb于20世紀(jì)90年代初期提出，它的高效性在于運(yùn)用一個非支配分類程序，使多目標(biāo)簡化至一個適應(yīng)度函數(shù)的方式。該方法能解決任意數(shù)目的目標(biāo)問題，并且能夠求最大和最小的問題。Deb于2002年對NSGA進(jìn)行了改進(jìn)，提出了NSGA-II，一種快速的非劣性排序方法：定義了擁擠距離估計某個點周圍的解密度取代適應(yīng)值共享。NSGA-II有效地克服了NSGA的三大缺陷：計算復(fù)雜性從O(mN3)降至O(mN2)，具備最優(yōu)保留機(jī)制及無需確定一個共享參數(shù)。進(jìn)一步提高了計算效率和算法的魯棒性。該算法得到的非劣解在目標(biāo)空間分布均勻，收斂性和魯棒性好，已成為進(jìn)化多目標(biāo)優(yōu)化領(lǐng)域的基準(zhǔn)算法之一。其步驟如下： (1) 快速非支配排序。在選擇運(yùn)算之前，根據(jù)個體的非劣解水平對種群分級。具體方法為：將當(dāng)前種群中所有非劣解個體劃分為同一等級，令其等級為l；然后將這些個體從種群中移出，在剩余個體中找出新的非劣解，再令其等級為2；重復(fù)上述過程，直至種群中所有個體都被設(shè)定相應(yīng)的等級。(2) 虛擬適應(yīng)度。為了保持個體的多樣性、防止個體在局部堆積，NSGA-II算法首次提出了虛擬適應(yīng)度的概念。它指目標(biāo)空間上的每一點與同級相鄰2點之間的局部擁擠距離。例如，圖1中目標(biāo)空間第i點的擁擠距離等于它在同一等級相鄰的點i-1和i+1組成的矩形2個邊長之和。這一方法可自動調(diào)整小生境，使計算結(jié)果在目標(biāo)空間比較均勻地散布，具有較好的魯棒性。圖6 局部擁擠距離示意圖 具體實現(xiàn)時，首先解碼染色體，然后計算每個個體相應(yīng)的目標(biāo)函數(shù)值，再根據(jù)目標(biāo)函數(shù)值進(jìn)行非劣分層，計算每層個體的虛擬適應(yīng)度，計算步驟為：對同層的個體初始化距離：Lid =0；對同層的個體按第m個目標(biāo)函數(shù)值升序排列：；使得排序邊緣上的個體具有選擇優(yōu)勢，給定一個大數(shù)L0d=Lld=M；對排序中間的個體，求擁擠距離： (為第i個體的第m個目標(biāo)函數(shù)值)；對不同的目標(biāo)函數(shù)，重復(fù)步驟。 (3) 選擇運(yùn)算。選擇過程使優(yōu)化朝Pareto最優(yōu)解的方向進(jìn)行并使解均勻散布。經(jīng)過排序和擁擠距離計算，群體中的每個個體i都得到2個屬性：非支配序irank。和擁擠距離。id當(dāng)irankjd時，i個體優(yōu)于j個體。上式的意義為：如果2個個體的非支配排序不同，取序號低的個體(分級排序時，先被分離出來的個體)；如果2個個體在同一級，取周圍較不擁擠的個體。 (4) 精英策略。精英策略即保留父代中的優(yōu)良個體直接進(jìn)入子代。采用的方法是：將父代Pt和子代Qt全部個體合成為一個種群，Rt的個體數(shù)為2N；將種群Rt快速非支配排序并計算每一個體局部擁擠距離，依據(jù)等級的高低逐一選取個體，直到個體數(shù)量達(dá)到N就形成了新的父代種群Pt+1；在基礎(chǔ)上開始新一輪的選擇、交叉和變異，形成新的子代種群Qt+1。4.2 并行遺傳算法13并行遺傳算法與常規(guī)遺傳算法的主要差別在于：它存在同時進(jìn)化的多個種群，對多個種群輪流進(jìn)行遺傳操作，這樣能夠提高算法的性能和效率，有效地克服單種群算法的早熟現(xiàn)象?！斑w移策略”是并行遺傳算法引入了一個新的算子，它是指在進(jìn)化過程中子群體間交換個體的過程，遷移可以加快較好個體在群體中的傳播，提高收斂速度和解的精度，與單種群相比可用較小的計算量達(dá)到同等性能，即使是在單一處理器上以串行(偽并行)的方式進(jìn)行并行計算也能產(chǎn)生較好的效果。遷移策略的主要控制參數(shù)有：子群體的連接拓?fù)?、遷移率、遷移間隔、遷移選擇和替換。具體描述見文獻(xiàn)13。4.3 基于偽并行NSGA-II算法的PID優(yōu)化設(shè)計 本文將NSGA-II算法與并行遺傳算法結(jié)合，在單一處理器上以串行(偽并行)的方式進(jìn)行并行計算，其流程圖如圖2所示?；趥尾⑿蠳SGA-II算法的多目標(biāo)魯棒PID優(yōu)化步驟為： (1) 編碼：、（分別為比例、積分和微分系數(shù))采用實數(shù)編碼方式，取值的上、下限視具體工程應(yīng)用背景確定。 (2) 初始種群的產(chǎn)生。取5個子種群，規(guī)模依次為50、30、30、40、50，隨機(jī)產(chǎn)生子種群的個體。 (3) 遺傳操作。每個子種群采用NSGA-II算法進(jìn)行遺傳操作，NSGA-II參數(shù)設(shè)置為：圖7偽并行NSGA-II算法流程圖 選擇：聯(lián)賽選擇，選擇規(guī)模為2； 重組：實值重組，重組率為0.9。為了提高算法的搜索能力，5個子種群采用不同的方式，依次為：離散重組、中間重組、線性重組、離散重組、中間重組； 變異。均勻變異，變異率為0.1。各子種群的變異步長依次為：0.1、0.03、0.01、0.003、0.001； (4) 遷移策略。子群體問采用網(wǎng)絡(luò)拓?fù)?，按照排列比例來選擇遷移個體，每運(yùn)行8代遷移1次，遷移率為0.1。(5) 迭代次數(shù)加1，返回步驟(3)，直至達(dá)到最大迭代次數(shù)為止，大種群中的所有非支配解即構(gòu)成Pareto最優(yōu)解集。最大迭代數(shù)設(shè)為50。5 算例分析 我們以前述的主動隊列管理系統(tǒng)，即式(10)進(jìn)行仿真。偽并行NSGA-II算法的參數(shù)設(shè)置如上文所述，式(1)中Gmin取2，Pmin取60，、的取值范圍為：1，3、1，2、1，1.5。 (1) 優(yōu)化結(jié)果本文的最大迭代次數(shù)設(shè)為50，實際運(yùn)行到30代時，Pareto最優(yōu)解集已基本保持不變，收斂速度很快。表1列出了部分具有代表性的Pareto最優(yōu)解。由表l可知本文方法求得的Pareto解集可滿足系統(tǒng)對快速性、穩(wěn)定性和魯棒性不同偏好的需求當(dāng)系統(tǒng)要求超調(diào)量很低時，可選擇第1組解；當(dāng)系統(tǒng)要求上升時間較小時，可選擇第8組解；在各種偏好下，其他性能指標(biāo)也能很好地兼顧。當(dāng)系統(tǒng)沒有偏好時即無偏最優(yōu)解在第4組解。這為快速性、穩(wěn)定性與魯棒性的權(quán)衡分析提供了有效的工具，解決了現(xiàn)有PID優(yōu)化方法難以兼顧的問題，避免了對多個指標(biāo)進(jìn)行加權(quán)求解的盲目性。表1 一組Pareto最優(yōu)解(的誤差帶取2)序號/12.18470.91401.49540.010.703.432.4071.0122.19901.04191.49980.750.753.062.4971.7632.05471.04161.46830.870.693.162.4069.0842.12391.12121.47511.120.722.882.4668.9252.25580.97881.49512.110.683.292.3868.2762.30180.95451.49873.300.663.332.3567.3972.20651.15831.33323.610.742.142.6063.1982.44650.99641.50036.620.633.902.2963.20 (2) 與原有優(yōu)化設(shè)計方法的比較 表2列出了GA、SPSO、QDPSO 、NSGA-II等設(shè)計方法的優(yōu)化結(jié)果，不難發(fā)現(xiàn)，本文算法所得的Pareto解集中無偏最優(yōu)解（即第4組解）比其更優(yōu)，GA，SPSO，QDPSO等原有優(yōu)化設(shè)計方法每次運(yùn)行只能得到一個解，而本文的設(shè)計方法一次運(yùn)行能得到多個Pareto最優(yōu)解，便于決策者根據(jù)實際系統(tǒng)的要求進(jìn)行選擇。表2 不同設(shè)計方法的比較(ts的誤差帶取2)優(yōu)化 算法/GA2.663.143.762.8754.20SPSO2.482.953.502.7554.32QDPSO2.382.843.352.7055.74NSGA-II2.4668.926 仿真實驗運(yùn)用NS2網(wǎng)絡(luò)仿真器驗證本算法性能。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖8所示，仿真實驗結(jié)果與RED、PID(GA)、PID(SPSO), PID(QDPSO) 等算法進(jìn)行比較。12in-1nAB10Mbps15Mbps5ms5msd ms45Mbpsci圖8 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)節(jié)點A和節(jié)點B之間的瓶頸鏈路容量15Mbps，延時5ms。n個持久性的FTP業(yè)務(wù)源與節(jié)點A之間的鏈路容量均為10Mbps，通常情況之下延時5ms，節(jié)點B和節(jié)點C之間的時延為dms。RED高低門限值分別為100packets和200packets， PID的隊列長度的期望值為150packets；各節(jié)點緩存大小均為300packets。實驗1：考察大時滯對算法性能的影響。n取60，時延d取220ms，所有FTP業(yè)務(wù)源均在0時刻啟動。瓶頸鏈路的容量為15Mbps，RTT時間約為0.6s，主要包括傳播時延、排隊時延等。采用前述方法，實驗仿真結(jié)果如圖9（a）、（b）、（c）、（d）、（e）所示。圖9(a) RED隊列長度（d=220ms） 圖9(b) PID（GA）隊列長度（d=220ms）圖9(c) PID（SPSO）隊列長度（d=220ms） 圖9(d) PID（QDPSO）隊列長度（d=220ms）圖9(e) PID（NSGA-II）隊列長度（d=220ms）從實驗結(jié)果可以看出，RED在大時滯中出現(xiàn)了持續(xù)震蕩，相比之下，基于GA、PSO、QDPSO、NSGA-II優(yōu)化的PID算法響應(yīng)速度較快，但基于NSGA-II 的優(yōu)化算法的響應(yīng)速度最快，動靜態(tài)綜合性能最好。各算法性能比較如表3所示，其中為超調(diào)量，ts 為調(diào)節(jié)時間，ess為穩(wěn)態(tài)誤差。表3 大時滯條件下各算法性能比較性能指標(biāo)算法ts/sess/packetsRED趨向系統(tǒng)不穩(wěn)定，不求ess值PID(GA)763PID(PSO)552PID(QDPSO)442PID(NSGA-II)332實驗2：考察突發(fā)業(yè)務(wù)流的沖擊對算法的影響，n取70，時延d取220ms，有60個FTP業(yè)務(wù)源均在0s時刻啟動，還有10個在15s時刻啟動，有60個FTP業(yè)務(wù)源均在0時刻啟動，還有10個在15s時刻啟動，發(fā)送100k字節(jié)后停止。仿真結(jié)果如圖10（a）、（b）、（c）、（d）、（e）所示。由圖看出，當(dāng)引入突發(fā)業(yè)務(wù)流時，RED、PI影響最大，隊列長度有所上升，而這些突發(fā)業(yè)務(wù)量終止時，其隊列有所下降，出現(xiàn)較大振蕩，相比之下，基于GA、PSO、QDPSO、NSGA-II的PID算法體現(xiàn)了一定的抗干擾能力，但基于NSGA-II算法抗干擾能力最強(qiáng)，性能最好。各算法性能比較如表4所示。 表4 突發(fā)業(yè)務(wù)流的沖擊對各算法性能影響比較性能指標(biāo)算法ts/sess/packetsRED趨向40系統(tǒng)不穩(wěn)定，不求ess值PID(GA)754PID(PSO)543PID(QDPSO)442PID(NSGA-II)332圖10(a) RED隊列長度（n增長至70） 圖10 (b) PID（GA）隊列長度（n增長至70）圖10 (c) PID（SPSO）隊列長度（n增長至70） 圖10 (d) PID（QDPSO）隊列長度（n增長至70） 圖10 (e) PID（NSGA-II）隊列長度（n增長至70）7 結(jié)論本文基于網(wǎng)絡(luò)簡化模型將PID控制器應(yīng)用于網(wǎng)絡(luò)AQM控制系統(tǒng)中，將NSGA-II與PGA相結(jié)合的優(yōu)化算法應(yīng)用于PID控制器參數(shù)進(jìn)行組合優(yōu)化。仿真結(jié)果表明，該 PID控制算法具有較好的綜合性能，比RED、基于GA優(yōu)化的PID控制算法、基于標(biāo)準(zhǔn)PSO優(yōu)化的PID控制算法、基于QDPSO優(yōu)化的PID控制算法更合適于AQM控制，性能表現(xiàn)為平均隊列長度更趨于期望值；超調(diào)量更??；調(diào)節(jié)時間更短；隊列長度的抖動更小；自適應(yīng)能力更強(qiáng)。參考文獻(xiàn)1 Christiansen M, Jeffay K, Ott D, Smith F D. Turing RED for Web Traffic J. ACM Computer Communication Review, 2000,30(4):139-150.2 Feng W, Kandlur D, Saha D, Shin K.A Self-configuration RED gatewayA. Proceedings of the INFOCOM99C. New York: IEEE Computer Society, 1999. 1320-1328 .3 Ott T j, Lakshman T V, Wong L H. SRED: stabilized REDA . Proceedings of the INFOCOM 99C. New York: IEEE Computer Society, 1999. 1346-1355.4 Athuraliya S, Low S, Li V H, Yin Q H. REM: Active queue managementJ. IEEE Network, 2001,15(3):48-53.5 Misra V, Gong W B, Towsley D. Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED A. Proc. ACM/SIGCOMMC. 2000, 151-160.6 Hollot C V, Misra V, owsley T D, et al. A Control Theoretic Analysis of REDA . Proc. IEEE INFOCOMC. Alaska, USA, 2001, 1510-1519.7 Hollot C V, Misra V, Towsley D, et al. On Designing Improved Controllers for AQM Routers Supporting TCP Flows A. Proc. IEEE INFOCOMC. Alaska, USA, 2001, 1726-1734.8 WU T B,LIU ZR,WANG J N.Optimizing PID parameters based on improved chaos algorithmJ. Journal of Electronic Mea