基于改進人工魚群算法的軟硬件劃分方法

全浩軍，張 濤，郭繼昌

(天津大學(xué)電子信息工程學(xué)院，天津 300072)

嵌入式系統(tǒng)廣泛應(yīng)用于醫(yī)療、電力、航空、消費類電子等領(lǐng)域．在嵌入式系統(tǒng)的設(shè)計中，往往采用軟硬件協(xié)同設(shè)計方法以縮短產(chǎn)品的研發(fā)周期，同時滿足產(chǎn)品在成本、功耗、性能等多方面的需求[1-2]，而軟硬件劃分是軟硬件協(xié)同設(shè)計中的重點和難點[3]．

由于軟硬件劃分技術(shù)可以在滿足特定約束的條件下有效提高系統(tǒng)性能、降低功耗，因此近年來很多研究人員都進行了相關(guān)算法的研究工作并取得了一定的進展[4-5]．在精確算法的研究方面，主要有分支定界、動態(tài)規(guī)劃和整數(shù)線性規(guī)劃等[4]．精確算法可以得到高性能的軟硬件劃分方案，但算法復(fù)雜度很高，因此啟發(fā)式算法成為目前主要的研究方向，其中包括遺傳算法、模擬退火、禁忌搜索、貪婪算法等基本算法和一些結(jié)合及改進算法，如遺傳模擬退火[6]、遺傳禁忌搜索[7]、遺傳粒子群優(yōu)化[8]、分支定界粒子群優(yōu)化[9]和改進的非支配分類遺傳算法[10]等．

人工魚群算法是將人工智能思想引入優(yōu)化命題的解決中而產(chǎn)生的一種高效智能優(yōu)化算法，具有并行性、簡單性、全局性、跟蹤性等諸多優(yōu)點，且算法只考慮目標(biāo)函數(shù)值而對目標(biāo)函數(shù)本身的性質(zhì)不敏感[11]．然而人工魚群算法主要應(yīng)用于求解連續(xù)型的優(yōu)化問題，對于離散型的優(yōu)化問題，雖已有人提出了應(yīng)用方法[12]，但存在最優(yōu)解出現(xiàn)概率低、收斂速度慢等問題．筆者將原始人工魚群算法應(yīng)用于軟硬件劃分，然后在對原始算法進行分析的基礎(chǔ)上提出了基于隨機步長和鄰域搜索的改進方法，最后使用TGFF 工具生成的有向無環(huán)圖(directed acyclic graphs，DAG)對兩算法進行對比測試．實驗結(jié)果驗證了改進后算法的高效性．

1 基于人工魚群算法的軟硬件劃分

1.1 魚群行為與人工魚群算法

人工魚群算法以魚群的聚群、追尾、覓食等幾種典型行為為基礎(chǔ)[11]．聚群行為是魚類在進化過程中形成的一種生活習(xí)性，在集體覓食或躲避傷害時，魚朝著某一中心位置聚集成群．追尾行為指當(dāng)魚群中有魚發(fā)現(xiàn)食物時，鄰近的魚會尾隨該魚從而能盡快找到食物．覓食行為則是魚隨機游走以尋找食物的行為．人工魚群算法通過以上行為更新魚群并對魚的位置進行評價，再通過行為選擇來控制魚群收斂，從而達到尋優(yōu)的目的．

1.2 數(shù)學(xué)描述

假設(shè)待劃分系統(tǒng)由 N 個結(jié)點構(gòu)成，每個結(jié)點既可以用軟件實現(xiàn)(用 0 表示)，也可以用硬件實現(xiàn)(用1 表示)，這樣 N 個結(jié)點的軟硬件劃分構(gòu)成了一個 N 維空間{0 ,1}N．將人工魚群中的所有魚置于該N 維空間中，令表示第i (i =1,2,… ,M )條魚在空間中所處的位置，這樣一個位置便對應(yīng)于一個確定的軟硬件劃分方案，其中 xi,j= 0(xi,j= 1)表示第j 個結(jié)點用軟件(硬件)實現(xiàn)．為便于描述，將第i條魚在空間中的位置稱為第i條魚所處的狀態(tài)，并以Xi,event表示第i條魚在 event 事件下的狀態(tài)，例如Xi,next表示第i條魚在下一時刻的狀態(tài)，Xi,dest表示第i條魚的目標(biāo)狀態(tài)．令 Yi,event表示 Xi,event狀態(tài)對應(yīng)軟硬件劃分方案的耗時，則在方案可行的前提下，Yi,event的值越小表明 Xi,event狀態(tài)對應(yīng)的劃分方案越好．

