基于NSGA-II算法的多目标参数优化的主动队列管理新策略2650.docx
《基于NSGA-II算法的多目标参数优化的主动队列管理新策略2650.docx》由会员分享,可在线阅读,更多相关《基于NSGA-II算法的多目标参数优化的主动队列管理新策略2650.docx(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、基于NSSGA-II算算法的多多目标参参数优化化的主动动队列管管理新策策略收稿日期:基金项目:国家自然科学基金(60474076), 江苏省“六大人才高峰”项目(07-E-013),南通市应用研究计划项目(K2007004)陆锦军11,2李李志权22王执铨铨1 (1南京京理工大大学自动动化学院院 南京京 21100994;2南通职职业大学学现代教教育技术术中心 南通 22660077)摘 要本本文推导导了基于于流体流流理论的的网络简简化模型型,基于于该模型型将NSSGA-II与PPGA相相结合的的优化算算法应用用于PIID控制制器参数数优化,提提出了一一种多目目标PIID优化化设计方方法在满足
2、足系统鲁鲁棒性的的前提下下,以超超调量、上升时时间和调调整时间间最小作作为多目目标优化化的子目目标,并并将NSSGA-与PGGA相结结合对其其求解。该算法法求得的的Parretoo最优解解分布均均匀,收收敛性和和鲁棒性性好,根根据网络络主动队队列管理理控制系系统的要要求在PPareeto解解集中选选择最终终的满意意解。仿仿真结果果表明,在在大时滞滞和突发发业务流流的冲击击两种情情况下,该方法法设计的的控制器器的动静静态性能能优于RRED、GA、SPSSO、QQDPSSO算法法的优化化结果。关键词主主动队列列管理 网络络拥塞 PIID控制制 NNSGAA-III中图分类类号TPP2733 文文献
3、标志志码A 国家标标准学科科分类代代码1220.330A Neew TTactticss off Muultii-Obbjecct PParaametter Opttimiizattionn foor AActiive Queeue Mannageemennt BBaseed oon NNSGAA-III AllgorrithhmLU JJin-junn1,22LI Zhii-quuan22WANNG ZZhi-quaan1(1Scchoool oof AAutoomattionn, NNanjjingg Unniveersiity of Sciiencce aand Tecchnoologg
4、y,NNanjjingg21000944, CChinna;2Cennterr off Edducaatioon aand Tecchnoologgy, Nanntonng VVocaatioonall Coolleege, Naantoong22660077,Chhinaa)Absttracct: Siimpllifiied nettworrk mmodeelbaasedd onn flluidd fllow theeoryy iss deerivved in thiis ppapeer, andd baasedd onn thhis moddel, ann immproovedd allg
5、orrithhm, i.ee. ooptiimizzatiion alggoriithmm coombiininng NNSGAA-III annd PPGA is appplieed tto ooptiimizzatiion of PIDD coontrrolller parrameeterrs. In thee foolloowinng, a mmultti-oobjeect PIDD opptimmizaatioon ddesiign metthodd iss puut fforwwardd, ii.e. whhen robbusttnesss oof tthe sysstemm iss
6、 saatissfieed, thee miinimmum of oveershhoott,risse ttimee annd aadjuustiing timme iis ttakeen aas tthe subb-obbjecct oof mmultti-oobjeect opttimiizattionn, aand sollve it by commbinningg NSSGA-II aand PGAA. TThe Parretoo opptimmal sollutiion gott byy thhis alggoriithmm diistrribuutess evven, annd h
7、has goood cconvverggencce aand robbusttnesss. Acccorddingg too reequeest of nettworrkedd Acctivve QQueuue MManaagemmentt coontrrol sysstemm, aa saatissfyiing sollutiion is choosenn inn Paaretto ssoluutioon sset. Thhe ssimuulattionn exxperrimeentaal rresuultss shhow thaat uundeer tthe twoo coondiitio
8、ons of larrge timme ddelaay aand sudddenn buusinnesss fllow,thee dyynammic staate andd stteaddy sstatte pperfformmancces offthee prropoosedd allgorrithhm aare obvviouuslyy suuperriorr too thhosee off thhe eexisstinng RRED,GA, SPPSO andd QDDPSOOalggoriithmms.Key worrds: aactiive queeue mannageemennt;
9、 neetwoork conngesstioon; PIID cconttroll;NSGGA-III1 引引言IP网络络拥塞控控制是人人们一直直着力解解决但未未能很好好解决的的问题,相继产生了不少有影响力的算法,如RED1、ARED2、SRED3、BLUE4等,同时也出现了许多基于网络流量的控制模型,但较具影响力的是V Misra等人于2000年基于流体流理论提出的网络模型5,该模型较为恰当地描述了TCP传输流的行为6,为研究人员广为采用,根据该模型,产生了PID7等主动队列管理算法和相应的PID参数优化算法8-11,增强了对队列长度的控制能力,但这些方法难以兼顾系统对快速性、稳定性和鲁棒性
10、的要求。针对这些缺陷,本文提出了一种多目标PID设计方法在满足系统鲁棒性的前提下,以系统输出的超调量、上升时问和调整时间作为多目标优化的子目标,并将带精英策略的快速非支配排序遗传算法(NSGA-II)12和并行遗传算法(PGA)13相结合,提出基于伪并行NSGA-II算法的多目标鲁棒PID优化设计方法,并且将得到的优化PID目标参数应用于网络主动队列管理系统中。仿真结果表明,在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。2 TTCP/AQMM简化模模型及其其AQMM控制V Miisraa等人在在分析网网络连续续数据流流
11、和随机机微分方方程的基基础上,建建立了TTCP的的动态模模型6,用如如下一组组非线性性微分方方程来描描述。 (1)式中:WW为预期期的TCCP拥塞塞窗口的的大小(包包);qq为预期期的队列列长度(包包);为为往返时时间;(秒秒),为传输输延时(秒秒);C为链路路容量(包包/秒);N为激活TCP连接数;P为分组的丢弃概率,P的取值范围为0,1;q和W满足。其中,、分别表示缓存容量和最大窗口尺寸。式(1)中第一个方程描述的是TCP的窗口控制动态特性,其中式右端的1/R项模拟了窗口的加性增加,W/2项对应于包丢失概率p的窗口大小乘性降低。第二个方程描述的是瓶颈队列长度,它等于包到达率NW/R和链路容
12、量C之间的差值。分析稳态工作点各参数之间的关系,主要研究低频性能,在W1时,忽略高频性能,加入AQM控制,最终可得到如图1所示的基于简化模型AQM控制系统框图。q(t)AQM控制p(t)e(t)q0图1 基基于简化化模型的的AQMM控制系系统框图图令Gp(s)为为AQMM系统简简化模型型,即Gp(S)=(2)其中,TT1=,。若链路容容量C、往返返时间和和连接数数N分别为为1055pacckett/s、0.003s和和30,则Gp(S)=(3)PID控控制是一一种具有有负反馈馈的闭环环控制系系统,能能够较好好的根据据系统实实时状态态快速作作出控制制反应,故故不妨假假设图55中的AAQM控控制器
13、仍仍具有PPID形形式,它它引入微微分环节节来增强强系统的的快速响响应的能能力,克克服其他他控制算算法响应应迟缓的的弱点,根根据偏差差的变化化趋势调调节,具具有超前前作用,对对系统的的时滞具具有补偿偿能力。即Gc(SS)=KKp+Kds (4)其中Kpp、Ki、Kp分别为为PIDD控制器器的比例例、积分分、微分分增益系系数,其其离散的的表达形形式为(5)其中是第第k时刻的的队列长长度采样样值,qq0为期望望队列长长度,pp(k)为k时刻的的丢包概概率。其增量形形式为(66)其中,T=0.006625ss(7)分组丢包包概率(8)3 多多目标鲁鲁棒PIID设计计与Paaretto解集集3.1 多
14、目目标鲁棒棒PIDD优化模模型 为了兼兼顾系统统对快速速性、稳稳定性和和鲁棒性性的要求求,这里里以系统统输出的的超调量量、上升升时间和和调节时时间作为为优化目目标,以以频域鲁鲁棒性为为约束(当然也也可以把把它作为为目标函函数处理理),建建立如下下的多目目标优化化模型: (9)式中:为为超调量量;为上上升时间间(由终终值2第一次次上升到到终值998%的的时间);为调调整时间间(误差差带取22);GM、PM为幅值值裕度和和相角裕裕度,下下标miin为约约束下限限。3.2 Parretoo解集 多目标标优化问问题可以以用函数数来定义义,该函函数把决决策向量量映射到到目标向向量,其其数学描描述为: (
15、10)式中:XX=(,)由mm个决策策变量构构成,由由n个需需同时优优化的目目标构成成;约束束g(X)由rr个等式式、不等等式gi(X)0构成成。多目标优优化问题题(2)中的各各目标往往往处于于冲突状状态,因因而不存存在使所所有目标标同时达达到最优优的绝对对最优解解,只能能获得满满意解即即Parretoo解。对对于极小小值多目目标优化化问题,PPareeto最最优解定定义为:在设计计变量的的可行域域内,对对于变量量X,当且且仅当不不存在其其他变量量,在不不违背约约束的条条件下满满足,至至少存在在一个ii使得成立立,则称称变量为为非支配配解,即即Parretoo最优解解。Paaretto最优优解
16、不是是唯一的的,多个个Parretoo最优解解构成PPareeto最最优解集集(也称称Parretoo前沿或或非支配配解集)。4基于伪伪并行NNSGAA-III算法的的PIDD优化4.1 NSGGA-算法12 NSGGA是由由Sriinivvas和和Debb于200世纪990年代代初期提提出,它它的高效效性在于于运用一一个非支支配分类类程序,使使多目标标简化至至一个适适应度函函数的方方式。该该方法能能解决任任意数目目的目标标问题,并并且能够够求最大大和最小小的问题题。Deeb于220022年对NNSGAA进行了了改进,提提出了NNSGAA-III,一种种快速的的非劣性性排序方方法:定定义了拥拥
17、挤距离离估计某某个点周周围的解解密度取取代适应应值共享享。NSSGA-II有有效地克克服了NNSGAA的三大大缺陷:计算复复杂性从从O(mmN3)降至至O(mmN2),具具备最优优保留机机制及无无需确定定一个共共享参数数。进一一步提高高了计算算效率和和算法的的鲁棒性性。该算算法得到到的非劣劣解在目目标空间间分布均均匀,收收敛性和和鲁棒性性好,已已成为进进化多目目标优化化领域的的基准算算法之一一。其步步骤如下下: (1)快速非非支配排排序。在在选择运运算之前前,根据据个体的的非劣解解水平对对种群分分级。具具体方法法为:将将当前种种群中所所有非劣劣解个体体划分为为同一等等级,令令其等级级为l;然后
18、将将这些个个体从种种群中移移出,在在剩余个个体中找找出新的的非劣解解,再令令其等级级为2;重复上上述过程程,直至至种群中中所有个个体都被被设定相相应的等等级。(2)虚虚拟适应应度。为为了保持持个体的的多样性性、防止止个体在在局部堆堆积,NNSGAA-III算法首首次提出出了虚拟拟适应度度的概念念。它指指目标空空间上的的每一点点与同级级相邻22点之间间的局部部拥挤距距离。例例如,图图1中目目标空间间第i点点的拥挤挤距离等等于它在在同一等等级相邻邻的点ii-1和和i+11组成的的矩形22个边长长之和。这一方方法可自自动调整整小生境境,使计计算结果果在目标标空间比比较均匀匀地散布布,具有有较好的的鲁
19、棒性性。图6 局部拥拥挤距离离示意图图 具体实实现时,首首先解码码染色体体,然后后计算每每个个体体相应的的目标函函数值,再再根据目目标函数数值进行行非劣分分层,计计算每层层个体的的虚拟适适应度,计计算步骤骤为:对同层层的个体体初始化化距离:Lid =00;对同层层的个体体按第mm个目标标函数值值升序排排列:;使得排排序边缘缘上的个个体具有有选择优优势,给给定一个个大数LL0d=Lld=M;对排序序中间的的个体,求求拥挤距距离: (为第第i个体体的第mm个目标标函数值值);对不同同的目标标函数,重重复步骤骤。 (3)选择运运算。选选择过程程使优化化朝Paaretto最优优解的方方向进行行并使解解
20、均匀散散布。经经过排序序和拥挤挤距离计计算,群群体中的的每个个个体i都得到到2个属属性:非非支配序序irannk。和和拥挤距距离。iid当irannkjd时,i个体优优于j个体。上式的的意义为为:如果果2个个个体的非非支配排排序不同同,取序序号低的的个体(分级排排序时,先先被分离离出来的的个体);如果果2个个个体在同同一级,取取周围较较不拥挤挤的个体体。 (4)精英策策略。精精英策略略即保留留父代中中的优良良个体直直接进入入子代。采用的的方法是是:将父代代Pt和子代代Qt全部个个体合成成为一个个种群,RRt的个体体数为22N;将种群群Rt快速非非支配排排序并计计算每一一个体局局部拥挤挤距离,依
21、依据等级级的高低低逐一选选取个体体,直到到个体数数量达到到N就形成成了新的的父代种种群Pt+11;在基础础上开始始新一轮轮的选择择、交叉叉和变异异,形成成新的子子代种群群Qt+11。4.2并并行遗传传算法13并行遗传传算法与与常规遗遗传算法法的主要要差别在在于:它它存在同同时进化化的多个个种群,对对多个种种群轮流流进行遗遗传操作作,这样样能够提提高算法法的性能能和效率率,有效效地克服服单种群群算法的的早熟现现象。“迁移策策略”是并行行遗传算算法引入入了一个个新的算算子,它它是指在在进化过过程中子子群体间间交换个个体的过过程,迁迁移可以以加快较较好个体体在群体体中的传传播,提提高收敛敛速度和和解
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 NSGA II 算法 多目标 参数 优化 主动 队列 管理 新策略 2650
限制150内