论基于nsga-ii算法的目标参数优化的主动队列管理新策略

基于NSGA-II算法的多目标参数优化的主动队列管理新策略收稿日期：基金项目：国家自然科学基金（）, 江苏省“六大人才高峰”项目（07-E-013）,南通市应用研究计划项目（K）陆锦军1,2李志权2王执铨1 (1南京理工大学自动化学院 南京 ;2南通职业大学现代教育技术中心 南通 )摘 要 本文推导了基于流体流理论的网络简化模型，基于该模型将NSGA-II与PGA相结合的优化算法应用于PID控制器参数优化，提出了一种多目标PID优化设计方法在满足系统鲁棒性的前提下，以超调量、上升时间和调整时间最小作为多目标优化的子目标，并将NSGA-与PGA相结合对其求解。该算法求得的Pareto最优解分布均匀，收敛性和鲁棒性好，根据网络主动队列管理控制系统的要求在Pareto解集中选择最终的满意解。仿真结果表明，在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。关键词 主动队列管理 网络拥塞 PID控制 NSGA-II中图分类号 TP273 文献标志码 A 国家标准学科分类代码 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,Nanjing, China;2 Center of Education and Technology, Nantong Vocational College, Nantong ,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网络拥塞控制是人们一直着力解决但未能很好解决的问题，相继产生了不少有影响力的算法，如RED1、ARED2、SRED3、BLUE4等，同时也出现了许多基于网络流量的控制模型，但较具影响力的是V Misra等人于2000年基于流体流理论提出的网络模型5，该模型较为恰当地描述了TCP传输流的行为6，为研究人员广为采用，根据该模型，产生了PID7等主动队列管理算法和相应的PID参数优化算法8-11，增强了对队列长度的控制能力，但这些方法难以兼顾系统对快速性、稳定性和鲁棒性的要求。针对这些缺陷，本文提出了一种多目标PID设计方法在满足系统鲁棒性的前提下，以系统输出的超调量、上升时问和调整时间作为多目标优化的子目标，并将带精英策略的快速非支配排序遗传算法(NSGA-II)12和并行遗传算法(PGA)13相结合，提出基于伪并行NSGA-II算法的多目标鲁棒PID优化设计方法，并且将得到的优化PID目标参数应用于网络主动队列管理系统中。仿真结果表明,在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。2 TCP/AQM简化模型及其AQM控制V Misra等人在分析网络连续数据流和随机微分方程的基础上，建立了TCP的动态模型6，用如下一组非线性微分方程来描述。 （1） 式中：W为预期的TCP拥塞窗口的大小（包）；q为预期的队列长度（包）；为往返时间；（秒），为传输延时（秒）；C为链路容量（包/秒）；N为激活TCP连接数；P为分组的丢弃概率，P的取值范围为0，1；q和W满足。其中，、分别表示缓存容量和最大窗口尺寸。式（1）中第一个方程描述的是TCP的窗口控制动态特性，其中式右端的1/R项模拟了窗口的加性增加，W/2项对应于包丢失概率p的窗口大小乘性降低。第二个方程描述的是瓶颈队列长度，它等于包到达率NW/R和链路容量C之间的差值。分析稳态工作点各参数之间的关系，主要研究低频性能，在W1时，忽略高频性能,加入AQM控制，最终可得到如图1所示的基于简化模型AQM控制系统框图。q(t)AQM控制p(t)e(t)q0图1 基于简化模型的AQM控制系统框图令Gp(s)为AQM系统简化模型，即Gp(S)= （2）其中，T1=，。若链路容量C、往返时间和连接数N分别为105packet/s、0.03s和30，则Gp(S)= （3）PID控制是一种具有负反馈的闭环控制系统，能够较好的根据系统实时状态快速作出控制反应，故不妨假设图5中的AQM控制器仍具有PID形式，它引入微分环节来增强系统的快速响应的能力，克服其他控制算法响应迟缓的弱点，根据偏差的变化趋势调节，具有超前作用，对系统的时滞具有补偿能力。即Gc（S）=Kp+Kds （4）其中Kp、Ki、Kp分别为PID控制器的比例、积分、微分增益系数，其离散的表达形式为（5）其中是第k时刻的队列长度采样值，q0为期望队列长度，p(k)为k时刻的丢包概率。其增量形式为（6）其中，T=0.00625s（7）分组丢包概率 （8）3 多目标鲁棒PID设计与Pareto解集3.1 多目标鲁棒PID优化模型 为了兼顾系统对快速性、稳定性和鲁棒性的要求，这里以系统输出的超调量、上升时间和调节时间作为优化目标，以频域鲁棒性为约束(当然也可以把它作为目标函数处理)，建立如下的多目标优化模型: （9）式中：为超调量；为上升时间(由终值2第一次上升到终值98%的时间)；为调整时间(误差带取2)；GM、PM为幅值裕度和相角裕度，下标min为约束下限。3.2 Pareto解集 多目标优化问题可以用函数来定义，该函数把决策向量映射到目标向量，其数学描述为： （10）式中：X=(,)由m个决策变量构成，由n个需同时优化的目标构成；约束g(X)由r个等式、不等式gi(X)0构成。多目标优化问题(2)中的各目标往往处于冲突状态，因而不存在使所有目标同时达到最优的绝对最优解，只能获得满意解即Pareto解。对于极小值多目标优化问题，Pareto最优解定义为：在设计变量的可行域内，对于变量X，当且仅当不存在其他变量，在不违背约束的条件下满足，至少存在一个i使得成立，则称变量为非支配解，即Pareto最优解。Pareto最优解不是唯一的，多个Pareto最优解构成Pareto最优解集(也称Pareto前沿或非支配解集)。4 基于伪并行NSGA-II算法的PID优化4.1 NSGA-算法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 局部拥挤距离示意图 具体实现时，首先解码染色体，然后计算每个个体相应的目标函数值，再根据目标函数值进行非劣分层，计算每层个体的虚拟适应度，计算步骤为：对同层的个体初始化距离：Lid =0；对同层的个体按第m个目标函数值升序排列：；使得排序边缘上的个体具有选择优势，给定一个大数L0d=Lld=M；对排序中间的个体，求拥挤距离： (为第i个体的第m个目标函数值)；对不同的目标函数，重复步骤。 (3) 选择运算。选择过程使优化朝Pareto最优解的方向进行并使解均匀散布。经过排序和拥挤距离计算，群体中的每个个体i都得到2个属性：非支配序irank。和拥挤距离。id当irankjd时，i个体优于j个体。上式的意义为：如果2个个体的非支配排序不同，取序号低的个体(分级排序时，先被分离出来的个体)；如果2个个体在同一级，取周围较不拥挤的个体。 (4) 精英策略。精英策略即保留父代中的优良个体直接进入子代。采用的方法是：将父代Pt和子代Qt全部个体合成为一个种群，Rt的个体数为2N；将种群Rt快速非支配排序并计算每一个体局部拥挤距离，依据等级的高低逐一选取个体，直到个体数量达到N就形成了新的父代种群Pt+1；在基础上开始新一轮的选择、交叉和变异，形成新的子代种群Qt+1。4.2 并行遗传算法13并行遗传算法与常规遗传算法的主要差别在于：它存在同时进化的多个种群，对多个种群轮流进行遗传操作，这样能够提高算法的性能和效率，有效地克服单种群算法的早熟现象。“迁移策略”是并行遗传算法引入了一个新的算子，它是指在进化过程中子群体间交换个体的过程，迁移可以加快较好个体在群体中的传播，提高收敛速度和解的精度，与单种群相比可用较小的计算量达到同等性能，即使是在单一处理器上以串行(伪并行)的方式进行并行计算也能产生较好的效果。迁移策略的主要控制参数有：子群体的连接拓扑、迁移率、迁移间隔、迁移选择和替换。具体描述见文献13。4.3 基于伪并行NSGA-II算法的PID优化设计 本文将NSGA-II算法与并行遗传算法结合，在单一处理器上以串行(伪并行)的方式进行并行计算，其流程图如图2所示。基于伪并行NSGA-II算法的多目标鲁棒PID优化步骤为： (1) 编码：、（分别为比例、积分和微分系数)采用实数编码方式，取值的上、下限视具体工程应用背景确定。 (2) 初始种群的产生。取5个子种群，规模依次为50、30、30、40、50，随机产生子种群的个体。 (3) 遗传操作。每个子种群采用NSGA-II算法进行遗传操作，NSGA-II参数设置为：图7伪并行NSGA-II算法流程图 选择：联赛选择，选择规模为2； 重组：实值重组，重组率为0.9。为了提高算法的搜索能力，5个子种群采用不同的方式，依次为：离散重组、中间重组、线性重组、离散重组、中间重组； 变异。均匀变异，变异率为0.1。各子种群的变异步长依次为：0.1、0.03、0.01、0.003、0.001； (4) 迁移策略。子群体问采用网络拓扑，按照排列比例来选择迁移个体，每运行8代迁移1次，迁移率为0.1。(5) 迭代次数加1，返回步骤(3)，直至达到最大迭代次数为止，大种群中的所有非支配解即构成Pareto最优解集。最大迭代数设为50。5 算例分析 我们以前述的主动队列管理系统，即式(10)进行仿真。伪并行NSGA-II算法的参数设置如上文所述，式(1)中Gmin取2，Pmin取60，、的取值范围为：1，3、1，2、1，1.5。 (1) 优化结果本文的最大迭代次数设为50，实际运行到30代时，Pareto最优解集已基本保持不变，收敛速度很快。表1列出了部分具有代表性的Pareto最优解。由表l可知本文方法求得的Pareto解集可满足系统对快速性、稳定性和鲁棒性不同偏好的需求当系统要求超调量很低时，可选择第1组解；当系统要求上升时间较小时，可选择第8组解；在各种偏好下，其他性能指标也能很好地兼顾。当系统没有偏好时即无偏最优解在第4组解。这为快速性、稳定性与鲁棒性的权衡分析提供了有效的工具，解决了现有PID优化方法难以兼顾的问题，避免了对多个指标进行加权求解的盲目性。表1 一组Pareto最优解(的误差带取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) 与原有优化设计方法的比较 表2列出了GA、SPSO、QDPSO 、NSGA-II等设计方法的优化结果，不难发现，本文算法所得的Pareto解集中无偏最优解（即第4组解）比其更优，GA，SPSO，QDPSO等原有优化设计方法每次运行只能得到一个解，而本文的设计方法一次运行能得到多个Pareto最优解，便于决策者根据实际系统的要求进行选择。表2 不同设计方法的比较(ts的误差带取2)优化 算法/GA2.663.143.762.8754.20SPSO2.482.953.502.7554.32QDPSO2.382.843.352.7055.74NSGA-II2.4668.926 仿真实验运用NS2网络仿真器验证本算法性能。网络拓扑结构如图8所示，仿真实验结果与RED、PID(GA)、PID(SPSO), PID(QDPSO) 等算法进行比较。12in-1nAB10Mbps15Mbps5ms5msd ms45Mbpsci图8 网络拓扑结构节点A和节点B之间的瓶颈链路容量15Mbps，延时5ms。n个持久性的FTP业务源与节点A之间的链路容量均为10Mbps，通常情况之下延时5ms，节点B和节点C之间的时延为dms。RED高低门限值分别为100packets和200packets， PID的队列长度的期望值为150packets；各节点缓存大小均为300packets。实验1：考察大时滞对算法性能的影响。n取60，时延d取220ms，所有FTP业务源均在0时刻启动。瓶颈链路的容量为15Mbps，RTT时间约为0.6s，主要包括传播时延、排队时延等。采用前述方法，实验仿真结果如图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）从实验结果可以看出，RED在大时滞中出现了持续震荡，相比之下，基于GA、PSO、QDPSO、NSGA-II优化的PID算法响应速度较快，但基于NSGA-II 的优化算法的响应速度最快，动静态综合性能最好。各算法性能比较如表3所示，其中为超调量，ts 为调节时间，ess为稳态误差。表3 大时滞条件下各算法性能比较性能指标算法ts/sess/packetsRED趋向系统不稳定，不求ess值PID(GA)763PID(PSO)552PID(QDPSO)442PID(NSGA-II)332实验2：考察突发业务流的冲击对算法的影响，n取70，时延d取220ms，有60个FTP业务源均在0s时刻启动，还有10个在15s时刻启动，有60个FTP业务源均在0时刻启动，还有10个在15s时刻启动，发送100k字节后停止。仿真结果如图10（a）、（b）、（c）、（d）、（e）所示。由图看出，当引入突发业务流时，RED、PI影响最大，队列长度有所上升，而这些突发业务量终止时，其队列有所下降，出现较大振荡，相比之下，基于GA、PSO、QDPSO、NSGA-II的PID算法体现了一定的抗干扰能力，但基于NSGA-II算法抗干扰能力最强，性能最好。各算法性能比较如表4所示。 表4 突发业务流的冲击对各算法性能影响比较性能指标算法ts/sess/packetsRED趋向40系统不稳定，不求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 结论本文基于网络简化模型将PID控制器应用于网络AQM控制系统中，将NSGA-II与PGA相结合的优化算法应用于PID控制器参数进行组合优化。仿真结果表明，该 PID控制算法具有较好的综合性能，比RED、基于GA优化的PID控制算法、基于标准PSO优化的PID控制算法、基于QDPSO优化的PID控制算法更合适于AQM控制，性能表现为平均队列长度更趋于期望值；超调量更小；调节时间更短；队列长度的抖动更小；自适应能力更强。参考文献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 Measurement and Instrument,2007,21(4):59-62.9 LI L X,PENG H P,et al.PID parameter tuning based on chaotic ant swarmJ. Chinese Journal of