一種求解軟硬件劃分問題的混合編碼二進制差分演化算法

翟慶雷，朱曉斌

(1. 河北地質大學 信息工程學院，河北 石家莊 050031；2. 石家莊文化傳媒學校，河北，石家莊 050000)

0 引言

隨著嵌入式系統的廣泛應用，軟硬件協同設計已成為一個重要的研究問題。硬件部分執行速度快，但是成本費用較高，花費的資源較多；軟件部分雖然執行速度較慢，但成本花費較低，操作相對靈活。合理地把嵌入式系統中的組件根據需求進行軟、硬件協同劃分執行，對整個系統的性能將有很大的提升，因此軟硬件劃分（hardware/software partitioning，HW/SW）已成為軟硬件協同設計中的一個重要問題。

近年來，基于啟發式算法求解大規模HW/SW問題逐漸成為了一個研究熱點。例如Arato等人[1]提出了一個求解HW/SW問題的2D搜索啟發式算法，該算法利用了HW/SW問題特點，因而能夠快速地找到高質量的解。Wu等人[2]將HW/SW問題看成帶有通信成本的擴展 0-1背包問題，提出了求解該問題的一個 1D搜索啟發式算法。該方法不僅提高了算法的性能，而且降低了算法的時間復雜度。Wang等人[3]提出了HEUR算法，并利用它給出了求解HW/SW問題的一種新方法。該方法首先忽略通信成本，將HW/SW問題看作是一個標準 0-1背包問題，求得其解作為原問題的一個潛在解；然后，再根據通信成本對潛在解進行調整，從而得到HW/SW的一個滿足約束條件的可行解。雖然HEUR算法比1D搜索啟發式算法[2]在解的質量上得到了很大提升，但是利用禁忌搜索對解作進一步的優化處理，在求解大規模HW/SW 實例時也是非常耗時的。正是由于HW/SW 的重要性和困難性，如何快速高效地求解該問題是一個值得研究與探討的重要問題。

差分演化算法（differential evolution，DE）[4]是Storn和Price為求解切比雪夫多項式而提出的一種著名演化算法，是一個基于實數編碼的演化算法,非常適合于求解連續域上的最優化問題。為了使 DE能夠求解離散域上的最優化問題，賀等人[5]基于數學變換思想引入“輔助搜索空間”和“個體混合編碼”等概念，通過定義一個特殊的滿射變換，在輔助搜索空間的作用下將連續域上的高效差分演化搜索變換為離散域上的同步演化搜索，由此提出了第1個二進制差分演化算法：具有混合編碼的二進制差分演化算法（binary differential evolution algo rithm with hybrid encoding，HBDE）。HBDE不僅完全具有DE的各種特性和所有優點，而且非常適用于求解離散域上的最優化問題，并且在求解具有單連續變量的背包問題[6]和多維背包[7]中表現出優異性能。為此，本文研究如何利用HBDE高效求解HW/SW。

1 HW/SW 問題的定義和數學模型

HW/SW的定義一般描述為：給出一個無向圖G=(V,E)，其中V和E分別表示節點集和邊集。s(vi)和h(vi)分別表示節點vi的軟件成本和硬件成本，簡記為si和hi；邊(vi,vj)的權值c(vi,vj)表示當節點vi與vj屬于不同劃分時它們之間的通信成本，簡記為cij。設P={VH,VS}為G的一個軟硬件劃分，其中VH表示用硬件實現的節點集合，VS表示用軟件實現的節點集合，VH∩VS=? 且VH∪VS=V。P的邊集為EP={(vi,vj)|(vi?VS,vj?VH)ˇ(vi?VH,vj?VS)}。HW/SW的目的是求一個劃分P在軟件成本與通信成本之和不超過給定值R的前提下使得硬件成本最小。

令X= (x1,x2,…,xn)? { 0,1}n，n為節點數，則X對應一個軟硬件劃分，xi= 1 表示節點vi由軟件實現，xi= 0 表示節點vi由硬件實現，則HW/SW問題的整數規劃模型為：

由 HW/SW 的整數規劃模型可知，其計算復雜度為O(n2)。需要注意的是，一個n維0-1向量只有滿足式（2）時才是HW/SW的一個可行解，否則是HW/SW的一個不可行解。

2 具有混合編碼的二進制差分演化算法

與 DE[4]類似，HBDE[5]的一次迭代進化由變異操作、交叉操作和選擇操作共同完成，它們的實現方法簡述如下：

在變異操作中，對于種群中的第i個個體Yi=(yi1,yi2,…,yin)?[-A,A]n，A是正實數，隨機選取種群中3個不同個體Yr1= (yr1,1,yr1,2 ,…,yr1,n)，Yr2= (yr2, 1,yr2, 2 , …,yr2,n)，Yr3= (yr3,1,yr3, 2 ,…,yr3,n)，將其中Yr2和Yr3的差縮放FS倍后與Yr1求和，產生中間個體Zi= (zi1,zi2,… ,zin)。變異操作的計算式為：