1.3 算法描述

文獻[12]以旅行商問題為實例，提出將人工魚群算法應(yīng)用于組合優(yōu)化問題．基于第 1.2 節(jié)中的定義，筆者將該算法應(yīng)用于軟硬件劃分，其偽代碼為

Algorithm.Alg-ori/*使用文獻[12]中的人工魚群算法進行軟硬件劃分*/

begin

M ：＝10，max_repeat_num：＝1,500，prey_try_num：＝10，delta：＝0.9，visual：＝30；/*變量初始化*/

Init_fishs()；/*魚群初始化*/

Bulletin_update_old()；/*公告欄更新*/

forrepeat_num：＝1tomax_repeat_numdo begin

fori：＝1toMdo

begin

/*聚群行為*/

neighbour_fish_num：＝Num(Xi,now，visual)；

/*計算魚在可視范圍內(nèi)的伙伴數(shù)目*/

Xi,center：＝Center(Xi,now，visual)；/*計算魚在

可視范圍內(nèi)與所有伙伴的中心位置*/

/*判斷中心位置是否有效、周圍是否擁擠以及

中心位置對應(yīng)的狀態(tài)是否更優(yōu)*/

if(is_valid（ Xi,center)&&neighbour_fish_num/

M ＜delta&& Yi,center＜Yi,now）

thenXi,next：＝ Xi,center；/*魚向中心位置前進*/

elsePrey_behavior(prey_try_num)；/*覓食行

為*/

/*追尾行為*/

Xi,best：＝Best(Xi,now，visual)；/*計算魚在可視

范圍內(nèi)伙伴的最優(yōu)狀態(tài)*/

/*計算最優(yōu)伙伴在可視范圍內(nèi)的伙伴數(shù)目*/

neighbour_fish_num：＝Num( Xi,best，visual)；

/*判斷該最優(yōu)伙伴周圍是否擁擠、是否比魚的

當(dāng)前狀態(tài)更優(yōu)*/

if(neighbour_fish_num/M＜delta&&) Yi,best＜Yi,now

thenXi,next：＝ Xi,best；/*魚向最優(yōu)伙伴前進*/

elsePrey_behavior(prey_try_num)；/*覓食行為*/

Moving_evaluation()；/*行為評價與選擇*/

endof for；

Bulletin_update_old()；/*公告欄更新*/

endof for；

end.

其中M為魚群規(guī)模，即魚群中魚的個數(shù)，max_repeat_num 為魚群的最大更新次數(shù)，prey_try_num 為魚的最大覓食嘗試次數(shù)，delta 為擁擠度因子，visual 為魚的可視范圍．

在算法 Alg-ori 中，如果聚群行為(追尾行為)無法找到有效的更優(yōu)狀態(tài)，則進行覓食行為．在覓食行為中，首先令魚在下一狀態(tài)游走到可視范圍內(nèi)的一個隨機狀態(tài)，然后判斷該狀態(tài)是否有效、是否比當(dāng)前狀態(tài)更優(yōu)，如果條件滿足，則不再嘗試，否則持續(xù)嘗試直至到達限定次數(shù)prey_try_num．對于魚群中的任一條魚，在完成以上行為后，都對這些行為產(chǎn)生的下一狀態(tài)進行評價并從中選擇最優(yōu)狀態(tài)作為魚的目標(biāo)狀態(tài)，即執(zhí)行 Moving_evaluation()函數(shù)．而在完成一次完整的魚群更新后，進行公告欄的更新，其偽代碼為

Function.Bulletin_update_old()

/*原始的公告欄更新函數(shù)*/

begin

/*計算魚群中魚的最優(yōu)狀態(tài)和最差狀態(tài)*/

Xnew_best：＝Find_best_fishstate()；

Xnew_worst：＝Find_worst_fishstate()；

if(Ynew_best＜Yold_best)

thenXold_best：＝ Xnew_best；

