采用遗传算法的网络优化技术

李国庆, 尹洪胜

(中国矿业大学 信息与电气工程学院, 江苏 徐州 221008)

采用遗传算法的网络优化技术

李国庆, 尹洪胜

(中国矿业大学 信息与电气工程学院, 江苏 徐州 221008)

针对树型网络的拓扑结构和数学模型，从个体编码、种群初始化、种群进化、适应度函数等方面构建基于遗传算法的网络优化方法.实验结果表明：所构建的方法进一步修正了适应度函数，增强了弱势个体被选择的概率，避免遗传算法优化过程的过早收敛问题，缩短了执行时间，取得了较佳的网络优化结果.

树型网络; 网络优化; 遗传算法; 适应度函数.

网络优化是诸多领域的关键技术，如通信网络、电力网络、交通网络等[1].无论是何种类型的网络，都会涉及到网络组建的成本最小化、网络节点连接代价最小化的问题，而这些问题又与网络的拓扑结构密切相关[2].在各领域的网络结构设计中，设计人员的经验起到至关重要的作用[3].但依托于人工手段实现的网络优化，优化效率和结果都难以达到最佳.在这种背景下，依托于计算机辅助手段的网络优化技术开始出现.在计算机辅助优化框架下，网络优化问题映射为全局优化的复杂性求解问题[4].很多全局优化算法都被引入到网络优化中，如禁忌搜索法、神经网络法、蚁群算法、粒子群算法等[5-6].赵云丰等[7]在人工免疫算法的基础上，构建了一种新的禁忌搜索机制，通过特赦准则和高斯变异实现网络优化，但该算法复杂度较高.李柞泳等[8]针对BP网络的实际问题，根据训练误差和检验误差更新信息素浓度，但该法只针对BP网络，具有一定的局限性.乔俊飞等[9]针对排污网络的具体问题，设计新的隶属度函数，构建了基于粒子群算法的网络智能优化系统.樊富有等[10]为了实现无线传感器网络的优化，设计了一种基于优化量子旋转门的遗传算法.然而，遗传算法在网络优化时，容易过早收敛.从已有的研究成果看，遗传算法在网络优化问题中已有比较成功的应用[11]，但也存在一些问题.因此，本文在前人研究成果的基础上，借助遗传算法并重点解决其过早收敛问题，以期实现对树状网络的拓扑优化.

图1 树型网络拓扑结构

1 树型网络及其数学模型

典型的网络结构有星型拓扑结构、环型拓扑结构、总线型拓扑结构、树型拓扑结构等.树型拓扑结构从总线型拓扑结构演变而来，不仅易于终端扩展，也有利于故障隔离.一般性的树型网络，如图1所示.

对树型网络的优化就是实现各个节点的更合理连通，使网络投资更小、网络连接代价更低.针对图1的网络结构，假设其中存在n个节点P，m个连接L，则其网络的拓扑结构可以描述为T(P,L)，并且具备属性为

式(1)，(2)分别描述了节点集合中的节点数量和各节点的最大可能连接.

对于节点i和节点j，判断它们之间是否存在连接的表达式为

式(3)中:li,j为2个节点之间的连接状况.

如果用{li,j}表示一个树型网络的所有连接集合，用{ci，j}表示所有连接对应的连接代价集合，则树型网络的优化问题就变成是对{ci，j}集合的优化问题，对应的数学模型为

式(4)中：R(l)为网络连接的优化函数.

2 基于遗传算法的网络优化方法的构建

遗传算法的执行环节：个体编码、种群初始化、种群进化(选择、交叉、变异)、计算适应度函数.

假设网络(图1)节点为12个，即n=12；同时，每个节点和其他节点的最大连接数目不超过4个.根据图1的具体结构，存在4个分支结构.为了从数学意义上描述当前连接状态，为种群的初始状态构建一个连接编码集合，即

