基于模拟植物生长算法的构造通讯网络Steiner最优树方法.pdf

《基于模拟植物生长算法的构造通讯网络Steiner最优树方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海理工大学学报第32卷第1期J．UniversityofShanghaiforScienceandTechnologyVo1．32No．12010文章编号：1007—6735(2010)01—0088—04基于模拟植物生长算法的构造通讯网络Steiner最优树方法丁雪枫’马良，丁雪松。(1．上海理工大学管理学院，上海200093；2．吉林大学商学院，长春130000)摘要：通讯网络作为现代社会信息系统不可或缺的重要枢纽，其设计问题直接影响总消耗成本的高低．本文提出了基于模拟植物生长算法求解通信网络设计问题的

2、新方法．对于给定原始通讯节点的通讯网络，利用模拟植物生长算法来构造网络的Steiner最优树使得网络总布线耗费达到最小．通过对实例计算，结果表明，本算法不仅可获得问题的最优解，计算所需时间也有减少，明显优于其他方法．关键词：通讯网络；Steiner最优树；模拟植物生长算法中图分类号：N945．15文献标志码：AMethodofconstructingSteinerminimaltreeforcommunicationnetworkbasedonplantgrowthsimuUlatilonalgo,rmith

3、mDINGXuo-feng，MALiang，DINGXue-so~(1．BusinessSchool，UniversityofShanghaiforScienceandTechnology，Shanghai200093，China；2．BusinessSchol，JilinUniversity，Changchun130000，China)Abstract：Asthemostimportanthingeofmodernsocietyinformationsystem，thedesignofcom—municat

4、ionnetworkdirectlyinfluencestheentireconsumingcost．Anewmethod-plantgrowthsim-ulationalgorithmwasproposedtosolvethedesignproblem．Foragivenoriginalcommunicationnetwork，aSteinerminimaltreewasconstructed，SOthattheWholenetworkconsumingcostcanreachminimum．Then。ex

5、perimentaltestsonrealinstanceswerecarriedout．Theresultsshowthatthealgorithmproposedissuperiortoothers．ItcanfindtheoptimumoftheSteinerpointlocations，andbequickerincalculationthanotheralgorithms．Keywords：communicationnetwork；Steinerminimaltree；plantgrowthsimu

6、lationalgo-rithm收稿日期：2009—04—08基金项目：国家自然科学基金资助项目(70871081)；上海市重点学科建设资助项目($30504)；上海市研究生创新基金资助项目(JWCXSL0901)作者简介：丁雪枫(1980一)，女，博士研究生．E-mail：dxf80310@sina．corn．工作单位：长春理工大学计算机学院长春130022第1期丁雪枫，等：基于模拟植物生长算法的构造通讯网络Steiner最优树方法89随着通讯网络设计和应用的不断发展，有关其控制和管理算法的设计已成为很多国

7、内外学者的研2模拟植物生长算法究热点．其核心问题之一就是通讯网络的路由设计问题．由于有线网络的通讯问题与通讯站点个数、站模拟植物生长算法将植物的整个生长空间模拟点间的相互距离均相关，且通讯的费用随着线路的为优化问题解的可行域，光源模拟为全局最优解，根长度而增加，因此设计使网络达到连通，同时整个网据植物学中的形态素浓度理论和植物的向光性动力生长机制，来模拟植物枝干在长满整个生长空间过络线路也达到最短的有线通讯网络的布线方案具有程中，在光线强度不同的环境下以全局最优的方式重要的现实意义[1]．文献[1]提出采用模

8、拟退火算法向光源快速生长动力模型【2。。．来求解通讯网络布线设计问题，该算法与穷举法相2．1模拟植物生长算法动力机制比，无论在精度、时间上均有不同程度的提高，但该植物的生长过程可描述如下：最初由种子破土优化算法的不足在于需要对初始温度、温度变化等生长出第一个茎枝，在茎、枝上可以生长出新枝的部因子进行设置，对于这些参数的优化会直接影响计位称为生长点，当植物具有大于一个生长点的时候，算速度、收敛性能和寻