模拟退火算法在结构化布线中的应用

谭 阳

(湖南网络工程职业学院,湖南长沙 410004)

模拟退火算法在结构化布线中的应用

谭 阳＊

(湖南网络工程职业学院,湖南长沙 410004)

针对在综合布线工程中水平子系统的布线设计难以达到最优化的缺陷,提出了使用模拟退火算法来计算结构化布线方案,使得总体布线方案基本达到最优化。后续实验证明该算法在实际运用中是有效的,较传统布线方法能优化 10%以上。

综合布线;模拟退火算法;最优化;算法

一、前言

在信息化时代,随着计算机和通信技术的飞速发展,网络互联的应用已成为一种基本需求,其中建筑的智能化成为网络互联应用中一个重要的研究方向。智能化建筑由建筑自动化系统 (BA)、通信自动化系统 (CA)和办公自动化系统 (OA)组成,通过信息系统的集成,使得 3A系统的信息得以共享,便可以实现科学合理地运用建筑物内所有的物理和逻辑上的资源。实现 3A系统的基础是信息通路的建设,建设计算机信息网络成为建设智能化建筑的核心。然而在结构化布线的设计当中,一般却难以获得最优化的布线方案,这使得整个信息网络实现方案存在着各种浪费和不合理的现象。

模拟退火算法是一种模拟金属冶炼中冷却过程的仿真算法。因为其具有求解与问题无关性、算法过程简单等优点,被广泛的用于函数优化、路径寻优及最优调度等实际应用中;也常用于各种 NP难题的求解上,是一种通用性很好的算法。本文通过在布线设计过程引入模拟退火算法,克服了传统方法的缺陷,使布线方案基本达到了最优化的目的。

二、基本理论

1、结构化综合布线及水平子系统

综合布线系统是一套开放式的布线系统,一般划分为:工作区子系统、水平子系统、管理子系统、干线子系统、设备间子系统、建筑群子系统六个子系统。它既能使语音、数据、图像和交换设备与其它信息管理系统彼此相连,也能使这些设备与外部信息网络相连接。但是在 PDS的应用中需要充分考虑通信技术的发展,设计时要留有足够的技术储备,能充分满足用户的长期需求。所以在设计结构化综合布线方案时,必须充分考虑所采用的网络技术及布线结构的优化,避免硬件资源的冗余和浪费。布线方案应具有高度的灵活性,各种设备位置的改变,网络拓扑结构的调整,应确保尽量不需重新布线,只要在配线间作适当的调整便可满足要求。

水平子系统通常的拓扑结构为星形拓扑,其主要是实现信息插座和管理子系统间的联接,并包括了传输介质与部件集成。选择水平子系统的联接介质,要根据建筑物内具体信息点的类型、容量、带宽和传输速率来确定。在水平子系统中一般采用超五类或六类非屏蔽的双绞电缆。其中需要注意的地方为:在水平布线链路中,使用双绞线其永久链路长度不能超过 90m,信道长度不能超过 100m。水平子系统线路结构复杂,其设计量和工程施工量都是综合布线工程的重点,亦是本文讨论的重点。其他子系统相对来说线路较为单一,并且使用的传输介质不同 (通常为光纤),本文暂不讨论。

2、模拟退火算法

模拟退火算法是由 S.Kirkpatrick,C.D.Gelatt和 M.P.Vecchi于 1983年所提出的,算法具有求得的解与初始值的无关性,并具有渐近全局最优解的收敛性,作为一种通用概率演算法,经常用来在一个大的搜寻空间内找寻命题的最优解。算法的基本思想是从一给定解开始的,从邻域中随机产生另一个解,接受准则允许目标函数在有限的范围内变坏,它由一控制参数 t决定,其作用类似于物理过程中的温度 T,对于控制参数的每一取值,算法持续进行“产生新解—判断—接受或舍弃”的迭代过程,对应着固体在某一恒定温度下趋于热平衡的过程。经过大量的解变换后,可以求得给定控制参数值时优化问题的相对最优解。然后减小控制参数的值,重复执行上述迭代过程。当控制参数逐渐减小并趋于零时,系统亦越来越趋于平衡状态,最后系统状态对应于优化问题的整体最优解,该过程也称为冷却过程。

模拟退火算法新解的产生和接受可分为如下四个步骤:

由一个产生函数从当前解产生一个位于解空间的新解,为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等;

计算与新解所对应的目标函数差,因为目标函数差仅由变换部分产生,所以目标函数差的计算一般按增量计算;

判断新解是否被接受,判断的依据是一个接受准则,常用的接受准则是 Metropolis准则,若△t’＜0则接受 S’作为新的当前解 S,否则以概率exp(-△t’/T)接受 S’作为新的当前解 S;

当新解被确定接受时,用新解代替当前解,需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值。此时,当前解实现了一次迭代,可在此基础上开始下一轮迭代。而当新解被判定为舍弃时,则在原有解的基础上继续下一轮迭代。

三、模拟退火算法在布线中的应用

在实际操作中,一般为分别对单一楼层进行设计施工。普通水平结构中会存在 1个或多个交换设备,并通过这些设备将同一水平结构中所有的工作子系统进行联接;要求所有工作子系统的数据都能汇聚,并能到达垂直干线子系统。如何使整个水平子系统的结构最为合理,即工程造价最低化、信息延迟最小化成了设计中首先要解决的问题。

