一种实现网络k-划分优化的改进遗传算法研究

The Study on an Improved Genetic Algorithm for Optimizing k-Way Networks Partitioning Problem

自动实现网络 k-划分优化问题 ,属于组合优化的范畴。经典遗传算法求解这类问题效率不高。本文运用图的多划分理论对该问题加以分析 ,同时结合该问题本身的特点提出了一种改进遗传算法 ,该算法从编码方式、遗传操作、以及参数选取上对经典遗传算法进行了改进。最后将该算法应用到计算机网络的 k-划分优化问题中 ,实际研究结果表明 ,该算法实现了自动网络划分优化的目的 ,且算法效率优于经典遗传算法。

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 description of genes of chromosome,the genetic operators and the parameters selection. Some experimental results in an application example verify the validity and efficiency of the algorithm.