基于无向图理论的计算机网络k划分优化遗传算法.docVIP

基于无向图理论的计算机网络k-划分优化遗传算法 黄新力 严广乐 （上海理工大学管理学院, 200093） 摘要 本文分析了网络多划分优化问题的实质，提出运用无向图多划分理论对该问题加以研究，并结合问题本身的特点，设计了一种改进型遗传算法。该算法从适应度函数设计、遗传操作算子以及参数选取等方面对经典遗传算法进行了改进。实际研究结果表明该算法实现了计算机网络自动划分优化的目的，且算法性能优于经典遗传算法。 关键词 遗传算法 无向图 k-划分 网络划分优化 引言 在计算机网络的设计与管理中，为了改善网络性能，同时便于对网络实施控制管理，采取的有效手段之一是将整个大的网络划分为多个较小的、相对独立的子网(该问题被称为“网络k-划分优化”问题，这里k指划分的子网数)。网络k-划分优化问题，属于组合优化的范畴，即根据输入的数据信息和网络基本拓扑模型，寻找可能的最佳网络配置，这是一个NP完全问题。对于该问题的研究，由于其计算复杂度随网络规模和需划分的子网数k的增大而急剧增加，传统的启发式有哪些信誉好的足球投注网站方法已无能为力。近年来，遗传算法已被引入到该问题的求解中来。遗传算法作为一种全局优化有哪些信誉好的足球投注网站算法，由于其本身所具有的全局收敛性和隐含的并行性，加之其简单易用、鲁棒性强，能够轻易地获得问题的全局最优解，且问题越复杂，它相对于其他算法的优越性越明显，故十分适合解决这类问题。但应用经典遗传算法求解网络的k-划分优化问题时，其求解时间很长，且求得最优解的成功率很低。因而，有必要针对该具体应用问题的特点，对经典的遗传算法加以改进。 本文针对所研究的问题——网络k-划分优化问题的实质进行理论分析，应用无向图多划分优化理论加以研究，并结合网络k-划分优化问题的具体特征，设计了一种改进遗传算法，用于自动实现大规模网络的k划分优化。在该算法中，我们通过改进适应度函数、遗传操作算子以及参数选取，既充分利用了遗传算法的全局有哪些信誉好的足球投注网站能力，又增强了遗传算法的局部有哪些信誉好的足球投注网站能力，使算法在求解网络的k-划分优化问题中具有较快的收敛速度和较高的成功率。 问题描述 2.1 网络k-划分的原则 子网间的通信流量应尽可能小，即将彼此之间通信量较少的网络节点分配到不同的 子网中，以减少通过网络互连设备的开销； 子网内的通信流量应尽可能大，即将彼此之间通信量较大或通信频繁的网络节点分 配到同一个子网中，以提高子网的资源利用率、增强子网内聚力； 各子网的流量应尽量趋于平衡，从而保证网络负载均衡，以防止因新增网络设备而 导致子网性能急剧下降。 2.2 网络流量分布模型 网络划分的一个重要依据是网络中任意一对站点间的通信量，因此可采用如下网络流量分布矩阵来描述网络中的流量分布状况。假设网络中有n个节点，于是网络流量分布矩阵的表达式可如下给出： （） （1） 这里，元素wij代表第i站点与第j站点间链路的总流量，因此wij=wji 成立。 通过流量分布矩阵，可计算出网络的总流量和每个服务器的输入/输出总流量： （2） （3） 通过对上述网络k-划分问题的划分原则和网络流量分布模型的分析可知，该问题的实质是研究无向图的多划分问题，即对于一无向图，将其顶点集划分为互不相交的k个子集，求使这些子集间联系最少的一种划分。故可应用无向图多划分优化理论对此问题加以研究。 无向图多划分优化理论 无向图多划分优化理论可概述为： 定义 对于一无向图，其中顶点集合，边的集合，用定义边的权值。现将图划分为个顶点子集，且，称为图的一个k-划分，要求划分以后 （4） 其中 且。 因为图中所有边的权值是一个常量，求属于不同划分的顶点之间的边的权值之和的最小值问题，实际上也就是求同一划分内各顶点之间的边的权值之和的最大值问题。因此，（4）式和下式是等价的： （5） 其中 且。 4 算法设计 4.1 经典遗传算法的不足 图的k-划分问题划分后所得到的任一子集都不能为空，至少必须包含一个顶点。 经典遗传操作（尤其是交叉操作）不能保证满足这一约束条件，因此需要对其进行修正。 网络的k-划分问题属于约束优化问题，经典遗传算法在产生非法解时丢弃，当合 法解产生概率较低时，该方法将浪费大量CPU时间。因此需要针对问题的约束条件构造算子和编码，保证只产生合法解，同时收敛速度较快。 4.2 对经典遗传算法改进 4.2.1 编码表示 编码表示方案的选取很大程度上依赖于问题的性质及遗传算子的设计。本文采取可直接在解的表现型上进行遗传操作的自然数编码方式。设网络有n个节点，根据需要欲划分为k个子网，则染色体（即问题的一个解）可如下表示： ， 其中， 例如，对具有30个站点的网络，划分为3个子网的某种网络划分编码如图1所示： 染色体si： 1 1