其中，0＜FS＜1為縮放因子，r1,r2和r3是在范圍[1,N]內的三個互不相同并且不等于i的隨機整數，N為種群規模。

HBDE的交叉操作是針對每一維分量產生一個隨機小數r，如果r＜CR（交叉因子）則進行交叉操作。交叉操作產生的中間個體不妨仍設為Zi=(zi1,zi2,…,zin)?[-A,A]，則交叉操作的計算式為：

由于DE中的變異操作是實數運算，不能直接應用于求解組合優化問題。為此，賀等人[5]利用映射的方法將實數編碼轉換為0-1編碼。設個體Zi=(zi1,zi2,…,zin)?[-A,A],A是正實數，Wi=(wi1,wi2,…,win)是n維0-1向量，則HBDE利用（6）式給出的滿射函數Ψ由Zi得到Wi：

HBDE的選擇操作采用的是貪心策略，即由（5）產生的中間個體Zi比當前個體Yi更優時，Zi作為下一代種群的第i個個體，否則Yi作為下一代種群的第i個個體。不妨設 minh(Y) ,Y?S?Rn表示一個最小優化問題，則HBDE的選擇操作的計算式為：

其中，X=(xi1,xi2,…,xin)?{0,1}n是個體Yi由Ψ得到的0-1向量。Wi=(wi1,wi2,…,win)?{0,1}n是Zi由Ψ得到的0-1向量。

3 求解HW/SW問題的方法

由于 HW/SW 是一個約束優化問題，在利用HBDE求解時不可避免地將會產生不可行解。為此，下面首先基于貪心策略提出處理HW/SW的不可行解的修復與優化算法GROA，然后在此基礎上給出基于HBDE求解HW/SW的啟發式算法。

3.1 基于貪心策略的修復與優化

3.2 基于HBDE求解HW/SW

4 仿真實驗

本文所有的計算均在配置為 Intel(R)Core(TM)i5-4210 CPU @ 1.70GH z和8GB RA M的微型計算機上進行，操作系統為 W indows 10，編程語言為C，編譯環境為Code::Blocks 17.12，使用Python在編譯環境JetBrains PyCharm繪圖。

4.1 HW/SW 實例與算法參數設置

本文所用的11個HW/SW測試實例來自于文獻[10]。在每個實例中，n和m分別為無向圖G=(V,E)中的節點數和邊數，size表示實例的規模，且size= 2 ×n+3×m。在表1中詳細給出了11個HW/SW測試實例。

表1 11個HW/SW實例Tab.1 1 1 HW/SW instances

在本文中，所有算法的種群規模均設置為N=30，迭代次數MIR=n（n為節點個數）。在HBDE中，–A=5和A=5分別表示的每個個體向量中的每一維分量取值的上界和下界，CR和FS分別為變異因子和縮放因子。在GA中，Pc=0.8和Pm=0.001分別為交叉因子和變異因子。

4.2 計算結果比較與分析

在本節中，利用HBDE和GA[11]對上述HW/SW實例進行計算，并對它們的計算結果進行比較。在表2中給出了算法對每一實例獨立計算30次所獲得的最好值為Best、平均值為Mean、標準差為Std。

表2 GA 和HBDE求解11個HW/SW實例的計算結果Tab.2 Calculation results of GA and HBDE for solving 11 HW/SW instances

從表2明顯可以看出，就指標Best而言，對于實例1，3和4，HBDE與GA的結果相等，對于實例 6，HBDE的結果比 GA差，對于實例 2和7-11，HBDE的結果明顯優于GA。就指標Mean而言，對于實例1和3，HBDE結果與GA相等，對于實例 2和 4-11，HBDE的結果優于 GA。就指標Std而言，對于實例1和3，HBDE與GA的結果相等，對于實例10，HBDE的結果比GA差，對于實例 2，4-9和 11，HBDE的結果明顯優于GA。因此通過以上分析我們可知，基于 HBDE求解HW/SW是一種高效可行的方法，并且其性能優于經典的GA。

5 總結與展望

本文首先給出了基于貪心策略處理 HW/SW的不可行解的修復與優化算法GROA，然后利用具有混合編碼的二進制差分演化算法（HBDE）求解HW/SW的一般框架，最后比較了HBDE和GA求解11個HW/SW實例的計算結果。計算結果表明，HBDE是一種求解HW/SW問題的高效算法。由于 HW/SW 在軟硬件協同設計中的重要性，對其快速高效求解的研究一直是一個重要的方向。為此，今后將嘗試利用新提出的演化算法，例如郊狼優化算法[12]（coyote opti mization algorithm，COA）、浣熊優化算法[13]（raccoon optimization algorith m，ROA）和松鼠搜索算法[14]（squirrel search algorithm，SSA）等求解HW/SW問題，進一步探討高效求解HW/SW問題的新方法。