(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111185378.X (22)申请日 2021.10.12 (71)申请人 福州大学 地址 350108 福建省福州市闽侯县福州大 学城乌龙江北 大道2号福州大 学 (72)发明人 刘耿耿　周茹平　郭文忠　陈国龙　 (74)专利代理 机构 福州元创专利商标代理有限 公司 35100 代理人 陈明鑫　蔡学俊 (51)Int.Cl. G06F 30/394(2020.01) G06F 30/398(2020.01) G06F 30/25(2020.01) G06F 30/27(2020.01) G06N 3/00(2006.01)G06F 111/06(2020.01) G06F 115/06(2020.01) (54)发明名称 基于两阶段竞争粒子群优化的时延驱动 XSMT构建方法 (57)摘要 本发明涉及一种基于两阶段竞争粒子群优 化的时延驱动XSMT构建方法。 该方法包括如下四 种有效策略： （1） 竞争粒子群优化。 使用多目标粒 子群优化算法同时优化线长与最大源汇路径， 并 加入竞争机制选择粒子的学习对象， 提高种群多 样性， 减少计算代价。 （2） 两阶段学习策略。 粒子 通过边学习与点学习更好地平衡算法的探索与 开发能力。 （3） 混合交叉策略。 针对不同粒子使用 不同交叉策略， 进 一步提高算法收敛质量。 （4） 离 散化框架的设计。 结合变异交叉算子， 设计合理 的目标函数与粒子编码方式， 实现了算法的离散 化， 更好地解决离散型时延驱动Steiner最小树 问题。 权利要求书3页 说明书9页 附图3页 CN 113919280 A 2022.01.11 CN 113919280 A 1.一种基于两阶段竞争粒子群优化的时延驱动XSMT构建方法， 其特征在于， 包括如下 步骤： 步骤S1、 设计目标函数以表示Steiner树的线长和最大源汇距离， 使用边点对编码策略 对每棵Stei ner树进行编码； 步骤S2、 在进行Steiner树的线长和最大源汇路径寻优时， 首先使用快速非支配排序以 及基于拥挤度计算的方法， 求得大小为10的精英粒子池， 并在精英池中使用竞争机制求得 赢家作为当前 粒子的学习对象； 步骤S3、 在迭代学习的寻优过程中， 使用多目标粒子群优化算法进行Steiner树的线长 和最大源汇路径的寻优， 并且重新设计多目标粒子群优化算法的框架， 设计两阶段学习 策 略， 在两阶段学习策略第一阶段， 即边学习阶段， 使用针对边结构的交叉操作， 粒子学习对 象为其个体历史最优以及竞争选出 的赢家粒子， 通过边学习， 粒子学习了优秀个体的部分 拓扑结构； 在两阶段学习策略的第二阶段， 即点学习阶段， 使用针对点选择的变异交叉操 作， 其中变异操作随机改变粒子的部分边的伪Steiner 点选择， 交叉操作学习对象同样为个 体历史最优以及竞争选出 的赢家粒子， 交叉操作使粒子学习优秀粒子的部分点选择； 在点 学习阶段中设计混合交叉策略， 对于质量较好的粒子使用多点交叉方式， 使得这部分粒子 以预定概率学习优秀粒子的部分基因； 对质量较差的粒子使用均匀交叉策略， 使得这部分 粒子学习优秀粒子的全部基因。 2.根据权利要求1所述的基于两阶段竞争粒子群优化的时延驱动XSMT构建方法， 其特 征在于， 步骤S1中， 目标函数构建过程如下： 时延驱动X结构Steiner最小树作 为一个多目标优化问题， 需要同时优化最大源汇路径 和总线长， 因此设计两个优化目标： 总线长和半径； 总线长代表这棵布线树的所有边线段长 度之和， 半径代表布线树中最大源汇路径上 的边线段长度之和； 将总线长和半径函数分别 表示为fwl和fpl， 其计算公式如下： 其中， ek指布线树T中的第k条边线段， ej指从源点s0到汇点si的路径上的第j条边线段。 3.根据权利要求2所述的基于两阶段竞争粒子群优化的时延驱动XSMT构建方法， 其特 征在于， 步骤S1中， 使用边 点对编码策略对每棵Stei ner树进行编码的方式如下： 考虑Steiner树的特点， 边点对编码方式以边为单位表示布线树， 树中的一条边由其边 两端的引脚及引脚间的PSP 选择方式组成， 为了连接线网中的n个引脚以构成布线树T， 需要 n‑1条边， 每 一条边由编码串(estart,eend,pspc)表示， 代表该边中PSP以pspc的选择方式接引 脚estart和引脚eend， 所以， 为了表示T的所有边， 需要 3×(n‑1)的编码长度， 另外， 考虑到时延 驱动X结构Steiner最小树的两个优化目标， 再增加两位表示该Steiner树的线长代价和半 径代价， 因此T的完整编码串长度为3 ×(n‑1)+2。 4.根据权利要求1所述的基于两阶段竞争粒子群优化的时延驱动XSMT构建方法， 其特 征在于， 步骤S2具体实现如下： 首先， 通过快速非支配排序以及基于拥挤度距离计算在种群中求得一个大小为t 的精权　利　要　求　书 1/3 页 2 CN 113919280 A 2英池X＝{x0,x1,...,xt}， 并随机选择其中两个精英粒子xa、 xb竞争， 竞争方式是通过比较xa 及xb与当前粒子形成夹角的大小， 夹角较小的为 竞争赢家， 夹角较大的则为输家。 5.根据权利要求1所述的基于两阶段竞争粒子群优化的时延驱动XSMT构建方法， 其特 征在于， 步骤S3中， 重新设计的多目标 粒子群优化 算法的粒子遵循以下 更新公式： 其中， ω为惯性权重， c1和c2为加速因子， iter为当前迭代次数， threshold为设定的迭 代阈值， 当迭代次数小于阈值， 则执行第一阶段的更新学习操作， 迭代次数大于阈值则执行 第二阶段的更新 学习操作， 其中， EF1和EF2分别代表边 学习阶段的历史引导分量和精英引导 分量， PF1、 PF2和PF3分别代表点学习阶段的自我引导分量、 历史引导分量和精英引导分量； (1)边学习阶段 1)历史引导分量 通过引入针对边学习的交叉操作实现EF1分量， 表示如下： 其中， Cu()是边交叉操作， 是该粒子的历史最优解， r1是[0,1)内的随机数， 经过 EF1操作后得到粒子为 如果产生的随机数r1<c1， 粒子执行边交叉操作， 否则， 维持粒子当前状态； 边交叉操作 的具体步骤如下： 1)对于当前粒子 对应的Steiner树， 确定其边集合为E＝{e1,e2,..., en‑1}， 其学习对象 对应的Steiner树的边集合为E'＝{e'1,e'2,...,e'n‑1}； 2)判断并保存 两棵树的相同边集合及不同边集合， 其中相同边作为新的粒子 的初始边； 3)不断从不同 边集合随机挑选边加入新粒子， 直到构建出一棵完整合法的Steiner树， 这个过程中使用并 查集的方法 保证布线树 不出现环路； 2)精英引导分量 通过EF2完成粒子的精英引导分量， 表示如下： 其中， 是通过竞争得到的赢家 精英粒子； (2)点学习阶段 1)自我引导分量 通过引入针对点学习的变异操作实现PF1分量， 表示如下： 其中， Mp()是点变异操作， r1是[0,1)内的随机数， 经过PF1操作后得到粒子为 Wit；权　利　要　求　书 2/3 页 3 CN 113919280 A 3