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

翟慶雷，朱曉斌

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

0 引言

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

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

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

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

HW/SW的定義一般描述為：給出一個無向圖G=(V,E)，其中V和E分別表示節(jié)點集和邊集。s(vi)和h(vi)分別表示節(jié)點vi的軟件成本和硬件成本，簡記為si和hi；邊(vi,vj)的權值c(vi,vj)表示當節(jié)點vi與vj屬于不同劃分時它們之間的通信成本，簡記為cij。設P={VH,VS}為G的一個軟硬件劃分，其中VH表示用硬件實現的節(jié)點集合，VS表示用軟件實現的節(jié)點集合，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為節(jié)點數，則X對應一個軟硬件劃分，xi= 1 表示節(jié)點vi由軟件實現，xi= 0 表示節(jié)點vi由硬件實現，則HW/SW問題的整數規(guī)劃模型為：

由 HW/SW 的整數規(guī)劃模型可知，其計算復雜度為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為種群規(guī)模。

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

由于DE中的變異操作是實數運算，不能直接應用于求解組合優(yōu)化問題。為此，賀等人[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更優(yōu)時，Zi作為下一代種群的第i個個體，否則Yi作為下一代種群的第i個個體。不妨設 minh(Y) ,Y?S?Rn表示一個最小優(yōu)化問題，則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 是一個約束優(yōu)化問題，在利用HBDE求解時不可避免地將會產生不可行解。為此，下面首先基于貪心策略提出處理HW/SW的不可行解的修復與優(yōu)化算法GROA，然后在此基礎上給出基于HBDE求解HW/SW的啟發(fā)式算法。

3.1 基于貪心策略的修復與優(yōu)化

3.2 基于HBDE求解HW/SW

4 仿真實驗

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

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

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

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

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

4.2 計算結果比較與分析

在本節(jié)中，利用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的結果明顯優(yōu)于GA。就指標Mean而言，對于實例1和3，HBDE結果與GA相等，對于實例 2和 4-11，HBDE的結果優(yōu)于 GA。就指標Std而言，對于實例1和3，HBDE與GA的結果相等，對于實例10，HBDE的結果比GA差，對于實例 2，4-9和 11，HBDE的結果明顯優(yōu)于GA。因此通過以上分析我們可知，基于 HBDE求解HW/SW是一種高效可行的方法，并且其性能優(yōu)于經典的GA。

5 總結與展望

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