[發明專利]一種基于帕雷托支配的MPRM電路多目標優化方法

有效

• 申請號: 202010133546.X
• 申請日: 2020-02-28
• 公開（公告）號: CN111400996B
• 公開（公告）日: 2023-06-06
• 發明（設計）人: 俞海珍;閆盼盼;張維山;史旭華
• 申請（專利權）人: 寧波大學
• 主分類號: G06F30/398
• 分類號: G06F30/398;G06N3/006;G06F111/06
• 代理公司: 寧波奧圣專利代理有限公司 33226
• 代理人: 方小惠

1.一種基于帕雷托支配的MPRM電路多目標優化方法，其特征在于包括以下步驟：

(1)讀取代表電路結構的函數表達式：

其中，n表示函數f(x_n-1,x_n-2,...,x_k,...,x₀)的輸入變量數，(x_n-1,x_n-2,...,x_k,...,x₀)為函數f(x_n-1,x_n-2,...,x_k,...,x₀)的n個輸入變量，x_k為函數f(x_n-1,x_n-2,...,x_k,...,x₀)的第k+1個輸入變量，k＝0,1,2,...n-1，∏為與運算符號，a_i是第i個最大項系數，且a_i∈{0,1}，i為最大項序數，用二進制表示為i_n-1i_n-2…i_k…i₀，m_i表示第i個最大項，其符號表示形式為式中的出現形式和i_k相關，若i_k＝1，若i_k＝0，其中為x_k的反變量；

(2)利用極性轉換方法將表示電路結構的函數表達式(1)轉換為P極性的MPRM表達式：

其中，P為極性值，用三進制表示為p_n-1p_n-2...p_g...p₀，p_g為極性值P第g+1位上的數，g＝0,1,2,...n-1，⊙∏為同或運算符，S_j表示第j個或項，d_j為第j個或項系數，d_j∈{0,1}，當d_j＝0時，表示S_j在MPRM表達式中出現，當d_j＝1時，表示(1+S_j)在MPRM表達式中出現，j為或項序數，j用二進制表示為j_n-1j_n-2…j_g…j₀，其中x_g與p_g和j_g的關系為：當p_g＝0，j_g＝0或1時，x_g以原變量的形式出現；當p_g＝1，j_g＝0或1時，x_g以反變量的形式出現；當p_g＝2，j_g＝1時，x_g以反變量的形式出現；當p_g＝2，j_g＝0時，x_g以原變量的形式出現；

(3)構建P極性的MPRM表達式對應的MPRM電路的面積函數與功耗函數，將面積函數采用式(3)表示為：

式(3)中，E_area表示P極性下MPRM電路的面積，為d_j的反變量，為j_g的反變量；

功耗函數采用式(4)表示為：

式(4)中，Epow表示P極性下MPRM電路的功耗，V_dd表示MPRM電路的電源電壓，f_clk表示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)設定粒子速度的最小邊界值，將其記為v_min，令v_min＝0，設定粒子速度的最大邊界值，將其記為v_max，令v_max＝6.0，設定粒子位置的最小邊界值，將其記為x_min，令x_min＝2.0，設定粒子位置的最大邊界值，將其記為x_max，令x_max＝3.0；

(7)構建用于存放全局最優粒子的外部集，對外部集進行初始化，具體過程為：

S1、構建第0代邊界粒子群：對第0代粒子群中每個粒子的速度和位置進行判定操作后得到第0代邊界粒子群，判定操作具體方式為：如果該粒子的速度大于等于0且小于等于6，則其速度保持不變，反之，將其速度減少為當前速度的一半，如果該粒子的位置大于等于x_min且小于等于x_max，則其位置保持不變，反之，將其位置修改為x_min；

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)所示：

x_fd(t)＝round(S_fd+2×σ×randx())???????????????????????(6)

其中，c₁、c₂和c₃為學習因子，c₁＝c₂＝c₃＝1.5，r₁、r₂和r₃是大于等于0且小于等于1的隨機數，w為慣性權重，式中w_start表示初始權重，w_end表示最終權重，初始慣性權重w_start＝0.9，終止慣性權重w_end＝0.4；v_fd(t)表示第t代更新完成后第f個粒子的速度，x_fd(t)表示第t代更新完成后第f個粒子的位置，f＝1,2,…,D，當t＝1時，x_fd(t-1)表示第f個粒子的初始位置，p_md(t-1)表示粒子群初始的全局最優位置，p_nd(t-1)表示粒子群中隨機任一粒子的初始位置，p_fd(t-1)表示第f個粒子初始的個體最優位置，v_fd(t-1)表示第f個粒子的初始速度，當t≥2時，x_fd(t-1)表示第t-1代離子群中第f個粒子的位置，p_fd(t-1)表示在第t-1代粒子群中第f個粒子的個體最優位置，p_nd(t-1)表示第t-1代粒子群中隨機任一粒子的位置，p_md(t-1)表示第t-1代粒子群的全局最優位置，v_fd(t-1)表示第t-1代粒子群中第f個粒子的速度，e表示自然對數的底，σ為權值且σ＝0.2，randn()為標準正態分布函數，round()表示四舍五入取整，上式(5)中，當計算得到的x_fd(t)為大于2的整數時，令x_fd(t)＝2,當計算得到的x_fd(t)為小于0的整數時，令x_fd(t)＝0，當計算得到的x_fd(t)為大于等于1且小于等于2的整數時，x_fd(t)的取值為其計算值；

B、對外部集進行第t代更新，具體過程為：

W1、構建第t代邊界粒子群：對第t代粒子群中每個粒子的速度和位置進行判定操作后得到第t代邊界粒子群，判定操作具體方式為：如果該粒子的速度大于等于0且小于等于6，則其速度保持不變，反之，將其速度減少為當前速度的一半，如果該粒子的位置大于等于x_min且小于等于x_max，則其位置保持不變，反之，將其位置修改為x_min；

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電路的面積和功耗作為最優面積和功耗輸出。