基于图论的网络拓扑优化算法研究  

Research on Network Topology Optimization Algorithm Based on Graph Theory

作　　者：韦萌萌 秦榕霞 苏俊琦 WEI Mengmeng;QIN Rongxia;SU Junqi(Huanghe Jiaotong University,Jiaozuo Henan 454950)

机构地区：[1]黄河交通学院,河南焦作454950

出　　处：《软件》2025年第2期65-68,共4页Software

摘　　要：研究提出了一种基于图论和遗传算法的网络拓扑优化方法,通过将网络结构抽象为带权无向图,建立了包含链路成本、传输时延和网络可靠性的多目标优化模型。采用改进的Kruskal算法进行初始解的构建,并引入自适应交叉算子对拓扑结构进行优化。在真实网络环境中的实验表明,该方法相比传统启发式算法,可将网络建设成本降低15%,同时保证了网络的连通性和服务质量需求。算法在大规模网络优化中表现出良好的扩展性和收敛特性。ing the network structure into a weighted undirected graph,it establishes a multi-objective optimization model that includes link costs,transmission delays,and network reliability.The improved Kruskal algorithm is used to construct the initial solution,and an adaptive crossover operator is introduced to optimize the topology.Experiments in real network environments show that compared to traditional heuristic algorithms,this method can reduce network construction costs by 15%,while ensuring network connectivity and service quality requirements.The algorithm demonstrates good scalability and convergence characteristics in large-scale network optimization.

关 键 词：网络拓扑优化 图论 遗传算法 多目标优化 KRUSKAL算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]