《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 業(yè)界動態(tài) > 免疫算法求解函數(shù)優(yōu)化問題及其SoPC實現(xiàn)

免疫算法求解函數(shù)優(yōu)化問題及其SoPC實現(xiàn)

2009-06-10
作者:龔 非,莫宏偉,馬向東

??? 摘? 要: SoPC是Altera公司近年來提出的一種靈活、高效的軟硬件協(xié)同設計可編程片上系統(tǒng)。本文首先搭建硬件平臺,在此平臺上進行軟件開發(fā),運用改進免疫克隆選擇算法解決函數(shù)優(yōu)化問題。仿真結果表明,在SoPC上處理函數(shù)問題是可行的,并且算法具有優(yōu)良的收斂速度及實時處理和抗退化能力。?

??? 關鍵詞: 可編程片上系統(tǒng);嵌入式系統(tǒng);函數(shù)優(yōu)化;免疫克隆選擇算法

?

??? 實際工程中,有很多問題都可轉化為函數(shù)優(yōu)化問題,而基于梯度的算法通常不能有效地解決高維且有多局部極值點的函數(shù)優(yōu)化問題。免疫系統(tǒng)是一種集進化機制和免疫機制于一體的全局并行系統(tǒng),能自適應地維持群體多樣性,其具有的自我調節(jié)能力,能使免疫算法具有整體、局部搜索能力強的特點。這類算法在函數(shù)優(yōu)化、數(shù)據(jù)挖掘等方面得到有效應用。?

1 SoPC技術[1]?

??? 嵌入式系統(tǒng)用于一些特定專用設備,通常這些設備的硬件資源(如處理器、存儲器)非常有限,并且對成本很敏感,有時對實時響應要求高。隨著消費家電的智能化,嵌入式系統(tǒng)更顯重要,手機、電子字典、交換機、路由器等都屬于典型的嵌入式系統(tǒng)。?

??? 片上系統(tǒng)SoC(System on a Chip)指在單片集成系統(tǒng)級多元化的大規(guī)模功能模塊,從而構成一個能夠處理各種信息的集成電路。這個系統(tǒng)通常由一個主控單元和一些功能模塊構成,主控單元是一個處理器,在這個主控單元的周圍,根據(jù)系統(tǒng)功能配置功能模塊,完成信號的接收、預處理、轉換及執(zhí)行任務,并將硬件邏輯和智能算法集成在一起。?

??? 可編程片上系統(tǒng)SoPC(System on Programmable Chip)技術提供了另一種實現(xiàn)SoC的途徑,即用大規(guī)??删幊唐骷腇PGA實現(xiàn)SoC的功能。?

2 SoPC軟硬件開發(fā)?

??? Quartus II軟件是Altera公司的綜合開發(fā)工具,通過使用此開發(fā)工具,設計者可以創(chuàng)建、組織和管理自己的設計[2]。?

2.1 硬件開發(fā)?

??? 硬件開發(fā)環(huán)境是在Quartus II工程中添加NiosII系統(tǒng)、鎖相環(huán)模塊、引腳等元件編譯完成的。NiosII系統(tǒng)由CPU、存儲器接口、標準外圍設備和用戶自定義的外圍設備等組件組成。如圖1所示。SoPC Builder將這些組件組合起來,生成對這些組件實例化的單個系統(tǒng)模塊,并自動生成必要的總線邏輯,以將這些組件鏈接起來。uart_usb用于接收實驗板的數(shù)據(jù),4個7段數(shù)碼管用于顯示運行的代數(shù)。?

?

?

2.2 軟件開發(fā)?

??? 軟件設計和應用程序開發(fā)是在上述已搭建硬件環(huán)境上進行的,其開發(fā)環(huán)境是Nios II IDE。SoPC軟件開發(fā)流程如圖2。?

?

?

3 免疫算法原理?

??? 免疫算法的靈感來自生物獲得性免疫克隆選擇原理[3]。根據(jù)該原理,在生物免疫系統(tǒng)中,一旦病原侵入機體,B淋巴細胞能夠為產(chǎn)生相應的抗體和抗原的結合,同時活化、增殖和分化產(chǎn)生漿細胞,通過中和、溶解和調理等作用,最終使抗原從體內清除。一些B細胞成為長期存活的記憶細胞,它通過血液、淋巴和組織液循環(huán),為下一次快速、高效地清除相同或者類似抗原引起的感染奠定了基礎[5]。?

??? 文本采用基于克隆選擇原理的免疫優(yōu)化算法[4]??寺∵x擇學說的中心思想是:抗體是天然產(chǎn)物,以受體的形式存在于細胞表面,抗原可與之選擇性地反應??乖c相應抗體受體的反應可導致細胞克隆性增殖,該群體具有相同的抗體特異性,其中某些細胞克隆分化為抗體生成細胞,另一些形成免疫記憶細胞,以參加之后的二次免疫反應。?

??? 本文的算法是基于標準克隆選擇算法改進而來的,標準克隆選擇算法流程如圖3。?

?

?

????(1)生成候選方案的一個集合(P)。它由記憶細胞(M)的子集加上剩余群體(Pr)(P=Pr+M)組成。?

