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

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

?

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

1 SoPC技術(shù)^[1]?

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

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

??? 可編程片上系統(tǒng)SoPC(System on Programmable Chip)技術(shù)提供了另一種實(shí)現(xiàn)SoC的途徑,，即用大規(guī)模可編程器件的FPGA實(shí)現(xiàn)SoC的功能,。?

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

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

2.1 硬件開發(fā)?

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

?

?

2.2 軟件開發(fā)?

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

?

?

3 免疫算法原理?

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

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

??? 本文的算法是基于標(biāo)準(zhǔn)克隆選擇算法改進(jìn)而來的,，標(biāo)準(zhǔn)克隆選擇算法流程如圖3。?

?

?

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

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

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

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

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

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

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

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

??? (2)克隆：對抗體群P中的抗體進(jìn)行擴(kuò)增操作得到群體C,，每個抗體的克隆數(shù)目與親和力(函數(shù)值)成正比,。?

??? (3)高頻變異：對抗體群C中的抗體進(jìn)行高頻變異得到種群C^*。?

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

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

??? (6)達(dá)到終止條件，程序結(jié)束,。?

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

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

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

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

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

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

?

?

參考文獻(xiàn)?

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

[2] 汪國強(qiáng).SoPC技術(shù)與應(yīng)用.北京：機(jī)械工業(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)原理與應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社,，2002.?

[6] 焦李成.免疫優(yōu)化計(jì)算、學(xué)習(xí)與應(yīng)用與識別[M].北京：科學(xué)出版社,，2006.