elseXnew_worst：＝Xold_best；

end.

在原始的公告欄更新函數(shù)中，首先計算更新后魚群中魚的最優(yōu)狀態(tài)Xnew_best與最差狀態(tài) Xnew_worst，然后將Xnew_best與更新前魚群中魚的最優(yōu)狀態(tài) Xold_best進行比較．如果相應(yīng)的劃分方案耗時 Ynew_best小于 Yold_best，則記錄更新后的最優(yōu)狀態(tài)Xnew_best，否則使用更新前的最優(yōu)狀態(tài) Xold_best替換更新后的最差狀態(tài) Xnew_worst以保證魚群狀態(tài)更新的收斂性．

2 算法分析與改進

算法Alg-ori 通過魚的3種行為不斷更新魚群狀態(tài)，可以在一定程度上表現(xiàn)出向最優(yōu)解收斂的特性，達到尋優(yōu)的目的，然而在魚移動步長、魚群狀態(tài)更新效率等方面存在問題，影響了算法的收斂速度．為此，從以下兩個方面進行分析和改進．

2.1 隨機步長

在算法 Alg-ori 中，覓食行為可以以一定概率找到更優(yōu)狀態(tài)，從而實現(xiàn)對局部解的逃逸，但這種搜索行為是隨機的，或者可以說是 “盲目” 的．而在聚群和追尾這種“引導(dǎo)” 式的搜索行為中，魚向目標(biāo)狀態(tài)的前進又是一步到達的，這樣雖然魚是朝著更優(yōu)狀態(tài)前進的，但存在兩點不足：①魚的當(dāng)前狀態(tài)與目標(biāo)狀態(tài)間可能存在更優(yōu)的中間狀態(tài)，而一步到達的方式跳過了這些中間狀態(tài)，不利于魚群的局部尋優(yōu)；②如果已經(jīng)有魚處于目標(biāo)狀態(tài)(在追尾行為中，這種現(xiàn)象必然發(fā)生)，則魚在下一狀態(tài)會與另一條魚的狀態(tài)合并為一個狀態(tài)，這樣不利于全局極值的搜索．為此，使用隨機步長的方法來改善魚的游走行為．

如圖 1 所示，第i 條魚當(dāng)前狀態(tài)Xi,now與目標(biāo)狀態(tài) Xi,dest對應(yīng)兩個不同的軟硬件劃分方案．設(shè)對結(jié)點j (j=1,2,… ,N)的劃分方案中，魚由當(dāng)前方案 xi,now,j變?yōu)槟繕?biāo)方案 xi,dest,j的概率為αi,j，令

圖1 隨機步長示意Fig.1 Schematic diagram of random step

則魚由當(dāng)前狀態(tài)Xi,now變?yōu)槟繕?biāo)狀態(tài)Xi,dest的概率為

2.2 無效迭代的產(chǎn)生及鄰域搜索

魚群狀態(tài)的更新是以魚的更優(yōu)狀態(tài)來替換次優(yōu)狀態(tài)的過程，因此魚群狀態(tài)的每一次完整更新都可視為一次迭代．在理想情況下，每一次迭代都應(yīng)當(dāng)產(chǎn)生至少一個更優(yōu)的狀態(tài)．然而在實際運行中，由于魚在離散空間游走的隨機性，每次迭代并不一定能產(chǎn)生更優(yōu)的狀態(tài)，在此將沒有產(chǎn)生更優(yōu)狀態(tài)的迭代稱為無效迭代．

無效迭代現(xiàn)象在迭代的后期會更加明顯，并會產(chǎn)生多次連續(xù)的無效迭代．這是由于隨著魚群的迭代，更優(yōu)的狀態(tài)往往出現(xiàn)在目前最優(yōu)狀態(tài)鄰域內(nèi)的一個較小的范圍內(nèi)，甚至只存在于目前最優(yōu)狀態(tài)鄰域內(nèi)的某一特定位置．而由于魚游走的隨機性且更優(yōu)狀態(tài)與目前最優(yōu)狀態(tài)之間可能并不存在中間狀態(tài)，因此魚可能會在最優(yōu)狀態(tài)附近迂回搜索但很難找到更優(yōu)的狀態(tài)．為此，使用鄰域搜索方法來避免多次無效迭代的產(chǎn)生、加速收斂．

