基于遗传算法的通信网络拓扑优化研究

摘要:该文通过分析通信网络中的拓扑优化问题,抽象出数学模型,并利用遗传算法对该模型进行求解。最后通过实例验证用遗传算法求解该问题明显优于一些传统的算法,文中所建立的数学模型和算法能够正确地解决通信网络拓扑优化问题。

关键词:遗传算法;通信网络;拓扑;优化

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)22-6278-02

Genetic Algorithm Based Optimization of Communication Network Topology

LIANG Xu1, WANG Huan1,2, HUANG Ming1

(1.DaLian JiaoTong University, Dalian 116028, China; 2.China Unit 91550 of Navy, Dalian 116023, China)

Abstract: By analyzing the communication network topology optimization, abstract mathematical models, and the genetic algorithm to solve the model.Finally, an example of the problem using genetic algorithm is superior to the traditional algorithm, the paper established a mathematical model and algorithm can correctly solve the communication network topology optimization.

Key words: genetic algorithm; topology optimization; communication network

随着信息化的发展,通信网络不断扩充新功能,发展新业务。这必然导致网络规模日益庞大,节点众多,并且网络拓扑的结构也越来越复杂。从而造成了数据信息的转接次数增多,迟延增加,维护难度增大,这就给现代通信网络的建设和管理提出了新的挑战。

对通信网络进行优化能够使其更加快速有效可靠地传递信息,避免和最大限度减少因网络中断或延迟带来的损失。遗传算法(GA)模拟自然进化过程,是一种具有并行特征的搜索算法,它能对解空间进行搜索,加快对解的搜索速度,便于推广到多结点的网络优化设计中,是解决大规模网络优化问题的有效工具。

1 遗传算法求解过程

遗传算法(GA)的主要特点是直接对结构对象进行操作,具有内在的隐含并行性和更好的全局寻优能力,自动获取和指导优化的搜索空间,自适应调整搜索方向,不需要确定的规则。

使用遗传算法求解通信网络的拓扑优化一般采用如图1的过程。

2 算法设计

2.1 编码和初始化种群

对于一个n结点的网络,其G图最多有n(n-1)/2条边,所以染色体的长度可定长为n(n-1)/2的二进制串。由于邻接矩阵具有对称性,因此只需使用该矩阵的上三角表示,这样可以使个体的长度为n(n-1)/2,压缩比为2。 所求问题可用图2的下(上)三角矩阵表示,称其为G的邻接矩阵T。如图2。

图2 G的邻接矩阵T

在上述编码方式中,则基因型可设为A[1,…,n(n-1)/2],由此可以生成W个基因个体,每个基因个体都是此通信网络的一种拓扑。

2.2 根据个体适应度进行选择

求解网络优化的数学模型属于求解目标函数最小值问题,适应度函数可设为

随着进化代数的增加,个体适应度之间的差别越来越小,可以对适应度函数增加一个比例系数a将其放大,f’(x)=af(x),a>1。

2.3 算法终止条件

当种群满足以下三个条件之一时算法终止并输出最优解。

1) 个体的最大适应度超过预先设定参数。

2) 个体的平均适应度超过预先设定参数。

3) 种群代数超过预先设定参数。

3 实验及结果分析

某通信主干网络节点数为9,经过多次实验后,选取POP=60,Pc=0.65,Pm=0.01, 并以最大代数max gen=3000做为程序的终止条件。其各节点间线路代价如表1所示。

经过该算法可得到计算结果如图3。

若采用枚举法,则时间复杂度为O(2N),此算法时间复杂度为O(N2),所以在对通信网络优化的同时,大大降低了时间复杂度。

4 结论与总结

通信网络的优化是一个复杂且涉及范围广泛的课题,是通信网络技术中不可缺少的部分。与遗传算法相比,传统算法比较复杂,局限性很大且计算时间较长。本文使用遗传算法较好地解决了通信网络优化问题。本文提出的算法对小规模通信网络的拓扑优化问题能够较好的求解,对大规模网络拓扑进行优化还存在不足。改进方法可以在遗传算法中融合其它优化算法,构成一种混合遗传算法。本文中对遗传算法在网络优化中的研究只进行了初步的探讨,要将这种方法完善还需要做进一步探讨和研究。

参考文献:

[1] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.

[2] 王小平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学,2002.

[3] 王玥,蔡皖东,段琪.基于遗传算法的网络脆弱性计算方法[J].系统仿真学报,2009(3): 1628-1632.

[4] 曹继伟.复杂网络拓扑建模及模型优化研究[D].武汉:华中师范大学,2006.