公文写作_写作培训资材大全790

基于无向图理论的计算机网络k-划分优化遗传算法黄新力 严广乐（上海理工大学管理学院, ）摘要 本文分析了网络多划分优化问题的实质，提出运用无向图多划分理论对该问题加以研究，并结合问题本身的特点，设计了一种改进型遗传算法。该算法从适应度函数设计、遗传操作算子以及参数选取等方面对经典遗传算法进行了改进。实际研究结果表明该算法实现了计算机网络自动划分优化的目的，且算法性能优于经典遗传算法。关键词 遗传算法 无向图 k-划分 网络划分优化1 引言在计算机网络的设计与管理中，为了改善网络性能，同时便于对网络实施控制管理，采取的有效手段之一是将整个大的网络划分为多个较小的、相对独立的子网(该问题被称为“网络k-划分优化”问题，这里k指划分的子网数)。网络k-划分优化问题，属于组合优化的范畴，即根据输入的数据信息和网络基本拓扑模型，寻找可能的最佳网络配置，这是一个NP完全问题。对于该问题的研究，由于其计算复杂度随网络规模和需划分的子网数k的增大而急剧增加，传统的启发式搜索方法已无能为力。近年来，遗传算法已被引入到该问题的求解中来。遗传算法作为一种全局优化搜索算法，由于其本身所具有的全局收敛性和隐含的并行性，加之其简单易用、鲁棒性强，能够轻易地获得问题的全局最优解，且问题越复杂，它相对于其他算法的优越性越明显，故十分适合解决这类问题。但应用经典遗传算法求解网络的k-划分优化问题时，其求解时间很长，且求得最优解的成功率很低。因而，有必要针对该具体应用问题的特点，对经典的遗传算法加以改进。本文针对所研究的问题网络k-划分优化问题的实质进行理论分析，应用无向图多划分优化理论加以研究，并结合网络k-划分优化问题的具体特征，设计了一种改进遗传算法，用于自动实现大规模网络的k划分优化。在该算法中，我们通过改进适应度函数、遗传操作算子以及参数选取，既充分利用了遗传算法的全局搜索能力，又增强了遗传算法的局部搜索能力，使算法在求解网络的k-划分优化问题中具有较快的收敛速度和较高的成功率。2 问题描述2.1 网络k-划分的原则a) 子网间的通信流量应尽可能小，即将彼此之间通信量较少的网络节点分配到不同的子网中，以减少通过网络互连设备的开销；b) 子网内的通信流量应尽可能大，即将彼此之间通信量较大或通信频繁的网络节点分配到同一个子网中，以提高子网的资源利用率、增强子网内聚力；c) 各子网的流量应尽量趋于平衡，从而保证网络负载均衡，以防止因新增网络设备而导致子网性能急剧下降。2.2 网络流量分布模型网络划分的一个重要依据是网络中任意一对站点间的通信量，因此可采用如下网络流量分布矩阵来描述网络中的流量分布状况。假设网络中有n个节点，于是网络流量分布矩阵的表达式可如下给出： （） （1）这里，元素wij代表第i站点与第j站点间链路的总流量，因此wij=wji 成立。通过流量分布矩阵，可计算出网络的总流量和每个服务器的输入/输出总流量：（2）（3）通过对上述网络k-划分问题的划分原则和网络流量分布模型的分析可知，该问题的实质是研究无向图的多划分问题，即对于一无向图，将其顶点集划分为互不相交的k个子集，求使这些子集间联系最少的一种划分。故可应用无向图多划分优化理论对此问题加以研究。3 无向图多划分优化理论无向图多划分优化理论可概述为：定义 对于一无向图，其中顶点集合，边的集合，用定义边的权值。现将图划分为个顶点子集，且，称为图的一个k-划分，要求划分以后（4）其中 且。因为图中所有边的权值是一个常量，求属于不同划分的顶点之间的边的权值之和的最小值问题，实际上也就是求同一划分内各顶点之间的边的权值之和的最大值问题。因此，（4）式和下式是等价的：（5）其中 且。4 算法设计4.1 经典遗传算法的不足1、 图的k-划分问题划分后所得到的任一子集都不能为空，至少必须包含一个顶点。经典遗传操作（尤其是交叉操作）不能保证满足这一约束条件，因此需要对其进行修正。2、 网络的k-划分问题属于约束优化问题，经典遗传算法在产生非法解时丢弃，当合法解产生概率较低时，该方法将浪费大量CPU时间。因此需要针对问题的约束条件构造算子和编码，保证只产生合法解，同时收敛速度较快。4.2 对经典遗传算法改进4.2.1 编码表示编码表示方案的选取很大程度上依赖于问题的性质及遗传算子的设计。本文采取可直接在解的表现型上进行遗传操作的自然数编码方式。设网络有n个节点，根据需要欲划分为k个子网，则染色体（即问题的一个解）可如下表示：， 其中，例如，对具有30个站点的网络，划分为3个子网的某种网络划分编码如图1所示：染色体si：11020210网 络：节点1节点2节点3节点4节点5节点6节点29节点30图1 基因型编码示意图4.2.2 适应度函数定义根据图的k-划分定义及划分原则，如下定义适应度函数f(x)： 其中其中o(x)就是式（5）中的目标函数，即上面第二个等号后面的第一项；r为惩罚系数，0r) / fmax(x(t)- fmin(x(t)为停机准则计算种群X(t)中各个体的适应度值比例，确定选择概率pi；for(k=1；kn；k=k+2) 根据选择概率pi和转盘式选择策略在X(t)中选择两个个体xa，xb；以概率pm对个体xa，xb执行变异操作，得到两个新个体xam，xbm；rdm=random0，1；if(rdmpc) / pc为杂交概率对个体xam，xbm执行杂交操作，得到两个新个体xamc，xbmc；对个体xamc，xbmc执行空划分检查校正操作，得到两个新个体x1，x2；else x1= xam;x2= xbm;将x1，x2插入到新种群X(t+1)中；计算X(t+1)中个体的适应度值，并用X(t)中适应度值最大的个体xmax(t)替换X(t+1)中适应度值最小的个体xmin(t+1)；t=t+1；输出X(t)；5 算法收敛性分析定理2：在选择算子前保留当前最好解的SGA能以概率收敛到全局最优解。本文设计的算法属于种群非重叠、遗传操作重叠结构的SGA（Simple Genetic Algorithm）,并在选择操作前保留当前最好解，依据定理，该算法以概率收敛到全局最优解。6 实验研究本实验对一个具有30个节点的网络进行3个子网的划分优化。运用上述改进的遗传算法，经过多次试验与统计分析，兼顾运算速度与网络划分配置解的优化，算法中选取种群大小n=100，交叉概率pc=0.95，变异概率pm=1.00，停机准则参数=0.01，问题的约束条件为SubNet0=SubNet1=SubNet2=10，其中SubNetk为第k个子网中网络节点的数目，k=0，1，2。对第k个划分，惩罚系数，当且仅当SubNetk=10时，u=0，否则u=1。表1将该改进遗传算法与经典遗传算法划分结果进行比较，可以看出前者的子网内流量总体较后者有所提高，且流量在3个子网中的分配更为均衡；而子网间流量低于后者，且子网间流量小于网络总流量的1/10，这表明网络通信流量基本上都在子网内部流动，子网负载比较均衡，满足2.1节中的网络划分原则，证明该改进算法是有效的，且性能优于经典遗传算法。表1 实际网络划分结果对比网络划分算法改进的网络k-划分遗传算法经典遗传算法各子网内流量（%）29.2735.6626.2827.4539.2921.76子网间流量（%）8.7911.50表2考察有无空划分检查校正操作对算法性能的影响，实验结果表明引入检查校正操作后虽然算法收敛时间有所增加，但成功率有明显的增加，算法性能得以改进。表2 有无空划分检查校正操作对算法性能的影响结果比较有空划分检查校正操作无空划分检查校正操作求解平均时间（ms）87656637成功率（%）94.181.6表3考察了变异概率pm分别取不同的值时对算法性能的影响，结果表明随着pm的增大，算法收敛于局部最优的可能性明显减小，采用1.00的变异概率将使算法性能达到最佳。表3 变异概率pm分别取不同的值时对算法性能的影响结果比较变异概率pm1.000.600.300.01求解平均时间（ms）8765533436272294成功率（%）94.183.678.261.1上述实验结果表明，本文设计的用于网络k-划分优化问题的改进遗传算法是正确的和高效的。7 结论与讨论本文利用无向图的多划分理论研究网络的k-划分问题，并在此基础上针对该问题的特点和经典遗传算法在解决该类问题上的不足，通过对适应度函数设计、遗传操作、参数选取等方面加以改进，设计了一种改进的遗传算法，并通过在一个具体网络k-划分优化问题中的成功应用，克服了经典遗传算法的缺陷，提高了算法的性能，证明了该改进算法的合理性和有效性。此外，如何引入更有效的遗传操作，如何确定适应性更高的惩罚函数以及如何使算法适用于更宽松灵活的约束条件是今后有待进一步研究的问题。参考文献1 陈国良, 王煦法, 庄镇泉等. 遗传算法及应用. 人民邮电出版社，19962 潘正君, 康立山, 陈毓屏. 演化计算.北京: 清华大学出版社，19983 Songerwala M. Efficient solutions to the network division problem. thesis.the Curtin University of Technology, 19944 LaszewskiV.Gregor. Intelligent structural operators for the k-way graph partitioning problem. ICGA97.Morgan Kaufman，1991Design a Genetic Algorithm for Optimizing k-Way Networks Partitioning Problem Based on Directionless Graph TheoryHuang Xinli Yan Guangle(School of Management，Univ. of Shanghai for Sci. & Tech.，Shanghai ，China)Abstract The Optimization of k-way networks partitioning is a problem of combination Optimization，and the classical genetic algorithms (SGA) can not solve the problem efficiently. In this Paper，the theory of multi-way graph partitioning is applied to analyze the problem，and an improved genetic algorithm is presented based on the characteristics of the problem. The algorithm is improved in the following three aspects: the definition of fitness function，the genetic operators and the parameters selection. Some experimental results in an appl