之后，以随机生成的方式，按照一定规模对网络各节点连接的初始状态进行初始化.以这些个体状态作为初始种群，按照遗传算法的典型操作执行网络优化.其中，交叉操作是以初始种群中的个体作为父代繁殖子代.繁殖过程中,个体被选择的概率，根据适应度函数计算，即

式(6)中：k为的是种群代数.交叉操作的结果形成新的网络连接，如果满足预先设定的各种约束条件,则保留;如果不满足,则选择另外的双亲执行新的交叉操作生成.

变异操作，是对个体状态的某个位进行随机变异，也是生成新个体的重要方法.每一轮遗传操作处理后，那些最优的个体会被保留，依据式(4)进行优化操作.

按照上述过程执行网络优化时，遗传算法存在早熟或局部收敛的问题，导致无法形成最优优化结果或非全局最优结果.其原因在于适应度函数的设置，使部分候选个体被选择的概率过小，而早早地被淘汰.为此，对适应度函数进行修改，增强弱势个体被选择的概率[12]，即

至此，针对树型网络模型构造了基于遗传算法的优化过程，并对早熟和局部收敛问题进行了抑制.

3 实验结果与分析

实验所用的计算机硬件配置为酷睿双核主频2.0 GHz的CPU，8 G内存；软件配置为Windows XP操作系统、Visual C++程序编译平台.

图2 优化结果显示界面

网络模型约束条件为12个网络节点，每个节点和其他节点最多不超过4个连接.遗传算法的群体规模最大为60，遗传迭代的代数为200.

根据文中方法获得的网络优化结果，如图2所示.图2中：左上位置是“最优网络连接视觉效果”显示区，用于显示最佳的网络连接拓扑结构；右上位置是“参数设置区”，包括节点个数、节点负载、遗传代数的设置；右下位置是“优化排名”显示区，用于将排名前5位的最小代价显示出来，排名第一的最小代价，就对应视觉效果显示区的网络连接拓扑结构；左下位置是3个按钮，分别链接到3种网络优化算法(禁忌搜索法、传统遗传法、文中算法).

根据当前的优化结果可以看出：在文中算法的优化后，整个网络连接的最低代价为280.29，网络连接的拓扑结构和初始状态比，从4个分支更新到3个分支.第一个分支，根节点1到中间节点2，再从中间节点2到中间节点3，最后从中间节点3到叶子节点4和叶子节点5；第二个分支，根节点1到中间节点6，再从中间节点6到中间节点7，最后从中间节点7到叶子节点8；第三个分支，根节点1到中间节点12，再从中间节点12到中间节点11，最后从中间节点11到叶子节点9和叶子节点10.

上述网络连接结果的数学描述为

比较禁忌搜索法、传统遗传法、文中算法3种方法形成的优化结果.3种方法优化出的网络最小代价排名前10位的结果,如表1所示.

从表1可知：禁忌搜索法获得的网络最小代价都比较高，其中排在第10位的最小代价为527.77，排在第1位的最小代价为333.85，从最小代价的绝对量上看，禁忌搜索法都劣于遗传算法；传统遗传算法获得的网络最小代价，排在第10位的为411.36，排在第1位的为308.02，这种方法在最小代价为311.64之后，趋于收敛状态，之后的最小代价与此值相差不大，存在过早收敛的问题；文中算法排在第10位的最小代价为408.27，排在第1位的最小代价为280.29，同时，没有出现过早收敛的问题，可以获得更小的网络连接代价.

进一步对比禁忌搜索法、传统遗传法、文中算法3种方法的执行时间[13]，如图3所示.图3中：t为时间；n为迭代次数.由图3可知：在迭代次数较低时，禁忌搜索法执行时间较快，随着迭代次数的增加，执行时间增加非常快.文中算法和传统遗传算法相比，执行时间相差不大，但文中算法的执行时间增长趋势在放缓，这也体现出文中算法在执行时间上的优势[14].

图3 3种方法的执行时间

表1 3种方法的优化结果

