新聞中心

EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計(jì)應(yīng)用 > 免疫算法求解函數(shù)優(yōu)化問題及其SoPC實(shí)現(xiàn)

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

作者: 時(shí)間:2017-06-05 來源:網(wǎng)絡(luò) 收藏

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

本文引用地址:http://m.butianyuan.cn/article/201706/349153.htm

1 SoPC技術(shù)[1]

嵌入式系統(tǒng)用于一些特定專用設(shè)備,通常這些設(shè)備的硬件資源(如處理器、存儲器)非常有限,并且對成本很敏感,有時(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)成一個(gè)能夠處理各種信息的集成電路。這個(gè)系統(tǒng)通常由一個(gè)主控單元和一些功能模塊構(gòu)成,主控單元是一個(gè)處理器,在這個(gè)主控單元的周圍,根據(jù)系統(tǒng)功能配置功能模塊,完成信號的接收、預(yù)處理、轉(zhuǎn)換及執(zhí)行任務(wù),并將硬件邏輯和智能算法集成在一起。

可編程片上系統(tǒng)SoPC(System on Programmable Chip)技術(shù)提供了另一種實(shí)現(xiàn)SoC的途徑,即用大規(guī)??删幊唐骷腇PGA實(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í)例化的單個(gè)系統(tǒng)模塊,并自動(dòng)生成必要的總線邏輯,以將這些組件鏈接起來。uart_usb用于接收實(shí)驗(yàn)板的數(shù)據(jù),4個(gè)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é)合,同時(shí)活化、增殖和分化產(chǎn)生漿細(xì)胞,通過中和、溶解和調(diào)理等作用,最終使抗原從體內(nèi)清除。一些B細(xì)胞成為長期存活的記憶細(xì)胞,它通過血液、淋巴和組織液循環(huán),為下一次快速、高效地清除相同或者類似抗原引起的感染奠定了基礎(chǔ)[5]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文算法的參數(shù)設(shè)置[6]如下:受體編輯系數(shù)Pc=0.2;高頻變異概率Pm=0.01;種群規(guī)模Popsize=50;算法迭50代結(jié)束。仿真選取f=x+10×sin(5x)+7×cos(4x),x∈[0,10]:一個(gè)單變量、多極值點(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)化問題時(shí)提高了收斂速度。

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

不管在SoPC還是PC上,免疫克隆算法處理函數(shù)優(yōu)化問題在進(jìn)入局部最小的時(shí)候,總能跳出這個(gè)局部最小,從而達(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í)時(shí)處理問題的能力。



評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