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

遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分.txt為什么我們?cè)谥v故事的時(shí)候總要加上從前？開(kāi)了一夏的花，終落得粉身碎骨，卻還笑著說(shuō)意義。 本文由ahlie1006貢獻(xiàn) pdf文檔可能在WAP端瀏覽體驗(yàn)不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機(jī)查看。 1000-9825/2005/16(04)0503 2005 Journal of Software 軟 件 學(xué) 報(bào) Vol.16, No.4 遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分 熊志輝 1,2+, 李思昆 1, 陳吉華 1 1 2 (國(guó)防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073) 410073) (國(guó)防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)與管理學(xué)院,湖南 長(zhǎ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)軟硬件雙路劃分問(wèn)題,提出遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟 硬件劃分算法.基本思想是:(1) 利用遺傳算法群體性,全局,隨機(jī),快速搜索的優(yōu)勢(shì)生成初始劃分解,將其轉(zhuǎn)化為 Supported by the National Natural Science Foundation of China under Grant No.90207019 (國(guó)家自然科學(xué)基金); the National High-Tech Research and Development Plan of China under Grant No.2002AA1Z1480 (國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863) 作者簡(jiǎn)介: 熊志輝(1976-),男,江西南昌人,博士,講師,主要研究領(lǐng)域?yàn)?SoC 系統(tǒng)設(shè)計(jì)方法,電子設(shè)計(jì)自動(dòng)化;李思昆(1941-), 男,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)殡娮釉O(shè)計(jì)自動(dòng)化,SoC 設(shè)計(jì)方法學(xué),虛擬樣機(jī)與分布式虛擬環(huán)境;陳吉華(1963-),男,教授,主要研 究領(lǐng)域?yàn)殡娮釉O(shè)計(jì)自動(dòng)化,VLSI 設(shè)計(jì)方法學(xué). 504 Journal of Software 軟件學(xué)報(bào) 2005,16(4) 螞蟻算法所需的初始信息素分布,然后利用螞蟻算法正反饋, 高效 6 收斂的優(yōu)勢(shì)求取最優(yōu)劃分解;(2) 在遺傳算法運(yùn) 行過(guò)程中動(dòng)態(tài)確定遺傳算法與螞蟻算法的最佳融合時(shí)機(jī),避免由于遺傳算法過(guò)早或過(guò)晚結(jié)束而影響劃分算法的整 體性能.該算法既發(fā)揮了遺傳算法與螞蟻算法在尋優(yōu)搜索中各自的優(yōu)勢(shì),又克服了遺傳算法在搜索到一定階段時(shí)最 優(yōu)解搜索效率低以及螞蟻算法初始信息素匱乏的不足,并且在算法中提出了遺傳算法與螞蟻算法動(dòng)態(tài)融合的銜接 策略.實(shí)驗(yàn)結(jié)果表明,該算法在性能上明顯優(yōu)于遺傳算法和螞蟻算法,并且劃分問(wèn)題規(guī)模越大,優(yōu)勢(shì)越明顯. 關(guān)鍵詞: 遺傳算法;螞蟻算法;嵌入式系統(tǒng);軟硬件劃分;信息素 文獻(xiàn)標(biāo)識(shí)碼: A 中圖法分類號(hào): TP18 軟硬件劃分是嵌入式系統(tǒng)和 SoC(system-on-a-chip)軟硬件協(xié)同設(shè)計(jì)的關(guān)鍵步驟,其基本任務(wù)是:在滿足某 些約束的條件下,將系統(tǒng)功能行為最優(yōu)地分配到一定的軟硬件系統(tǒng)結(jié)構(gòu)上.根據(jù)目標(biāo)系統(tǒng)結(jié)構(gòu)不同,軟硬件劃 分問(wèn)題可分為雙路劃分(bi-partitioning)和多路劃分(multi-way partitioning).其中雙路劃分應(yīng)用最廣泛,也是軟硬 件劃分問(wèn)題的基礎(chǔ).在有些研究中,把劃分作為軟硬件綜合的一部分1,2. 軟硬件劃分是 NP 完全問(wèn)題3.1992 年,Gupta 等人開(kāi)發(fā)了一種軟硬件劃分算法用于自動(dòng)化設(shè)計(jì)空間探索過(guò) 程 2.此后,人們研究了各具特色的劃分算法.其中,應(yīng)用效果較好的典型算法是啟發(fā)式算法 4,如爬山法 5,遺傳 算法1,6,7,模擬退火8,禁忌搜索9等,這些算法通過(guò)定義啟發(fā)信息指導(dǎo)搜索過(guò)程逐步向最優(yōu)解收斂.爬山法采 用以退為進(jìn)的策略尋優(yōu),但易于陷入局部最優(yōu);遺傳算法吸取了生物進(jìn)化和遺傳變異論的研究成果,是一種群 體性全局尋優(yōu)方法,但算法執(zhí)行到一定階段后向最優(yōu)解收斂速度緩慢.模擬退火算法模擬物質(zhì)材料的冷卻與結(jié) 晶過(guò)程,通過(guò)退火溫度控制搜索過(guò)程,但問(wèn)題規(guī)模較大時(shí),系統(tǒng)進(jìn)入熱平衡狀態(tài)(對(duì)應(yīng)于最優(yōu)解)的時(shí)間較長(zhǎng).禁忌 搜索法模擬人類智力過(guò)程,通過(guò)引入靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)禁忌準(zhǔn)則來(lái)避免迂回搜索,并通過(guò)藐視準(zhǔn)則赦免一 些 被 禁 忌 的 優(yōu) 良 狀 態(tài) , 具 有 較 強(qiáng) 的 爬 山 能 力 , 但 數(shù) 據(jù) 存 取 操 作 頻 繁 , 影 響 了 搜 索 速 度 . 另 外 , 較 有 特 色 的 軟/硬件排斥節(jié)點(diǎn)和普通節(jié)點(diǎn)來(lái)體現(xiàn)進(jìn)程節(jié)點(diǎn)在硬件和軟件上執(zhí) GCLP/IBS 算法10通過(guò)定義軟/硬件極端節(jié)點(diǎn), 行時(shí)表現(xiàn)出來(lái)的性能特征,但該算法對(duì)目標(biāo)系統(tǒng)結(jié)構(gòu)的依賴性較大.文獻(xiàn)11提出的約束驅(qū)動(dòng)與松弛時(shí)間消除 相結(jié)合的軟硬件劃分算法11在求解效率上改進(jìn)了 GCLP/IBS 算法. 文獻(xiàn)12提出應(yīng)用螞蟻算法求解軟硬件系統(tǒng)任務(wù)雙路劃分問(wèn)題的方法,試圖在滿足面積約束的條件下優(yōu)化 時(shí)間性能.與前述方法相比,該方法在求解時(shí)間和尋優(yōu)精度上取得了更好的結(jié)果.但單純的螞蟻算法在運(yùn)行初期 缺乏信息素,這限制了算法搜索效率的進(jìn)一步提高.我們研究表明,螞蟻算法中約占整個(gè)運(yùn)算過(guò)程 65%的時(shí)間,被 用于形成最優(yōu)解上的信息素強(qiáng)度. 文 獻(xiàn) 13 提 出 了 遺 傳 算 法 與 螞 蟻 算 法 融 合 的 一 般 性 優(yōu) 化 問(wèn) 題 求 解 策 略 , 在 對(duì) TSP(traveling salesman problem)問(wèn)題的應(yīng)用實(shí)驗(yàn)中取得了良好效果.該策略將遺傳算法設(shè)置為運(yùn)行固定的迭代次數(shù),具有簡(jiǎn)單,易行的 優(yōu)點(diǎn),但這樣容易造成融合時(shí)機(jī)過(guò)早或過(guò)晚.文獻(xiàn)14將螞蟻算法與遺傳算法反復(fù)交叉,利用螞蟻算法不斷生成 種群個(gè)體,進(jìn)行同步時(shí)序電路的初始化,這種優(yōu)化方法能夠盡可能多地初始化觸發(fā)器,但每次種群進(jìn)化都要經(jīng)歷 幾代,運(yùn)行效率較低. 面向嵌入式系統(tǒng)和 SoC 軟硬件雙路劃分問(wèn)題,本文提出遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分算法 (dynamic combination of genetic algorithm and ant algorithm,簡(jiǎn)稱 DCG3A).基本思想是:(a) 先利用遺傳算法快 速隨機(jī)的群體性全局搜索能力生成劃分問(wèn)題初始解,并將其轉(zhuǎn)化為初始信息素分布,然后利用螞蟻算法正反 饋,高效收斂的優(yōu)勢(shì)尋求最優(yōu)劃分解.(b) 遺傳算法迭代過(guò)程中統(tǒng)計(jì)子代群體的進(jìn)化率,在給定的遺傳迭代次數(shù) 范圍內(nèi),如果連續(xù)若干代,子代群體的進(jìn)化率都低于預(yù)設(shè)的最小進(jìn)化率,則終止遺傳算法過(guò)程,進(jìn)入螞蟻算法,確 保遺傳算法和螞蟻算法在最佳時(shí)機(jī)融合. 實(shí)驗(yàn)表明,與已有的基于遺傳的劃分算法1和基于螞蟻的劃分算法12相比,本文算法運(yùn)行效率提高約 1 倍, 而且劃分問(wèn)題規(guī)模越大,改進(jìn)效果越明顯. 熊志輝 等:遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分 505 1 遺傳算法與螞蟻算法動(dòng)態(tài)融合 1.1 遺傳算法簡(jiǎn)介 美國(guó) Michigan 大學(xué) J. Holland 教授于 1975 年提出的遺傳算法,以達(dá)爾文生物進(jìn)化理論適者生存,優(yōu)勝劣 汰和孟德?tīng)栠z傳變異理論生物遺傳進(jìn)化主要在染色體上,子代是父代遺傳基因在染色體上的有序排列為基 礎(chǔ),模擬生物進(jìn)化過(guò)程 15.此算法在自適應(yīng)控制,組合優(yōu)化,模式識(shí)別,機(jī)器學(xué)習(xí),規(guī)劃策略,信息處理等領(lǐng) 域的應(yīng)用中展示了明顯的優(yōu)越性.在軟硬件劃分領(lǐng)域,遺傳算法也有應(yīng)用1,6,7. 遺傳算法的主要優(yōu)點(diǎn)是:a) 具有領(lǐng)域無(wú)關(guān)的群體性全局搜索能力,可避免陷入局部最優(yōu);b) 搜索使用評(píng)價(jià) 函數(shù)啟發(fā),過(guò)程簡(jiǎn)單;c) 使用概率機(jī)制進(jìn)行迭代,具有隨機(jī)性;d) 可擴(kuò)展性強(qiáng),易于介入到已有模型中,且易于與 其他優(yōu)化技術(shù)結(jié)合. 主要缺點(diǎn)是:a) 沒(méi)有充分利用系統(tǒng)反饋信息,使搜索具有盲目性;b) 算法求解到一定范圍時(shí)往往做大量冗 余迭代,向最優(yōu)解收斂的速度大大降低,導(dǎo)致求最優(yōu)解效率較低. 1.2 螞蟻算法簡(jiǎn)介 意大利學(xué)者 M. Dorigo 在文獻(xiàn)16中提出了螞蟻算法,并因此獲得 2003 年度瑪麗-居里夫人杰出成就獎(jiǎng).研 究表明,幾乎不具備視覺(jué)的螞蟻之所以能夠找到蟻巢到食物之間的最短路徑,是靠其在走過(guò)的路上釋放一種揮 發(fā)性分泌物(即信息素,pheromone)來(lái)實(shí)現(xiàn)的,后來(lái)的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上信息素的強(qiáng)度成 正比.當(dāng)某路徑上通過(guò)的螞蟻越來(lái)越多時(shí),在此路徑上留下的信息素也越來(lái)越強(qiáng),使得后來(lái)的螞蟻選擇此路徑的 概率更高,從而更增加了此路徑上的信息素強(qiáng)度,可吸引更多的螞蟻選擇此路徑,這樣就形成了一種正反饋機(jī) 制,使螞蟻?zhàn)罱K可發(fā)現(xiàn)最短路徑.螞蟻算法在許多組合優(yōu)化問(wèn)題上取得了較好的效果,如二次分配問(wèn)題.TSP 問(wèn)題 和車間作業(yè)調(diào)度問(wèn)題等. 螞蟻算法的主要優(yōu)點(diǎn)是:a) 具有正反饋機(jī)制,通過(guò)信息素的不斷更新高效收斂到最優(yōu)解;b) 具有通用隨機(jī) 優(yōu)化特性,并且在螞蟻中融入人類智能;c) 是一種分布式優(yōu)化方法,有利于并行計(jì)算;d) 是一種全局優(yōu)化方法,既 可求解單目標(biāo)優(yōu)化問(wèn)題,也可求解多目標(biāo)優(yōu)化問(wèn)題. 主要缺點(diǎn)是:初期信息素缺乏,導(dǎo)致搜索初期積累信息素占用的時(shí)間較長(zhǎng). 1.3 遺傳算法與螞蟻算法動(dòng)態(tài)融合基本原理 通過(guò)對(duì)遺傳算法與螞蟻算法的研究與實(shí)驗(yàn)發(fā)現(xiàn),它們?cè)诳傮w態(tài)勢(shì)上呈現(xiàn)出如圖 1 所示的速度-時(shí)間曲線.遺 傳算法在搜索的初期(t0ta 時(shí)間段)具有較高向最優(yōu)解收斂的速度,但 ta 之后求最優(yōu)解的效率顯著降低.而螞蟻算 法在搜索的初期(t0ta 時(shí)間段)由于缺乏信息素,使得搜索速度緩慢,但當(dāng)信息素積累到一定的強(qiáng)度之后(ta 時(shí)刻 之后),向最優(yōu)解收斂的速度迅速提高.遺傳算法與螞蟻算法動(dòng)態(tài)融合的基本思想就是:在最佳點(diǎn)(a 點(diǎn))之前采用 遺傳算法生成初始信息素分布,在最佳點(diǎn)之后采用螞蟻算法求取最優(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 遺傳算法與螞蟻算法速度-時(shí)間曲線 文獻(xiàn)13提出了遺傳算法與螞蟻算法融合的一般性優(yōu)化問(wèn)題求解策略,在 TSP 應(yīng)用實(shí)驗(yàn)中取得了良好的優(yōu) 化效果.該策略將遺傳算法設(shè)置為運(yùn)行固定的迭代次數(shù),這樣會(huì)造成過(guò)早(如 td 時(shí)刻)或過(guò)晚(如 te 時(shí)刻)結(jié)束遺傳 算法過(guò)程,不能有效保證兩者在最佳時(shí)機(jī)(ta 時(shí)刻)的融合. 506 Journal of Software 軟件學(xué)報(bào) 2005,16(4) 本文提出的動(dòng)態(tài)融合策略可以確保遺傳算法與螞蟻算法在最佳時(shí)機(jī)融合.方法是:a) 設(shè)置最小遺傳迭代次 數(shù) Genemin(如 tb 時(shí)刻)和最大遺傳迭代次數(shù) Genemax(如 tc 時(shí)刻).b) 遺傳算法迭代過(guò)程中統(tǒng)計(jì)子代群體的進(jìn)化率, 并以此設(shè)置子代群體最小進(jìn)化率 Genemin-impro-ratio.c) 在設(shè)定的迭代次數(shù)范圍內(nèi),如果連續(xù) Genedie 代,子代群體的 進(jìn)化率都小于 Genemin-impro-ratio,說(shuō)明這時(shí)遺傳算法優(yōu)化速度較低,因此可終止遺傳算法過(guò)程,進(jìn)入螞蟻算法. 2 軟硬件劃分問(wèn)題與雙著色模型 定義 1(k 路劃分問(wèn)題). 對(duì)于模塊集合 M=m1,m2,mn,k 路劃分問(wèn)題就是尋找簇的集合 P=p1,p2,pk, 滿足: pi M ,1 i k k . pi = M i =1 pi p j = ,1 i, j k , i j k 路劃分問(wèn)題的求解通常是要在滿足某些約束的條件下優(yōu)化目標(biāo)函數(shù).當(dāng) k=2 時(shí),稱為雙路劃分問(wèn)題;當(dāng) k2 時(shí),稱為多路劃分問(wèn)題. 軟硬件劃分是嵌入式系統(tǒng)設(shè)計(jì)中的關(guān)鍵問(wèn)題之一 ,目前研究和應(yīng)用較多的是雙路劃分 ,即考慮系統(tǒng)中只有 t0 t1 Software,c1 Hardware,c2 t3 t4 t5 一個(gè)處理器再加上 ASIC 或其他硬件部件的情況.本文考慮嵌入式系統(tǒng)任 務(wù)軟硬件雙路劃分,并在論文敘述中簡(jiǎn)稱為軟硬件劃分. 任務(wù)是粗粒度, 接口定義清晰的一系列運(yùn)算操作的集合,通常表現(xiàn)為 高級(jí)語(yǔ)言中的一個(gè)算法過(guò)程.可以用任務(wù)圖表達(dá)嵌入式系統(tǒng)的功能行為. 求 解 軟 硬 件 劃 分 問(wèn) 題 時(shí) , 通 常 用 有 向 無(wú) 環(huán) 圖 (DAG) 描 述 任 務(wù) 圖 , t2 G=(T,E),其中 ,T=(t0,t1,tn)是任務(wù)節(jié)點(diǎn)集 ,E 是有向邊集 .節(jié)點(diǎn)代表功能行 為(t0 和 tn 是虛擬任務(wù)節(jié)點(diǎn),用于確保任務(wù)圖中只有一個(gè)開(kāi)始節(jié)點(diǎn)和一個(gè) 結(jié)尾節(jié)點(diǎn)),有向邊代表節(jié)點(diǎn)之間的控制/數(shù)據(jù)依賴關(guān)系與數(shù)據(jù)通信代價(jià). 可以用圖的雙著色模型12來(lái)表示軟硬件雙路劃分問(wèn)題,如圖 2 所示. 把劃分到軟件部分的功能用顏色 c1 表示 ,劃分到硬件部分的功能用顏色 t6 t7 c2 表示 .劃分的目標(biāo)是尋找任務(wù)圖中所有節(jié)點(diǎn)的最優(yōu)著色方案 ,使得在不 t8 tn 超過(guò)給定硬件面積的條件下系統(tǒng)的執(zhí)行時(shí)間最短.由于 t0 和 tn 是虛擬任務(wù) 節(jié)點(diǎn),因此,最終優(yōu)化方案與節(jié)點(diǎn) t0,tn,邊 e01 以及邊 e8n 的顏色無(wú)關(guān).著色過(guò) 程中將邊 eij 的顏色設(shè)置為該邊目標(biāo)節(jié)點(diǎn)(即 tj)的顏色,并且每條邊 eij 對(duì)應(yīng) 于兩個(gè)全局啟發(fā)信息ij(k),分別表示任務(wù) tj 被著色為顏色 ck 的概率,其中 Fig.2 Bi-Coloring model 雙著色模型 圖2 k=1,2. 3 基于 DCG3A 的軟硬件劃分算法 下面以軟硬件劃分的雙著色模型為基礎(chǔ),介紹本文提出的基于 DCG3A 的軟硬件劃分算法. 3.1 DCG3A中的遺傳算法規(guī)則 遺傳編碼:采用二進(jìn)制編碼方法15,0 代表顏色 c1(劃分到軟件),1 代表顏色 c2(劃分到硬件). 目標(biāo)函數(shù)與適應(yīng)值函數(shù) :本文討論的軟硬件劃分是在硬件面積約束條件下使系統(tǒng)運(yùn)行時(shí)間最短 ,因此 ,將目 標(biāo)函數(shù)定義為 sbest=arg min times,適應(yīng)值函數(shù)定義為 fitness(s)=1/times.其中,times 表示著色(劃分 )方案 s 的運(yùn)行 時(shí)間. 初始種群生成:采用隨機(jī)方法生成初始種群. 選擇算子:采用遺傳算法中應(yīng)用最廣的轉(zhuǎn)盤式選擇策略(roulette wheel selection)15. 交叉算子:采用均勻雜交(uniform crossover)策略15. 熊志輝 等:遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分 變異算子:以變異概率 pm 將所選個(gè)體位取反. 507 遺傳控制參數(shù)設(shè)置 :采用算子執(zhí)行非重疊遺傳過(guò)程 , 依據(jù)文獻(xiàn) 15給定的控制參數(shù)經(jīng)驗(yàn)值范圍 , 設(shè)定種群規(guī) 模 N=50,雜交概率 pc=0.6,變異概率 pm=0.2. 遺傳算法結(jié)束條件 : 在本文算法中 ,遺傳算法結(jié)束條件實(shí)際上就是判斷遺傳算法與螞蟻算法的最佳融合時(shí) 機(jī) . 我 們 設(shè) 置 最 小 遺 傳 迭 代 次 數(shù) Genemin=15, 最 大 遺 傳 迭 代 次 數(shù) Genemax=50, 最 小 進(jìn) 化 率 Genemin-impro-ratio= 3%,Genedie=3. 3.2 DCG3A中的螞蟻算法規(guī)則 目標(biāo)函數(shù)與適應(yīng)值函數(shù):同遺傳算法. 信息素設(shè)置與更新規(guī)則:以 Thomas Stuzle 在 MMAS(max-min ant system)算法17中提出的信息素設(shè)置與更 新策略為基礎(chǔ).因此,信息素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ù)]發(fā)率,ij(k)max 和ij(k)min 分別是邊 eij 上 ck 信息素的最大值和最小值(本文分別設(shè)定為無(wú)限大和 60),ij(k)best 是本圈最佳螞蟻對(duì)邊 eij 上 ck 信息素的增加量,定義為 ij (k ) best = 其中,Q 是常數(shù). Q / times , s best中eij 著色為c k best 0, 其他情況 (2) 螞蟻圈模型各因子定義:對(duì)于除 tn 以外的每個(gè)節(jié)點(diǎn) ti,螞蟻試圖確定 ti 的每個(gè)后繼 tj 的顏色,它主要依據(jù)邊 eij 上的全局啟發(fā)信息(即信息素ij(k)和節(jié)點(diǎn) tj 上的局部啟發(fā)信息(運(yùn)行時(shí)間與面積的綜合代價(jià))完成此工作.準(zhǔn) 確地說(shuō),節(jié)點(diǎn) ti 上的螞蟻,以如下概率猜測(cè)后繼節(jié)點(diǎn) tj 將被著色為 ck: pij (k ) = l =1,2 ij (l ) ij (k ) j (k ) j (l ) (3) 其中,ij(k)是邊 eij 上的信息素,和 是全局啟發(fā)信息和局部啟發(fā)信息相對(duì)重要性的控制因子,j(k)是 tj 被著色為 ck 的局部啟發(fā)信息,定義為 j ( k ) = 1 /( wt timet ( k ) + ( wa area j ( k ) , 其中,wt 和 wa 是運(yùn)行時(shí)間和所需硬件面積之間的歸一化權(quán)重因子,timej(k)和 areaj(k)分別表示節(jié)點(diǎn) tj 被著色為 ck 時(shí)的運(yùn)行時(shí)間和所需面積. 當(dāng)螞蟻進(jìn)入節(jié)點(diǎn) ti 時(shí),將綜合考慮 ti 所有前驅(qū)節(jié)點(diǎn)對(duì) ti 著色猜測(cè)的結(jié)果,猜測(cè) ti 在本次螞蟻迭代中的顏色. 它以如下概率猜測(cè) ti 被著色為 ck: pi (k ) = 猜測(cè)ti 著色為ck的前驅(qū)個(gè)數(shù) 節(jié)點(diǎn)ti的前驅(qū)個(gè)數(shù) (4) 螞蟻算法控制參數(shù)設(shè)置:=1,wt=1,wa=2,信息素?fù)]發(fā)率=0.2,常數(shù) Q=1000. 螞蟻數(shù)設(shè)置:螞蟻數(shù) m 的設(shè)置有 2 種選擇:a) m 等于任務(wù)圖平均分支數(shù);b) m 等于任務(wù)圖最大分支數(shù).本文將 m 設(shè)置為任務(wù)圖平均分支數(shù). 螞蟻算法結(jié)束條件:當(dāng)滿足以下條件之一時(shí),螞蟻算法終止:a) 螞蟻算法迭代代數(shù)達(dá)到 Antmax;b) 迭代中連 續(xù) Antdie 代,子代優(yōu)化解改進(jìn)率都小于 Antmin-improv-ratio.本文設(shè)置 Antmax=100,Antdie=3,Antmin-improv-ratio=0.5%. 3.3 DCG3A中遺傳算法與螞蟻算法的銜接 DCG3A 算法前期執(zhí)行遺傳算法過(guò)程,后期執(zhí)行螞蟻算法過(guò)程,因此兩者的銜接是很重要的.主要包括這些 問(wèn)題: 動(dòng)態(tài)融合時(shí)機(jī)設(shè)置:同前述遺傳算法結(jié)束條件. 508 Journal of Software 軟件學(xué)報(bào) 2005,16(4) 螞蟻算法信息素初值設(shè)置:MMAS 算法把各路徑信息素初值設(shè)定為最大值 tmax,文獻(xiàn)12中所提算法把初值 固定為0=100.我們利用遺傳算法得到初始信息素分布,將各邊 eij 的信息素初值設(shè)定為 S C G ij (k ) = ij (k ) + ij (k ) C 其中, ij (k ) 是 eij 上 ck 信息素常數(shù),相當(dāng)于 MMAS 中的 tmin, (5) G ij (k)是從遺傳算法求解結(jié)果轉(zhuǎn)換而來(lái)的 eij 上的 ck 信息素值.本文設(shè)置ij (k)=ij(k)min=60,0i,jn,k=1,2. 遺 傳 算 法 求 解 結(jié) 果 向 信 息 素 值 轉(zhuǎn) 換 : 我 們 選 取 遺 傳 算 法 終 止 時(shí) 種 群 中 適 應(yīng) 值 最 好 的 前 10%( 即 C gene gene G 0.1N=0.150=5)個(gè)體作為遺傳優(yōu)化解集合,記為 S10% better .開(kāi)始時(shí),設(shè)置 ij (k ) 為 0,0i,jn,k=1,2.對(duì)于 S10% better 中 G 的每個(gè)解 s,如果邊 eij 被著色為 ck,則 ij (k ) 自加 20. 3.4 基于DCG3A的軟硬件劃分算法過(guò)程 首先將問(wèn)題描述為雙著色模型,然后執(zhí)行遺傳算法過(guò)程,直到到達(dá)最佳融合時(shí)機(jī)為止,然后,按式(5)將遺傳 算法求解結(jié)果轉(zhuǎn)換為螞蟻算法信息素初值,最后執(zhí)行螞蟻算法直到結(jié)束. 下面詳細(xì)描述 DCG3A 中遺傳算法,螞蟻算法以及兩者銜接部分的執(zhí)行過(guò)程. /遺傳算法部分: 1.初始化遺傳算法控制參數(shù)(種群規(guī)模 N=50,雜交概率 pc=0.6,變異概率 pm=0.2); 2.設(shè)置遺傳算法結(jié)束條件(Genemin=15,Genemax=50,Genemin-impro-ratio=3%,Genedie=3); 3.隨機(jī)生成初始種群 P(0),g=0; 4.計(jì)算 P(0)中個(gè)體的適應(yīng)值; 5.反復(fù)執(zhí)行下列操作,直到滿足遺傳算法結(jié)束條件: a) 根據(jù)個(gè)體適應(yīng)值及轉(zhuǎn)盤式選擇策略確定 P(g)內(nèi)每個(gè)個(gè)體的選擇概率 pi; b) for(k=0;kN;k=k+2) i. 根據(jù)概率 pi 在 P(g)內(nèi)選擇兩個(gè)父體; ii. r=random0,1; iii. if(rpm),對(duì)所選 2 個(gè)父體執(zhí)行變異操作,并將所得 2 個(gè)后代插入新群體 P(g+1)中; else if(rpm+pc),執(zhí)行雜交操作,并將所得 2 個(gè)后代插入新群體 P(g+1)中; else,執(zhí)行繁殖操作,將 2 個(gè)父體不變地插入新群體 P(g+1)中; /end for(k=0;kN;k=k+2) c) 計(jì)算 P(g+1)中個(gè)體的適應(yīng)值,g=g+1; /遺傳算法與螞蟻算法銜接部分: gene 6.從 P(g)中選擇適應(yīng)能力強(qiáng)的前 10%個(gè)體(5 個(gè)),放入集合 S10% better 中,作為優(yōu)化解集合; gene 螞蟻算法信息 7.對(duì)于 S10% better 中的每個(gè)優(yōu)化解 s,按前面描述的遺傳算法求解結(jié)果向信息素值轉(zhuǎn)換策略, /g 是遺傳代數(shù) 素初值設(shè)置策略以及式(5),計(jì)算任務(wù)圖中各邊 eij 關(guān)于 ck 的信息素初值ijS(k),k=1,2; /螞蟻算法部分: 8.初始化螞蟻算法控制參數(shù)(=1,wt=1,wa=2,信息素?fù)]發(fā)率=0.2,常數(shù) Q=1000); 9.設(shè)置螞蟻算法結(jié)束條件(Antmax=100,Antdie=3,Antmin-improv-ratio=0.5%); 10.在節(jié)點(diǎn) t0 處放置 m 只螞蟻;/t0 是唯一的起點(diǎn),m 取為任務(wù)圖的平均分支數(shù) 11.每只螞蟻按任務(wù)圖所對(duì)應(yīng) DAG 中邊的方向遍歷所有的邊和節(jié)點(diǎn),最終到達(dá)節(jié)點(diǎn) tn.每只螞蟻在遍歷過(guò)程 中,都要依據(jù)式(3)和式(4)計(jì)算的概率,猜測(cè)所達(dá)節(jié)點(diǎn)的顏色,并最終確定一個(gè)可行的著色方案 si,i=1,m; 是唯一的終點(diǎn) 12.計(jì)算所得 m 種著色方案的適應(yīng)值,并從中選擇最佳方案 sbest=arg min times; 時(shí)間最小的著色方案 13.依據(jù)式(1)和式(2)更新任務(wù)圖中所有邊的信息素值; /即滿足面積約束并且運(yùn)行 /tn 熊志輝 等:遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分 509 14.若滿足螞蟻算法結(jié)束條件,報(bào)告最佳著色方案 sbest 并退出;否則,繼續(xù)執(zhí)行步驟 10. 3.5 算法分析與討論 (1) 復(fù)雜性分析 DCG3A 算法的運(yùn)行時(shí)間 TDCG3A 主要由遺傳算法部分運(yùn)行時(shí)間 TGA, 螞蟻算法部分運(yùn)行時(shí)間 TAA 和銜接部 分運(yùn)行時(shí)間 TJOINT 組成,可表示為 TDCG3A=TGA+TAA+TJOINT.DCG3A 中的遺傳算法與螞蟻算法過(guò)程采用相同的適 應(yīng)值計(jì)算規(guī)則,因此我們可以使用一致的時(shí)間值 Tcal-fitness 表示這兩個(gè)算法中計(jì)算每個(gè)劃分方案適應(yīng)值所需的時(shí) 間.下面分別分析 TGA,TAA 與 TJOINT 的大小: TGA 包括遺傳算法初始設(shè)置時(shí)間 TGA-init(步驟 1步驟 3),終止條件判斷時(shí)間 TGA-termi 和種群進(jìn)化迭代時(shí) 間(步驟 4,步驟 5).假設(shè)遺傳算法進(jìn)化了 IGA 代,種群規(guī)模為 N,種群中每個(gè)個(gè)體完成一次遺傳操作(步驟 5 中的 過(guò)程 a,b)所需的時(shí)間為 TGA-operation,那么,種群迭代進(jìn)化時(shí)間就是 IGAN(TGA-operation+Tcal-fitness).這樣,TGA=TGA-init+ TGA-termi+IGAN(TGA-operation+Tcal-fitness),而 TGA-init+TGA-termi 遠(yuǎn)小于 IGAN(TGA-operation+Tcal-fitness),因此,TGAIGAN (TGA-operation+Tcal-fitness). TAA 包括螞蟻算法初始設(shè)置時(shí)間 TAA-init(步驟 8,步驟 9),終止條件判斷時(shí)間 TAA-termi 和螞蟻算法迭代時(shí) 間(步驟 10步驟 14).假設(shè)螞蟻算法迭代了 IAA 次,每次迭代中使用了 m 只螞蟻,每只螞蟻完成一次任務(wù)圖著色 ( 即 求 取 一 個(gè) 解 ) 的 時(shí) 間 為 TAA-operation, 那 么 , 螞 蟻 算 法 的 迭 代 時(shí) 間 就 是 IAAm(TAA-operation+Tcal-fitness). 這 樣,TAA=TAA-init+TAA-termi+IAAm(TAA-operation+Tcal-fitness),而 TAA-init+TAA-termi 遠(yuǎn)小于 IAAm(TAA-operation+Tcal-fitness), 因此,TAAIAAm(TAA-operation+Tcal-fitness). TJOINT 包括構(gòu)造優(yōu)化解集合(步驟 6)所需的時(shí)間 TJOINT-10%better 與計(jì)算信息素初值(步驟 7)所需的時(shí)間 TJOINT-initial-pheromone.假設(shè)采用逐個(gè)順序比較的方法構(gòu)造優(yōu)化解集合,那么 TJOINT-10%betterNN10%Tfloat-compare(其 中,Tfloat-compare 為完成一次浮點(diǎn)數(shù)比較所需的時(shí)間;10%表示選擇了適應(yīng)值高的 10%個(gè)體).進(jìn)一步假設(shè)任務(wù)圖節(jié) 點(diǎn)數(shù)為 K,邊數(shù)為 H,每次計(jì)算一條邊上的信息素值的時(shí)間為 TJOINT-edge-pheromone,那么,信息素初值計(jì)算時(shí)間 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.實(shí)際運(yùn)算中,我們發(fā)現(xiàn) Tcal-fitness 的復(fù)雜度為 O(KH),遠(yuǎn)大于 TGA-operation,TAA-operation 以及 NN10%Tfloat-compare+N10%HTJOINT-edge-pheromone.因此,可以將 TDCG3A 簡(jiǎn)化為 TDCG3AIGANTcal-fitness+ IAAmTcal-fitness=(IGAN+IAAm)Tcal-fitness. 在 運(yùn) 行 過(guò) 程 中 , 遺 傳 算 法 部 分 所 需 的 存 儲(chǔ) 空 間 約 為 2NO(K), 螞 蟻 算 法 部 分 所 需 的 存 儲(chǔ) 空 間 約 為 mO(K+H),算法銜接部分構(gòu)造優(yōu)化解集合所需的存儲(chǔ)空間為 10%NO(K).當(dāng)然,不同的程序?qū)崿F(xiàn),對(duì)算法運(yùn)算 時(shí)間與存儲(chǔ)空間也有一定的影響. (2) 算法運(yùn)行效率探討 上述復(fù)雜性分析表明,DCG3A 算法的運(yùn)行時(shí)間 TDCG3A 主要取決于 IGAN+IAAm 與 Tcal-fitness 的乘積.其 中,Tcal-fitness 是對(duì)某個(gè)劃分解進(jìn)行評(píng)價(jià)(求適應(yīng)值)所需的時(shí)間,與所用的優(yōu)化算法無(wú)關(guān).對(duì)于特定的組合優(yōu)化問(wèn) 題,Tcal-fitness 本質(zhì)上是評(píng)價(jià)問(wèn)題空間中一個(gè)解所需的時(shí)間.因此,DCG3A 算法效率改進(jìn)的關(guān)鍵在于最小化 IGAN +IAAm,其中 N,m 是控制參數(shù),分別表示遺傳算法的種群規(guī)模和螞蟻算法的螞蟻數(shù),在算法中一般是固定的值. 極端情況下,當(dāng)遺傳算法迭代次數(shù) IGA 為 0 時(shí),DCG3A 算法就退化為螞蟻算法;當(dāng)螞蟻算法迭代次數(shù) IAA 為 0 時(shí),DCG3A 算法則退化為遺傳算法. DCG3A 在遺傳算法運(yùn)行過(guò)程中加入了子代優(yōu)化解改進(jìn)效率檢測(cè)機(jī)制,使得當(dāng)遺傳算法對(duì)優(yōu)化解改進(jìn)效率 降低到一定程度時(shí),及時(shí)終止遺傳過(guò)程,從而避免 IGA 無(wú)謂的增長(zhǎng).此外,由于有了較為準(zhǔn)確的初始信息素,使螞蟻 算法大大降低了用于形成最優(yōu)解上信息素所需的迭代次數(shù).這時(shí),利用螞蟻算法正反饋,高效收斂的優(yōu)勢(shì),可以 在 IAA 很 小 的 情 況 下 ,迅 速 找 到 最 優(yōu) 解 . 因 此 ,DCG3A 算 法 通 過(guò) 抑 制 IGA 與 IAA 無(wú) 謂 的 增 長(zhǎng) , 從 而 最 小 化 IGAN+IAAm 來(lái)達(dá)到提高搜索效率的目的. 510 Journal of Software 軟件學(xué)報(bào) 2005,16(4) 4 實(shí) 驗(yàn) 采用與文獻(xiàn)12相似的實(shí)驗(yàn)?zāi)Ｐ秃头椒?與基于遺傳算法1,基于螞蟻算法12的軟硬件劃分進(jìn)行比較. 4.1 目標(biāo)系統(tǒng)結(jié)構(gòu) 本文考慮軟硬件系統(tǒng)任務(wù)雙路劃分問(wèn)題,目標(biāo)系統(tǒng)中有 PowerPC RISK CPU core Shared memory Configurable logic blocks (FPGA) 1 個(gè)處理器和 1 個(gè)硬件可編程部件(如 FPGA).使用 Xilinx Distributed local memory Virtex II Pro Platform FPGA 作為參考模型,它最多可包含 4 個(gè) 處理器核,13 404 個(gè)可編程邏輯塊.實(shí)驗(yàn)中,我們限制使用 1 個(gè) 處理器和最多 1 232 個(gè)可編程邏輯塊.目標(biāo)系統(tǒng)結(jié)構(gòu)抽象模型 如圖 3 所示. Fig.3 Abstract model of target architecture 圖3 目標(biāo)系統(tǒng)結(jié)構(gòu)抽象模型 4.2 實(shí)驗(yàn)假設(shè) 為簡(jiǎn)化實(shí)驗(yàn),作如下合理的假設(shè): a) 任務(wù)在處理器和在可編程部件上實(shí)現(xiàn)所需的運(yùn)行時(shí)間和占用的硬件面積是靜態(tài)的,可預(yù)先計(jì)算出來(lái); b) 任務(wù)間通信開(kāi)銷不變并已經(jīng)包含在任務(wù)的開(kāi)銷(時(shí)間,面積)中; c) 不考慮硬件實(shí)現(xiàn)的并行性. 4.3 實(shí)驗(yàn)環(huán)境與實(shí)例 目前,在嵌入式系統(tǒng)軟硬件劃分領(lǐng)域,國(guó)際上還沒(méi)有公認(rèn)的測(cè)試集 12.常見(jiàn)做法是隨機(jī)生成有向無(wú)環(huán)圖,并 對(duì)節(jié)點(diǎn)與邊賦以屬性.我們采用如下方法構(gòu)造測(cè)試集:a) 用 GVF 工具包隨機(jī)生成指定節(jié)點(diǎn)數(shù), 指定平均分支數(shù) 的若干個(gè)有向無(wú)環(huán)圖,作為任務(wù)圖;b) 將每個(gè)任務(wù)與一個(gè)函數(shù)(或算法過(guò)程)相關(guān)聯(lián),并以此函數(shù)的開(kāi)銷(運(yùn)行時(shí) 間,硬件面積,通信代價(jià)等)作為任務(wù)開(kāi)銷;c) 從 MediaBench 基準(zhǔn)程序包中選擇與任務(wù)相關(guān)聯(lián)的函數(shù). 利用上述方法生成 7 組 DAG(分別記為 DAG20,DAG30,DAG80),每組包含 30 個(gè) DAG 樣本.7 組 DAG 的節(jié) 點(diǎn)數(shù)分別為 20,30,80,平均分支數(shù)依次為 5,5,7,7,9,9,11.以各組 30 個(gè)樣本的性能平均值作為該組的最終性能 結(jié)果. 實(shí)驗(yàn)環(huán)境為:a) AMD Duron 700MHz 處理器,128MB 內(nèi)存,b) Linux 7.3 操作系統(tǒng),c) KDevelop 2.1 編程環(huán)境. 4.4 實(shí)驗(yàn)結(jié)果與分析 螞蟻算法12進(jìn)行軟硬件劃分得到的實(shí)驗(yàn)數(shù)據(jù).其中,遺傳算法 表 1 給出了本文 DCG3A 算法與遺傳算法1, 與螞蟻算法中控制參數(shù)的設(shè)置與 DCG3A 中相應(yīng)的設(shè)置相同.我們使這 3 種算法求解的最優(yōu)解與理論最優(yōu)解之 間的誤差基本一致,以保證公平性.圖 4 描述了表 1 中 3 種算法求解時(shí)間與節(jié)點(diǎn)規(guī)模的關(guān)系. Table 1 Comparison of genetic algorithm (GA), ant algorithm (AA) and DCG3A algorithm 表1 遺傳算法,螞蟻算法與 DCG3A 算法對(duì)比 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 當(dāng)任務(wù)圖節(jié)點(diǎn)數(shù)較少(2030)時(shí),DCG3A 算法略優(yōu)于遺傳算法和螞蟻算法,但效果不很明顯.而當(dāng)節(jié)點(diǎn)數(shù)超 過(guò) 40 時(shí),DCG3A 算法明顯優(yōu)于遺傳算法和螞蟻算法.隨著任務(wù)圖規(guī)模的增大,性能改進(jìn)的效果越顯著. 算法控制參數(shù)對(duì)實(shí)驗(yàn)結(jié)果也有一定的影響,本實(shí)驗(yàn)使用了文獻(xiàn)1,12中相同的控制參數(shù),以增強(qiáng)可比性.對(duì) 于特定的組合優(yōu)化問(wèn)題,可分別使用相應(yīng)問(wèn)題中已驗(yàn)證的優(yōu)化控制參數(shù),也可以使用典型控制參數(shù)設(shè)置值15,16. 控制參數(shù) Genemin-impro-ratio 決定了遺傳算法的終止時(shí)機(jī),此值若過(guò)大,則遺傳算法在更接近 tb(如圖 1 所示)的時(shí)刻 熊志輝 等:遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分 511 結(jié)束;若過(guò)小,遺傳算法就將在靠近 tc 的時(shí)刻結(jié)束.實(shí)驗(yàn)發(fā)現(xiàn),當(dāng) Genemin-impro-ratio=3%時(shí),遺傳算法在 tb 與 tc 之間中 間點(diǎn)位置(靠近最佳融合時(shí)機(jī) ta)結(jié)束,因此,本實(shí)驗(yàn)將 Genemin-impro-ratio 設(shè)置為 3%. 在所使用的目標(biāo)體系結(jié)構(gòu)下,本實(shí)驗(yàn)在一定的硬件面積約束下優(yōu)化系統(tǒng)運(yùn)行時(shí)間.實(shí)際上,在嵌入式系統(tǒng)與 SoC 軟硬件劃分中,其他性能指標(biāo)(如功耗)的約束與優(yōu)化也是非常重要的方面,本文算法同樣適用于求解這類 劃分問(wèn)題.另外,對(duì)于具有強(qiáng)實(shí)時(shí)性需求的嵌入式系統(tǒng)與 SoC 軟硬件劃分問(wèn)題,需要多個(gè)嵌入式處理器協(xié)同工作, 這時(shí),除了運(yùn)用本文算法進(jìn)行劃分求解外,還需要在劃分中考慮嵌入式處理器之間的任務(wù)分配與負(fù)載平衡,我們 將繼續(xù)對(duì)這個(gè)問(wèn)題進(jìn)行深入的研究. 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 運(yùn)算時(shí)間-節(jié)點(diǎn)規(guī)模曲線 5 結(jié) 語(yǔ) DCG3A 算法吸取了遺傳算法與螞蟻算法在尋優(yōu)問(wèn)題上各自的優(yōu)勢(shì),克服了它們的不足.在嵌入式系統(tǒng)和 SoC 軟硬件劃分中取得了很好的效果,并且隨著問(wèn)題規(guī)模的增大,性能改進(jìn)更顯著. 下一步我們將研究不同控制參數(shù)值對(duì) DCG3A 算法性能的影響,尋找適合 DCG3A 軟硬件劃分算法控制參 數(shù)的一組經(jīng)驗(yàn)值,并將 DCG3A 算法應(yīng)用于軟硬件多路劃分問(wèn)題. References: 1 Zhang LF. Research on techniques of hard