遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分.doc

遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分.txt為什么我們在講故事的時候總要加上從前？開了一夏的花，終落得粉身碎骨，卻還笑著說意義。 本文由ahlie1006貢獻 pdf文檔可能在WAP端瀏覽體驗不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機查看。 1000-9825/2005/16(04)0503 2005 Journal of Software 軟 件 學 報 Vol.16, No.4 遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分 熊志輝 1,2+, 李思昆 1, 陳吉華 1 1 2 (國防科學技術大學 計算機學院,湖南 長沙 410073) 410073) (國防科學技術大學 信息系統(tǒng)與管理學院,湖南 長沙 Hardware/Software Partitioning Based on Dynamic Combination of Genetic Algorithm and Ant Algorithm XIONG Zhi-Hui1,2+, 1 2 LI Si-Kun1, CHEN Ji-Hua1 (School of Computer Science, National University of Defense Technology, Changsha 410073, China) (School of Information System and Management, National University of Defense Technology, Changsha 410073, China) + Corresponding author: Phn: +86-731-4573560, Fax: +86-731-4575876, E-mail: , Received 2003-12-30; Accepted 2004-05-08 Xiong ZH, Li SK, Chen JH. Hardware/Software partitioning based on dynamic combination of genetic algorithm and ant algorithm. Journal of Software, 2005,16(4):503512. DOI: 10.1360/jos160503 Abstract: Genetic algorithm can do colony global searching quickly and stochastically, but cant efficiently get to optimal results, since it slows down when solving to certain scope. On the other hand, ant algorithm gets to optimal results efficiently, but lacks initial pheromone at the beginning. To solve the hardware/software bi-partitioning problem in embedded system and system-on-a-chip design, the authors put forward a new algorithm based on dynamic combination of genetic algorithm and ant algorithm. The basic idea is: (1) using genetic algorithm to generate preliminary partitioning results, converting them into initial pheromone distribution for ant algorithm, and then using ant algorithm to search for optimal partitioning scheme; (2) while running genetic algorithm, dynamically determining the best combination time of genetic algorithm and ant algorithm to avoid too early or too late termination of the genetic algorithm. The algorithm utilizes the advantages of the two algorithms and overcomes their disadvantages, and it introduces a dynamic combination strategy between them. Experimental results show the algorithm excels genetic algorithm and ant algorithm in performance, and it is discovered that the bigger the partitioning problem is concerned, the better the algorithm performs. Key words: 摘 要: genetic algorithm; ant algorithm; embedded system; hardware/software partitioning; pheromone 面向嵌入式系統(tǒng)和 SoC(system-on-a-chip)軟硬件雙路劃分問題,提出遺傳算法與螞蟻算法動態(tài)融合的軟 硬件劃分算法.基本思想是:(1) 利用遺傳算法群體性,全局,隨機,快速搜索的優(yōu)勢生成初始劃分解,將其轉化為 Supported by the National Natural Science Foundation of China under Grant No.90207019 (國家自然科學基金); the National High-Tech Research and Development Plan of China under Grant No.2002AA1Z1480 (國家高技術研究發(fā)展計劃(863) 作者簡介: 熊志輝(1976-),男,江西南昌人,博士,講師,主要研究領域為 SoC 系統(tǒng)設計方法,電子設計自動化;李思昆(1941-), 男,教授,博士生導師,主要研究領域為電子設計自動化,SoC 設計方法學,虛擬樣機與分布式虛擬環(huán)境;陳吉華(1963-),男,教授,主要研 究領域為電子設計自動化,VLSI 設計方法學. 504 Journal of Software 軟件學報 2005,16(4) 螞蟻算法所需的初始信息素分布,然后利用螞蟻算法正反饋, 高效 6 收斂的優(yōu)勢求取最優(yōu)劃分解;(2) 在遺傳算法運 行過程中動態(tài)確定遺傳算法與螞蟻算法的最佳融合時機,避免由于遺傳算法過早或過晚結束而影響劃分算法的整 體性能.該算法既發(fā)揮了遺傳算法與螞蟻算法在尋優(yōu)搜索中各自的優(yōu)勢,又克服了遺傳算法在搜索到一定階段時最 優(yōu)解搜索效率低以及螞蟻算法初始信息素匱乏的不足,并且在算法中提出了遺傳算法與螞蟻算法動態(tài)融合的銜接 策略.實驗結果表明,該算法在性能上明顯優(yōu)于遺傳算法和螞蟻算法,并且劃分問題規(guī)模越大,優(yōu)勢越明顯. 關鍵詞: 遺傳算法;螞蟻算法;嵌入式系統(tǒng);軟硬件劃分;信息素 文獻標識碼: A 中圖法分類號: TP18 軟硬件劃分是嵌入式系統(tǒng)和 SoC(system-on-a-chip)軟硬件協(xié)同設計的關鍵步驟,其基本任務是:在滿足某 些約束的條件下,將系統(tǒng)功能行為最優(yōu)地分配到一定的軟硬件系統(tǒng)結構上.根據(jù)目標系統(tǒng)結構不同,軟硬件劃 分問題可分為雙路劃分(bi-partitioning)和多路劃分(multi-way partitioning).其中雙路劃分應用最廣泛,也是軟硬 件劃分問題的基礎.在有些研究中,把劃分作為軟硬件綜合的一部分1,2. 軟硬件劃分是 NP 完全問題3.1992 年,Gupta 等人開發(fā)了一種軟硬件劃分算法用于自動化設計空間探索過 程 2.此后,人們研究了各具特色的劃分算法.其中,應用效果較好的典型算法是啟發(fā)式算法 4,如爬山法 5,遺傳 算法1,6,7,模擬退火8,禁忌搜索9等,這些算法通過定義啟發(fā)信息指導搜索過程逐步向最優(yōu)解收斂.爬山法采 用以退為進的策略尋優(yōu),但易于陷入局部最優(yōu);遺傳算法吸取了生物進化和遺傳變異論的研究成果,是一種群 體性全局尋優(yōu)方法,但算法執(zhí)行到一定階段后向最優(yōu)解收斂速度緩慢.模擬退火算法模擬物質材料的冷卻與結 晶過程,通過退火溫度控制搜索過程,但問題規(guī)模較大時,系統(tǒng)進入熱平衡狀態(tài)(對應于最優(yōu)解)的時間較長.禁忌 搜索法模擬人類智力過程,通過引入靈活的存儲結構和相應禁忌準則來避免迂回搜索,并通過藐視準則赦免一 些 被 禁 忌 的 優(yōu) 良 狀 態(tài) , 具 有 較 強 的 爬 山 能 力 , 但 數(shù) 據(jù) 存 取 操 作 頻 繁 , 影 響 了 搜 索 速 度 . 另 外 , 較 有 特 色 的 軟/硬件排斥節(jié)點和普通節(jié)點來體現(xiàn)進程節(jié)點在硬件和軟件上執(zhí) GCLP/IBS 算法10通過定義軟/硬件極端節(jié)點, 行時表現(xiàn)出來的性能特征,但該算法對目標系統(tǒng)結構的依賴性較大.文獻11提出的約束驅動與松弛時間消除 相結合的軟硬件劃分算法11在求解效率上改進了 GCLP/IBS 算法. 文獻12提出應用螞蟻算法求解軟硬件系統(tǒng)任務雙路劃分問題的方法,試圖在滿足面積約束的條件下優(yōu)化 時間性能.與前述方法相比,該方法在求解時間和尋優(yōu)精度上取得了更好的結果.但單純的螞蟻算法在運行初期 缺乏信息素,這限制了算法搜索效率的進一步提高.我們研究表明,螞蟻算法中約占整個運算過程 65%的時間,被 用于形成最優(yōu)解上的信息素強度. 文 獻 13 提 出 了 遺 傳 算 法 與 螞 蟻 算 法 融 合 的 一 般 性 優(yōu) 化 問 題 求 解 策 略 , 在 對 TSP(traveling salesman problem)問題的應用實驗中取得了良好效果.該策略將遺傳算法設置為運行固定的迭代次數(shù),具有簡單,易行的 優(yōu)點,但這樣容易造成融合時機過早或過晚.文獻14將螞蟻算法與遺傳算法反復交叉,利用螞蟻算法不斷生成 種群個體,進行同步時序電路的初始化,這種優(yōu)化方法能夠盡可能多地初始化觸發(fā)器,但每次種群進化都要經(jīng)歷 幾代,運行效率較低. 面向嵌入式系統(tǒng)和 SoC 軟硬件雙路劃分問題,本文提出遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分算法 (dynamic combination of genetic algorithm and ant algorithm,簡稱 DCG3A).基本思想是:(a) 先利用遺傳算法快 速隨機的群體性全局搜索能力生成劃分問題初始解,并將其轉化為初始信息素分布,然后利用螞蟻算法正反 饋,高效收斂的優(yōu)勢尋求最優(yōu)劃分解.(b) 遺傳算法迭代過程中統(tǒng)計子代群體的進化率,在給定的遺傳迭代次數(shù) 范圍內(nèi),如果連續(xù)若干代,子代群體的進化率都低于預設的最小進化率,則終止遺傳算法過程,進入螞蟻算法,確 保遺傳算法和螞蟻算法在最佳時機融合. 實驗表明,與已有的基于遺傳的劃分算法1和基于螞蟻的劃分算法12相比,本文算法運行效率提高約 1 倍, 而且劃分問題規(guī)模越大,改進效果越明顯. 熊志輝 等:遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分 505 1 遺傳算法與螞蟻算法動態(tài)融合 1.1 遺傳算法簡介 美國 Michigan 大學 J. Holland 教授于 1975 年提出的遺傳算法,以達爾文生物進化理論適者生存,優(yōu)勝劣 汰和孟德爾遺傳變異理論生物遺傳進化主要在染色體上,子代是父代遺傳基因在染色體上的有序排列為基 礎,模擬生物進化過程 15.此算法在自適應控制,組合優(yōu)化,模式識別,機器學習,規(guī)劃策略,信息處理等領 域的應用中展示了明顯的優(yōu)越性.在軟硬件劃分領域,遺傳算法也有應用1,6,7. 遺傳算法的主要優(yōu)點是:a) 具有領域無關的群體性全局搜索能力,可避免陷入局部最優(yōu);b) 搜索使用評價 函數(shù)啟發(fā),過程簡單;c) 使用概率機制進行迭代,具有隨機性;d) 可擴展性強,易于介入到已有模型中,且易于與 其他優(yōu)化技術結合. 主要缺點是:a) 沒有充分利用系統(tǒng)反饋信息,使搜索具有盲目性;b) 算法求解到一定范圍時往往做大量冗 余迭代,向最優(yōu)解收斂的速度大大降低,導致求最優(yōu)解效率較低. 1.2 螞蟻算法簡介 意大利學者 M. Dorigo 在文獻16中提出了螞蟻算法,并因此獲得 2003 年度瑪麗-居里夫人杰出成就獎.研 究表明,幾乎不具備視覺的螞蟻之所以能夠找到蟻巢到食物之間的最短路徑,是靠其在走過的路上釋放一種揮 發(fā)性分泌物(即信息素,pheromone)來實現(xiàn)的,后來的螞蟻選擇該路徑的概率與當時這條路徑上信息素的強度成 正比.當某路徑上通過的螞蟻越來越多時,在此路徑上留下的信息素也越來越強,使得后來的螞蟻選擇此路徑的 概率更高,從而更增加了此路徑上的信息素強度,可吸引更多的螞蟻選擇此路徑,這樣就形成了一種正反饋機 制,使螞蟻最終可發(fā)現(xiàn)最短路徑.螞蟻算法在許多組合優(yōu)化問題上取得了較好的效果,如二次分配問題.TSP 問題 和車間作業(yè)調(diào)度問題等. 螞蟻算法的主要優(yōu)點是:a) 具有正反饋機制,通過信息素的不斷更新高效收斂到最優(yōu)解;b) 具有通用隨機 優(yōu)化特性,并且在螞蟻中融入人類智能;c) 是一種分布式優(yōu)化方法,有利于并行計算;d) 是一種全局優(yōu)化方法,既 可求解單目標優(yōu)化問題,也可求解多目標優(yōu)化問題. 主要缺點是:初期信息素缺乏,導致搜索初期積累信息素占用的時間較長. 1.3 遺傳算法與螞蟻算法動態(tài)融合基本原理 通過對遺傳算法與螞蟻算法的研究與實驗發(fā)現(xiàn),它們在總體態(tài)勢上呈現(xiàn)出如圖 1 所示的速度-時間曲線.遺 傳算法在搜索的初期(t0ta 時間段)具有較高向最優(yōu)解收斂的速度,但 ta 之后求最優(yōu)解的效率顯著降低.而螞蟻算 法在搜索的初期(t0ta 時間段)由于缺乏信息素,使得搜索速度緩慢,但當信息素積累到一定的強度之后(ta 時刻 之后),向最優(yōu)解收斂的速度迅速提高.遺傳算法與螞蟻算法動態(tài)融合的基本思想就是:在最佳點(a 點)之前采用 遺傳算法生成初始信息素分布,在最佳點之后采用螞蟻算法求取最優(yōu)解. v d b Ant algorithm va a c t0 td tb ta tc Genetic algorithm e te t Fig.1 Speed-Time curve of genetic algorithm and ant algorithm 圖1 遺傳算法與螞蟻算法速度-時間曲線 文獻13提出了遺傳算法與螞蟻算法融合的一般性優(yōu)化問題求解策略,在 TSP 應用實驗中取得了良好的優(yōu) 化效果.該策略將遺傳算法設置為運行固定的迭代次數(shù),這樣會造成過早(如 td 時刻)或過晚(如 te 時刻)結束遺傳 算法過程,不能有效保證兩者在最佳時機(ta 時刻)的融合. 506 Journal of Software 軟件學報 2005,16(4) 本文提出的動態(tài)融合策略可以確保遺傳算法與螞蟻算法在最佳時機融合.方法是:a) 設置最小遺傳迭代次 數(shù) Genemin(如 tb 時刻)和最大遺傳迭代次數(shù) Genemax(如 tc 時刻).b) 遺傳算法迭代過程中統(tǒng)計子代群體的進化率, 并以此設置子代群體最小進化率 Genemin-impro-ratio.c) 在設定的迭代次數(shù)范圍內(nèi),如果連續(xù) Genedie 代,子代群體的 進化率都小于 Genemin-impro-ratio,說明這時遺傳算法優(yōu)化速度較低,因此可終止遺傳算法過程,進入螞蟻算法. 2 軟硬件劃分問題與雙著色模型 定義 1(k 路劃分問題). 對于模塊集合 M=m1,m2,mn,k 路劃分問題就是尋找簇的集合 P=p1,p2,pk, 滿足: pi M ,1 i k k . pi = M i =1 pi p j = ,1 i, j k , i j k 路劃分問題的求解通常是要在滿足某些約束的條件下優(yōu)化目標函數(shù).當 k=2 時,稱為雙路劃分問題;當 k2 時,稱為多路劃分問題. 軟硬件劃分是嵌入式系統(tǒng)設計中的關鍵問題之一 ,目前研究和應用較多的是雙路劃分 ,即考慮系統(tǒng)中只有 t0 t1 Software,c1 Hardware,c2 t3 t4 t5 一個處理器再加上 ASIC 或其他硬件部件的情況.本文考慮嵌入式系統(tǒng)任 務軟硬件雙路劃分,并在論文敘述中簡稱為軟硬件劃分. 任務是粗粒度, 接口定義清晰的一系列運算操作的集合,通常表現(xiàn)為 高級語言中的一個算法過程.可以用任務圖表達嵌入式系統(tǒng)的功能行為. 求 解 軟 硬 件 劃 分 問 題 時 , 通 常 用 有 向 無 環(huán) 圖 (DAG) 描 述 任 務 圖 , t2 G=(T,E),其中 ,T=(t0,t1,tn)是任務節(jié)點集 ,E 是有向邊集 .節(jié)點代表功能行 為(t0 和 tn 是虛擬任務節(jié)點,用于確保任務圖中只有一個開始節(jié)點和一個 結尾節(jié)點),有向邊代表節(jié)點之間的控制/數(shù)據(jù)依賴關系與數(shù)據(jù)通信代價. 可以用圖的雙著色模型12來表示軟硬件雙路劃分問題,如圖 2 所示. 把劃分到軟件部分的功能用顏色 c1 表示 ,劃分到硬件部分的功能用顏色 t6 t7 c2 表示 .劃分的目標是尋找任務圖中所有節(jié)點的最優(yōu)著色方案 ,使得在不 t8 tn 超過給定硬件面積的條件下系統(tǒng)的執(zhí)行時間最短.由于 t0 和 tn 是虛擬任務 節(jié)點,因此,最終優(yōu)化方案與節(jié)點 t0,tn,邊 e01 以及邊 e8n 的顏色無關.著色過 程中將邊 eij 的顏色設置為該邊目標節(jié)點(即 tj)的顏色,并且每條邊 eij 對應 于兩個全局啟發(fā)信息ij(k),分別表示任務 tj 被著色為顏色 ck 的概率,其中 Fig.2 Bi-Coloring model 雙著色模型 圖2 k=1,2. 3 基于 DCG3A 的軟硬件劃分算法 下面以軟硬件劃分的雙著色模型為基礎,介紹本文提出的基于 DCG3A 的軟硬件劃分算法. 3.1 DCG3A中的遺傳算法規(guī)則 遺傳編碼:采用二進制編碼方法15,0 代表顏色 c1(劃分到軟件),1 代表顏色 c2(劃分到硬件). 目標函數(shù)與適應值函數(shù) :本文討論的軟硬件劃分是在硬件面積約束條件下使系統(tǒng)運行時間最短 ,因此 ,將目 標函數(shù)定義為 sbest=arg min times,適應值函數(shù)定義為 fitness(s)=1/times.其中,times 表示著色(劃分 )方案 s 的運行 時間. 初始種群生成:采用隨機方法生成初始種群. 選擇算子:采用遺傳算法中應用最廣的轉盤式選擇策略(roulette wheel selection)15. 交叉算子:采用均勻雜交(uniform crossover)策略15. 熊志輝 等:遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分 變異算子:以變異概率 pm 將所選個體位取反. 507 遺傳控制參數(shù)設置 :采用算子執(zhí)行非重疊遺傳過程 , 依據(jù)文獻 15給定的控制參數(shù)經(jīng)驗值范圍 , 設定種群規(guī) 模 N=50,雜交概率 pc=0.6,變異概率 pm=0.2. 遺傳算法結束條件 : 在本文算法中 ,遺傳算法結束條件實際上就是判斷遺傳算法與螞蟻算法的最佳融合時 機 . 我 們 設 置 最 小 遺 傳 迭 代 次 數(shù) Genemin=15, 最 大 遺 傳 迭 代 次 數(shù) Genemax=50, 最 小 進 化 率 Genemin-impro-ratio= 3%,Genedie=3. 3.2 DCG3A中的螞蟻算法規(guī)則 目標函數(shù)與適應值函數(shù):同遺傳算法. 信息素設置與更新規(guī)則:以 Thomas Stuzle 在 MMAS(max-min ant system)算法17中提出的信息素設置與更 新策略為基礎.因此,信息素ij(k)的更新方程為 (1 ) ij (k ) + ij (k ) best 且 ij (k ) = ij (k ) max , if ij (k ) ij (k ) max 且 (k ) , if (k ) (k ) ij ij min ij min (1) 其中,是信息素揮發(fā)率,ij(k)max 和ij(k)min 分別是邊 eij 上 ck 信息素的最大值和最小值(本文分別設定為無限大和 60),ij(k)best 是本圈最佳螞蟻對邊 eij 上 ck 信息素的增加量,定義為 ij (k ) best = 其中,Q 是常數(shù). Q / times , s best中eij 著色為c k best 0, 其他情況 (2) 螞蟻圈模型各因子定義:對于除 tn 以外的每個節(jié)點 ti,螞蟻試圖確定 ti 的每個后繼 tj 的顏色,它主要依據(jù)邊 eij 上的全局啟發(fā)信息(即信息素ij(k)和節(jié)點 tj 上的局部啟發(fā)信息(運行時間與面積的綜合代價)完成此工作.準 確地說,節(jié)點 ti 上的螞蟻,以如下概率猜測后繼節(jié)點 tj 將被著色為 ck: pij (k ) = l =1,2 ij (l ) ij (k ) j (k ) j (l ) (3) 其中,ij(k)是邊 eij 上的信息素,和 是全局啟發(fā)信息和局部啟發(fā)信息相對重要性的控制因子,j(k)是 tj 被著色為 ck 的局部啟發(fā)信息,定義為 j ( k ) = 1 /( wt timet ( k ) + ( wa area j ( k ) , 其中,wt 和 wa 是運行時間和所需硬件面積之間的歸一化權重因子,timej(k)和 areaj(k)分別表示節(jié)點 tj 被著色為 ck 時的運行時間和所需面積. 當螞蟻進入節(jié)點 ti 時,將綜合考慮 ti 所有前驅節(jié)點對 ti 著色猜測的結果,猜測 ti 在本次螞蟻迭代中的顏色. 它以如下概率猜測 ti 被著色為 ck: pi (k ) = 猜測ti 著色為ck的前驅個數(shù) 節(jié)點ti的前驅個數(shù) (4) 螞蟻算法控制參數(shù)設置:=1,wt=1,wa=2,信息素揮發(fā)率=0.2,常數(shù) Q=1000. 螞蟻數(shù)設置:螞蟻數(shù) m 的設置有 2 種選擇:a) m 等于任務圖平均分支數(shù);b) m 等于任務圖最大分支數(shù).本文將 m 設置為任務圖平均分支數(shù). 螞蟻算法結束條件:當滿足以下條件之一時,螞蟻算法終止:a) 螞蟻算法迭代代數(shù)達到 Antmax;b) 迭代中連 續(xù) Antdie 代,子代優(yōu)化解改進率都小于 Antmin-improv-ratio.本文設置 Antmax=100,Antdie=3,Antmin-improv-ratio=0.5%. 3.3 DCG3A中遺傳算法與螞蟻算法的銜接 DCG3A 算法前期執(zhí)行遺傳算法過程,后期執(zhí)行螞蟻算法過程,因此兩者的銜接是很重要的.主要包括這些 問題: 動態(tài)融合時機設置:同前述遺傳算法結束條件. 508 Journal of Software 軟件學報 2005,16(4) 螞蟻算法信息素初值設置:MMAS 算法把各路徑信息素初值設定為最大值 tmax,文獻12中所提算法把初值 固定為0=100.我們利用遺傳算法得到初始信息素分布,將各邊 eij 的信息素初值設定為 S C G ij (k ) = ij (k ) + ij (k ) C 其中, ij (k ) 是 eij 上 ck 信息素常數(shù),相當于 MMAS 中的 tmin, (5) G ij (k)是從遺傳算法求解結果轉換而來的 eij 上的 ck 信息素值.本文設置ij (k)=ij(k)min=60,0i,jn,k=1,2. 遺 傳 算 法 求 解 結 果 向 信 息 素 值 轉 換 : 我 們 選 取 遺 傳 算 法 終 止 時 種 群 中 適 應 值 最 好 的 前 10%( 即 C gene gene G 0.1N=0.150=5)個體作為遺傳優(yōu)化解集合,記為 S10% better .開始時,設置 ij (k ) 為 0,0i,jn,k=1,2.對于 S10% better 中 G 的每個解 s,如果邊 eij 被著色為 ck,則 ij (k ) 自加 20. 3.4 基于DCG3A的軟硬件劃分算法過程 首先將問題描述為雙著色模型,然后執(zhí)行遺傳算法過程,直到到達最佳融合時機為止,然后,按式(5)將遺傳 算法求解結果轉換為螞蟻算法信息素初值,最后執(zhí)行螞蟻算法直到結束. 下面詳細描述 DCG3A 中遺傳算法,螞蟻算法以及兩者銜接部分的執(zhí)行過程. /遺傳算法部分: 1.初始化遺傳算法控制參數(shù)(種群規(guī)模 N=50,雜交概率 pc=0.6,變異概率 pm=0.2); 2.設置遺傳算法結束條件(Genemin=15,Genemax=50,Genemin-impro-ratio=3%,Genedie=3); 3.隨機生成初始種群 P(0),g=0; 4.計算 P(0)中個體的適應值; 5.反復執(zhí)行下列操作,直到滿足遺傳算法結束條件: a) 根據(jù)個體適應值及轉盤式選擇策略確定 P(g)內(nèi)每個個體的選擇概率 pi; b) for(k=0;kN;k=k+2) i. 根據(jù)概率 pi 在 P(g)內(nèi)選擇兩個父體; ii. r=random0,1; iii. if(rpm),對所選 2 個父體執(zhí)行變異操作,并將所得 2 個后代插入新群體 P(g+1)中; else if(rpm+pc),執(zhí)行雜交操作,并將所得 2 個后代插入新群體 P(g+1)中; else,執(zhí)行繁殖操作,將 2 個父體不變地插入新群體 P(g+1)中; /end for(k=0;kN;k=k+2) c) 計算 P(g+1)中個體的適應值,g=g+1; /遺傳算法與螞蟻算法銜接部分: gene 6.從 P(g)中選擇適應能力強的前 10%個體(5 個),放入集合 S10% better 中,作為優(yōu)化解集合; gene 螞蟻算法信息 7.對于 S10% better 中的每個優(yōu)化解 s,按前面描述的遺傳算法求解結果向信息素值轉換策略, /g 是遺傳代數(shù) 素初值設置策略以及式(5),計算任務圖中各邊 eij 關于 ck 的信息素初值ijS(k),k=1,2; /螞蟻算法部分: 8.初始化螞蟻算法控制參數(shù)(=1,wt=1,wa=2,信息素揮發(fā)率=0.2,常數(shù) Q=1000); 9.設置螞蟻算法結束條件(Antmax=100,Antdie=3,Antmin-improv-ratio=0.5%); 10.在節(jié)點 t0 處放置 m 只螞蟻;/t0 是唯一的起點,m 取為任務圖的平均分支數(shù) 11.每只螞蟻按任務圖所對應 DAG 中邊的方向遍歷所有的邊和節(jié)點,最終到達節(jié)點 tn.每只螞蟻在遍歷過程 中,都要依據(jù)式(3)和式(4)計算的概率,猜測所達節(jié)點的顏色,并最終確定一個可行的著色方案 si,i=1,m; 是唯一的終點 12.計算所得 m 種著色方案的適應值,并從中選擇最佳方案 sbest=arg min times; 時間最小的著色方案 13.依據(jù)式(1)和式(2)更新任務圖中所有邊的信息素值; /即滿足面積約束并且運行 /tn 熊志輝 等:遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分 509 14.若滿足螞蟻算法結束條件,報告最佳著色方案 sbest 并退出;否則,繼續(xù)執(zhí)行步驟 10. 3.5 算法分析與討論 (1) 復雜性分析 DCG3A 算法的運行時間 TDCG3A 主要由遺傳算法部分運行時間 TGA, 螞蟻算法部分運行時間 TAA 和銜接部 分運行時間 TJOINT 組成,可表示為 TDCG3A=TGA+TAA+TJOINT.DCG3A 中的遺傳算法與螞蟻算法過程采用相同的適 應值計算規(guī)則,因此我們可以使用一致的時間值 Tcal-fitness 表示這兩個算法中計算每個劃分方案適應值所需的時 間.下面分別分析 TGA,TAA 與 TJOINT 的大小: TGA 包括遺傳算法初始設置時間 TGA-init(步驟 1步驟 3),終止條件判斷時間 TGA-termi 和種群進化迭代時 間(步驟 4,步驟 5).假設遺傳算法進化了 IGA 代,種群規(guī)模為 N,種群中每個個體完成一次遺傳操作(步驟 5 中的 過程 a,b)所需的時間為 TGA-operation,那么,種群迭代進化時間就是 IGAN(TGA-operation+Tcal-fitness).這樣,TGA=TGA-init+ TGA-termi+IGAN(TGA-operation+Tcal-fitness),而 TGA-init+TGA-termi 遠小于 IGAN(TGA-operation+Tcal-fitness),因此,TGAIGAN (TGA-operation+Tcal-fitness). TAA 包括螞蟻算法初始設置時間 TAA-init(步驟 8,步驟 9),終止條件判斷時間 TAA-termi 和螞蟻算法迭代時 間(步驟 10步驟 14).假設螞蟻算法迭代了 IAA 次,每次迭代中使用了 m 只螞蟻,每只螞蟻完成一次任務圖著色 ( 即 求 取 一 個 解 ) 的 時 間 為 TAA-operation, 那 么 , 螞 蟻 算 法 的 迭 代 時 間 就 是 IAAm(TAA-operation+Tcal-fitness). 這 樣,TAA=TAA-init+TAA-termi+IAAm(TAA-operation+Tcal-fitness),而 TAA-init+TAA-termi 遠小于 IAAm(TAA-operation+Tcal-fitness), 因此,TAAIAAm(TAA-operation+Tcal-fitness). TJOINT 包括構造優(yōu)化解集合(步驟 6)所需的時間 TJOINT-10%better 與計算信息素初值(步驟 7)所需的時間 TJOINT-initial-pheromone.假設采用逐個順序比較的方法構造優(yōu)化解集合,那么 TJOINT-10%betterNN10%Tfloat-compare(其 中,Tfloat-compare 為完成一次浮點數(shù)比較所需的時間;10%表示選擇了適應值高的 10%個體).進一步假設任務圖節(jié) 點數(shù)為 K,邊數(shù)為 H,每次計算一條邊上的信息素值的時間為 TJOINT-edge-pheromone,那么,信息素初值計算時間 TJOINTinitial-pheromone 就是 N10%HTJOINT-edge-pheromone.這樣,TJOINTNN10%Tfloat-compare+N10%HTJOINT-edge-pheromone. 由 上 述 分 析 可 知 , TDCG3AIGAN(TGA-operation+Tcal-fitness)+IAAm(TAA-operation+Tcal-fitness)+NN10%Tfloat-compare+ N10% H TJOINT-edge-pheromone.實際運算中,我們發(fā)現(xiàn) Tcal-fitness 的復雜度為 O(KH),遠大于 TGA-operation,TAA-operation 以及 NN10%Tfloat-compare+N10%HTJOINT-edge-pheromone.因此,可以將 TDCG3A 簡化為 TDCG3AIGANTcal-fitness+ IAAmTcal-fitness=(IGAN+IAAm)Tcal-fitness. 在 運 行 過 程 中 , 遺 傳 算 法 部 分 所 需 的 存 儲 空 間 約 為 2NO(K), 螞 蟻 算 法 部 分 所 需 的 存 儲 空 間 約 為 mO(K+H),算法銜接部分構造優(yōu)化解集合所需的存儲空間為 10%NO(K).當然,不同的程序實現(xiàn),對算法運算 時間與存儲空間也有一定的影響. (2) 算法運行效率探討 上述復雜性分析表明,DCG3A 算法的運行時間 TDCG3A 主要取決于 IGAN+IAAm 與 Tcal-fitness 的乘積.其 中,Tcal-fitness 是對某個劃分解進行評價(求適應值)所需的時間,與所用的優(yōu)化算法無關.對于特定的組合優(yōu)化問 題,Tcal-fitness 本質上是評價問題空間中一個解所需的時間.因此,DCG3A 算法效率改進的關鍵在于最小化 IGAN +IAAm,其中 N,m 是控制參數(shù),分別表示遺傳算法的種群規(guī)模和螞蟻算法的螞蟻數(shù),在算法中一般是固定的值. 極端情況下,當遺傳算法迭代次數(shù) IGA 為 0 時,DCG3A 算法就退化為螞蟻算法;當螞蟻算法迭代次數(shù) IAA 為 0 時,DCG3A 算法則退化為遺傳算法. DCG3A 在遺傳算法運行過程中加入了子代優(yōu)化解改進效率檢測機制,使得當遺傳算法對優(yōu)化解改進效率 降低到一定程度時,及時終止遺傳過程,從而避免 IGA 無謂的增長.此外,由于有了較為準確的初始信息素,使螞蟻 算法大大降低了用于形成最優(yōu)解上信息素所需的迭代次數(shù).這時,利用螞蟻算法正反饋,高效收斂的優(yōu)勢,可以 在 IAA 很 小 的 情 況 下 ,迅 速 找 到 最 優(yōu) 解 . 因 此 ,DCG3A 算 法 通 過 抑 制 IGA 與 IAA 無 謂 的 增 長 , 從 而 最 小 化 IGAN+IAAm 來達到提高搜索效率的目的. 510 Journal of Software 軟件學報 2005,16(4) 4 實 驗 采用與文獻12相似的實驗模型和方法,與基于遺傳算法1,基于螞蟻算法12的軟硬件劃分進行比較. 4.1 目標系統(tǒng)結構 本文考慮軟硬件系統(tǒng)任務雙路劃分問題,目標系統(tǒng)中有 PowerPC RISK CPU core Shared memory Configurable logic blocks (FPGA) 1 個處理器和 1 個硬件可編程部件(如 FPGA).使用 Xilinx Distributed local memory Virtex II Pro Platform FPGA 作為參考模型,它最多可包含 4 個 處理器核,13 404 個可編程邏輯塊.實驗中,我們限制使用 1 個 處理器和最多 1 232 個可編程邏輯塊.目標系統(tǒng)結構抽象模型 如圖 3 所示. Fig.3 Abstract model of target architecture 圖3 目標系統(tǒng)結構抽象模型 4.2 實驗假設 為簡化實驗,作如下合理的假設: a) 任務在處理器和在可編程部件上實現(xiàn)所需的運行時間和占用的硬件面積是靜態(tài)的,可預先計算出來; b) 任務間通信開銷不變并已經(jīng)包含在任務的開銷(時間,面積)中; c) 不考慮硬件實現(xiàn)的并行性. 4.3 實驗環(huán)境與實例 目前,在嵌入式系統(tǒng)軟硬件劃分領域,國際上還沒有公認的測試集 12.常見做法是隨機生成有向無環(huán)圖,并 對節(jié)點與邊賦以屬性.我們采用如下方法構造測試集:a) 用 GVF 工具包隨機生成指定節(jié)點數(shù), 指定平均分支數(shù) 的若干個有向無環(huán)圖,作為任務圖;b) 將每個任務與一個函數(shù)(或算法過程)相關聯(lián),并以此函數(shù)的開銷(運行時 間,硬件面積,通信代價等)作為任務開銷;c) 從 MediaBench 基準程序包中選擇與任務相關聯(lián)的函數(shù). 利用上述方法生成 7 組 DAG(分別記為 DAG20,DAG30,DAG80),每組包含 30 個 DAG 樣本.7 組 DAG 的節(jié) 點數(shù)分別為 20,30,80,平均分支數(shù)依次為 5,5,7,7,9,9,11.以各組 30 個樣本的性能平均值作為該組的最終性能 結果. 實驗環(huán)境為:a) AMD Duron 700MHz 處理器,128MB 內(nèi)存,b) Linux 7.3 操作系統(tǒng),c) KDevelop 2.1 編程環(huán)境. 4.4 實驗結果與分析 螞蟻算法12進行軟硬件劃分得到的實驗數(shù)據(jù).其中,遺傳算法 表 1 給出了本文 DCG3A 算法與遺傳算法1, 與螞蟻算法中控制參數(shù)的設置與 DCG3A 中相應的設置相同.我們使這 3 種算法求解的最優(yōu)解與理論最優(yōu)解之 間的誤差基本一致,以保證公平性.圖 4 描述了表 1 中 3 種算法求解時間與節(jié)點規(guī)模的關系. Table 1 Comparison of genetic algorithm (GA), ant algorithm (AA) and DCG3A algorithm 表1 遺傳算法,螞蟻算法與 DCG3A 算法對比 AA12 Iterations 72.3 65.1 83.6 89.2 92.7 68.0 97.5 Time (ms) 332 659 1 463 2 235 3 280 5 762 9 368 Iterations 43.2 36.8 47.3 44.7 68.7 51.3 55.1 Time (ms) 207 513 742 1 662 2 038 2 679 3 651 DCG3A IterationsGA+AA 23.1+14.6 31.2+12.4 19.4+21.6 27.7+18.3 26.8+21.8 21.4+19.4 27.2+16.3 TotalDAGNodes 20 30 40 50 60 70 80 GA1 Time (ms) 258 579 1 296 2 694 4 833 8 436 15 623 當任務圖節(jié)點數(shù)較少(2030)時,DCG3A 算法略優(yōu)于遺傳算法和螞蟻算法,但效果不很明顯.而當節(jié)點數(shù)超 過 40 時,DCG3A 算法明顯優(yōu)于遺傳算法和螞蟻算法.隨著任務圖規(guī)模的增大,性能改進的效果越顯著. 算法控制參數(shù)對實驗結果也有一定的影響,本實驗使用了文獻1,12中相同的控制參數(shù),以增強可比性.對 于特定的組合優(yōu)化問題,可分別使用相應問題中已驗證的優(yōu)化控制參數(shù),也可以使用典型控制參數(shù)設置值15,16. 控制參數(shù) Genemin-impro-ratio 決定了遺傳算法的終止時機,此值若過大,則遺傳算法在更接近 tb(如圖 1 所示)的時刻 熊志輝 等:遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分 511 結束;若過小,遺傳算法就將在靠近 tc 的時刻結束.實驗發(fā)現(xiàn),當 Genemin-impro-ratio=3%時,遺傳算法在 tb 與 tc 之間中 間點位置(靠近最佳融合時機 ta)結束,因此,本實驗將 Genemin-impro-ratio 設置為 3%. 在所使用的目標體系結構下,本實驗在一定的硬件面積約束下優(yōu)化系統(tǒng)運行時間.實際上,在嵌入式系統(tǒng)與 SoC 軟硬件劃分中,其他性能指標(如功耗)的約束與優(yōu)化也是非常重要的方面,本文算法同樣適用于求解這類 劃分問題.另外,對于具有強實時性需求的嵌入式系統(tǒng)與 SoC 軟硬件劃分問題,需要多個嵌入式處理器協(xié)同工作, 這時,除了運用本文算法進行劃分求解外,還需要在劃分中考慮嵌入式處理器之間的任務分配與負載平衡,我們 將繼續(xù)對這個問題進行深入的研究. 18000 16000 Genetic algorithm 14000 12000 Search time used (ms) 10000 8000 6000 * * * Ant algorithm * 4000 2000 0 * 20 * * * * * * * * * Our algorithm * 30 * * * * * * 40 50 60 70 80 Count of task nodes Fig.4 圖4 Running-Time/nodes curve 運算時間-節(jié)點規(guī)模曲線 5 結 語 DCG3A 算法吸取了遺傳算法與螞蟻算法在尋優(yōu)問題上各自的優(yōu)勢,克服了它們的不足.在嵌入式系統(tǒng)和 SoC 軟硬件劃分中取得了很好的效果,并且隨著問題規(guī)模的增大,性能改進更顯著. 下一步我們將研究不同控制參數(shù)值對 DCG3A 算法性能的影響,尋找適合 DCG3A 軟硬件劃分算法控制參 數(shù)的一組經(jīng)驗值,并將 DCG3A 算法應用于軟硬件多路劃分問題. References: 1 Zhang LF. Research on techniques of hard