基于改进支配准则的高维多目标进化方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115983174A(43)申请公布日2023.04.18(21)申请号202211736470.5(22)申请日2022.12.30(71)申请人福州大学地址350108福建省福州市闽侯县福州大学城乌龙江北大道2号福州大学(72)发明人刘耿耿陈子阳鲁任裴镇宇(74)专利代理机构福州元创专利商标代理有限公司35100专利代理师郭东亮蔡学俊(51)Int.Cl.G06F30/337(2020.01)G06N3/126(2023.01)权利要求书3页说明书8页附图1页(54)发明名称基于改进支配准则的高维多目标进化方法(57)摘要本发明提出基于改进支配准则的高维多目标进化方法，用于优化超大规模集成电路物理设计的布线设计，包括以下步骤；步骤一、根据定义的收敛性指标保证非支配解集的收敛性，并结合了基于遗传算法小生境的自适应参数来控制解集的多样性，通过最小化MOP来优化布线设计的半径目标和线长目标，改进支配准则；步骤二、设计收敛性指标与多样性指标，使两者共同构成动态适应度函数，自适应地保留具有较好收敛性和多样性的个体，以进行MaOEA‑IDR环境选择；步骤三、提出能在高维空间中兼顾柯西算子的全局搜索能力和高斯算子的局部探索能力的自适应t分布交叉算子，使t分布交叉算子ASDX自适应；本发明能有效解决超大规模集成电路物理设计的布线问题。CN115983174ACN115983174A权利要求书1/3页1.基于改进支配准则的高维多目标进化方法，用于优化超大规模集成电路物理设计的布线设计，其特征在于：包括以下步骤；步骤一、根据定义的收敛性指标保证非支配解集的收敛性，并结合了基于遗传算法小生境的自适应参数来控制解集的多样性，通过最小化MOP来优化布线设计的半径目标和线长目标，改进支配准则；步骤二、设计收敛性指标与多样性指标，使两者共同构成动态适应度函数，自适应地保留具有较好收敛性和多样性的个体，以进行MaOEA‑IDR环境选择；步骤三、提出能在高维空间中兼顾柯西算子的全局搜索能力和高斯算子的局部探索能力的自适应t分布交叉算子，使t分布交叉算子ASDX自适应。2.根据权利要求1所述的基于改进支配准则的高维多目标进化方法，其特征在于：所述步骤一采用以下方法，方法A1、最小化MOP，具体为：在超大规模集成电路的布线问题中，综合考虑半径和线长这两个目标，令最小化MOP问题表示如下：2其中，x＝(x1,x2,...,xn)表示取n个布线可行解，Ω是解空间；F:Ω→R组成两个目标函数，R2是目标空间；对于两个决策空间中的两个候选解x1和x2，当且仅当fi(x1)≤fi(x2)且fi(x1)＜fi(x2)时，称x1支配x2；若候选解x1不被其他任意一个候选解所支配，则称候选解x1为帕累托最优解；所有Pareto最优解所构成的集合被称为帕累托最优解集(ParetooptimalSet,PS)，其在目标空间上的映射被称为帕累托前沿(ParetoFront,PF)；函数f1(x)是布线的线长计算公式，其计算过程如下所示：f1(x)＝(∑e∈xWLe)‑WLr公式二；其中，e表示两个引脚之间的边，WLe表示e的线长，WLr表示重复边的线长；函数f2(x)是布线的半径计算公式，其计算过程如下所示；f1(x)＝(∑e∈xWLe)‑WLr公式三；其中，p表示引脚，leaf(x)表示布线解x生成树中的叶子节点的集合，lp表示从源点到引脚p的路径；方法A2、改进支配准则IDR：IDR判断解之间的支配关系的评判依据是以收敛指标为主，目的是增强种群的收敛性；为了提高群体的多样性，将各解按余弦相似度分到各自的小生境内；IDR利用定制的小生境技术来均衡非支配解集的收敛性和多样性，具体为，在IDR中，候选解x支配候选解y，当且仅当：Con(x)·λ＜Con(y)公式四；其中，Con(x)是收敛性指标，λ为自适应参数，计算公式如下：2CN115983174A权利要求书2/3页其中，是个体的小生境大小，θ(x,y)为解之间的夹角，计算公式如下：小生境大小的不同取值会对种群的收敛性与多样性产生影响；若过小，易使IDR支配的非支配解集收敛性欠佳；若过大，则会使IDR支配的非支配解集多样性欠佳；为此参数被设置为下列集合P中第|P|/2小的不重复角度：3.根据权利要求2所述的基于改进支配准则的高维多目标进化方法，其特征在于：所述步骤二采用以下方法；方法A3、适应度函数计算，提出同时兼顾收敛性指标和多样性指标的适应度函数，具体为：种群中个体x的动态适应度函数Fitness(x)以及自适应参数的计算方式以下述公式九、公式十表示：Fitness(x)＝α·RCon(x)+(1‑α)·RDiv(x)公式九；其中，Con(x)是收敛性指标，计算方