4 结束语

以树型网络的优化为切入点，对其拓扑结构和数学模型进行研究.基于此，从个体编码、种群初始化、种群进化、适应度函数计算等方面，构建了一种可以优化树型网络的遗传算法.为了避免遗传优化过程的过早收敛，对适应度函数进行了改进，可以增强弱势个体在遗传操作时被选择的概率.实验结果表明：与禁忌搜索法和传统遗传法相比，文中算法可以获得理想的网络优化结果，执行时间随着迭代次数的增加，增长趋势也在放缓.

[1] 邓亮,赵进,王新.基于遗传算法的网络编码优化[J].软件学报,2009,20(8):2269-2279.

[2] MICHAEL B,RICHARD M,SLYKE V.Backtracking algorithms for network reliability analysis[J].Annals of Discrete Mathematics,2012,1:221-235.

[3] 吴琼,郑士源,朱太球.基于列生成算法的集装箱班轮运输网络优化[J].上海海事大学学报,2014,35(1):29-35.

[4] GREINER D,WINTER G,EMPERADOR J M.Optimising frame structures by different strategies of genetic algorithms[J].Finite Elements in Analysis and Design,2001,37(5):381-442.

[5] AMORETTI M,GRAZIOLI A,ZANICHELLI F.Towards a formal approach to mobile cloud computing[C]∥Euromicro International Conference on Parallel, Distributed, and Network-Based Processing.Torino:IEEE Press,2014:743-750.

[6] BILGAIYAN S,SAGNIKA S,DAS M.A multi-objective cat swarm optimization algorithm for workflow scheduling in cloud computing environment[J].Advances in Intelligent Systems and Computing,2015,308(1):73-84.

[7] 赵云丰,付冬梅,尹怡欣,等.一种改进的人工免疫网络优化算法及其性能分析[J].自然科学进展,2009,19(4):434-445.

[8] 李柞泳,汪嘉杨,郭淳,等.基于蚁群算法的BP网络优化算法[J].计算机应用,2010,30(6):1513-1517.

[9] 乔俊飞,逢泽芳,韩红桂.基于改进粒子群算法的污水处理过程神经网络优化控制[J].智能系统学报,2012,7(5):429-437.

[10] 樊富有,杨国武,乐千恺,等.基于量子遗传算法的无线视频传感网络优化覆盖算法[J].通信学报,2015,36(6):22-27.

[11] 杨四海.TSP的等价解及其对免疫遗传算法的干扰[J].华侨大学学报(自然科学版)，2007,28(1):27-29.

[12] 庄健,杨清宇,杜海峰，等.一种高效的复杂系统遗传算法[J].软件学报,2010,21(11):2790-2801.

[13] 都成娟,李和成.多下层分式双层规划问题的改进遗传算法[J].计算机应用,2012,32(11):2998-3001.

[14] 黄江波,付志红.基于自适应遗传算法函数优化与仿真[J].计算机仿真,2011,28(5):237-240.

(责任编辑： 黄晓楠 英文审校： 吴逢铁)

Network Optimization Technique Using Genetic Algorithm

LI Guoqing， YIN Hongsheng

(School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221116, China)

Based on genetic algorithm， a network optimization method is proposed according to the topology and mathematical model of tree-shape network from the aspects of individual encoding, population initialization, population evolution, fitness function and so on. Experimental results show that the proposed method can further modify the fitness function， enhance the probability of the weak individuals′ being chosen， avoid the premature convergence of genetic algorithm， and reduce the execution time. The results show good networking optimization.

tree-shape network; network optimization; genetic algorithm; fitness function

1000-5013(2015)06-0663-04

10.11830/ISSN.1000-5013.2015.06.0663

2015-10-08

李国庆(1966-)，男，副教授，主要从事软件工程、计算机网络应用技术的研究.E-mail:xzcxlgq@126.com.

国家自然科学基金资助项目(61379100)

TP 312; TP 393

A