已知第i 條魚當(dāng)前狀態(tài)為Xi,now，則所有與Xi,now距離小于 1 的狀態(tài) Xi,state_1構(gòu)成一個集合，稱為第i 條魚的一維鄰域．類似地，所有與Xi,now距離小于l 的目標(biāo)狀態(tài)Xi,state_l構(gòu)成一個集合，稱為第i 條魚的l 維鄰域．如果對第i 條魚的l 維鄰域按一定規(guī)則進行搜索以獲得更優(yōu)狀態(tài)，則這種行為稱為對第i 條魚的l 維鄰域搜索．搜索的維數(shù)是從搜索廣度上而言的，在搜索深度上，默認是對所有可能狀態(tài)進行搜索，即遍歷搜索．然而，遍歷搜索具有很高的算法復(fù)雜度，因此可以在找到一個更優(yōu)狀態(tài)后結(jié)束搜索以減少耗時．

鄰域搜索只有在連續(xù)無效迭代達到一定的次數(shù)(即滿足鄰域搜索條件)時才會執(zhí)行，而如果此時鄰域搜索仍無法找到更優(yōu)狀態(tài)，則在后續(xù)的無效迭代中不再執(zhí)行鄰域搜索直至無效迭代被重新計數(shù)．當(dāng)連續(xù)無效迭代次數(shù)達到停止條件時，則默認無法找到更優(yōu)的狀態(tài)，從而不再更新魚群狀態(tài)，結(jié)束搜索．

鄰域搜索條件的判斷在公告欄更新函數(shù)中執(zhí)行，改進后的公告欄更新函數(shù)偽代碼為

Function.Bulletin_update_new()

begin

/*計算魚群中魚的最優(yōu)狀態(tài)和最差狀態(tài)*/

Xnew_best：＝Find_best_fishstate()；

Xnew_worst：＝Find_worst_fishstate()；

if(Ynew_best＜Yold_best)

then begin

un_update_count：＝0；/*無效迭代次數(shù)置零*/

Xold_best：＝ Xnew_best；

endof if；

else begin

Xnew_worst：＝ Xold_best；

un_update_count：＝un_update_count＋1；/*無效

迭代次數(shù)遞增*/

if(un_update_count ＝Neighborhood_searching_

condition)/*是否滿足鄰域搜索條件？*/

then begin

/* 鄰域搜索，找到更優(yōu)狀態(tài)則返回

SUCCESS*/

return_value：＝Neighborhood_searching()；

if(return_value＝SUCCESS)

then begin

un_update_count：＝0；/*無效迭代次數(shù)置零

*/

Xnew_best：＝the best fish in Neighbor

hood_searching()；

Xold_best：＝ Xnew_best；

endof if；

endof if；

else if(un_update_count＝stop_condition)/*是否

滿足結(jié)束條件？*/

thenexit()；

endof else；

end.

同原始公告欄更新函數(shù)類似，在新的公告欄更新函數(shù)中，首先統(tǒng)計更新后魚群中魚的最優(yōu)狀態(tài)Xnew_best與最差狀態(tài) Xnew_worst，如果最優(yōu)狀態(tài)對應(yīng)劃分方案的耗時 Ynew_best小于原最優(yōu)狀態(tài)耗時 Yold_best，則記錄 Xnew_best并將無效迭代次數(shù) u n_update_count 清零，否則，首先用原始魚群的最優(yōu)狀態(tài)替換當(dāng)前魚群的最差狀態(tài)并將無效迭代次數(shù) un_update_count 加 1，然后根據(jù) u n_update_count 判斷滿足的條件并執(zhí)行相應(yīng)的運算．如果 un_update_count 等于鄰域搜索條件Neighborhood_searching_condition，則進行鄰域搜索從而檢索鄰域內(nèi)的更優(yōu)狀態(tài)，如果更優(yōu)狀態(tài)存在，則記錄該狀態(tài)并將 un_update_count 清零．當(dāng)un_update_count 等于結(jié)束條件 s top_condition 時，則認為無法找到更優(yōu)狀態(tài)，算法結(jié)束．

3 實驗結(jié)果及分析

