1.一种基于帕雷托支配的MPRM电路多目标优化方法,其特征在于包括以下步骤:
(1)读取代表电路结构的函数表达式:
其中,n表示函数f(xn‑1,xn‑2,...,xk,...,x0)的输入变量数,(xn‑1,xn‑2,...,xk,...,x0)为函数f(xn‑1,xn‑2,...,xk,...,x0)的n个输入变量,xk为函数f(xn‑1,xn‑2,...,xk,...,x0)的第k+1个输入变量,k=0,1,2,...n‑1,∏为与运算符号,ai是第i个最大项系数,且ai∈{0,
1},i为最大项序数,用二进制表示为in‑1in‑2…ik…i0,mi表示第i个最大项,其符号表示形式为 式中 的出现形式和ik相关,若ik=1, 若ik=0,其中 为xk的反变量;
(2)利用极性转换方法将表示电路结构的函数表达式(1)转换为P极性的MPRM表达式:
其中,P为极性值,用三进制表示为pn‑1pn‑2...pg...p0,pg为极性值P第g+1位上的数,g=
0,1,2,...n‑1,⊙∏为同或运算符,Sj表示第j个或项,dj为第j个或项系数,dj∈{0,1},当dj=0时,表示Sj在MPRM表达式中出现,当dj=1时,表示(1+Sj)在MPRM表达式中出现,j为或项序数,j用二进制表示为jn‑1jn‑2…jg…j0,其中xg与pg和jg的关系为:当pg=0,jg=0或1时,xg以原变量的形式出现;当pg=1,jg=0或1时,xg以反变量的形式出现;当pg=2,jg=1时,xg以反变量的形式出现;当pg=2,jg=0时,xg以原变量的形式出现;
(3)构建P极性的MPRM表达式对应的MPRM电路的面积函数与功耗函数,将面积函数采用式(3)表示为:
式(3)中,Earea表示P极性下MPRM电路的面积, 为dj的反变量, 为jg的反变量;
功耗函数采用式(4)表示为:
式(4)中,Epow表示P极性下MPRM电路的功耗,Vdd表示MPRM电路的电源电压,fclk表示MPRM电路的时钟频率,另外,将MPRM电路分解为门电路后,MPRM电路由XNOR门和OR门构成,将MPRM电路中XNOR门和OR门的数量之和记为N,将MPRM电路分解得到的XNOR门和OR门均称为MPRM电路的门,MPRM电路分解得到的N个门的顺序随机排列,其中, 表示MPRM电路的第s个门的输出负载电容, 表示MPRM电路的第s个门的开关活动性,s=1,2,3…N;
(4)将MPRM电路面积和功耗优化的各参数与多目标三值多样性粒子群算法的各参数进行关联:将P极性的MPRM表达式中输入变量数n定义成粒子群的搜索空间维数,将P极性的MPRM表达式中的极性定义为粒子群的粒子,将P极性的MPRM表达式中极性的极性值P的三进制数定义为粒子位置;设定粒子群中粒子的数量为D,D为大于等于50且小于等于100的整数,最大迭代数为T,T为大于等于100且小于等于150的整数;
(5)对粒子群进行初始化,得到第0代粒子群,具体为:随机初始化粒子群中各粒子的速度、位置和每个粒子的个体最优位置,将初始化后的粒子群称为第0代粒子群;
(6)设定粒子速度的最小边界值,将其记为vmin,令vmin=0,设定粒子速度的最大边界值,将其记为vmax,令vmax=6.0,设定粒子位置的最小边界值,将其记为xmin,令xmin=2.0,设定粒子位置的最大边界值,将其记为xmax,令xmax=3.0;
(7)构建用于存放全局最优粒子的外部集,对外部集进行初始化,具体过程为:
S1、构建第0代边界粒子群:对第0代粒子群中每个粒子的速度和位置进行判定操作后得到第0代边界粒子群,判定操作具体方式为:如果该粒子的速度大于等于0且小于等于6,则其速度保持不变,反之,将其速度减少为当前速度的一半,如果该粒子的位置大于等于xmin且小于等于xmax,则其位置保持不变,反之,将其位置修改为xmin;
S2、假设两个粒子,将某一粒子的位置映射为极性后,该极性下MPRM电路的面积称为该粒子的面积,该极性下MPRM电路的功耗称为该粒子的功耗,设定支配规则:将两个粒子分别称为粒子A和粒子B,如果粒子A的面积≤粒子B的面积并且粒子A的功耗≤粒子B的功耗,则认为粒子A支配粒子B,如果粒子A的面积>粒子B的面积并且粒子A的功耗>粒子B的功耗,则认为粒子A被粒子B支配,如果粒子A的面积≤粒子B的面积且粒子A的功耗>粒子B的功耗或者粒子A的面积>粒子B的面积且粒子A的功耗≤粒子B的功耗,则认为粒子A与粒子B不相关;
S3、构造第0代非支配集,对第0代非支配集进行赋值,具体为:
S3‑1、采用第0代边界粒子群中的所有粒子构成第0代非支配粒子群;
S3‑2、从当前非支配粒子群中随机选择一个粒子,将该粒子的面积和功耗分别与当前非支配粒子群中其他粒子面积和功耗进行比较,根据支配规则判定该粒子与其他粒子的关系,如果该粒子支配其他任意粒子,则将该粒子放入非支配集,完成第0代非支配集的赋值,如果该粒子支配其他粒子中一部分粒子,且其他粒子中另一部分粒子支配该粒子或者与该粒子不相关,则进入步骤S3‑3;
S3‑3、将当前非支配粒子群中该粒子支配的其他粒子中一部分粒子删除,保留另一部粒子,得到更新后的非支配粒子群,将更新后的非支配粒子群作为当前非支配粒子群,如果当前非支配粒子群中只存在一个粒子,则将该粒子放入非支配集,完成第0代非支配集的赋值,否则返回步骤S3‑2;
S4、将第0代非支配集中的粒子存放到外部集中,完成外部集的初始化;
(8)将当前外部集中粒子的位置作为粒子群初始的全局最优位置;
(9)设定迭代次数,将其记为t,对t进行初始换,令t=1;
(10)对粒子群进行第t代迭代更新,具体过程为:
A、采用三值多样性粒子群中粒子的运动方程式对第t‑1代粒子群中各粒子的速度和位置进行更新,得到第t代粒子群,三值多样性粒子群中粒子的运动方程式如式(5)至式(7)所示:xfd(t)=round(Sfd+2×σ×randx()) (6)其中,c1、c2和c3为学习因子,c1=c2=c3=1.5,r1、r2和r3是大于等于0且小于等于1的随机数,w为惯性权重, 式中wstart表示初始权重,wend表示最终权重,初始惯性权重wstart=0.9,终止惯性权重wend=0.4;vfd(t)表示第t代更新完成后第f个粒子的速度,xfd(t)表示第t代更新完成后第f个粒子的位置,f=1,2,…,D,当t=1时,xfd(t‑1)表示第f个粒子的初始位置,pmd(t‑1)表示粒子群初始的全局最优位置,pnd(t‑1)表示粒子群中随机任一粒子的初始位置,pfd(t‑1)表示第f个粒子初始的个体最优位置,vfd(t‑1)表示第f个粒子的初始速度,当t≥2时,xfd(t‑1)表示第t‑1代离子群中第f个粒子的位置,pfd(t‑1)表示在第t‑1代粒子群中第f个粒子的个体最优位置,pnd(t‑1)表示第t‑1代粒子群中随机任一粒子的位置,pmd(t‑1)表示第t‑1代粒子群的全局最优位置,vfd(t‑1)表示第t‑1代粒子群中第f个粒子的速度,e表示自然对数的底,σ为权值且σ=0.2,randn()为标准正态分布函数,round()表示四舍五入取整,上式(5)中,当计算得到的xfd(t)为大于2的整数时,令xfd(t)=2,当计算得到的xfd(t)为小于0的整数时,令xfd(t)=0,当计算得到的xfd(t)为大于等于1且小于等于2的整数时,xfd(t)的取值为其计算值;
B、对外部集进行第t代更新,具体过程为:
W1、构建第t代边界粒子群:对第t代粒子群中每个粒子的速度和位置进行判定操作后得到第t代边界粒子群,判定操作具体方式为:如果该粒子的速度大于等于0且小于等于6,则其速度保持不变,反之,将其速度减少为当前速度的一半,如果该粒子的位置大于等于xmin且小于等于xmax,则其位置保持不变,反之,将其位置修改为xmin;
W2、构造第t代非支配集,对第t代非支配集进行赋值,具体为:
W2‑1、采用第t代边界粒子群中的所有粒子构成第t代非支配粒子群;
W2‑2、从当前非支配粒子群中随机选择一个粒子,将该粒子的面积和功耗分别与当前非支配粒子群中其他粒子面积和功耗进行比较,根据支配规则判定该粒子与其他粒子的关系,如果该粒子支配其他任意粒子,则将该粒子放入非支配集,完成第t代非支配集的赋值,如果该粒子支配其他粒子中一部分粒子,且其他粒子中另一部分粒子支配该粒子或者与该粒子不相关,则进入步骤W2‑3;
W2‑3、将当前非支配粒子群中该粒子支配的其他粒子中一部分粒子删除,保留另一部粒子,得到更新后的非支配粒子群,将更新后的非支配粒子群作为当前非支配粒子群,如果当前非支配粒子群中只存在一个粒子,则将该粒子放入非支配集,完成第t代非支配集的赋值,否则返回步骤W2‑2;
W3、更新外部集,具体为:
根据支配规则确定第t代非支配集中的粒子与当前外部集中的粒子的支配关系,如果第t代非支配集中的粒子被当前外部集中的粒子支配或者两者不相关,则对当前外部集不做处理,完成外部集的第t代更新,如果第t代非支配集中的粒子支配当前外部集中的粒子,则将当前外部集中的粒子删除,并将第t代非支配集中的粒子存放到当前外部集中,完成外部集的第t代更新;
C、将当前外部集中粒子的位置作为第t代粒子群的全局最优位置;
D、将第t代粒子群中每个粒子的位置映射为极性,采用式(3)和式(4)分别计算第t代迭代更新后每个极性下MPRM电路的面积和功耗;
E、将第t代粒子群中每个粒子的位置映射为极性计算得到的面积和功耗与该粒子在第t‑1代更新完成后的个体最优位置映射为极性计算得到的面积和功耗值进行比较,如果第t代粒子群中粒子位置对应极性下计算得到的面积≤第t‑1代该粒子个体最优位置对应极性下计算得到的面积并且第t代粒子群中粒子位置对应极性下计算得到的功耗≤第t‑1代该粒子个体最优位置对应极性下计算得到的功耗,则采用该粒子第t代更新后的位置取代该粒子在第t‑1代更新完成后的个体最优位置作为该粒子第t代更新完成后的个体最优位置;
如果第t代粒子群中粒子位置对应极性下计算得到的面积>第t‑1代该粒子个体最优位置对应极性下计算得到的面积并且第t代粒子群中粒子位置对应极性下计算得到的功耗>第t‑1代该粒子个体最优位置对应极性下计算得到的功耗,则采用将该粒子在第t‑1代更新完成后的个体最优位置作为该粒子第t代更新完成后的个体最优位置;如果第t代粒子群中粒子位置对应极性下计算得到的面积≤第t‑1代该粒子个体最优位置对应极性下计算得到的面积并且第t代粒子群中粒子位置对应极性下计算得到的功耗>第t‑1代该粒子个体最优位置对应极性下计算得到的功耗,则采用该粒子第t代更新后的位置取代该粒子在第t‑1代更新完成后的个体最优位置作为该粒子第t代更新完成后的个体最优位置;如果第t代粒子群中粒子位置对应极性下计算得到的面积>第t‑1代粒子个体最优位置对应极性下计算得到的面积并且第t代粒子群中粒子位置对应极性下计算得到的功耗≤第t‑1代粒子个体最优位置对应极性下计算得到的功耗,则采用将该粒子在第t‑1代更新完成后的个体最优位置作为该粒子第t代更新完成后的个体最优位置;
F、粒子群第t代更新完成;
(11)判断t的取值是否等于T,如果不等于,则采用t的当前值加1的和更新t的值后,返回步骤(10)进行下一代更新,如果等于,则迭代完成进入步骤(12);
(12)将第T代粒子群的全局最优位置作为最优极性输出,将该最优极性对应的MPRM电路的面积和功耗作为最优面积和功耗输出。