基于NSGA-II算法的多目标参数优化的主动队列管理新策略

-1-基于NSGA-II算法的多目标参数优化的主动队列管理新策略陆锦军1,2李志权2王执铨1(1南京理工大学自动化学院南京210094;2南通职业大学现代教育技术中心南通226007)摘要本文推导了基于流体流理论的网络简化模型，基于该模型将NSGA-II与PGA相结合的优化算法应用于PID控制器参数优化，提出了一种多目标PID优化设计方法——在满足系统鲁棒性的前提下，以超调量、上升时间和调整时间最小作为多目标优化的子目标，并将NSGA-Ⅱ与PGA相结合对其求解。该算法求得的Pareto最优解分布均匀，收敛性和鲁棒性好，根据网络主动队列管理控制系统的要求在Pareto解集中选择最终的满意解。仿真结果表明，在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。关键词主动队列管理网络拥塞PID控制NSGA-II中图分类号TP273文献标志码A国家标准学科分类代码120.30ANewTacticsofMulti-ObjectParameterOptimizationforActiveQueueManagementBasedonNSGA-IIAlgorithmLUJin-jun1,2LIZhi-quan2WANGZhi-quan1（1SchoolofAutomation,NanjingUniversityofScienceandTechnology,Nanjing210094,China;2CenterofEducationandTechnology,NantongVocationalCollege,Nantong226007,China）Abstract:Simplifiednetworkmodelbasedonfluidflowtheoryisderivedinthispaper,andbasedonthismodel,animprovedalgorithm,i.e.optimizationalgorithmcombiningNSGA-IIandPGAisappliedtooptimizationofPIDcontrollerparameters.Inthefollowing,amulti-objectPIDoptimizationdesignmethodisputforward,i.e.whenrobustnessofthesystemissatisfied,theminimumofovershoot,risetimeandadjustingtimeistakenasthesub-objectofmulti-objectoptimization,andsolveitbycombiningNSGA-IIandPGA.TheParetooptimalsolutiongotbythisalgorithmdistributeseven,andhasgoodconvergenceandrobustness.AccordingtorequestofnetworkedActiveQueueManagementcontrolsystem,asatisfyingsolutionischoseninParetosolutionset.Thesimulationexperimentalresultsshowthatunderthetwoconditionsoflargetimedelayandsuddenbusinessflow,thedynamicstateandsteadystateperformancesoftheproposedalgorithmareobviouslysuperiortothoseoftheexistingRED,GA,SPSOandQDPSOalgorithms.Keywords:activequeuemanagement;networkcongestion;PIDcontrol;NSGA-II1引言IP网络拥塞控制是人们一直着力解决但未能很好解决的问题，相继产生了不少有影响力的算法，如RED[1]、ARED[2]、SRED[3]、BLUE[4]等，同时也出现了许多基于网络流量的控制模型，但较具影响力的是VMisra等人于2000年基于流体流理论提出的网络模型[5]，该模型较为恰当地描述了TCP传输流的行为[6]，为研究人员广为采用，根据该模型，产生了PID[7]等主动队列管理算法和相应的PID参数优化算法[8-11]，增强了对队列长度的控制能力，但这些方法难以兼顾系统对快速性、稳定性和鲁棒性的要求。针对这些缺陷，本文收稿日期：基金项目：国家自然科学基金（60474076）,江苏省“六大人才高峰”项目（07-E-013）,南通市应用研究计划项目（K2007004）-2-提出了一种多目标PID设计方法——在满足系统鲁棒性的前提下，以系统输出的超调量、上升时问和调整时间作为多目标优化的子目标，并将带精英策略的快速非支配排序遗传算法(NSGA-II)[12]和并行遗传算法(PGA)[13]相结合，提出基于伪并行NSGA-II算法的多目标鲁棒PID优化设计方法，并且将得到的优化PID目标参数应用于网络主动队列管理系统中。仿真结果表明,在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。2TCP/AQM简化模型及其AQM控制VMisra等人在分析网络连续数据流和随机微分方程的基础上，建立了TCP的动态模型[6]，用如下一组非线性微分方程来描述。))(())((2))(()()(1tRtptRtRtRtWtWtRW（1）)()()()(tCtWtRtNq式中：W为预期的TCP拥塞窗口的大小（包）；q为预期的队列长度（包）；tR为往返时间；pTtCtqtR（秒），pT为传输延时（秒）；C为链路容量（包/秒）；N为激活TCP连接数；P为分组的丢弃概率，P的取值范围为[0，1]；q和W满足WWqq,0,,0。其中，q、W分别表示缓存容量和最大窗口尺寸。式（1）中第一个方程描述的是TCP的窗口控制动态特性，其中式右端的1/R项模拟了窗口的加性增加，W/2项对应于包丢失概率p的窗口大小乘性降低。第二个方程描述的是瓶颈队列长度，它等于包到达率NW/R和链路容量C之间的差值。分析稳态工作点各参数之间的关系，主要研究低频性能，在W1时，1sRoe，忽略高频性能,加入AQM控制，最终可得到如图1所示的基于简化模型AQM控制系统框图。图1基于简化模型的AQM控制系统框图令Gp(s)为AQM系统简化模型，即Gp(S)=)1)(1(210sTsTKesR（2）其中302()4RCkN，T1=0R，2022RCTN。若链路容量C、往返时间0R和连接数N分别为105packet/s、0.03s和30，q(t)AQM控制)1)(1(210sTsTKesRp(t)e(t)q0－-3-则Gp(S)=)15.1)(103.0(107.503.06sses（3）PID控制是一种具有负反馈的闭环控制系统，能够较好的根据系统实时状态快速作出控制反应，故不妨假设图5中的AQM控制器仍具有PID形式，它引入微分环节来增强系统的快速响应的能力，克服其他控制算法响应迟缓的弱点，根据偏差的变化趋势调节，具有超前作用，对系统的时滞具有补偿能力。即Gc（S）=Kp+sKi+Kds（4）其中Kp、Ki、Kp分别为PID控制器的比例、积分、微分增益系数，其离散的表达形式为TkekeKjeKkeKkpdkjip)]1()([)()()(0（5）其中)(,)()(0kqqkqke是第k时刻的队列长度采样值，q0为期望队列长度，p(k)为k时刻的丢包概率。其增量形式为)2()1(21)(1)(keTTkeTTkeTTTTKkpdddip（6）其中ipiKKT，pddKKT，T=0.00625s)()1()(kpkpkp（7）分组丢包概率1)(11)(0)(0)(0)(kckckckckp（8）3多目标鲁棒PID设计与Pareto解集3.1多目标鲁棒PID优化模型为了兼顾系统对快速性、稳定性和鲁棒性的要求，这里以系统输出的超调量、上升时间和调节时间作为优化目标，以频域鲁棒性为约束(当然也可以把它作为目标函数处理)，建立如下的多目标优化模型:minmin),,min(minPPGGttfMMsr（9）式中：为超调量；rt为上升时间(由终值2％第一次上升到终值98%的时间)；st为调整时间(误差带取2％)；GM、PM为幅值裕度和相角裕度，下标min为约束下限。3.2Pareto解集多目标优化问题可以用函数f来定义，该函数把决策向量X映射到目标向量Y，其数学描述为：-4-TrTXgXgXgXgXfXfXfXfY))(),...,(),(()())(,...),(),(()(min21n21（10）式中：X=(21x,x,…,mx)由m个决策变量ix构成，Y由n个需同时优化的目标)X(fi构成；约束g(X)由r个等式、不等式gi(X)≤0构成。多目标优化问题(2)中的各目标往往处于冲突状态，因而不存在使所有目标同时达到最优的绝对最优解，只能获得满意解即Pareto解。对于极小值多目标优化问题)(minXf，Pareto最优解定义为：在设计变量的可行域内，对于变量X，当且仅当不存在其他变量*X，在不违背约束的条件下满足)X(f)X(f*ii，至少存在一个i使得)X(f)X(f*ii成立，则称变量*X为非支配解，即Pareto最优解。Pareto最优解不是唯一的，多个Pareto最优解构成Pareto最优解集(也称Pareto前沿或非支配解集)。4基于伪并行NSGA-II算法的PID优化4.1NSGA-Ⅱ算法[12]NSGA是由Srinivas和Deb于20世纪90年代初期提出，它的高效性在于运用一个非支配分类程序，使多目标简化至一个适应度函数的方式。该方法能解决任意数目的目标问题，并且能够求最大和最小的问题。Deb于2002年对NSGA进行了改进，提出了NSGA-II，一种快速的非劣性排序方法：定义了拥挤距离估计某个点周围的解密度取代适应值共享。NSGA-II有效地克服了NSGA的三大缺陷：计算复杂性从O(mN3)降至O(mN2)，具备最优保留机制及无需确定一个共享参数。进一步提高了计算效率和算法的鲁棒性。该算法得到的非劣解在目标空间分布均匀，收敛性和鲁棒性好，已成为进化多目标优化领域的基准算法之一。其步骤如下：(1)快速非支配排序。在选择运算之前，根据个体的非劣解水平对种群分级。具体方法为：将当前种群中所有非劣解个体划分为同一等级，令其等级为l；然后将这些个体从种群中移出，在剩余个体中找出新的非劣解，再令其等级为2；重复上述过程，直至种群中所有个体都被设定相应的等级。(2)虚拟适应度。为了保持个体的多样性、防止个体在局部堆积，NSGA-II算法首次提出了虚拟适应度的概念。它指目标空间上的每一点与同级相邻2点之间的局部拥挤距离。例如，图1中目标空间第i点的拥挤距离等于它在同一等级相邻的点i-1和i+1组成的矩形2个边长之和。这一方法可自动调整小生境，使计算结果在目标空间比较均匀地散布，具有较好的鲁棒性。图6局部拥挤距离示意图具体实现时，首先解码染色体，然后计算每个个体相应的目标函数值，再根据目标函数值进行非劣分层，计算每层个体的虚拟适应度，计算步骤为：①对同层的个体初始化距离：L[i]d=0；②对同层的个体按第m个目标函数值升序排列：),(mLsortL；③使得排序边缘上的个体具有选择优势，给定一个大数L[0]d=L[l]d=M；④对排序中间的个体，求拥挤距离：)]1[]1[(][][mmddiLiLiLiL(miL][为第i