??? (2)選擇n個具有較高親和力的個體。?

??? (3)克隆這n個最好的個體,組成一個臨時的克隆群體(C)。與抗原親和力越高,個體在克隆時規(guī)模也就越大。?

??? (4)把克隆軀體提交到高頻變異,根據(jù)親和力的大小決定變異,產(chǎn)生一個成熟的抗體種群C*。?

??? (5)對C*進行重新選擇,組成記憶細胞集合M。P中的一些成員可以被C*的其他一些改進的成員替換掉。?

??? (6)生成d個新的抗體取代P中d個低親和力的抗體,保持多樣性。?

??? 本文提出一種改進克隆選擇算法,用于求解函數(shù)優(yōu)化問題。本文采用二進制編碼,將該函數(shù)的值空間映射到位串空間中,然后在位串空間進行免疫克隆選擇操作,結果通過解碼過程還原成數(shù)值解,再進行親和力評估。由于對函數(shù)的精度要求是6位小數(shù),(1/222≈2×10-6),所以本文的編碼長度為6位。改進后的算法的實現(xiàn)步驟如下:?

??? (1)初始化:隨機產(chǎn)生N個長度為22的二進制編碼的抗體,組成初始抗體P。?

??? (2)克?。簩贵w群P中的抗體進行擴增操作得到群體C,每個抗體的克隆數(shù)目與親和力(函數(shù)值)成正比。?

??? (3)高頻變異:對抗體群C中的抗體進行高頻變異得到種群C*。?

??? (4)選擇:從抗體群中選擇d個親和力高的抗體替換P中的d個親和力低的抗體,d與抗體群P的平均親和力成反比。?

??? (5)判斷終止條件,否則轉(2)。?

??? (6)達到終止條件,程序結束。?

4 仿真實驗?

??? 本文算法的參數(shù)設置[6]如下:受體編輯系數(shù)Pc=0.2;高頻變異概率Pm=0.01;種群規(guī)模Popsize=50;算法迭50代結束。仿真選取f=x+10×sin(5x)+7×cos(4x),x∈[0,10]:一個單變量、多極值點的函數(shù),用來測試優(yōu)化算法是否能搜索到函數(shù)的最優(yōu)解。?

??? 在PC上分別運用標準和改進后的克隆選擇算法處理函數(shù)優(yōu)化問題,從圖4(a)、圖4(b)不難看出,改進后算法在第6代就能迅速達到全局最優(yōu),而標準算法需要13代。改進后算法在處理函數(shù)優(yōu)化問題時提高了收斂速度。?

??? 運用改進的克隆選擇算法處理函數(shù)優(yōu)化問題,從圖4(b)、圖4(c)不難看出,在SoPC上運行了4代就得到了全局最優(yōu)而每一代處理時間約0.35 s,達到最優(yōu)所需時間約為1.4 s。而在PC機上運行6代后得到的最優(yōu)結果,其每一代處理時間約為0.27 s,運行6代所需時間約為1.62 s。?

??? 不管在SoPC還是PC上,免疫克隆算法處理函數(shù)優(yōu)化問題在進入局部最小的時候,總能跳出這個局部最小,從而達到另一最小,進而達到全局最小。這體現(xiàn)了算法的抗退化能力。?

??? 本文將改進免疫克隆選擇算法應用在SoPC上,在實驗開發(fā)板上搭建了硬件平臺,在此基礎上進行軟件開發(fā)。實驗表明,在PC機和SoPC上都能有效求解函數(shù)優(yōu)化問題和避免陷入局部最小并達到全局最優(yōu)。當資源明顯不如PC機的情況下,在SoPC上處理到第4代就能迅速達到全局最優(yōu),而在PC機上則需要6代。獲得這樣的結果足以表明,SoPC有較強的優(yōu)化和實時處理問題的能力。?

?

?

參考文獻?

[1] 楊春玲,張輝.現(xiàn)代可編程邏輯器件及SoPC應用技術[M].哈爾濱:哈爾濱工業(yè)大學出版社,2005.?

[2] 汪國強.SoPC技術與應用.北京:機械工業(yè)出版社,2006.?

[3] DASGUPTA D.Artificial immune systems and their applications[M].Springer,1998.?

[4] BURNET F M.The clone selection theory of acquired immunity.Cambridge University Press,1959.?

[5] 莫宏偉.人工免疫系統(tǒng)原理與應用[M].哈爾濱:哈爾濱工業(yè)大學出版社,2002.?

[6] 焦李成.免疫優(yōu)化計算、學習與應用與識別[M].北京:科學出版社,2006.

本站內容除特別聲明的原創(chuàng)文章之外,轉載內容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點。轉載的所有的文章、圖片、音/視頻文件等資料的版權歸版權所有權人所有。本站采用的非本站原創(chuàng)文章及圖片等內容無法一一聯(lián)系確認版權者。如涉及作品內容、版權和其它問題,請及時通過電子郵件或電話通知我們,以便迅速采取適當措施,避免給雙方造成不必要的經(jīng)濟損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。