基于混合遗传免疫粒群优化的网络拥塞控制方法

孔金生，肖 天，徐 津

(1.郑州大学电气工程学院，河南郑州450001;2.华中科技大学电子与信息工程系，湖北武汉430074)

0 引言

近年来，经济的飞速发展已经带动了网络技术的巨大进步，而Internet作为发展最广泛、最迅速的计算机网络，在人类的生活中有着不可替代的作用.当过多的数据包存在网络中时，网络的整体性能就会下降，这种现象称为拥塞.拥塞会降低吞吐量、延时等一些性能指标，影响网络运行的稳定性和服务质量，因此，通过适当的方法来预防和控制拥塞是目前网络研究的一个热点问题［1-2］.利用全局搜索寻优技术的智能优化算法在网络优化领域得到了广泛应用，包括微粒群算法(PSO)、遗传算法(Genetic Algorithm，GA)、免疫算法(Immune Algorithm，IA)等优化算法［3-4］.微粒群算法实现方便，具有良好的收敛性［5］;遗传算法的全局搜索能力强，具有较好的鲁棒性，不易陷入局部最优［6］;免疫算法具有种群多样性，速度相对快，易获得全局最优解等优越性.这些优化算法还存在一些问题，例如微粒群算法在处理复杂优化问题时出现过早收敛，不能尽快找到最优解;遗传算法初始种群往往是随机生成的，导致算法的收敛时间长［7］;免疫算法易陷入局部最优，这些优化算法在解决实际问题时会受到一定的限制.

笔者将遗传算法和免疫算法引入到微粒群算法中，形成了遗传免疫粒群优化算法(简称IGAPSO)，这种混合的策略并不是对3种算法的简单拼凑，也不是机械的继承，通过理论分析研究，IGAPSO算法既提高了跳出局部最优的能力，又保证了群体的多样性，提高了寻优效率.仿真结果验证了该优化算法的可行性，最后将遗传免疫粒群算法应用到网络拥塞控制中，提出一种基于混合遗传免疫粒群优化的网络拥塞控制方法.

1 混合的遗传免疫粒群优化算法

1.1 算法设计

遗传免疫粒群算法通过将遗传算法中的交叉变异机制和免疫算法中的识别选择思想引入PSO，提高适应度好的个体机率，并利用已经产生的优秀个体与随机产生的微粒个体进行交叉变异产生新微粒，与此同时微粒的多样性也不会受到影响［8］.具体算法如下

①对微粒群进行初始化，(含n个微粒);

②算出每个粒子的适应度值;

③判断每个粒子的当前适应度值，若优于个体极值，则用当前适应度值替换个体极值，再将每个粒子的当前个体极值与全局极值做比较，若优于全局极值，则用该个体极值替换全局极值，并将当前粒子保存至记忆库;

④基于个体最优和全体最优值更新粒子;

⑤判断是否满足终止条件，若满足则结束，不满足则进行下一步;

⑥判定是否出现“早熟”现象，若没有，转②，否则进行下一步;

⑦随机生成n/2个粒子，再在记忆库中随机选出n/2个粒子，两部分粒子共同构成新的微粒群，对新微粒群中的各微粒，基于其适应度大小和浓度赋予各自参与交叉和变异运算的选择概率，粒子依概率进行交叉变异运算，得到下一代粒子群，然后返回进行②.

1.2 性能测试

采用IGAPSO和标准PSO针对一个标准的多峰测试函数进行优化，来比较两者在“逃逸”局部极值方面的能力［9］.

图1 测试函数图像Fig.1 Image of test function

2种算法中均取粒子数40，设置循环结束条件为达到最大迭代次数10 000.2种算法的性能测试结果如图2、图3所示，结果表明标准PSO在第607代陷入了局部最优值15.919 4，全程耗时653.812 000 s，而IGAPSO则在第4 451代得到了全局最优值 1.7764×10-15，全程耗时538.609 000 s.可见，经过改进，遗传免疫粒群算法在“逃逸”局部极值方面的能力得到了显著增强.

图2 标准PSO算法性能测试结果Fig.2 Performance test result of standard PSO

图3 IGAPSO算法性能测试结果Fig.3 Performance test result of

2 遗传免疫粒群算法在网络拥塞控制中的应用

仿真采用的网络拓扑模型是随机产生的，结构如图4所示，共有15个节点.每条链路设置带宽和延迟两个QoS(Quality of Service)参数点，分别用B和D表示.假设现在有2个业务流分别应用到网络中，共同经过链路9—13，业务流1所需B1=70，D1=10;业务流2 所需 B2=80，D2=12;链路9-13的链路带宽B3=70.

图4 网络拓扑结构Fig.4 Image of network topology

由于遗传免疫粒群优化算法选择网络资源较为充足的链路，而传统算法选择网络中最短的路径.2个业务流同时发送请求，遗传免疫粒群算法与传统算法优化结果比较如表1所示.

表1 IGAPSO与传统算法的比较结果Tab.1 Comparison result of IGAPSO and tradition algorithm

由表1可以看出采用遗传免疫粒群优化算法的业务流1、2都会选择最适合的路径，使网络负载利用得更加均匀，而传统算法只选择最短路径，造成丢包率很高，网络无法满足业务流对带宽的需求，也浪费了其它合适路径的网络资源.图5反映了网络优化前后链路9—13的吞吐量，显然优化后的网络资源利用更合理，吞吐量更高，也保证了以后的业务请求.因此，遗传免疫粒群算法在避免出现网络拥塞的前提下合理利用网络负载，尽量降低网络资源消耗，提高吞吐量.

图5 链路9—13的吞吐量Fig.5 Throughput of link 9—13

3 结论

笔者将遗传算法和免疫算法引入到微粒群算法中，形成了基于遗传免疫粒群的优化算法(IGAPSO)，该算法既提高了算法跳出局部最优的能力，又保证了群体的多样性，在克服各个算法缺点的同时能更大发挥各自的优点.最后将遗传免疫粒群算法应用到网络拥塞控制中，提出一种基于混合的遗传免疫粒群优化的网络拥塞控制方法来解决网络拥塞现象，通过仿真研究，验证了该方法的可行性.

［1］杨新宇，曾明，江晓，等.一种新的自适应网络拥塞控制算法［J］.计算机工程，2004，30(8):17-18.

［2］刘红，白栋，丁炜，等.多目标的 Internet路由优化控制算法［J］.电子学报，2004，32(2):306-308.

［3］王小平，曹立明.遗传算法—理论、应用与软件实现［M］.西安:西安交通大学出版社，2002.

［4］EAGELS P K，NOCOL V M.Recent approaches to global optimization problems through particle swam optimization［J］.Natural Computing，2002，12(1):235-306.

［5］谢晓峰，张文俊，杨之廉.微粒群算法综述［J］.控制与决策，2003，18(2):129-134.

［6］玄光男，程润伟，汪定伟，等.遗传算法与工程设计［M］.北京:科学出版社，2000.

［7］赵静，孔金生.基于遗传算法和禁忌搜索的混合优化策略［J］.计算机工程与设计，2009，30(23):5489-5491.

［8］朱洪程.基于遗传免疫微粒群算法的工程项目多目标综合优化研究［D］.天津:天津大学管理与经济学院，2010.

［9］ALFI A.PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems［J］.Acta Automatica Sinica.2011，37(5):541-549.

［10］金超，叶春明.基于QPSO算法的模糊流水车间调度问题［J］.计算机工程与应用.2012，48(2):238-240.