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

翟慶雷，朱曉斌

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

0 引言

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

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

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

1 HW/SW 問題的定義和數(shù)學(xué)模型

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

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

2 具有混合編碼的二進(jìn)制差分演化算法

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

在變異操作中，對于種群中的第i個個體Yi=(yi1,yi2,…,yin)?[-A,A]n，A是正實(shí)數(shù)，隨機(jī)選取種群中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求和，產(chǎn)生中間個體Zi= (zi1,zi2,… ,zin)。變異操作的計(jì)算式為：

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

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

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

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

其中，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求解時(shí)不可避免地將會產(chǎn)生不可行解。為此，下面首先基于貪心策略提出處理HW/SW的不可行解的修復(fù)與優(yōu)化算法GROA，然后在此基礎(chǔ)上給出基于HBDE求解HW/SW的啟發(fā)式算法。

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

3.2 基于HBDE求解HW/SW

4 仿真實(shí)驗(yàn)

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

4.1 HW/SW 實(shí)例與算法參數(shù)設(shè)置

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

表1 11個HW/SW實(shí)例Tab.1 1 1 HW/SW instances

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

4.2 計(jì)算結(jié)果比較與分析

在本節(jié)中，利用HBDE和GA[11]對上述HW/SW實(shí)例進(jìn)行計(jì)算，并對它們的計(jì)算結(jié)果進(jìn)行比較。在表2中給出了算法對每一實(shí)例獨(dú)立計(jì)算30次所獲得的最好值為Best、平均值為Mean、標(biāo)準(zhǔn)差為Std。

表2 GA 和HBDE求解11個HW/SW實(shí)例的計(jì)算結(jié)果Tab.2 Calculation results of GA and HBDE for solving 11 HW/SW instances

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

5 總結(jié)與展望

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