对问题的描述为:可移动的交换节点与终端之间的距离的总和,目标要求为距离总和最小化。约束条件为:节点与终端之间的距离不能大于 90m,之后还需考虑工程上施工的可行性,如:是否有强电的支持及是否为架空等因素。通过对问题的数学分析,该问题为一带约束条件的路径最优化问题。问题本身为 NP难题,目前还没有常规方法可以计算出精确解。通常采用“贪婪法”和“分支定界法”来求近似解,但效果并不理想。

为了提高布线问题解的质量,应用模拟退火算法的流程如下:

步骤 2:若 T＞T0,转步骤 3;否则算法终止,输出X0;

步骤 3:随机生成网络交换节点 i和终端 j,令 xiy=0(k=1,2,…,m,k≠j),xiy=1,此时变量记为 X1;

步骤 4:若新方案合理 (不存在 l(xiy)＞90),则计算新的总体布线长度 L1,△E=L1-L0;否则转步骤3;

步骤 5:若△E≤0,则接受新的布线方案 X0←X0,T←αT,转步骤 2;否则,若 exp(-△E/T)＞rand(0,1)时 ,也接受新值 ,X0←X1,T←αT,转步骤 2;否则转步骤 3。

在给定初始值之后,可以根据实际问题规模的大小选择相适应的始温度 T及退火速度α。因为对问题求解的工程目标通常为总体造价最低,在新解生成时应注意交换节点的数量是可以变化的,所以还要了解多少长度的连接距离和一个交换节点等价,并考虑多种数量的交换节点的设计方案,并通过实际情况加以选择。

四、实验

某小型公司对网络建设要求及基本格局情况如下:

网络布局为单一水平结构,共计有 31间房间需要联通网络,建筑呈 L形结构,如图 1所示。网络要求 100M到桌面,并考虑升级到 1000M的远期规划。需要独立设立一个网络管理及维护房间,并以此房间为外网接入点。考虑交换端口的容量及以后可能新增加的终端,并留有部分供维护和替换的端口,采用了 2台 24口的交换设备。算法设定交换节点为2,网络终端接口为 31,起始温度 T=1000,终止温度T0=1,退火速度为α=1.0,模拟初始化 X0,计算目标为布线总体长度最小化。计算所使用的设备为P4-2.4GHz的 CPU,内存为 512MB。

比较使用“贪心算法”、“分支定界算法”和“模拟退火算法”3种方法,分别就同一问题进行 10次给定不同的初始状态进行求解。表 1为几种算法计算结果的比较。

图1 平面信息点分布情况

表1 几种算法性能的比较

通过表 1可以看出,在布线设计中运用了模拟退火算法以后,无论是平均目标出长度还是最优目标长度的值都优于传统算法。这说明模拟退火算法在运用于结构化布线设计后,可以使得布线工程趋于最优化,使得工程费用得以降低,避免了在设计过程中存在的浪费。优化率分别达到了 11.83%和12.72%。若此方法用于大型项目优化比率还可以进一步提升。

表2 几种算法耗时的比较

从表 2中可以看出,因为模拟退火算法是基于多重迭代的计算,所以耗时较长;但是就目前大多数计算设备的水平而言,增加一点计算时间的消耗,换来 10%以上的资金节约还是值得的。且模拟退火算法可以十分容易地实现并行化计算,对于大规模布线应用如:校园网布线的整体结构化设计,其计算时间也能够控制在可以接受的范围之内。

五、结论

本文通过对结构化布线中,布线结构难以达到最优化的问题,提出应用模拟退火算法来解决此问题。通过对实际问题的分析,给出了模拟退火算法对解决结构布线问题的计算模型。并通过实验验证了本文方法的可行性和有效性;实验结论得出较传统方法而言,本文方法可以获得更好的布线设计方案以及更大的经济效益。

[1]吴达金.综合布线系统工程设计标准实施指南 [M].北京:电子工业出版社,2006.

[2]何志议.智能大厦结构化综合布线系统设计方案综述[J].电气应用,2003(12):39-42.

[3]S.Kirkpatrick,C.D.Gelatt,M.P.Vecchi JrM P.Opt imization by s imulated annealing[J].Science,1983,(220):671-680.

[4]李江涛.智能建筑结构化布线施工图计算机辅助优化设计研究[D].重庆:重庆大学,2004.

[5]李振涛,王淑玲等.利用遗传模拟退火算法优化神经网络结构[J].计算机工程与应用,2007,(36):74-76.

[6]尚晓航,解文彬,马颂阳.介质长度对五类非屏蔽双绞线电气性能的影响[J].北京联合大学学报,2006,(3):64-68.

[7]李陶深,陈松乔等.基于模拟退火遗传算法的时延控制选播路由算法研究[J].计算机应用研究,2007,(12):336-341.

[8]康立山,谢云,尤矢勇,罗祖华.非数值并行算法 (第一册)模拟退火算法 [M].北京:科学出版社,1994.

S imulation Anneal Arithmetic in StructurizedW ir ing Application

TAN Yang

The project for integrated wiring,the Horizontal design difficult to optimize the defect,use of the SAA to calculate the program of structured cabling,wiringmakes the overall program to achieve the best opt imization.The following exper iment proved this algorithm in the actual utilization is effective,compares the traditionalwiringmethod to be able to optimize above 10%.

integrated wiring;simulate anneal arithmetic(SAA);optimization;algorithm

TP301.6

A

1009-5152(2010)01-0050-03

2009-06-12

湖南省自然科学基金项目(06JJ50107)

谭阳 (1979- ),男,湖南网络工程职业学院讲师,工程师,计算数学硕士。