第3章 X结构Steiner最小树算法 3．1引言 作为超大规模集成电路物理设计中一个关键的环节，总体布线面临诸多复杂的难题。Steiner最小树(Steiner Minimal Tree，SMT)问题是在给定引脚集合的基础上通过引入一些额外的点(Steiner点)以寻找一棵连接给定引脚集合的最小代价布线树。因为Steiner最小树模型是VLSI总体布线中多端线网的最佳连接模型，所以Steiner最小树构建是VLSI布线中一个关键环节。 总体布线的布线算法主要基于曼哈顿结构以及非曼哈顿结构两种。其中，非曼哈顿结构因其更强的布线优化能力受到越来越多研究人员的关注。为了更好地研究非曼哈顿结构布线，首要工作是研究非曼哈顿结构Steiner最小树的构建问题。本章3．2节~3．6节分别介绍了5种有效的X结构Steiner最小树(Xarchitecture Steiner Minimum Tree，XSMT)算法，并取得了不错的优化效果。 本章涉及的专有名词符号见表3．1。 表3．1专用名词符号表 缩写英 文 全称 中 文 全 称 VLSIVery Large Scale Integration circuit超大规模集成电路 EDAElectronic Design Automation电子设计自动化 SMTSteiner Minimal TreeSteiner最小树 RSMTRectilinear Steiner Minimal Tree矩形Steiner最小树 XSMTXarchitecture Steiner Minimal TreeX结构Steiner最小树 WLXSMTWireLengthdriven Xarchitecture Steiner Minimum Tree线长驱动X结构Steiner最小树 PSOParticle Swarm Optimization粒子群优化 SLPSOSocial Learning Particle Swarm Optimization社会学习粒子群优化 续表 缩写英 文 全 称中 文 全 称 SLDPSOSocial Learning Discrete Particle Swarm Optimization社会学习离散粒子群优化 DEDifferential Evolution差分进化 DDEDiscrete Differential Evolution离散差分进化 MDDEMultistrategy optimization Discrete Differential Evolution多策略优化离散差分进化 MAMemetic Algorithm文化基因算法 XSMT通过引入Steiner点以最小的代价连接给定的引脚集合，这里连接线可走线方向除了包括传统的水平方向和垂直方向，还允许45°和135°的绕线方向。 XSMT问题中给定P={P1，P2，P3，…，Pn}作为待布线网的n个引脚集合，且每个Pi对应一个坐标对(xi，yi)。例如有一个待布线网有8个引脚，表3．2给出了引脚的输入信息，相应的引脚版图分布如图3．1所示，例如，其中编号为1的引脚对应的坐标对信息为表3．2第二列所示的(33,33)。 表3．2待布线网的引脚输入信息 编号12345678 X坐标332424734383720 Y坐标33935212540 图3．1待布线网的引脚分布情况 对X结构的4种pseduoSteiner点选择方式的具体定义已在前面给出，详见2．5．2节。 3．2基于离散PSO的X结构Steiner最小树算法 由于Steiner最小树问题是一个NP难问题，所以一些在求解NP难问题中展现出良好应用前景的进化算法［包括粒子群优化算法(Particle Swarm Optimization，PSO)和蚁群算法（Ant Colony Optimization,ACO）］被用于求解RSMT和XSMT问题。作为一类基于种群进化的方法，粒子群优化算法于1995年由Eberhart和Kennedy共同提出。PSO算法相对其他优化算法而言，操作简单且能快速收敛至一个合理、优秀的解方案。 基于以上相关研究工作的分析，本节设计并实现一种基于离散粒子群优化的有效算法，即XSMT_PSO算法，用来求解X结构Steiner最小树的构建问题。首先，为了解决PSO算法在高维问题中收敛慢的现象。其次，根据X结构Steiner最小树的特点，受遗传算法中的变异算子和交叉算子的启发，提出了离散化的PSO更新操作策略。然后，设计了一种适合于X结构Steiner最小树问题的有效编码策略。最后，设计相应的仿真实验，通过实验结果证明本节算法的可行性和有效性。 XSMT_PSO算法的流程图如图3．2所示。 图3．2本节算法的流程图 3．2．1XSMT_PSO算法 对于基本PSO算法的具体介绍已在前面给出，详见2．3．2节。 基本PSO算法主要运用于解决连续优化问题，而XSMT问题的解空间离散，因此需要构造一种离散形式的PSO算法模型。现有文献应用PSO解决离散问题，主要有将速度作为位置变化的概率、直接将连续PSO用于离散问题的求解以及重新定义PSO操作算子3种策略。为此，本节设计了适合XSMT问题的有效离散PSO算法，即XSMT_PSO算法。 1． 粒子的编码策略 XSMT_PSO算法采用边点对编码。在该编码方式中，候选XSMT的一条边由边的两个端点与边对应的pseudoSteiner点选择方式。pseudoSteiner点选择方式是将生成树的边转化成X结构Steiner树(Xarchitecture Steiner Tree，XST)的X结构边。对于一个含n个引脚的线网，其每棵候选的XST都由n-1条边构成，每条边有两个引脚以及一个对应的pseudoSteiner点选择方式，同时用一位数字表示该XST的适应度值，所以每个粒子编码的总长度为3×(n-1)+1。例如，一个候选XST(n=8)可用XSMT_PSO算法中一个粒子的编码表示，其编码采用如下所示的数字串表示： 76064175151213018152210．0100 其中，最后一个数“10．0100”为该粒子的适应度值，各个斜体数字为对应边的pseudoSteiner点选择方式。对第二个数字子串(641)而言，编号6和4的引脚以及pseudoSteiner点选择方式1选择构成了该边。 2． 粒子的适应度函数 定义3．1一棵X结构Steiner最小树的长度是该布线树中所有边片段的长度总和，其计算方式如下： L(TX)=∑ei∈TXl(ei) (3．1) 其中，l(ei)表示在布线树TX中每个边片段ei的长度。 根据X结构Steiner树的4种互连线选择方式，XST所有边片段可分为以下4种类型： 水平边片段、垂直边片段、45°斜边片段及135°斜边片段。为计算方便，将45°边片段顺时针方向旋转为水平边； 同理，将135°边片段顺时针方向旋转为垂直边，使得所有边片段都可分为水平和垂直两种。最后将水平边根据其左引脚的大小按从下往上、从左到右的方式排列，垂直边则根据其下引脚的大小按从左到右、从下到上的方式排列。依照上述方式，求解XST的长度只需要计算所有不重复的边片段即可。 本节算法中的粒子的适应度函数设计如下： fitness=1L(TX)+1 (3．2) 其中，分母做布线树的长度加1的操作是防止出现布线树的长度为0的情况，即两端线网中两个引脚的位置重合。可以看出，布线树长度越小，即粒子适应度值越大，则粒子越优。 3． 粒子的更新公式 XSMT_PSO算法结合遗传算法的变异和交叉操作改变了基本PSO粒子的更新方式以实现构建X结构Steiner最小树这一离散问题。粒子的更新公式如下： Xti=N3(N2(N1(Xt-1i,w),c1),c2) (3．3) 其中，w是惯性权重因子，c1和c2是加速因子，N1表示变异操作，N2和N3表示交叉操作，r1、r2、r3都是在区间［0，1)的随机数。 1) 粒子的速度更新 粒子的速度更新公式如下： Wti=N1(Xt-1i,w)=M(Xt-1i),r1f- crl，否则(3．22) 其中,cri=0．1，cru=0．6，fi、fmin、fmax、f-分别为当前个体的适应度值、种群最小适应度值、种群最大适应度值及种群平均适应度值。 6． XSMTDDE算法流程 XSMTDDE算法流程图如图3．10所示。 图3．10XSMTDDE算法流程图 当进行迭代操作时，在第一阶段的每次迭代中，依次以本节重新设计的变异算子(见式(3．19))、交叉算子(见式(3．20))进行种群的变异交叉； 在第二阶段，由于只变换边的走线方式，故直接采用式(3．11)及式(3．16)对种群个体进行变异交叉，最后通过贪心选择策略进行种群的个体更新优化并根据式(3．18)重新计算种群每个个体的适应度值。 7． XSMTDDE算法伪代码 XSMTDDE算法伪代码如算法3．4所示，同样分为两个阶段。第一阶段，以引脚点的曼哈顿距离作为边的权值，采用Prim算法构造最小生成树。第二阶段分为两个时期： 第二阶段前期，采用改进的变异算子及交叉算子对种群进行变异和交叉，再进行贪心选择； 第二阶段后期，采用传统的变异算子和交叉算子，再进行贪心选择，直至达到最大迭代次数结束，最后再对得到的种群采取精炼操作。 算法3．4 XSMTDDE算法 输入： XSMTDDE参数； 阈值： threshold； 引脚点集合 输出： 最优解向量 Δ 1. t←1(initialization)； 2. for i=1 to M do 3. Prim(); 4. end 5. while |f(Δ)|≥ε or (t≤T) do 6. for i=1 to M do 7. if t≤T×threshold then 8. vji,t=ImproveMutation(xji,t); 9. uji,t=ImproveCrossover(xji,t,vji,t); 10. else 11. vji,t=TraditionalMutation(xji,t); 12. uji,t=TraditionalCrossover(xji,t,vji,t); 13. end 14. if f(ui,t)1，从边集合Xgbest⊙Xgi中随机淘汰n条边{e1,e2,…,en}，其中ei∈Xgi且eiXgbest，n的值由式(3．38)计算得到。 n=round((Fi-1)×|Xgi|) (3．38) 定义3．7若Fi=1，则不改动任何边集合的保留比例，按原先的运算策略进行。 2) 参数F更新过程 每个个体Xgi设置一个自适应参数Fi，初始化均为1，在迭代过程中，每次选择操作结束后对参数Fi进行更新。自适应参数F更新过程的伪代码如算法3．7所示。 算法3．7 自适应学习因子更新 输入 种群P，种群大小NP，迭代次数evaluations 输出 自适应参数F Begin： 1. Fi←1; //初始化 2. r=max{10,0．001×fbest}; 3. for j=1 to evaluations do 4. for i=1 to NP do 5. Δ=fi-fbest; 6. if Δr Fi-0．05，Δ≤r (3．40) 适应度值fi足够接近Xgbest的适应度值fbest时，此时减小Fi的值，更大程度地保留原有结构； 反之增大Fi值，以扩大变异范围。 3．4．2算法仿真与实验结果 1． 开发环境与数据来源 本节算法的开发工具为Visual Studio 2019，使用C/C++语言，操作系统为Windows 10。为验证本节所述算法能较好地解决XSMT问题，设计如下3组对比实验，其中前两组的测试数据来源为GEO，第三组的测试数据来源为IBM： 第一组实验为加入多策略优化前后的结果进行比较，验证多策略优化后的DE算法在解决XSMT问题中的有效性； 第二组实验将本节算法的实验结果与DDE、ABC和GA算法进行对比； 第三组实验采用IBM数据集，实验结果与SAT和KNN进行对比。在本节所述实验的所有算法初始种群大小均为50，迭代次数均为500。 2． 实验结果分析 1) 多策略优化的有效性验证 第一组实验： 为了验证多策略优化DE算法在解决XSMT问题中的有效性，将加入多策略优化前后的实验结果进行对比，实验对比结果分别如表3．10和表3．11所示，其中表3．10为平均线长优化结果，表3．11为标准差优化结果。可以看出,加入多策略优化后能够取得2．40%的平均线长优化率及95．65%的标准差优化率。 表3．10多策略优化的平均线长优化结果 电路引脚数XSMTDDEXSMTMDDE平均线长优化率/% 1816956169000．33 2918083180230．33 31019430193970．17 41525728256240．40 52032434320911．06 65049103480902．06 77057386561052．23 810070407684572．77 94001451831385124．59 续表 电路引脚数XSMTDDEXSMTMDDE平均线长优化率/% 104101466801403594．31 115001600311526494．61 1210002320572170605．90 均值 2．40 表3．11多策略优化的标准差优化结果 电路引脚数XSMTDDEXSMTMDDE标准差优化率/% 18560100．00 29580100．00 310420100．00 415198895．96 5203432293．59 650103611988．51 770108213687．43 8100190518790．18 940032215798．23 1041032225698．26 1150031935098．43 121000397711397．16 均值 95．65 2) XSMTMDDE实验对比 第二组实验： 为了测试多策略优化的离散差分进化算法(MDDE)在解决XSMT问题上的能力，将本节算法与传统离散差分进化算法(DDE)、人工蜂群算法(ABC)和遗传算法(GA)进行对比，表3．12~表3．14分别展示了4种算法对于平均线长、最优线长和标准差的优化对比。与DDE、ABC和GA相比，本算法分别得到2．40%、1．74%和1．77%的平均线长优化率，1．26%、1．55%和1．77%的最优线长优化率，95．65%、33．52%和28．61%的标准差优化率。 表3．12各算法平均线长优化对比 电路引脚数 平 均 线 长平均线长优化率/% DDEABCGAMDDEDDEABCGA 18169561691816918169000．330．000．00 29180831804118041180230．330．100．10 310194301969619696193970．171．521．52 415257282591925989256240．401．141．40 520324343248832767320911．061．222．06 续表 电路引脚数 平 均 线 长平均线长优化率/% DDEABCGAMDDEDDEABCGA 650491034894048997480902．061．741．85 770573865762057476561052．232．632．39 8100704077053270277684572．772．942．59 94001451831418351418231385124．592．402．40 104101466801436421434451403594．312．292．15 115001600311564571563941526494．612．432．39 1210002320572225472224872170605．902．472．44 均值2．401．741．77 表3．13各算法最优线长优化对比 电路引脚数 最 优 线 长最优线长优化率/% DDEABCGAMDDEDDEABCGA 18169181691816918169000．110．110．11 29180411804118041180230．100．100．10 310194151969619696193970．091．521．52 415256272562725897256050．090．091．13 520322093234432767320910．370．782．06 650479874863748783479750．031．361．66 770564085722757445559190．872．292．66 8100688297038270092680391．153．332．93 94001419671414901414671383822．532．202．18 104101440331433101432821401792．682．182．17 115001569501560341561101525912．782．212．25 1210002266542222622222852168244．342．452．46 均值1．261．551．77 表3．14各算法标准差优化对比 电路引脚数 标准差标准差优化率/% DDEABCGAMDDEDDEABCGA 1856000100．00—— 2958000100．00—— 31042000100．00—— 41519814846895．9694．5982．61 520343118452293．5981．3651．11 650103624213311988．5150．8310．53 770108219514013687．4330．262．86 续表 电路引脚数 标准差标准差优化率/% DDEABCGAMDDEDDEABCGA 810019056911218790．18-171．01-66．96 940032212001705798．2371．5066．47 1041032221461225698．2661．6454．10 1150031931601335098．4368．7562．41 121000397713110711397．1613．74-5．61 均值95．6533．5228．61 第三组实验： 为了验证本节算法在构造多线网XSMT的能力，本实验采用IBM数据集，与文献［14］的SAT算法和文献［8］的KNN算法进行对比，实验结果如表3．15所示，分别得到10．05%和8．86%的线长优化率。 表3．15IBM数据集中各算法构造XSMT的效果对比 电路线网数引脚数 线长平均线长优化率/% SATKNNMDDESATKNN ibm0111507442666100561071560808．078．17 ibm02184297817117251816735915486810．237．46 ibm03216217571015013814798213399910．759．45 ibm0426263895911649981648281497279．269．16 ibm063335412429928970528099825667411．408．66 ibm07443941643693680153680153355568．828．82 ibm084794419818043187941320137194813．889．98 ibm09530391878724183824175433822828．638．44 ibm10642272690005880795891025326449．439．58 均值10．058．86 3．4．3小结 本节设计了3种优化策略用于改进离散差分进化算法，以求解XSMT问题。通过精英克隆选择策略扩大搜索空间，多变异策略扩大变异范围，更好地平衡全局与局部的搜索能力，自适应学习因子策略动态调整保留当前个体边集与全局最优个体边集之间的比例。本节提出的基于多策略优化离散差分进化的XSMT算法，以线长优化和标准差优化为评价指标，与其他相关算法相比均取得了不错的优化结果。同时，XSMTMDDE在引脚数量越大的线网中所体现出的优化能力越强，因此应用在VLSI布线中能够得到优秀的布线结果。 3．5基于文化基因的X结构Steiner最小树算法 文化基因算法(Memetic Algorithm，MA)于1989年由Pablo Moscato首次提出，并逐渐引起各国研究人员的兴趣和关注。在一般遗传算法中，操作的对象是局部搜索得到的优秀种群，避免迂回的无用搜索，以更好地搜索全局最优。而文化基因则是结合全局搜索和局部搜索，在某些问题领域提高了算法的搜索效率，适用于求解NP难问题。近年来，文化基因算法已被成功地应用到了自动化控制、工程优化、机器学习等领域并得到了令人满意的结果。 本节主要介绍一种基于文化基因算法的X结构Steiner最小树构建算法，即MA_XMST算法。首先，使用Prim算法预处理种群，产生初始种群，解决了因引脚数过多而无法收敛的情况。然后，通过修改文化基因的个体更新公式并设计了一种新的文化基因中的操作，使其能应用于离散X结构Steiner树，用于解决VLSI中的布线问题。最后，调整文化基因中的权重因子，能在一定迭代次数下，快速得到一个最优或者较优的拓扑结果。 3．5．1MA_XMST算法 1． MA_XMST算法描述 MA_XMST算法是基于文化基因算法，通过使用Prim算法进行预处理，产生初始种群，并修改文化基因算法中的个体编码方式，同时修改相关操作来实现X结构Steiner最小树构建这个问题的解决。个体的更新公式如式(3．41)所示。 Pti=S(M2(M1(C(Pt-1i,w),m1),m2)) (3．41) 其中，Pti表示第t次迭代以后种群中第i个个体。C表示基于最大并集的交叉操作，M1、M2表示双重变异操作，S表示局部搜索操作。m1、m2、w是权重因子。 MA_XMST算法伪代码如算法3．8所示。 算法3．8 MA_XMST 输入： 所有的线网 Step1．选取一个线网 Step2．用Prim算法产生种群 Step3．遍历种群中每个个体并计算其适应度函数值 Step4．算法终止条件内： 1基于最大并集的交叉操作 2双重变异操作 3局部搜索 4计算适应度函数值 5. 选择下一次迭代的个体 6. 迭代次数加一 Step5算法终止 Step6输出结果 2． 初始化种群 初始化种群一般使用随机的方法，也可以根据已有信息人为选取比较优质的种群个体。在MA_XMST算法中，使用Prim算法初始化种群。这种预处理策略，能加速收敛，并能辅助算法优化拓扑结构。其中，Prim算法的伪代码如3．3．2节中的算法3．2所示。 3． 适应度函数 在X结构Steiner最小树问题中，优化Steiner树的拓扑结构，使其总线长最短是首要目标。因此，在MA_XMST算法中，个体的目标函数值是所有边的长度之和，计算公式如3．2．1节式(3．1)，个体的适应度函数是一个非零常数与目标函数值之和的倒数，其计算公式如式(3．42)所示。 F(Ni)=1C+L(TX) (3．42) 其中，C是一个非零常数，代表的是线网中的单位长度。这样做的目的是防止式（3.42）中分母为0的情况出现，即引脚重合。 4． 混合优化的遗传算子 遗传操作将局部的启发式搜索与全局寻优搜索结合得到混合搜索机制： 首先选出适应度值较优的个体且产生一些交叉作用后的新个体。可能位于新区域的新个体，在下一代局部搜索中被优秀个体取代，然后再进行进一步的全局进化。这种混合优化的策略在进化效率上显然要比单纯的个体间搜索高得多。本节使用是混合优化遗传算子，分别使用基于最大并集的交叉操作和双重变异操作。 1) 基于最大并集的交叉操作 为了加快算法的收敛速度，MA_XMST算法采用最大并集的策略来实现交叉操作，选择当前最优的个体和迭代过程中最优的个体进行交叉。初始阶段是得到两个个体的交集，第二个阶段是将剩下未连接到Steiner树的引脚，随机选择前两者中的一种连接方式连接起来，最终得到交叉操作的结果。例如，有一个5个引脚的线网，图3．13(a)是个体A，图3．13(b)是个体B，基于最大并集的交叉操作后得到的结果如图3．13(c)、图3．13(d)所示。 图3．13基于最大并集的交叉操作 2) 双重变异操作 为了降低造成局部收敛的可能性，避免种群选择的局限性。本算法采用双重变异操作，即两种变异方式来拓展文化基因算法的搜索： 第一种是拐点的变异； 第二种是引脚选取方式的变异。 拐点的变异是改变边的选择方式，从4种选择方式中随机选择一种边选择方式。图3．14是拐点变异操作，线网1的边选择方式从选择2(见图3．14(a))变异成为选择0(见图3．14(b))，从而得到了更优的个体。 图3．14拐点变异操作 引脚的变异是多点变异，改变了X结构Steiner树的拓扑结构。通过不同的拓扑结构来寻优，让MA_XMST算法有较强的搜索能力，使其得到更好的结果。例如，将线网1上的引脚1和引脚2的连接变异成为引脚1和引脚3的连接，得到了不同的拓扑结构，如图3．15所示。 图3．15引脚变异操作 5． 局部搜索 局部搜索的目的是得到局部区域内最优秀的个体。若不采用局部搜索算法，则可能导致算法的局部搜索能力变差，无法得到最优或者较优的结果。在MA_XMST算法中，局部搜索的领域是个体所有边的4种边选择方式，从选择0到选择3。最终得到局部搜索领域中最优的个体，更新种群。局部搜索算法的伪代码如算法3．9所示。 算法3．9 局部搜索算法 输入： 个体的边集 1．E={e} 2．while E!=NULL do 3．for i=0 to choice［i］<4 do 4．NewFitness=calculateFitness(choice［i］); 5．if NewFitness>MaxFitness do 6．MaxFitness=NewFitness; 7．Update(choice［i］); 8．end 9．end 10．End 6． 选择种群 合并父代和子代个体，计算所有个体的适应度值，按照适应度函数值大小排序，选择与种群规模大小相同的优秀个体组成新种群。 3．5．2实验仿真与结果分析 1． 开发环境及数据来源 本节算法采用C++实现，用Visual Studio 2015编写与开发，在Windows 10操作平台上运行，分别对单个线网和多个线网两种测试电路数据进行实验。为了验证预处理策略有效性的实验数据来自文献［5］，并与未采用预处理策略的实验结果进行对比； 为了验证MA_XMST算法的优越性，实验数据采用ISPD98测试数据集，并与文献［8］提出的K近邻算法(KNearest Neighbour，KNN)和文献［14］提出的伪布尔SAT的算法(A pseudo boolean SAT)进行对比。 2． 实验结果分析 1) 预处理策略的有效性证明 为了验证MA_XMST算法所使用的预处理策略的有效性，本节算法设置种群规模为50，最大的迭代次数为200，验证预处理有效性的10组测试用例是单个线网数据集，其引脚数量最少的为8，最多的是1000，每个测试用例均运行10次的本节算法并取线长的平均值。 表3．16给出的是在算法中使用Prim算法和未使用Prim算法预处理种群在相同的运行环境下，通过这10组测试用例，验证预处理策略的有效性。通过使用Prim算法预处理种群生成一个最小生成树，避免了因为引脚数过多造成的解空间过大而不能得到一个收敛结果的情况。 实验结果如表3．16所示，第三列是未使用预处理策略得到的线网线长，第四列是使用预处理策略得到的线网线长，对于任何一个测试用例，预处理策略都产生了优化效果，并且随着引脚数量的增加，使用Prim算法预处理得到的结果优化率显著提高。 表3．16验证预处理策略的有效性 测 试 用 例引脚数未使用预处理使用预处理减少率/% 1817107169181．10 2919273180406．40 31020955196956．01 420480603225732．88 5501278844858062．01 6701807525732968．28 71002151207008667．42 841092626414331884．53 9500124418115633187．44 101000257242022216091．36 均值50．74 对于这10组数据，使用了预处理方案的结果比未使用预处理的结果平均优化了50．74%的布线线长。 2) 与其他算法的实验对比 为了验证MA_XMST算法的优越性，本节算法设置种群规模为50，最大的迭代次数为200，验证算法优越性的测试用例是ISPD98的9组多线网数据集。其中线网数目从11507个增长到64227个，引脚总数从44266个增长到269000个。本节中每个测试用例均运行10次的本节算法并取线长的平均值，最后与KNN和SAT进行比较。 表3．17是本节提出的基于文化基因的X结构Steiner树算法与KNN算法和SAT算法的实验结果对比。本算法对于每个测试用例在线长方面都有较大的优化，几乎每个测试用例都优化了10%以上。最终，MA_XMST算法分别比SAT和KNN平均减少了11．52%和10．24%的布线线长，充分说明基于文化基因的X结构Steiner树算法在处理现实布线中能有较大的优越性。 表3．17与SAT和KNN算法的对比 测试用例线网数目引脚数目SATKNNMA_XMST 减少率/(%) SATKNN ibm01115074426661005610715482310．1310．23 ibm02184297817117251816735915260411．548．82 ibm03216217571015013814798213184812．1810．90 ibm04261638959116499816482814627711．3511．25 ibm063335412429928970528099825354812．489．77 ibm074439416436936801536801532964710．4310．43 ibm084794419818043187941320136869414．6310．77 ibm09530931878724183824175433766099．989．80 ibm106422726900058807958310252373010．9410．18 均值11．5210．24 3．5．3小结 本节提出了基于文化基因的X结构Steiner树算法，并成功应用于VLSI的布线问题。首先，在预处理阶段使用Prim算法处理种群，克服了因为引脚数量过多造成的无法收敛的问题，得到了将近50．74%的优化率。其次，根据X结构Steiner树结构的特点，结合文化基因算法，设计了离散个体更新公式并修改了相应操作，使算法快速收敛。最后，通过实验证明基于文化基因的X结构Steiner树算法的有效性和优越性，在与最近几年提出解决布线问题的SAT和KNN算法相比，分别取得了11．52%和10．24%的优化率。 3．6线长驱动的X结构Steiner最小树算法 3．6．1引言 早期解决Steiner最小树问题的方法大多为精确算法和传统启发式算法，面临复杂度极高和极易陷入局部最优解的难题，而群智能(Swarm Intelligence，SI)技术的高效搜索能力和自组织能力，能够更好地完成Steiner最小树的构建。尤其是粒子群优化算法，其控制参数少、实现简单和优秀的寻优能力在提高Steiner树问题的解的质量方面具有明显优势。然而，由于传统的粒子群优化方法仅通过向种群最优粒子学习来实现粒子的社交过程，使得算法开发强度过大，一旦陷入局部极值，就很难跳出。因此，本节提出了基于社会学习离散PSO的线长驱动X结构Steiner最小树算法(WirelengthDriven Xarchitecture Steiner Minimum Tree algorithm based on Social Learning Discrete Particle Swarm Optimization，SLDPSOWLXSMT)，使得算法能够平衡好开发和探索的强度，从而更好地解决WLXSMT问题。该算法由两个阶段构成。 (1) 社会学习粒子群搜索阶段。该阶段通过PSO技术搜索到一棵令人满意的具有较短线长的XST。首先，使用混沌惯性权重以加强PSO的全局搜索； 其次，提出了一个新的社会学习策略，改变粒子在每次迭代中只向个体历史最优粒子(pbest)或种群最优粒子(gbest)位置靠近的单一学习方式，通过维护样例池不断改变粒子在每次迭代中的学习对象，增强了种群进化的多样性； 最后，变异和交叉算子被融合进粒子的更新公式中以实现PSO的离散化，从而构建一棵理想的X结构Steiner树。 (2) 线长减少阶段。该阶段设计了一个有效的基于局部拓扑优化的策略以减少XST的线长。通过不断调整每个引脚所在的局部最优结构，进一步优化布线树的长度，得到最终的XSMT。 3．6．2算法设计 本节提出的SLDPSOWLXSMT算法首先通过SLDPSO搜索找到一棵令人满意的具有较短线长的XST。在这个阶段，混沌下降变异策略和结合交叉算子的社会学习策略被加入到PSO中，用来增强种群进化的多样性，同时能够平衡算法的开发和探索能力。接着再通过线长减少阶段调整Steiner树的局部最优结构得到最终XSMT。该算法的整体架构如图3．16所示。 图3．16SLDPSOWLXSMT算法的整体架构图 1． SLDPSO搜索阶段 由于XST问题是一个离散问题，SPSO的粒子更新过程不再适用于解决XSMT问题。为此，需要对XSMT问题进行编码，设计针对线长优化的适应度函数，同时变异和交叉算子被融合进粒子的更新公式中以完成PSO的离散化。本节基于混沌搜索和新的社会学习模式，设计了针对WLXSMT问题的社会学习离散PSO算法，并给出了算法实现的细节，即从混沌下降变异策略，基于样例池机制的社会学习策略、粒子编码、适应度函数、粒子更新公式以及该阶段的具体步骤5个方面详细展开。 1) 混沌下降变异策略 惯性权重是影响PSO收敛精度的重要参数，而常数的惯性权重会不利于PSO算法的全局探索。为此，Shi和Eberhart提出了一种有效的参数策略，即线性递减策略。该策略能有效提高解的质量，并被广泛应用在VLSI布线的相关问题中。而文献［17］的工作对惯性权重进行了更为深入的研究，在15种惯性权重的实验对比中，发现混沌惯性权重能够获得最佳效果。 性质3．4混沌搜索是一种具有伪随机性、遍历性和规律性的随机运动，具有不对初始值敏感、计算精度高的特点。 定义3．8Logistic映射利用Logistic映射方程生成一组具有遍历性的随机序列。 zn+1=μ·zn·(1-zn),n=0,1,2,…(3．43) 其中，z∈(0,1)为混沌变量，z的初始值z0≠{0．25,0．5,0．75}，否则最终的随机序列会是周期性的。μ∈［0,4］为控制参数，当μ=4时，Logistic映射将表现出完全的混沌动力学，混沌变量的轨迹在整个搜索空间上分布密集，即其混沌结果分布在区间［0,1］。 SLDPSOWLXSMT采用混沌下降的惯性权重，使得PSO算法在迭代前期进行全局探索，尽可能扩大搜索解的范围，而在迭代后期更倾向于局部搜索使算法快速收敛，同时保持粒子在整个迭代过程中变异的随机性。具体公式如下： ω=(ωinit-ωend)·Maxiter-iteriter+z·ωend (3．44) 其中，ωinit和ωend分别是ω的起始值和结束值，z是混沌变量，遵循式(3．44)，Maxiter和iter分别是算法的最大迭代次数和当前的迭代次数。混沌下降的惯性权重能够在保持原有变化趋势的同时又具有混沌特性。 2) 基于样例池机制的社会学习策略 社会学习在群体智能的学习行为中扮演着重要角色，有利于种群中的个体在不会增加自身试验和错误代价的前提下，从其他个体上学习行为。社会学习粒子群优化(Social Learning Particle Swarm Optimization，SLPSO)是一种改进PSO算法，其中提出的社会学习机制极大地提升了粒子群的全局搜索能力并改善算法性能。在该算法的基础上，文献［21］的研究工作设计了一种单样例学习和均值样例学习来分别代替SLPSO的模仿分量和社会认知分量。但是这些更新公式都不能直接应用在离散问题上。因此，受SLPSO算法的启发，本节设计了一个适用于离散问题的新的社会学习策略以融入粒子的更新公式中，从而提升粒子群优化算法的性能。 定义3．9学习样例池种群S={Xi|1≤i≤M}中所有粒子按适应度值大小升序排列： S={X1,…,Xi-1,Xi,Xi+1,…,XM}，则粒子群EP={X1,…,Xi-1}构成了粒子Xi的学习样例池。 性质3．5不同的粒子，其学习的样例池不同； 同一个粒子，在每次迭代中，其学习的样例池也不一定相同。 性质3．6粒子在每一次的社会学习中，从自身当前的样例池中随机选择一个粒子作为学习对象。特别地，当粒子选择的学习对象是样例池中的第一个粒子X1，则粒子此时学习的是全局最优解XG。 图3．17显示了粒子学习的样例池。五角星是未知的待探索的最优解，粒子XG是目前种群找到的最优解。对粒子Xi来说，圆形粒子是相对落后的粒子，而三角形粒子比Xi更接近全局最优解，具有比Xi更好的适应度值，这些粒子(包括XG)构成了Xi的样例池，其中每一个粒子都有可能成为其社会学习的对象。粒子Xi在每一次更新时会随机选择样例池中的任意一个粒子Xk(1≤k≤i-1) 并学习其经验(即该粒子的历史最优方案XPk)，来完成自身的社会学习过程。这样的社会学习方式，一方面允许粒子在进化过程中通过不断学习不同的优秀个体来提升自己(根据性质3．5可得)，有利于种群的多样化发展； 另一方面，粒子在更换学习对象的过程中也有一定的概率学习到全局最优粒子(根据性质3．6可得)，从而使得算法能够较好地平衡种群的探索与开发。 图3．17粒子的学习样例池示意图 3) 粒子编码 算法采用的边点对的粒子编码策略，详细介绍见3．2．1节。 4) 适应度函数 一个粒子就代表一棵候选Steiner树，粒子的适应度值就反映了Steiner树的质量。由于本节工作考虑的是线长驱动的XSMT问题。因此，设定粒子的适应度值为对应布线树的长度。一棵X结构Steiner树的长度等于这棵树中所有边线段的长度总和，具体计算公式如下： fitFunc=L(TX)=∑ei∈TXl(ei) (3．45) 其中，l(ei)表示布线树TX中边线段ei的长度。 5) 粒子更新公式 由于SPSO算法不能直接应用在XSMT这个离散问题上，因此，本节借助交叉和变异操作来实现SLPSO的离散化，从而更好地解决XSMT问题。在SLDPSOWLXSMT算法中，粒子遵循以下的更新公式: Xti=SF3(SF2(SF1(Xt-1i,ω),c1),c2) (3．46) 其中，ω为惯性权重因子，c1和c2为加速因子，SF1为惯性分量，SF2和SF3分别为个体认知分量和社会认知分量。在SLDPSOWLXSMT中，SF1通过变异操作实现，变异程度决定了多大程度上保留上一次迭代的状态； SF2和SF3通过交叉操作实现，即分别与个体历史最优方案(pbest)和样例池中任意优秀粒子的历史最优方案(kbest)进行部分基因交叉。 SPSO的社会认知分量，是通过与种群最优粒子(gbest)学习来实现的。gbest是种群中所有粒子pbest中最优的一个，这是综合了种群(社会)中所有粒子的学习经验而得出的最佳学习对象。值得注意的是，每一次迭代粒子都以某种概率向gbest学习。这意味着，一旦算法搜寻到一个局部极值，这个局部极值会立即成为这一代中的gbest，是其他所有粒子进行社会学习的对象。而所有粒子同时只向同一个对象学习，很容易陷入局部寻优的僵局，使得在后面的迭代中粒子会反复在局部极值附近寻找最优值。因此，本节将基于样例池的社会学习策略融入离散的PSO中，同时使用混沌下降的惯性权重，以更好地解决WLXSMT问题。 (1) 惯性分量。算法使用SF1表示粒子的惯性分量，通过变异操作实现，表示如下： Wti=SF1(Xt-1i,ω)=Mp(Xt-1i),r1<ω Xt-1i,否则 (3．47) 其中，Wti是变异后的粒子，惯性权重ω决定了粒子进行变异操作的概率，遵循式(3．44)的混沌下降公式，Mp()为针对PSP变换的变异操作，r1是［0,1)区间的随机数。 SLDPSOWLXSMT算法采用两点变异。如果产生的随机数r1<ω，算法将随机选出两条边，更换这两条边的选择方式(选择0~3)，从而达到随机改变布线树拓扑结构的目的； 如果产生的随机数r1≥ω，则保持布线树不变。图3．18给出了一棵含有6个引脚的布线树的变异示意图，布线树下方是粒子的编码(图中未给出粒子适应度值)。从图3．18可以看到，算法随机选择了粒子Xi ： 321 122 253 423 260 673的两条边m1(3，2，1)和m2(2，5，3)，经过SF1操作后，m1和m2的布线方式分别由选择1和选择3变成选择2和选择0。 图3．18SLDPSOWLXSMT算法的变异操作 (2) 个体认知分量。算法使用SF2表示粒子的个体认知分量，通过交叉操作实现，表示如下: Sti=SF2(Wti,c1)=Cp(Wti,XPi),r2d时(见图3．20(c))，由于始终有e(s1，s3) +(e(s1，s2)+e(s2，v1))>e(s1，s3)+e(s3，v1)，所以v2通过选择0连接到v1，即(v2，v1，s3)是最优的结构； 当e(s1，s2) < d时(见图3．20(d))时，很明显，相比X结构，直角结构的布线方式能获得更短的线长，即(v2，v1，s2)是最优结构。 上述分析一方面说明了仅仅依靠X结构或直角结构都不能获得最佳的拓扑，二者的有效结合才能得到更短的线长。另一方面，基于这种思考模式，本节设计了相应的局部拓扑优化策略来进一步优化SLDPSO算法得到的XSMT。 2) 线长优化的具体步骤 性质3．9SLDPSOWLXSMT算法提出的局部拓扑优化策略通过逐一调整线网中所有引脚的局部拓扑结构，能有效减少XST的线长。局部拓扑优化策略的伪代码如算法3．10所示。 假定线网中度数最多的引脚度数为Q，q是用户自定义参数，且满足： 1≤q≤Q。考虑到实际线网结构的复杂性，不建议对引脚的所有邻接边进行调整，尤其是Q很大，并且线网中存在较多的度接近Q的引脚的时候，此时会付出较大的时间代价。因此，局部拓扑优化策略设定最多遍历每个引脚的q条邻接边并进行适当的调整。同时，算法可以通过调整参数q的大小，在优化效果和时间之间做一个折中。q的值越接近Q，优化效果就越好。本节设定q= 0．8×Q 。 算法3．10 局部拓扑优化策略 输入： XST 输出： XSMT Begin 1. // 1．记录XST中每个点的度数及其邻接点列表 2. for each terminal vi in P of XST do 3. Initialize vi．degree=0，vi．adj_list［］=; 4. end for 5. for each edge(vi,vj) of XST do 6. if vi．degree < q then 7. vi．degree +=1; 8. add vi to vj．adj_list［］; 9. end if 10. if vj．degree < q then 11. vj．degree +=1; 12. add vj to vi．adj_list［］; 13. end if 14. end for 15. // 2． 所有点按度降序排列，每个点的邻接点列表中的元素也按照点的度数降序排列 16. Sort(P) in decreasing order according to vi．degree; 17. for each terminal vi in P of XST do 18. Sort(vi．adj_list) in decreasing order according to vi．adj_list［k］．degree;//1≤k≤vi．degree 19. end for 20. // 3．依次优化各个点的局部拓扑结构 21. for each terminal vi in P do 22. for each edge(vi,vi．adj_list［k］) connected to vi do 23. curChoice=getChoice(vi，vi．adj_list［k］); //获取边的连接方式 24. if choice==bestChoice then //如果已经是最优结构，则不处理 25. Continue; 26. else //否则更新当前局部拓扑为最优结构 27. ResetChoice(vi，vi．adj_list［k］，bestchoice); 28. end if 29. end for 30. end for End 布线树中的每个节点都有两个属性： 一个是degree，存储的是这个节点的度，即其邻接点个数； 另一个是邻接点列表adj_list［］，用来存储各个邻接点。该策略的具体实现步骤如下。 步骤1，记录XST中每个点的度数及其邻接点列表。在这一步骤中，算法通过遍历XST的每一条边来记录每个点的度数，并将其邻接点加入对应列表。特别地，对于度大于q的点来说，算法仅仅记录该点的q个邻接点。 步骤2，设置局部拓扑优化的顺序为： 从度数大的点往度数小的点优化。通过将所有点按度数从大到小排列，同时将每个点的邻接点也按度数从大到小排列，来实现先优化密集区域的拓扑结构，再优化稀疏区域的拓扑结构。 步骤3，优化局部拓扑结构。按照步骤2的顺序，依次优化各个点的局部拓扑结构。对于P中的每个点vi，遍历该点的每一条邻接边(vi，vi．adj_list［k］)，其中1≤k ≤vi．degree，并通过调整该条边的选择方式(选择0~3)，用局部最优拓扑替换当前的拓扑结构，若已经是最优结构，则不进行处理。 局部拓扑优化策略通过不断调整每个点的每条邻接边的选择方式，以获得在当前XST拓扑下的局部最优结构，从而优化XST的线长。 3． 算法的流程和复杂度分析 SLDPSOWLXSMT算法由社会学习离散粒子群搜索阶段和线长减少阶段构成。首先，通过基于样例池机制的社会学习粒子群的迭代搜索以寻找一棵较高质量的X结构Steiner树，再利用局部拓扑优化策略对上一阶段的解方案进行线长优化，以得到最终的XSMT。算法的整体流程如图3．21所示。 图3．21SLDPSOWLXSMT算法的整体流程图 引理3．2假设种群大小为M，迭代次数为T，引脚个数为n，则SLDPSOWLXSMT的时间复杂度为O(MT×(Mlog2M+nlog2n))。 证明： (1) SLDPSO搜索阶段。在SLDPSO搜索阶段的步骤3~步骤5中，包含变异与交叉操作、计算适应度和更新样例池。变异和交叉操作的时间复杂度均为常数时间O(1)。布线树线长的计算时间主要由排序时间决定，为O(nlog2n)。由于每一次迭代结束，粒子会进行样例池的更新，消耗的时间为排序所花的时间，即O(Mlog2M)。故算法内部循环的复杂度为O(Mlog2M+nlog2n)。加上外部循环的条件M和T，这一阶段的时间复杂度为O(MT×(Mlog2M+nlog2n))。 (2) 线长减少阶段。该阶段分为3个步骤。步骤1中记录XST中所有点的度数及其邻接点列表所花时间为O(n)。步骤2需要对所有引脚按度排序，所需时间为O(nlog2n)，并且需要对每个引脚的邻接表元素按度排序。由于在本节工作中每个引脚的邻接表元素个数最大不超过4，可忽略这部分的排序时间，则步骤2的总时间复杂度为O(nlog2n)。步骤3中优化所有点的局部拓扑结构时需要遍历每个引脚，时间复杂度为O(n)。因此，这一阶段的时间复杂度为O(nlog2n+2n)，即其近似复杂度为O(nlog2n)。 综上所述，SLDPSOWLXSMT算法的近似时间复杂度为O(MT×(Mlog2M+nlog2n))。 3．6．3实验仿真与结果分析 为了验证本节算法和相关策略的有效性，本节在基准测试电路GEO上开展实验，并给出了详细的实验对比数据。该测试电路的规模包括总引脚数为8~1000的线网。本节算法设置种群大小为100，粒子迭代次数为1000，其余参数与文献［22］设置的参数一致。考虑到粒子群算法的随机性，本节所有实验中的平均值均通过独立运行20次得来。 1． 初始边选择策略的有效性验证 为验证初始化边选择策略的有效性，本节对比了初始边选择为选择0~3(记为4init)和本节算法所采用的初始边选择为选择0或选择1(记为2init)所得到的布线树的线长，如表3．18所示。从表3．18中可以看到，对于所有的测试用例，2init的初始边选择方式相比4init能够取得更好的平均线长，平均优化线长6．762%； 在最优粒子方面，除了测试电路1以外，2init能够获得比4init具有更短线长的最优粒子。很明显，“平均线长”代表了初始种群的质量，而“最优线长”代表了种群中最有潜力的粒子。因此，2init的初始边选择方式能够为算法带来更多优质的初始粒子，从而加快算法找到最优的解方案。 表3．182init初始边选择策略的有效性验证 电路引脚数 最优线长平均线长 4init2init优化率 /%4init2init优化率 /% 181743417506-0．41118939177516．269 2918377180411．83120211182839．540 31019823197030．60321710199448．134 42033874328103．14235624330727．163 55051022491383．69252884493406．702 67059494575473．27261093577215．519 710073271703653．96675104705696．038 84101514511433025．3811531091436836．156 95001640331558884．9651663401564815．927 1010002355072222355．6362371722225426．168 均值3．2086．762 2． SLDPSO方法的有效性验证 为验证SLDPSOWLXSMT算法第一阶段，即基于样例池机制的社会学习DPSO(记为SLDPSOXSMT)方法的有效性，本节将SLDPSOXSMT与文献［4］提出的DPSOXSMT算法进行比较，实验结果如表3．19所示。为了实验的公平，DPSOXSMT算法的数据均是在本节设定的参数下运行得来的，其中惯性权重设置0．95~0．4线性递减。本节比较了20次独立实验中，SLDPSO方法和DPSO方法找到的最佳XSMT的线长、平均线长以及标准差。 表3．19SLDPSOXSMT和DPSOXSMT算法的性能比较 电路引脚数 最优线长平均线长标准差 DPSOSLD PSO优化率 /%DPSOSLD PSO优化率 /%DPSOSLD PSO优化率 /% 1816918169180．00016918169180．000000．00 2918041180410．00018041180410．000000．00 续表 电路引脚数 最优线长平均线长标准差 DPSOSLD PSO优化率 /%DPSOSLD PSO优化率 /%DPSOSLD PSO优化率 /% 31019696196960．00019696196960．000000．00 42032193321930．00032213322070．019111011．29 55047960479530．01448038479820．118833261．45 67056279562780．00256448563410．191983564．73 710068578684860．13368911686970．31118210442．69 84101414271409020．3711418521411430．49923810854．50 95001543651538890．3081547421540560．4432049752．70 1010002207952199550．3802211422202400．40828216740．68 均值0．1210．19932．80 从表3．19可以看出，相对DPSO方法，本节提出的SLDPSO方法在测试电路4~测试电路10上(引脚数为20~1000)取得了线长优化。其中，对电路8(引脚数为410)的优化效果最好，得到的最佳XSMT的线长优化了0．371%、平均线长减少了0．499%以及标准差优化了54．50%。表3．19中的实验数据证明了本节提出的社会学习策略的有效性。 值得注意的是，SLDPSO相对早期的DPSO方法，其标准差大大减少，说明算法的稳定性得到了极大的提升。其一是由于本节算法采用了混沌下降的惯性权重。因为粒子群的惯性保持部分是通过变异操作实现的，而惯性权重的大小决定了变异的概率。单纯的线性递减方式，使得粒子群变异的频率在很大程度上依赖于设定的初始值和结束值，因此会出现在迭代初期变异的频率很高，而在迭代后期变异的频率又很低的情况。由于混沌搜索的伪随机性、遍历性和对不依赖初始值的特点，使得惯性权重的值能较均匀地分布在线性递减的区域中，使得变异的概率相对稳定，同时又能随迭代次数的增长而降低。其二是因为粒子的社会学习通过样例池实现，扩大了学习对象的范围，而DPSO方法只通过学习种群最优粒子(gbest)来进行社会学习。对于种群中落后的粒子来说，由于与gbest的差距较大，它们的一次更新可能产生很大的位置改动，从而导致算法稳定性较差。而通过样例池随机选择学习对象，从一定程度缓解了这种跳跃的情况，从而提高了算法的稳定性。 3． 局部拓扑优化策略的有效性验证 SLDPSOWLXSMT算法提出的局部拓扑优化策略通过逐一调整线网中所有引脚的局部最优拓扑，能有效减少XST的线长。为验证该策略的有效性，本节分别对比了使用该策略前后算法获得的最佳Steiner树的线长、最差Steiner树的线长以及平均线长，如表3．20所示。可以看到，局部拓扑优化策略对50个引脚以上的测试用例有明显优化效果，并且引脚数越多，该策略的优化效果越强。对于1000个引脚的线网来说，该策略能减少2．381%的平均线长，其中针对最不理想的Steiner树，其线长为220629，经过局部拓扑优化之后，线长减少到214950，减少了2．574%。 表3．20局部拓扑优化策略使用前后的实验结果对比 电路引脚数 最佳线长最差线长平均线长 之前之后优化率 /%之前之后优化率 /%之前之后优化率 /% 1816918169180．00016918169180．00016918169180．000 2918041180410．00018041180410．00018041180410．000 31019696196960．00019696196960．00019696196960．000 42032193321930．00032214322140．00032205322050．001 55047960479530．01448032479530．16547977479530．051 67056281562710．01856489563070．32356351562800．125 710068486683350．22169019683350．99168697683470．510 84101409021390821．2911413321391221．5641411431390741．466 95001538891514551．5821541961514411．7861540561514081．719 1010002199702149912．2632206292149502．5742202332149902．381 均值0．5390．7400．625 另外，可以很明显看到，对于所有的测试用例，最差XST的线长减少率均高于最佳XST的线长减少率，并且最差的XST经过局部拓扑优化后，有可能得到比最佳XST更短的线长。例如，对于测试电路9来说，由SLDPSO搜索得到的最佳XST线长为153889，最差的为154196，而在经过该优化策略后，最差的XST线长为151441，比最好的XST优化后的线长151455还要短。表3．20中的实验数据证明了局部拓扑优化策略在减少线长上的有效性。 4． 与现有SMT算法的对比 为验证本节提出的SLDPSOWLXSMT算法的有效性，本节先后对比了SLDPSOWLXSMT算法与现有的SMT算法的线长优化能力，包括RSMT和XSMT算法。表3．21给出了本节算法与文献［3］提出的DPSO(R)和文献［22］提出的HTSPSO(R)两种RSMT算法的线长优化能力的对比。表中数据显示，在测试电路1~电路10上，DPSO(R)、HTSPSO(R)和本节提出的SLDPSOWLXSMT算法得到的SMT的线长平均比为1．114∶1．089∶1。 其中，针对引脚数量最小的测试电路1，DPSO(R)和HTSPSO(R)算法求得的SMT线长分别比本节算法长6．0%和4．6%； 针对规模最大的测试电路10，DPSO(R)算法得到的SMT线长是本节算法的1．141倍，HTSPSO(R)算法得到的SMT线长比本节算法长11．6%。并且观察表3．21中的数据可以看到，针对引脚数越多的线网，本节算法得到的Steiner最小树线长优化越明显。 表3．21SLDPSOWLXSMT和两种RSMT算法的线长优化能力对比 电路引脚数 平均线长归一化值 DPSO(R)HTS PSO(R)本节 算法DPSO(R)HTS PSO(R)本节 算法 181793117693169181．0601．0461．000 292050319797180411．1361．0971．000 3102191021226196961．1121．0781．000 4203572335072322051．1091．0891．000 5505338352025479531．1131．0851．000 6706198761129562801．1011．0861．000 71007601674416683471．1121．0891．000 84101565201536721390741．1251．1051．000 95001702731665921514081．1251．1001．000 1010002452012398242149901．1411．1161．000 均值1．1141．0891．000 同时，本节也将提出的算法与3种性能较好的XSMT算法进行线长优化能力对比，包括文献［23］的DDE(X)算法、文献［4］的DPSO(X)算法和文献［22］的HTSPSO(X)算法。表3．22和表3．23分别对比了上述算法所求XSMT的平均线长和标准差，这两个评价指标分别反映了算法的线长优化能力和稳定性。 表3．22SLDPSOWLXSMT和3种XSMT算法的平均线长优化能力对比 电路引脚数 平均线长归一化值 DDE (X)DPSO (X)HTS PSO(X)本节 算法DDE (X)DPSO (X)HTS PSO(X)本节 算法 18169111691816921169181.0001.0001.0001.000 29180391804118023180411.0001.0000.9991.000 310194691969619397196960.9881.0000.9851.000 420323423221332063322021.0041.0000.9961.000 550486684803848027479531.0151.0021.0021.000 670572555644856350562781.0171.0031.0011.000 7100706866891168625683471.0341.0081.0041.000 841014711514418521408981390741.0581.0201.0131.000 95001596721547421537081514081.0551.0221.0151.000 1010002323592211422199542149901.0811.0291.0231.000 均值1.0251.0081.0041.000 表3．23SLDPSOWLXSMT 和3种XSMT算法的标准差对比 电路引脚数 标准差归一化值 DDE (X)DPSO (X)HTS PSO(X)本节 算法DDE (X)DPSO (X)HTS PSO(X)本节 算法 18340160—-—— 2941000—-—— 310133000—-—— 42016511311016．011．103．011．000 55082783940———— 6701135981451479．636．8910．161．000 7100180218215014130．9413．2210．861．000 8410361523818836100．806．645．231．000 950036882041814680．214．443．931．000 101000408928218434119．958．285．401．000 均值87．926．766．431．000 如表3．22所示，3种XSMT算法与本节算法产生的XSMT线长平均比为1．025∶1．008∶1．004∶1，说明本节算法总体上优于这3种XSMT算法。与DDE(X)算法相比，在引脚数为20及以上的线网测试集中，本节算法具有明显的线长优化。其中，针对电路10，SLDPSOWLXSMT算法产生的Steiner树线长仅为214990，而DDE(X)产生的线长为232359，比本节算法得到线长多出8．1%。与DPSO(X)算法相比，本节算法能够在所有测试数据上取得相同或者更短的线长。而HTSPSO(X)算法针对引脚数为20及以下的线网测试集来说，比本节算法略胜一筹，但在大规模线网中，SLDPSOWLXSMT算法能够获得更短的线长。综合分析，本节算法较上述3种XSMT算法，在电路5~电路10上有明显的线长优化，并且线网规模越大，SLDPSOWLXSMT算法的线长优化能力越强。特别地，对于测试电路10，DDE(X)、DPSO(X)和HTSPSO(X)算法得到的线长比本节算法长8．1%、2．9%和2．3%。可见，SLDPSOWLXSMT算法具有较强的线长优化能力，尤其针对大规模线网，效果显著。 在稳定性方面，SLDPSOWLXSMT算法表现出明显优势。如表3．23所示，在电路1~电路3和电路5上，本节算法能够将标准差降到0，而对于其他测试用例来说，DDE(X)、DPSO(X)、HTSPSO(X)算法与本节算法产生的XSMT线长标准差平均比为87．92∶6．76∶6．43∶1。特别地，SLDPSOWLXSMT算法在测试电路7(100个引脚)上表现出最强的稳定性，而上述3种算法的实验结果波动性较大，其标准差分别是本节算法的130．94倍、13．22倍和10．86倍。 3．6．4小结 本节针对VLSI布线中线长驱动的Steiner最小树问题，提出了一个基于SLDPSO的XSMT算法。算法首先采用X结构作为Steiner树边的连接方式以充分利用布线资源。其次，为了克服SPSO算法容易陷入局部极值的不足，在粒子群搜索阶段使用混沌下降的惯性权重并结合变异算子实现PSO的惯性部分，以保持粒子在整个进化过程中变异的随机性，增强了算法的全局搜索能力； 设计了一个基于样例池机制的社会学习策略并结合交叉算子实现PSO的社会认知部分以拓宽粒子的学习范围，从而保持种群进化的多样性。最后，在线长减少阶段，设计了一个局部拓扑优化策略，通过逐一调整线网中引脚的局部最优拓扑来进一步优化Steiner树的线长。实验证明，本节提出的SLDPSO方法具有较强的全局搜索能力和算法稳定性，从而更好地解决Steiner树问题。 3．7本章总结 本章主要介绍了X结构Steiner最小树算法的基本原理以及多种的研究方法并提出了5种有效的X结构Steiner最小树算法： 基于离散PSO的X结构Steiner最小树构建算法、基于离散差分进化的X结构Steiner最小树算法、基于多策略优化离散差分进化的X结构Steiner最小树算法、基于文化基因的X结构Steiner最小树算法、线长驱动的XSMT算法，详细描述了算法原理后在每节实验部分详细列出了与多个先进算法的实验对比结果，证实了本章提出算法的有效性。 参 考 文 献 ［1］Garey M R,Johnson D S.The rectilinear Steiner tree problem is NPcomplete［J］.SIAM Journal on Applied Mathematics，1977，32(4)： 826834. ［2］Jacob T P,Pradeep K.A multiobjective optimal task scheduling in cloud environment using cuckoo particle swarm optimization［J］.Wireless Personal Communications，2019，109(1)： 315331. ［3］Liu G G，Chen G L,Guo W Z，et al.DPSObased rectilinear Steiner minimal tree construction considering bend reduction［C］//2011 Seventh International Conference on Natural Computation，2011，11611165. ［4］Liu G,Chen G，Guo W.DPSO based octagonal steiner tree algorithm for VLSI routing［C］//2012 IEEE Fifth International Conference on Advanced Computational Intelligence(ICACI).IEEE，2012： 383387. ［5］Zachariasen M. GeoSteiner Homepage，2003.［Online］.Available： http： //www.diku.dk/ geosteiner. ［6］Coulston C S. Constructing exact octagonal Steiner minimal tree［C］//Proceeding of the 13th ACM Great Lakes Symposium on VLSI.New York，NY，USA： ACM Press，2003，2829. ［7］Beasley,J.E.ORLibrary： Distributing Test Problems by Electronic Mail［J］.Journal of the Operational Research Society，1990，41(11)： 10691072. ［8］Kundu S,Roy S，Mukherjee S.Knearest neighbour(KNN) approach using SAT based technique for rectilinear steiner tree construction［C］//2017 Seventh International Symposium on Embedded Computing and System Design(ISED)，Durgapur，India： IEEE,2017： 15. ［9］Epitropakis M G,Tasoulis D K，Pavlidis N G，et a1.Enhancing differential evolution utilizing proximitybased mutation operators［J］.IEEE Transactions on Evolutionary Computation，2011，15(1)： 99119. ［10］刘漫丹. 文化基因算法(Memetic Algorithm)研究进展［J］.自动化技术与应用，2007，26(11)： 14. ［11］谭立状,贠国潇,张家华.采用基于遗传算法的文化基因算法求解TSP问题［J］.科技视界,2016(05)： 6264. ［12］许晶,陈建利.求解边坡最小安全系数的混合文化基因算法［J］.福州大学学报(自版),2017,45(04)： 559565. ［13］张亚娟,刘寒冰,靳宗信.一种解决VLSI布局问题的文化基因算法［J］.科技通报,2013,29(12)： 154156. ［14］Kundu S，Roy S,Mukherjee S.Sat based rectilinear steiner tree construction［C］//2016 2nd International Conference on Applied and Theoretical Computing and Communication Technology(iCATccT)，Bengaluru，India： IEEE，2016： 623627. ［15］Chen X,Liu G，Xiong N，et al.A survey of swarm intelligence techniques in VLSI routing problems［J］，IEEE Access，2020，8： 2626626292. ［16］Huang X,Liu G，Guo W，et al.Obstacleavoiding algorithm in Xarchitecture based on discrete particle swarm optimization for VLSI design［J］.ACM Transactions on Design Automation of Electronic Systems，2015，20(2)： 128. ［17］Bansal J C,Singh P K，Saraswat M，et al.Inertia weight strategies in particle swarm optimization［C］//2011 Third World Congress on Nature and Biologically Inspired Computing.IEEE，2011： 633640. ［18］Xu X，Rong H,Trovati M，et al.CSPSO： chaotic particle swarm optimization algorithm for solving combinatorial optimization problems［J］.Soft Computing，2018，22(3)： 783795. ［19］Feng Y，Teng G F，Wang A X，et al.Chaotic inertia weight in particle swarm optimization［C］//The Second International Conference on Innovative Computing，Informatio and Control.IEEE，2007： 475475. ［20］Cheng R，JIN Y. A social learning particle swarm optimization algorithm for scalable optimization［J］.Information Sciences，2015，291： 4360. ［21］Zhang X，Wang X，Kang Q，et al.Differential mutation and novel social learning particle swarm optimization algorithm［J］.Information Sciences，2019，480： 10929. ［22］Liu G，Chen Z，Zhuang Z,et al.A unified algorithm based on HTS and selfadapting PSO for the construction of octagonal and rectilinear SMT［J］.Soft Computing，2020，24(6)： 39433961. ［23］Wu H，Xu S,Zhuang Z，et al.Xarchitecture Steiner minimal tree construction based on discrete differential evolution［C］//The International Conference on Natural Computation，Fuzzy Systems and Knowledge Discovery.Springer，Cham，2019： 433442.