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

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


页数：7 字数：3960

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

摘要 本文分析了网络多划分优化问题的实质，提出运用无向图多划分理论对该问题加以研究，并结合问题本身的特点，设计了一种改进型遗传算法。该算法从适应度函数设计、遗传操作算子以及参数选取等方面对经典遗传算法进行了改进。实际研究结果表明该算法实现了计算机网络自动划分优化的目的，且算法性能优于经典遗传算法。
关键词 遗传算法 无向图 k-划分 网络划分优化

引言
在计算机网络的设计与管理中，为了改善网络性能，同时便于对网络实施控制管理，采取的有效手段之一是将整个大的网络划分为多个较小的、相对独立的子网(该问题被称为“网络k-划分优化”问题，这里k指划分的子网数)。网络k-划分优化问题，属于组合优化的范畴，即根据输入的数据信息和网络基本拓扑模型，寻找可能的最佳网络配置，这是一个NP完全问题。对于该问题的研究，由于其计算复杂度随网络规模和需划分的子网数k的增大而急剧增加，传统的启发式搜索方法已无能为力。近年来，遗传算法已被引入到该问题的求解中来。遗传算法作为一种全局优化搜索算法，由于其本身所具有的全局收敛性和隐含的并行性，加之其简单易用、鲁棒性强，能够轻易地获得问题的全局最优解，且问题越复杂，它相对于其他算法的优越性越明显，故十分适合解决这类问题。但应用经典遗传算法求解网络的k-划分优化问题时，其求解时间很长，且求得最优解的成功率很低。因而，有必要针