基于遗传算法的通信网络优化规划

《基于遗传算法的通信网络优化规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、曲润涛等:基于遗传算法的通信网络优化规划①基于遗传算法的通信网络优化规划曲润涛②　席裕庚　韩　兵(上海交通大学自动化研究所　上海200030)摘　要　综述了使用遗传算法进行通信网络优化的问题,指出了原有遗传算法进行通信网络优化存在的不足,并提出了一种新的基于动态惩罚的解决策略。通过对一个简单问题的仿真,验证了动态惩罚策略的有效性。关键词　通信网络,遗传算法,动态惩罚0　引言　　通信网络的优化规划,一般是在满足各种约束如链路带宽的约束、网络时延的约束、可靠性[1]的约束等前提下优化网络的建设代价。大规模通信网络规划的优化规划问题可以看成是选

2、择网络节点、链路和链路带宽的组合优化问题。这是一类不能用任何已知多项式算法求解的问题,通常[2]称为组合规划中的NP2Hard问题。当网络规模扩大时,问题的求解空间成指数增长。[3]遗传算法(GeneticAlgorithm)是一种具有并行特征的搜索算法,并已成功地运用于一些大规模的问题的求解。遗传算法的特点是对问题的描述形式要求不高,对相关的问题有较好的鲁棒性。因此运用遗传算法这一新型工具,对网络的优化问题进行研究成为通信网络优化设计的新热点。1　遗传算法在通信网络优化规划中的应用[4-15]　　目前已经有很多有关遗传算法在通信网络优化

3、中应用的文献,这些文献涵盖了从窄带到宽带,从有线到无线的所有网络形式。从网络的拓扑结构形式上看,则有对一般网络结构的优[4-11][12-15]化,有对特殊网络结构的优化。其中文献[12,13]研究了树形网络的优化,文献[12]研究了无约束树形网络的优化,文献[13]研究了有链路容量约束的树形网络优化,另外文献[14,15]研究了在已知网络拓扑结构下通信网络的扩展问题,其中文献[14]研究了网络节点的扩展问题,文献[15]研究了网络链路的扩展问题。使用遗传算法求解通信网络的优化一般采用如下的过程:(1)编码。一般采用邻接矩阵作为网络结构的

4、编码。大多文献采用将邻接矩阵展开的方式,形2成一N长的一维编码;也有文献采用保持邻接矩阵形式的两维编码。这两种编码方式在本质上是没有区别的,但采用两维的方式更直观一些,同时便于网络的计算。[12](2)群体的初始化。一般采用随机初始化的方式,也可采用启发式初始化的方式。启发式的初始化可以提高搜索的效率,但对算法的最终结果没有直接的影响。(3)交叉。在交叉方式的选择上存在两种主要的方式:一种是点随机交叉的方式,随机选择交叉的节点,交换一两个个体节点的全部数据。另一种是窗口交叉的方式,可选择多个交叉的节点,每个节点交叉部分数据。(4)变异。和

5、普通遗传算法的变异方式不同,在通信网络优化问题实质上是整数规划问题。因①国家科技部基础研究基金资助项目。②男,1973年生,博士;研究方向:通信网络的优化;联系人。(收稿日期:1998207213;修订日期:1998209214)—43—高技术通讯　1999161此变异的方式为随机选择编码位取反。另外为了保持优化的全局性能,避免陷入局部极值,一般变异的频率远远大于普通的遗传算法。(5)选择。选择操作和普通遗传算法基本相同,普通遗传算法的选择策略都可以都用。由于变异和交叉会产生不可行解,一般适应度函数都带有惩罚项。2　基于遗传算法的通信网络

6、设计存在的问题和一些解决方案[4-15]　　许多学者研究了使用遗传算法进行通信网络设计的问题,但他们都片面强调算法的有效性而未明确指出遗传算法在通信网络设计中存在的问题。事实上使用遗传算法进行通信网络的优化规划存在很大的问题,主要表现在:(1)编码问题。遗传算法进行通信网络优化首先要对网络进行编码,编码后的空间称为重组空间,网络在此空间内进化。通信网络只有在它的有效空间内中才有意义,才可以被评价,因此有效空间称为评价空间。通信网络从重组空间到评价空间通过解释函数映射,在大多情况下,解释函数都难以得到,因此文献中大都使用邻接矩阵作为网络结构

7、的编码。但使用邻接矩阵作为编码实际大大扩大了优化问题的搜索空间,降低了遗传算法的效率。(2)交换问题。遗传算法的交换操作为更优个体的出现提供了机会,但由于网络结构的不确定性,在通信网络优化问题中两个结构不同网络的交换操作,往往破坏原有的函数映射,产生不可行解。在上述文献中交换操作都带来了大量的不可行解,因此如何处理不可行解成为算法需要考虑的主要问题。根据对不可行解的不同处理,形成了各种不同的策略。这些策略主要有:(a)启发式修补的策略。这种策略对交叉产生的不可行解进行启发式的修补,使之成为可行解。其缺点是鲁棒性不强,修补只能针对特定的问题

8、,同时容易陷入局部极小点。其优点是算法的效率较高。(b)抛弃不可行解。该策略将交叉产生的不可行解抛弃,重新选择个体进行交叉。其缺点是效率不高,特别是在可行空间相对优化空间较小时,这一点尤其明显