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

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

1 SoPC技術(shù)[1]

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

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

可編程片上系統SoPC(System on Programmable Chip)技術(shù)提供了另一種實(shí)現SoC的途徑，即用大規?？删幊唐骷腇PGA實(shí)現SoC的功能。

2 SoPC軟硬件開(kāi)發(fā)

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

2.1 硬件開(kāi)發(fā)

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


2.2 軟件開(kāi)發(fā)

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


3 免疫算法原理

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

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

本文的算法是基于標準克隆選擇算法改進(jìn)而來(lái)的，標準克隆選擇算法流程如圖3。

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗

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

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

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

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

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