基于改进遗传算法的无向加权图的k点连通扩充  

Refined Genetic Algorithm for the Augmentation of Undirected Weigh ted Graphs to k-Vertex-Connected Graphs

作　　者：孙立华[1] 孙雨耕[1] 曹其国[1] 杨挺[1] 

机构地区：[1]天津大学电气与自动化工程学院,天津300072

出　　处：《天津大学学报（自然科学与工程技术版）》2003年第5期595-599,共5页Journal of Tianjin University：Science and Technology

基　　金：教育部博士点基金资助项目(2000005634).

摘　　要：加权图的连通扩充问题已被证明是NP完全问题.作者提出一种改进遗传算法来解决无向加权图的k点连通扩充问题,通过改进遗传算法中的交叉和变异操作有效地改善了群体的效果,有助于搜索解空间中新的区域,能以较大概率搜索到全局最优.仿真结果表明,该算法在原来简单遗传算法上做了进一步改善,为解决加权图的扩充问题提供了新的方法.The connected augmentation of weighted g raphs is NP hard problem that has been proved. This paper presents a refined app roach of genetic algorithm for k-vertex-connected augmentation of undirected weighted graphs. This algorithm efficiently improves the solution s in the population by improving crossover and mutation of genetic algorithm, an d helps to search new regions of the solution space, and can acquire global opti mum by bigger probability. The simulating results demonstrate that the refined g enetic algorithm is more effective than the simple genetic algorithm and makes t he results more perfect. At the same time, it provides a new way to resolve the augment of weighted graphs.

关 键 词：无向加权图 k点连通扩充 改进遗传算法 NP完全问题 图论 网络拓扑结构 连通度 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术] O157.6[自动化与计算机技术—计算机科学与技术]