盡管軟硬件劃分方法很多，每種方法都可以在特定的軟硬件協(xié)同設(shè)計環(huán)境下取得較好的劃分效果，然而由于啟發(fā)式因子的不同、參數(shù)設(shè)置的差異以及公認測試集的缺乏，方法間很難進行橫向?qū)Ρ萚4,13]. TGFF是一個隨機圖生成工具，可用于軟硬件劃分的對比測試．本文中以TGFF 工具隨機生成的DAG 圖作為測試集、以縮短 DAG 圖的關(guān)鍵路徑為優(yōu)化目標(biāo)對原始人工魚群算法和改進后的人工魚群算法進行對比測試．測試中共使用 TGFF 生成 4 個 DAG 圖，參數(shù)設(shè)置如表1 所示，其中±表示浮動范圍．

表1 TGFF工具參數(shù)設(shè)置Tab.1 Parameters setting of TGFF tool

由于TGFF 工具默認對結(jié)點數(shù)的浮動變化，實際生成的結(jié)點數(shù)分別為 29、49、69、100．實驗硬件環(huán)境為Intel T2050 1.6,GHz CPU，2.87,G 內(nèi)存；軟件環(huán)境為 Windows XP Professional 2002,SP3，Microsoft Visual C++．對魚群算法的參數(shù)設(shè)置為：魚群規(guī)模10 ，覓食嘗試次數(shù) 10，擁擠度因子 0.9，可視范圍N/ 2(N為結(jié)點數(shù))，最大迭代次數(shù) 1,5 0 0 ．此外，對于改進的魚群算法，附加的參數(shù)設(shè)置為：步長概率γ = 3 3.3%，搜索維數(shù)為 2，鄰域搜索條件為 10 次無效迭代，結(jié)束條件為 20 次無效迭代．為了降低隨機因素的影響，對于每個結(jié)點的 DAG 圖，兩種算法均執(zhí)行 2 0 次．將平均每次的執(zhí)行時間記為平均執(zhí)行時間，得到的實驗結(jié)果如表2 所示．

表2 原始人工魚群算法與改進后人工魚群算法實驗結(jié)果Tab.2 Experimental results of original and improved AFSA

根據(jù)表2 中的數(shù)據(jù)，從以下4 個方面進行分析．

1) 算法效率

在最優(yōu)解上，改進后算法得到的最優(yōu)解等于或優(yōu)于原始算法；在最優(yōu)解出現(xiàn)概率上，改進后算法的最優(yōu)解出現(xiàn)概率為原算法的 5～7 倍．因此改進后算法具有更強的搜索和尋優(yōu)能力，不僅最優(yōu)解出現(xiàn)概率高，而且可以得到更優(yōu)的解．

2) 算法穩(wěn)定性

平均解和最差解反映了解的分布情況，由于改進后算法的最差解小于等于原始算法，而平均解小于原始算法，因此改進算法的解沒有出現(xiàn)大范圍擴散的現(xiàn)象，算法相對穩(wěn)定．

3) 算法資源利用率

在平均硬件面積上，由表 1 的參數(shù)設(shè)置可知，平均硬件耗時小于軟件耗時，所以關(guān)鍵路徑耗時降低意味著更多的結(jié)點趨向于被劃分到硬件，由于改進后的算法最優(yōu)解出現(xiàn)概率高且可能得到更優(yōu)的解，因此在滿足硬件約束的前提下改進后算法的平均硬件面積高于原始算法，即改進后算法對硬件資源進行了更充分的利用．

4) 算法收斂速度

在迭代次數(shù)和平均迭代時間上，由于使用了鄰域搜索的方法，因此改進后算法的平均每次迭代耗時大于原始算法．但在總耗時上，改進后算法的平均耗時約為原算法的 6.5%～34.5%，且改進后算法的最優(yōu)解出現(xiàn)概率高于原始算法，因此改進后算法具有更快的收斂速度.

4 結(jié) 語

將人工魚群算法應(yīng)用于軟硬件劃分，從而提出一種新的軟硬件劃分方法．針對原始的人工魚群算法在應(yīng)用于軟硬件劃分時存在的最優(yōu)解出現(xiàn)概率低、收斂速度慢等問題，提出了基于隨機步長和鄰域搜索的改進方法．改進后算法的平均耗時約為原算法的6.5%～34.5%，而最優(yōu)解出現(xiàn)概率則為原算法的 5～7倍．結(jié)果表明，改進后算法具有更高的最優(yōu)解出現(xiàn)概率和更快的收斂速度，可更高效地完成軟硬件劃分任務(wù)．

