基于Elmore模型的Steiner树问题的求解

系统工程与电子技术 文章编号：1(101．5艏x(2003)12—1465-04 基于Elmore模型的Steiner树问题的求解 刘西奎，李艳 (徐州师范大学工学院，江苏徐州，221011) 摘要：建立了一种求解基于ⅡⅡ眦延迟模型的steiner树问题的遗传算法。针对Stelnet树问题的特点．在引 入一种新的具有自适应性的杂交概率和变异概率的基础上，提出了面向Sleiner树问题的遗传算法和一种构造染色 体的新方法。提供了遗传算法的结构并讨论了遗传算子。分析了基于时间和空间的算法复杂性。 关键词：总体布线；遗传算法；自适应；概率 中圈分类号：TPl8 文献标识码：A s0№fbrSteiⅡer帆掣曲‰basedm陆mmodel UUXi-kui．LIY蛐 (西扣咖蛳可血d州No,'ma／￡蛐挑竹，Aud蛐221011．0‰) 蠊喇：AgeneticalgorithmofⅡleSteiDer№pmb胁isgvenAccorolingtothecharacter0fthe即Mm∞theb日sisaf iIl血dtil唔anewr惟tI州埘tll鸵啦吐p6vee叫nnuteardnlltatep．曲曲ilityanewgenetic蜊ⅡⅡn岛fSleinerh髓印blemanda newr呻tllodforc口瑁咖dIIgcIⅡ饼帕oI嘶atept氆咖LedThe咖尬眦ofgenetic且l印血IlⅡ氇ispIDvjdedandlb目enetic如ithra 0p目at015帅di鄙I酬．1he唧lexityof蛔t}Imbased011timeand却峨isⅢ脚y捌 Key啪陆：辨嘴甜wilinlg；目剃calgmidⅡlI；9e盯d—f；asiNe曲岫；prob出lai哆 1引言 总体布线是VIN自动化布图中继布局之后的一个重要 环节．Neiner树问题是总体布线中要解决的关键问题。由于 互连线延迟越来越大，总体布线的目标已经从最小代价发展 到延迟驱动[“。文献[2]提出了以最小代价为目标的最佳启 发式算法，算法精度为0(n3)。以延迟驱动为目标，文献 [3]提出了基于关键汇点的近优Steiner树算法。算法复杂度 为指数级，很难应用到vIsI自动布图中。 遗传算法在算法实现上具备结构上的隐含并行性、计算 原理上的随机性和自适应性，对非线性复杂问题有全局搜索 能力，简单通用、鲁棒性强，已成为学术界和工程界研究的重 点。本文以延迟驱动为布线目标，根据Neiner树的拓扑结构 特点 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 适应树形结构的矩阵编码方式和自适应遗传操作 算子，建立了一种求解基于日I砌e延迟摸型的sl如盯树问题 的遗传算法。 2问题描述 一般地。对于某一电路，在布局阶段通过延迟的估算和 分析，指定关键路径。关键路径上的相关线网的汇点称为关 键汇点，关键路径上的线网称为关键线网．布线时将优先考 虑。 2．1延迟驱动的shdlw布线树伺琏 设网络c=(。o，"l，”2．⋯，‰)，。o和"。(1≤i≤n)分别 为网络的源点和汇点，则该网络的Sloiner布线树为T=(P， E)，其中y=(s，p1．也，⋯，‰)，P．∈E为点q到其父节点的 边。对于布线树r(y，E)，任意两个互连的汇点口．，坼间的延 迟记作d(i，j)，从源点”o到汇点q的延迟记作t。，源点和汇 点q权值记作q≥o；令c(r)为T(nE)的代价，则面向路 径的延迟驱动sIeiner布线树问题可描述如下。 给定网络c=(％，w，，”2．⋯，"。)，源点和汇点q权值记 作啦≥0，构造布线树r(V，E)．使 ．k ming(r)=^1∑吖。+^2×c(T) 式中：第一项——各汇点的ⅡIIHe延迟加权和，且A，4-^2= 1．^I≥0，^2≥0o 2．2Ⅱ呻on延迟模型 本文采用基于Elf舯fe延迟模型。给定网络G和r= (P，E)，边q的电阻和电容分别为‘和仁。设t=(K．丘) 为以汇点址为根点的r的子树，记C，为t中所有汇点与边的 收稿日期：2002—119一16；修回日期：2003—03—20。 基金项目：国家自然科学基金资助课题(6027d026和60174047)。 作者筒介：刘西奎(1973一)，男．博士研究生，主要研究方向为DNA计算，遗传算法厦网络优化方向的研究。 万方数据 ，』!!；彗； !． 至釜苫堡主皇王兰銮翌翌王 集总电容，rd为源点的驱动电阻，则汇点w，的El啪雎延迟定 义为 t=编+∑r,(c。／2+G)(1) 呼” 式中：P——s到“的路。 Ehnom延迟模型有如下优点’31。 (1)计算量小。计算树的所有汇点的延迟时间复杂度 为O(n)； (2)计算精度高。Elmore延迟模型的计算精度比线性 延迟模型的计算精度高； (3)保真度高。El咖m延迟模型所得到的近优(或最优) 布线树和其它高阶延迟模型得到的近优(或最优)布线树具 有等优性。 2．3树形结构的矩阵编码方法 树形结构个体一般采用LISP语言中的S式进行编码， 但这种编码方法不够直观，遗传操 作不方便，存储量大。本文采用一 种有效的树结构编码方法——矩阵 编码。矩阵编码方式简单、直观，适 合遗传算法操作。图1是关于6个 汇点的Steirer树个体的平面图，编 码的矩阵T(“O”表示无)为 T= 图16个{L点的Steiner 树个体的平呵圈 l 2 3 O] I 2 0 O l 3 6 7 l 6 12 133I 7 0 o 3} 12 0 0 6l 13 o o 6J 2．4群体栩始化 遗传算法的群体适宜规模可保证算法的全局收敛性，也 可以有效控制计算量。群体规模依赖于编码长度，一般为编 码长度的两倍。由于本文采用树的矩阵编码 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，即将群体 规模Ⅳ设定在10～加之间，并且把树的深度d加以固定，从 而避免了过大的计算量。 首先根据Steiner树结构的特点，设给定网络G=(‰ 吣％⋯，‰)，根据编码的根节点的第一个子节点的不同． 把初始种群划分为n个不同的子群。按群体的规摸肘，在 每个子群中随机均匀地产生M／n个个体；然后+采用如下的 模拟退火更瓤策略对群体进行更新。 (1)当子个体的适应度高于父个体时，用子个体替代父 个体； (2)否则以概率exp(一。×鱼厂／以)替换父个体。△，为父 个体和子个体的适应度差异；a≥0为常数，且当B≥l时， 口=E+1；否则口=1；e，定义为 耳=击薯(“班，))2 式中：“一)——个体n的不考虑遗传环境影响的基丁目标 函数值的基准适应度．产一平均基准适应度。B的作用类 似于模拟退火算法中的温度控制参数。节点关系如表l所 示。 表1节点关系衰 节点 左节点 右符点 父H点 2 3 0 2 0 0 l 3 6 ， —— 6 12 j3 3 O 0 3 12 0 0 6 13 0 0 6 2．s自适应变异算子 树结构的变异算子与二进制和l‘进制编码的变异算子 有本质的区别。本文设计了如下几种变异操作。 (1)个体变异：在树个体上随机选取⋯个子树，用一个 随机产生的树替换该子树，变异概率为Pk； (2)将节点的第^个节点用另个元素替换，变异概率 为一； (3)交换节点的左右于树，采用一种变异概率与父代染 色体串的相对欧氏距离成反比，随相对遗传代数指数下降的 自适应变异概率．公式为 fp⋯·exp(一17E／f一)·(1一R／月～)P二>p⋯ Pm2 I％．～ 矗≤‰。 (2) 式中：R——父代之间的欧氏距离，R一——父代之间的最 大欧氏距离，l——最大遗传代数⋯P一——最大变异概 率⋯P岫——最小变异概率，目一一常数。 变异概率选择逐渐变小，有两方面的优点：在进化初期， 较大的变异概率可以使搜索空间变大，避免出现局部最优 解；在进化的后期，较小的变异概率可以提高搜索效率．使搜 索速度不致过低。 2．6自适应交叉算子 交叉算于采用节点交叉的策略，将Steiner树结构的子树 作为·个整体进行交叉．即在两个交叉个体中独立随机地选 取交叉点。交叉时，两个个体以其交叉点作为根节点的两个 子树进行交叉互换，生成两个新个体。图2所示为两个个体 的交叉操作过程。 常用的最优交叉概率的取值范围是P，=0．5—095。 本文采用相对于遗传代数双曲线下降的自适应交叉概率．公 式为 万方数据 第t2期 基于E11蛳模型的s曲时树问题的求解 ．1467． P：：{瓦肌’儿一 (3) 【n．岫 正《n．m 式中：p}一第t代的杂交概率，Pc．—一最大的杂交概 率，p⋯——最小的杂交概率．￡——遗传代数．1一——最 大遗传代数。 ，<。 3父蠢 愈＼ 图2西个个体的交卫操作过程(虚线框足参与交叉的子树) 2．7选择算子和适应度函数 采用适应度选择方式，个体梭选择的概率为 上 p(正)=“正)／2』“t) 虽优Steiner树问题的要求是寻找满足如下条件的 Steit’ex树T，使 raing(r)=^l∑8^+^2×C(r) 算法采用的适应度函数为 “T)=2w√s—g(I) 式中：5——线网G的边界矩形面积。 2．8剪枝算子 经过上述操作后，会产生更椿的树，使计算量加大，因此 要对超过给定深度d的树个体进行剪枝，即把超过给定探度 的树的节点删除。 3算法描述和收敛性分析 3．1算法描述 求解网络的优化stei地r树问题的遗传算法描述如下。 随机产生初始化种群x(o)=l，，(0)，≈(0)．⋯． zM(0)}；／／M：种群规模t=O；／／t：演化代敷，初值l=0 根据适应度函数定义，计算x(o)中每个个体的适应度 值“黾)； while(，m。(x(t))一允。(*(t))>E)／∥o(』(f))一 A。(x(1))>￡)为停机准则 计算种群X(￡)中各个体的适应度值比例，确定 选择概率P。； ’ for(t=1；k≤Ⅳ；k；‘4-2) 根据选择概率P／和转盘式选择策略在X(￡)中选 择两个个体‰，‰； 以概率蹁对个体岛，‰执行变异操作，得到两个新个 体#叽，5h5 rdm=random[0．1]； if(rdm≤n)／／n为杂交概率 {对个体#嘶，‰执行杂交操作，得到两个新个体 x∽t1*kwl {对个体z一，x押执行剪枝检查校正操作，得到两 个新个体4l，。2； else zI2‰ 将xl，。2插入到新种群x(1+1)中 计算'：r(￡+1)中个体的适应度值，并用置(t)中适应度 值最大的个体x一(I)替换x(1+1)中适应度值最小的个体 Xmin(t+1)； ￡=I+1： 输出x(o) 3．2算法收敛性分析 定义1设I‰Im≥0}为一系列取值为离散变量的随 机变量，离散值集合为n=⋯，称为状态空间。若对于任意 的m≥1和“∈n(^≤m+1)有 P{‰+l=“／z。=i。，⋯．xfJ=i。} =PI#m+12‘+l／Xm=im} 则称{‰Im≥0}为‰链。 ．№rbF描述了穿越状态空间n的概率轨迹，是分析遗 传算法收敛性的有力工具。在时问l内，从状态i转换到状态 ，的概率^(‘)称为时间步I从i到，的转移概率，M吼叫链被 称为是葡构的；若转移概率与时间l无关，则设初始串岛突 变为C，。由于CI优于c0的概率越大，越有利于进化，所以对 于适应值，'将选用概率P(“C-)≥一co))的大小作为选择 变异概率p。的依据。 定义2串Cl，co的汉明距离为 警 ／／(c1．co)=∑I且(c1)一且(Co)I 式中：B。(c)——串C中在第i个基因位上韵值0，l，i=l， 2，⋯，R一。 定义3对于串c0定义n5”={CI“C)《以co)． 日(C．，Co)=i}和如下的类嗡”，力5”，⋯，n5“，⋯。称f】5‘’ 为co的i位改进子空间，U乩2，n50为c0的改进空问，筒 记为big：up蹦”。 ＼他缝豳 蠢、<鞴 万方数据 !』!望霎二．-!一 至笙三堡主皇王茎查 竺：兰 引理l【41 Co突变为C1进人i改进子空间的概率 P(n刖(C1)≥咖f(Co))在变异概率几=i／N时取最大值， _】、T为基因串长度。 由引理1知，快速搜索要求变异概率具有自适应性，总 体上应该是随进化代数的增加而增强，与汉明距离成反比。 因此有如下定理。 定理1按照式(3)的自适应变异概率匕进行变异，可 以保证算法是最快收敛的。 设遗传算法的状态空问为n={n，，n：，⋯，吼}，且c。 为状态0．经过交叉操作转移到状态n，的概率．记交叉矩阵 C=(cg)^。^．显然∑co，即c是随机矩阵。同理，状态n．经 过变异操作、选择操作转移到状态n，的概率分别形成的变 异矩阵．!If和选择矩阵s也是随机的。 在变异操作中，根据所设计的3种操作，设采用3种不 同的变异策略进行变异的个体数目分别为n．口，7，则状态 o．经过变异操作转移到状态q，哪=儿p。lpm2Pm≥0，所 以变异矩阵是正的。 引理2【5】若C，M，S是随机的，其中M≥0，S是列可 容的，则CMS≥0。 引理3【副若P是本原随机矩阵，则当k一∞时，收敛 到一个正的稳定随机矩阵，并与初始分布无关。 引理4悼】设P是可约随机矩阵，其中o，。是本原随 机矩阵，R和r不为0，则 r c^01 一艘P=艘l莹刺p|=【：；×。蒿 。 盟 是稳定的随机矩阵且P。=JP。，其中R。是∑PRO一的 极限，是唯一的且与初始分布无关。 显然在树结构遗传算法中，矩阵乘积P=cMs是算法 的转移矩阵，由引理2知，P是本原的，根据引理3得到如下 定理。 定理2 采用适应度比例选择策略的树编码遗传算法 是一个遍历的Markov链，即遗传算法的各个状态是非零概 率可达的，这个最终的状态与初始状态无关。 此种遗传算法对原有的数值编码的遗传算法的收敛性 理论都适用。根据文献[5]， 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的遗传算法不能收敛到最优 解，因此对遗传算法进行了改造：进化的每一代，记录前面的 最优解，把最优解加入染色体的最右端，作为符号，事实上不 参加运算，从而在遗传到下一代时+保留最佳个体。于是由文 献[5]和}l理4得到以下定理。 定理3树结构的遗传算法在交叉、变异、选择后保留 当前的最优值．能够收敛到全局最优解。 4 实验仿真 对本文设计的算法进行了实验，末加说明的时间单位是 So实验时首先确定了遗传算法中需要的参数，最后选取的参 数如表2所示。然后根据参数^．，^2对结果的影响．选取了适 当的^】和也值。实验中，连线总长随^．的增大而单调递 降，同时关键路径长度单调增加。本文中，选定^l=A2=0．5。 表3中的数据是实验中^．从01逐渐变化到1时所得到的 有关连线总长、关键路径长度和延迟时间。 裹2实验’数和实验分析 Pm．mⅡ ‘～和pep—size 最佳收敛代数一 10∞ I．0 045 27 200 O．5 0∞1 10 表3工．对结果的影响 ^l 连线总长 关键路径长度 延迟时间 0．1 ll704 42"78 21．43 0．4 9662 4284 20．48 0．5 9417 5190 23．66 0．6 9299 6749 24．07 l 883l 7508 25．28 通过对实际问题的仿真．得到了训练时间和目标函数的 关系，如图3所示。从图3可以看出，具有自适应概率的遗 传算法的收敛性是比较好的。 最后用本文的算法对 70 实验电路进行r测试。实 垂一50 验中采用了两种方案：方案 辱帅 1是采用传统计算技术(动 120 态规划和非线性优化技 1u 术)；方案2是采用本文的 0 20 40 60 80100 训练时『开J／s 算法。方案1虽然可以获图3训练时间和目标函数的关系 得问题的解，但是搜索时间 长，时间复杂性随顶点数增加呈指数增长，不适合求解多顶 点的线网。而按照方案2进行实验，对于多顶点的线网也可 以很快地达到稳定，获得最佳解。通过对顶点较少的线网分 别按照方案1和方案2得到的解进行比较，发现两种方案所 得的结果误差不大，从而可以说明本文算法的有效性。表4 是实验中得到的结果对比。 寰4实验站幂对比 线罔 连线总长 延迟时衙 搜索时间 平均 散目 方素l 方案2 误差 方案l方案2 谋差 方案l 方案2 误差 髑 4让7玎 稍∞7 1 lO％7183 瑚l0捣 08l O卯 05％ l唰190嘶193粥L33％12677d26930∞％ 2 33 0％％ h，嘲％9l如562叫1m17唧97107目l4％ 52 97 l弱％ f1：转第1516页) 万方数据 ：：i：!： 至苎三堡主皇：茎銮：竺王 具有对目标机动加速度估计的能力。 嗡[≯i旦锈匹卫 o 4；J2”20⋯；，?2”20o 4 8，b121620 ，／s ；嚣固1．蠢区羽 (a)情况2下视(b)情况2下视线角(c)情况2下导弹制 线角变化曲 速度变化曲线 导指令加建度变 线 化曲线 图2情况2的仿真结果 7结论 根据以上分析与数字仿真结果，得出以下结论。 (1)变结构制导律依赖于滑动模态的存在，因而能够消 除系统中存在的结构参数摄动和外界干扰所带来的影响，基 于这种思想．可以把目标的机动加速度视为一类具有有界扰 动的不确定因素，从而本文所提出的变结构制导律具有很强 的鲁棒性； (2)基于Lyapunov稳定性原理所确定的适应律，实质上 是对外界不确定扰动因素的界的估计，引入这种适应律不但 能够使系统稳定．改善控制特性，而且能提高导弹的导引精 度； (3)本文的这种变结构制导律不需要太多的观测信息+ 其控制结构简单，计算量小，因此易于工程实现。 参考文献： [1]高为炳变结构控制理论基础[M]北京：巾国科学技术出版 社，1990 【2]mDi，MuO-mndi．)【l|Wenli．0pIiⅢSlidlng-ModeGuidance0f }hnir学蛐BB如[c]h唧既di“铲0fthe38Coafef,moa叽脑两叩& Cd删．2000．5131—5136 [3]Z]louDi，MuChundi，XuWenliA埘vPSllding-ModeC．uidaace0fa H∞衄Missile[J]．JoumaldGuldanⅢ，Contnd，andD】“∞， 1．999，22(4)：589—594 [4]Ravindm岫K，S口'maI C-，Sw∞ayK N．S“tehBimPrOlXdOaat MI喇∞forH岫Guidance增血哦HighlyManeuveringTarl酽ls[J]． ^J,J唧al0fC．tfid,m慢．Cantm]，and脚枷曲，1994．17C6)：1357一 ■ 1363 [5]GerardkngOddeaeeAlgafithmI．k“gn：ANoalinearIn一廿 proⅢda[J]Journal0fGuidance．GaatrolmdD]mamia，1998．21 (5)：742—746． [6]JinY伽≈c嫡，nI水严mgch，}hPil‰№血m旺^dl灿铒 Gtddanee喇dcd％TaⅫetU“nfiesmdControlLoop功Ⅲa [c]．n眦啪血驿0ftheAmeclcauc。“hdc【llIi皿傥，Adinglon，VA， 200l25—27 (上接第1468页) S结论 本文设计的具有白适应杂交概率和变异概率的遗传算 法能够对延迟驱动的S',einer布线树问题进行求解。本文给 出了利用遗传算法求解背包问题的适应度函数和自适应遗 传算法操作算子，采用的自适应杂交概率和变异概率能够保 证遗传算法快速收敛，有很高的收敛精度。本文设计的自适 应遗传算法具有全局收敛性。 参考文献： [1]洪先龙，一个以时延优化为目标的力指向蜘树算法[J]半 导体学报，1995．16(3)：218—223． [2]JeffC．tⅫllth，RobinsG．da1．coI她thecq：Near-OptimalSteiaer TreePrdo]日n岫P(dvr”向越1k[J]．IEEETram肌CAD，1994．13 (11)：1351—1365 [3]BoeaeKD，KahngAB．Rdoimc．一性0I·idCriticalSinkR椰tillg TreeC．omtmeficas[c]№，ACM／IEEEDesignAukmm∞(hf， 1993．IB2一l舒． [4]张良杰．遗传算法中突变因子的分析及改进策略[J]电子学报 学刊，1996，18(6)：590—595 [5]陈国良．遗传算法厦其应用[M]北京：人民邮电出版社，1996 130—136 万方数据 基于Elmore模型的Steiner树问题的求解 作者： 刘西奎， 李艳 作者单位： 徐州师范大学工学院,江苏,徐州,221011 刊名： 系统工程与电子技术 英文刊名： SYSTEMS ENGINEERING AND ELECTRONICS 年，卷(期)： 2003,25(12) 参考文献(5条) 1.陈国良 遗传算法及其应用 1996 2.张良杰 遗传算法中突变因子的分析及改进策略 1996(06) 3.Boese K D;Kahng A B;Robins G Near Optimal Critical Sink Routing Tree Constructions 1993 4.Jeff Griffith;Robins G Colsing the Gap: Near-Optimal Steiner Tree Problem in Polynomial Time 1994(11) 5.洪先龙 一个以时延优化为目标的力指向Steiner树算法[期刊论文]-半导体学报 1995(03) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_xtgcydzjs200312007.aspx