| 基于改进遗传算法的无向加权图的k点连通扩充 |
| |
| 引用本文： | 孙立华,孙雨耕,曹其国,杨挺. 基于改进遗传算法的无向加权图的k点连通扩充[J]. 天津大学学报(自然科学与工程技术版), 2003, 36(5): 595-599 |
| |
| 作者姓名： | 孙立华 孙雨耕 曹其国 杨挺 |
| |
| 作者单位： | 天津大学电气与自动化工程学院，天津大学电气与自动化工程学院，天津大学电气与自动化工程学院，天津大学电气与自动化工程学院 天津300072，天津300072，天津300072，天津300072 |
| |
| 基金项目： | 教育部博士点基金资助项目(2000005634). |
| |
| 摘 要： | 加权图的连通扩充问题已被证明是NP完全问题，作者提出一种改进遗传算法来解决无向加权图的k点连通扩充问题，通过改进遗传算法中的交叉和变异操作有效地改善了群体的效果，有助于搜索解空间中新的区域，能以较大概率搜索到全局最优，仿真结果表明，该算法在原来简单遗传算法上做了进一步改善，为解决加权图的扩充问题提供了新的方法。
|
| 关 键 词： | 无向加权图 k点连通扩充 改进遗传算法 NP完全问题 图论 网络拓扑结构 连通度 |
| 文章编号： | 0493-2137(2003)05-0595-05 |
| 修稿时间： | 2003-01-01 |
Refined Genetic Algorithm for the Augmentation of Undirected Weighted Graphs to k-Vertex-Connected Graphs |
| |
| SUN Li-hua,SUN Yu-geng,CAO Qi-guo,YANG Ting. Refined Genetic Algorithm for the Augmentation of Undirected Weighted Graphs to k-Vertex-Connected Graphs[J]. Journal of Tianjin University(Science and Technology), 2003, 36(5): 595-599 |
| |
| Authors: | SUN Li-hua SUN Yu-geng CAO Qi-guo YANG Ting |
| |
| Abstract: | 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. |
| |
| Keywords: | undirected weighted graph k-vertex-connected augmentation refined genetic algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
