基于进化规划求解最优通信生成树

基于进化规划求解最优通信生成树 基于进化规划求解最优通信生成树 2000年1月 第21卷第1新 通信 JOURNALOFCHINAINSTITUTEOFCOMMONICATIONS VoL21No1 Janua~2000 }短文{ 基于进化规划求解最优通信生成树 一 ;cl|,蝽兵,?{',,韩兵7,'{ (上海变通大学自动化研究所,上海20003~) 摘要:本文分析了使用遗传算法求解最优通信生成树的缺陷,提出了基于进化规划求解最优通 信生成树的新方法,并将这一方法扩展到有约束最优通信生成树问题.仿真结果验证了算法的有 效性. 关键词:进化规划{遗传算法f最优通信生成树?-.- _一-—-,,一'—_.._-_一 中图分类号:TN913.2l文献标识码:A文章编号:1000-436X(2o00)010055.05 Optimalcommunicationspanningtreedesignbasedon evolutionaryprogramming QURun—taO,XIYu—geng.HANBing (Dep.ofAutomation.ShanghaiJmotengUniverstiy—Shanghai200030.China) Abstract:Inthispaper,weanalyzedthedrawbacksofusinggeneticalgorithmstodealwiththe op- timalcommunicationspanningtree(OCST)problem— Thenanovelmethodbasedonevolutionary programmingwasproposedtodealwiththeproblem.Wea[soextendedthemethodtothecon- strainedOCSTproblem.Simu[ationresultsshowedtheeffectivenessofthemethod. Keywords:evo[utionaryprogrammingtgeneticalgorithm,OCST 1引言 最优通信生成树(OCST)E..是在树形网络的设计中提出的问题.通信网络通常可模型化 为一个图G(N,).N代表节点的集合,代表链路的集合.C.,表示节点i和之间建立链路 的单位容量代价,通常G.=c...,R表示源节点s和目的节点d间的通信容量要求,则OCST 问题的优化模型如下; ?(R?G.)(I),?(f?E{T 上式中P一()表示源节点s和目的节点d间的路径. 考虑到网络节点和链路的容量约束,在实际的通信网络设计中通常面对的是有约束OC— ST问题.为了简化问题,本文仅使用节点度数约束,通过对节点的度数加以约束,来保持网络 负载的平衡,减轻中心节点的超载负担,这样有约束OCST问题可描述为0] ?(R.?c)(2) 收稿日期:1988一.l一21;修订B期:1999.10.20 基盎项目:国家科委基础研究基金资助项目[1996]573 通信2000罐 ?,i—l,2,…,(3)0 X一l,如果节点i和,之间有边存在;=0,如果节点i和节点J之间没有边存在.为节点 的度数约束. OCST问题,特别是有约束OCST问题的表述尽管比较简单,但难以用常规的方法 求 解'.因此本文考虑使用进化规划算法求解该问题. 2基于遗传算法求解OCST问题的缺陷 Palmer在[3]中提出了使用遗传算法求解OCST问题的方法.基于遗传算法的OCST解 决方案的难点主要是编码问题,Palmer给出了解决OCST问题的有效编码需要满足的6条特 性,它实际上就是进化算法设计的要求: 1)能表示所有的树; 2)所有树的表示应该是公平的,以保证公平的初始化和公平的机会达到所有的解空间; 3)只表示树,这样才能随机初始化,同时交叉和变异才不会产生不可行解; 4)方便的编码和解码,方便的适应度函数的计算; 5)编码要尽可能短,以提高遗传算法的效率; 6)编码应有连续性,小的编码改变代表小的树的变化,以保证在交叉和变异后,父代的好 的特性能被下一代继承.如果没有这一特性遗传算法很难收敛. 在OCST问题的遗传算法设计中以上特性是很难全部满足的,目前还未找到这样理想的 编码方式.进化规划和遗传算法同属于进化算法,但有不同的侧重点.遗传算法强调遗传操作 符,性能的改进主要通过交换;进化规划则侧重于群体层次的进化,性能的改进主要通过变异. 在进化规划进行优化搜索时,可以不用对变量进行编码,这样使得问题的表达更加自然.而且 在进化规划中变异是唯一的基因重组操作,这样可以避免因为结构的不定而使交换操作变得 无效.这两个特点使得进化规划在解决结构不固定的优化问题时具有一定的优越性,因而进化 规划比遗传算法更适合于OCST问题的求解. 3基于进化规划的OCST问题求解 3.1基于进化规划求解OCST问题的算法设计 1)优化空间 如上节所述,进化规划不需要编码.因此可以直接针对求解空间进行运算.同时可以直接 使用公式(1)作为进化规划的性能指标.据此对个体进行选择和排序. 2)群体初始化 为了使问题的求解一般化,本文采用了随机初始化的方法,具体为: 将节点空间分为选择空间s和候选空间.s初始化为0,T初始化为节点空间?.在,, 中任意选择节点i,将节点i从空间去除,加入选择空间s.如果空间不为0,从和s空 间任意各选一点m和,将m加入s,将边(m,)加入网络,直到空间为0. 3)变异操作 变异操作是进化规划的核心,变异必须保证在解空间进行,同时需要满足连续性,以使子 代能继承父代的优良品质,才能使解不断进化.对此本文定义变异操作为:连续?空间任意两 节点,同时断开由此形成回路上的一条边. 第1期曲璃濞等:基于进化规埘求解最优通信生成树 和遗传算法一样理想的进化规划算法应能满足上节提出的6点要求.由于进化规划不需 编码,因此要求4和5自然成立.同时进化规划由于直接在问题空间求解,要求1也自然成立 根据图论中的几个结论,可以很容易地证明初始化,变异不仅能够保证搜索在树的范围进 行,而且能够保证公平地对树进行搜索.同时根据变异操作可以看出子代和父代只有一条边不 同,这样就保证了解的连续性,使得父代的优良品质能够保留到子代. 3.2基于进化规划求解有约束OCST问题 3.1节给出了无约束OCST问题的算法,对于有约束OcsT问题,由于约束的存在必须对 算法进行改进.一种常用的方案是在适应度函数中,对不满足约束的解进行惩罚,但这样搜索 只能在所有的树中进行,而不能在满足约束的树中进行,即算法不能满足上节的特性要求3, 会造成算法效率的下降因此本文采用如下的方法来改进原算法: 从s中选1)在初始化时,使用数组Degree()记录节点i从s空间选择的次数,在每次择 节点时,首先检查Degree(i),如果Degree(i)=等于节点度数的约束,则放弃这次选择,重新 随机选择i.这样就避免了在切始化过程中,不可行解的产生. 2)在变异操作时,对于选择加边的节点首先检查Degree(),如果Degree()<r则进行变 异,否则随机重新选择添加的边,在加边和减边操作完成后应相应修改Degree(i). 3)在选择策略上,算法作了如下改进:在进化的每一代,设C一为群体中的最大值,对于 相同的个体,保留一个个体.争其他个体的代价修改为:G=G+c.根据进化规划的选择规 则,每一代从好到坏排列,然后选择50的个体遗传到下一代,因此相同的个体不会出现,保 持了种群的多样性,避免了过早收敛 通过前两点改进,可以保证进化过程中不会出现违反约束的解,使搜索始终在解空间进 行,这样算法仍然能够满足上节提出的6点要求.选择策略的改进是因为约束的存在,使得问 题的局部极小点增多,算法容易收敛于局部极值. 4仿真结果和分析 利用本文提出的算法分别对多种节点分布和多种流量矩阵的阿络进行了仿真计算.图1 和图2分别给出了l2节点的规则网络,在不规则流量矩阵下的阿络结构和仿真运行曲线.图 3和图4分别给出了一随机产生的16节点网络,在无约束和有约束下的求得的阿络结构.表l 给出了枚举法和进化规划算法效率的比表2给出了使用有约束算法和使用无约束算法加惩 罚策咯求解有约束问题的比较. 图2中横坐标为进化代数,纵坐标为阿络代价.从图l可以看出OCST的结构由链路代价 矩阵和流量要求矩阵共同决定,规则的阿络结构,并不能保证规则的OCST结构.从图2的进 化曲线可以看出网络代价随着进化代数逐渐降低,从最初的大于1200,降低到约 ,优 600左右 化的效果是明显的,表明进化规划算法能够有效地求解OCST问题. 比较图3和图4的结果,可以看出在无节表1进化规划和枚举法搜索点敷的比较 点度数约束时OCST问题的解可能导致部分 节点的负担过重,而约束的存在则限制了这种 结构的无节制发展,使各个网络节点的流量负 载保持了一定程度上的平衡. 表1中P代表群体规模,R代表进化代数,其中的数据为lO次仿真的平均值.枚举法的 计点数可以根据:对于完备图来说,所有可能树的数目是?个,来进行计算.从表中可以看 ? ?通信2000越 出进化规划算法显着提高了搜索的效率. 衰2基于惩罚策略和有约束OCST算法的比较 节点度数约束,67 比较内容RCRCRCRCRC 一 般算法鬈罚策略234268921224619024491982446191 有约柬OCST算法l4526411562467163244916224461672446 表2中R为进化代数,C为求得的阿络代价,从表中可以看出在节点度数约束比较宽松 】I2点网培OCST结掏图2I2节点同络的进化规划埘真曲线 圈316节点无约束的OCST结掏圈416节点有约束(y毫3)OCST结掏 时,两种策略都能得到较好的优化结果,但有约束进化规划算法的收敛速度要略快一些.在约 束趋紧时,可行空间减小,这一点变得更加明显.而基于惩罚策略的算法收敛速度反而变慢,这 是由于大量的搜索在不可行空间进行的缘故.当约束非常强时基于惩罚策略的算法得到解的 性能要差于有约束OCST的算法.同时从表2可以看出有约束OCST问题即使在约束比较紧 时,网络的代价也仅比无约束高不到十分之一,因此通过节点度数的约束可以在不过分增加网 络的代价的前提下,使网络的负载趋于平衡. 5结论 本文指出了遗传算法求解OCST问题存在的缺陷,并提出了一种使甩进化规划算法求解 OCST问题的新方法,同时将这种策略扩展到有约束OCST问题的求解,仿真表明这种方法 是有效的. ?皿蛐B6420 64208642O 第1期曲诲涛等摹于进化规蜘求解最优通信生成树 参考文献 [1]HUTC.Optimumcommunicationspannit~treesD].SIAMJComput1974,3(3):188,195 [胡PALMERCC.KERSHENBAUMTATwoalgoz~thmsforfindingoptimalcommunications spanningtrees[R].Tech一 ?lReportRC19394,IBMTJWastonResearchCentertYorktownHeights,NY,1994. [33PALMERCC,KERSHENBAUMTA.Anapproachtoaproblemnetworkdesignusingge neticalgorithms_J].Net— works.1995.29(2):151,163. :4陈国良等遗传算法及其应用[M]北京:人民邮电出版社,1996. :5]谢政,李建平.同络算法与复杂性理论[M].长沙:国防科技大学出版杜t1995,266,267 中国通信学会《通信》第五届编辑委员会 主任委员 副主任委员 名誉委员 常务委员 委员 周炯架 邓震垠 莫梧生 史美林 张树京 甘仲民 匡镜明 汪元江 陈如明 姚庆栋 菅雨生 冯重熙陈芳烈胡正名 恒基 陈锦章 王行刚 冯大慈 李乐民 言华 周文表 袁保宗 黄肇明 李承恕 徐孟侠 王宏禹 邬贺铨 李征帆 张其善 郑继禹 顾学道 董兆鑫 何振亚 馀善驾 王汝馨 刘明 李国瑞 张爽斌 荆显英 圈 程蝉 (姓名排列以姓氏笔划为序) 张乃通 孔宪正 孙玉 李承权 陆志刚 赵志法 高坦弟 樊昌信