［1］Ye Hua，Wu Jigang. Computing models and algorithms for complex co-design systems[J].Journal of University of Electronic Science and Technology of China，2011，40(3)：333-345.

［2］Abdelhalim M B，Habib S E-D. An integrated high-level hardware/software partitioning methodology[J].Des Autom Embed Sys，2011，15(1)：19-50.

［3］于蘇東，劉雷波，尹首一，等. 嵌入式粗顆粒度可重構(gòu)處理器的軟硬件協(xié)同設(shè)計流程[J]. 電子學(xué)報，2009，37(5)：1136-1140.Yu Sudong，Liu Leibo，Yin Shouyi，et al. Hardwaresoftware co-design flow for embedded coarse-grained reconfigurable processor[J].Chinese Journal of Electronics，2009，37(5)：1136-1140(in Chinese).

［4］Wu Jigang，Srikanthan T，Guang Chen. Algorithmic aspects of hardware/software partitioning：1D search algorithms[J].IEEE Transactions on Computers，2010，59(4)：532-544.

［5］Arato P，Mann Z A，Orban A. Algorithmic aspects of hardware/software partitioning[J].ACM Transactions on Design Automation of Electronic Systems， 2005 ，10(1)：136-156.

［6］Li Lanying，Song Yanbo，Gao Ming. A new genetic simulated annealing algorithm for hardware-software partitioning[C]// 2010 2nd International Conference on Information Science and Engineering(ICISE). Hangzhou，China，2010：1-4.

［7］Li Lanying，Shi Min. Software-hardware partitioning strategy using hybrid genetic and tabu search[C]// 2008International Conference on Computer Science and Software Engineering(CSSE). Wuhan，China，2008：83-86.

［8］劉 安，馮金富，梁曉龍，等. 基于遺傳粒子群優(yōu)化的嵌入式系統(tǒng)軟硬件劃分算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報，2010，22(6)：927-933.Liu An，F(xiàn)eng Jinfu，Liang Xiaolong，et al. Algorithm of hardware/software partitioning based on genetic particle swarm optimization[J].Journal of Computer-Aided Design and Computer Graphics，2010，22(6)：927-933(in Chinese).

［9］Eimuri T，Salehi S. Using DPSO and B and B algorithms for hardware/software partitioning in codesign[C]// 2010 2ndInternational Conference on Computer Research and Development(ICCRD). Kuala Lumpur，Malaysia，2010：416-420.

［10］羅勝欽，馬蕭蕭，陸 憶. 基于改進的 NSGA 遺傳算法的 SOC 軟硬件劃分方法[J]. 電子學(xué)報，2009，37(11)：2595-2599.Luo Shengqin，Ma Xiaoxiao，Lu Yi. An advanced nondominated sorting genetic algorithm based SOC hardware/software partitioning [J].Chinese Journal of Electronics，2009，37(11)：2595-2599(in Chinese).

［11］李曉磊，邵之江，錢積新. 一種基于動物自治體的尋優(yōu)模式：魚群算法[J]. 系統(tǒng)工程理論與實踐，2002，22(11)：32-38.Li Xiaolei，Shao Zhijiang，Qian Jixin. An optimizing method based on autonomous animats：Fish-swarm algorithm [J].System Engineering Theory and Practice，2002，22(11)：32-38(in Chinese).

［12］李曉磊，路 飛，田國會，等. 組合優(yōu)化問題的人工魚群算法應(yīng)用[J]. 山東大學(xué)學(xué)報：工學(xué)版，2004，34(5)：64-67.Li Xiaolei，Lu Fei，Tian Guohui，et al. Applications of artificial fish school algorithm in combinatorial optimization problems[J].Journal of Shandong University：Engineering Science， 2004 ， 34(5) ： 64-67(in Chinese).

［13］Lopez-Vallejo M，Lopez J C. On the hardware-software partitioning problem：System modeling and partitioning techniques[J].ACM Transactions on Design Automation of Electronic Systems，2003，8(3)：269-297.