新聞中心

EEPW首頁 > EDA/PCB > 設(shè)計(jì)應(yīng)用 > 硬件化演化算法在函數(shù)優(yōu)化上的運(yùn)用

硬件化演化算法在函數(shù)優(yōu)化上的運(yùn)用

作者:張金柱,朱志敏,潘偉豐 時(shí)間:2008-10-31 來源:現(xiàn)代電子技術(shù) 收藏

1 引 言

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

  演化計(jì)算是一種借鑒生物演化和自然遺傳選擇的思想和原理來求解實(shí)際問題的一種極為有效的方法,它的根本思想是Darwin的進(jìn)化論和Mendel的遺傳學(xué)說,具有智能性、并行性和魯棒性等特征。演化計(jì)算是一種基于種群的搜索算法,它在搜索的過程中具有將適應(yīng)值好的個(gè)體保存到下一代的特點(diǎn),再通過選擇、交叉和變異等遺傳操作來產(chǎn)生更適應(yīng)環(huán)境的后代。演化計(jì)算提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架,它不需要事先描述問題的全部特點(diǎn),它不依賴于問題的具體領(lǐng)域,對(duì)問題的種類有很強(qiáng)的魯棒性,所以廣泛應(yīng)用于眾多學(xué)科,也被廣泛應(yīng)用與求解各種問題,但是它也具有一個(gè)突出的問題,演化速度比較慢,不大適合與實(shí)時(shí)運(yùn)用的場(chǎng)合。

  隨著微電子技術(shù)的迅速發(fā)展,大規(guī)模集成電路加工技術(shù)不斷發(fā)展,可編程邏輯器件(PLD)問世,它由于具有集成度高、速度快、功耗低、價(jià)格低等優(yōu)點(diǎn)在很多領(lǐng)域都日益發(fā)揮著重要的作用。而現(xiàn)場(chǎng)可編程門陣列(FPGA)是近幾年加入到用戶可編程電路行列的器件,它的設(shè)計(jì)為器件的選擇和內(nèi)連提供了更大的自由度,它的結(jié)構(gòu)包括由邏輯功能塊構(gòu)成的陳列和連接這些邏輯功能塊的可編程內(nèi)部連線2個(gè)部分。FPGA可以由用戶的設(shè)計(jì)而動(dòng)態(tài)地改變其內(nèi)部的功能結(jié)構(gòu),其設(shè)計(jì)周期短、修改、擴(kuò)充、維護(hù)方便,用FPGA實(shí)現(xiàn)的系統(tǒng)成本低,升級(jí)容易,而且隨著電子設(shè)計(jì)自動(dòng)化技術(shù)(EDA)和VHDL,AHDL等硬件描述語言的不斷完善,用戶只要進(jìn)行行為級(jí)、功能級(jí)的描述,則像AlteraⅡ等開發(fā)環(huán)境會(huì)自動(dòng)將其生成為對(duì)最終硬件進(jìn)行配置的網(wǎng)表文件,開發(fā)設(shè)計(jì)簡(jiǎn)單。這些特點(diǎn)為在硬件系統(tǒng)實(shí)現(xiàn)演化算法、提高演化算法的速度、擴(kuò)大演化算法的實(shí)時(shí)應(yīng)用提供了可能性。

  本文正是基于以上這些考慮,用Altera公司的CycloneⅡ型號(hào)的FPGA,并用VHDL實(shí)現(xiàn)了一種比較先進(jìn)的演化算法,并用該硬件化演化算法求解問題。最后的實(shí)驗(yàn)結(jié)果表明,用這種硬件化的演化算法大大地提高了演化算法的運(yùn)算速度,為演化算法在實(shí)時(shí)場(chǎng)合的運(yùn)用提供可能性。

2 演化算法硬件化構(gòu)造

  演化算法的硬件化和演化算法的軟件實(shí)現(xiàn)存在很大的不同,演化算法的軟件實(shí)現(xiàn)只需考慮軟件的功能實(shí)現(xiàn)就可以,很多演化算法中的特殊的算子,復(fù)雜的算子只要在理論上可行,實(shí)現(xiàn)的時(shí)候基本上不會(huì)存在什么大的問題,但當(dāng)硬件實(shí)現(xiàn)時(shí),問題會(huì)變得比較復(fù)雜。

2.1 演化算法的軟件實(shí)現(xiàn)思路

  演化算法的軟件實(shí)現(xiàn),是借助某一種高級(jí)語言,譬如:VC,Java等來實(shí)現(xiàn)演化算法的過程。在實(shí)現(xiàn)一個(gè)典型的演化算法過程中一般包括以下幾個(gè)問題:編碼、初始種群的生成、適應(yīng)度評(píng)價(jià)函數(shù)設(shè)計(jì)和選擇、交叉、變異算子的設(shè)計(jì)。

  軟件實(shí)現(xiàn)各個(gè)部分含義為:

  (1)編碼的軟件實(shí)現(xiàn):編碼是演化算法求解問題的前提,因?yàn)檠莼惴ㄒ话悴恢苯犹幚韱栴}空間中的變量,而只能通過編碼將問題空間轉(zhuǎn)化為解空間。目前比較流行的編碼技術(shù)包括:二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼、符號(hào)編碼、排列編碼、二倍體編碼、DNA編碼、混合編碼、二維染色體編碼和矩陣編碼等。

  由于目前的高級(jí)語言基本上都支持所有的數(shù)據(jù)類型,包括:整型、實(shí)數(shù)型、字符型等,所以上面的各種數(shù)據(jù)類型基本上都可以實(shí)現(xiàn)。

  (2)初始化種群的軟件實(shí)現(xiàn):初始種群的生成也就是隨機(jī)地產(chǎn)生N個(gè)個(gè)體組成1個(gè)初始種群,該種群代表一些可能解的集合。

  在軟件實(shí)現(xiàn)時(shí),若選擇的編碼方式是實(shí)數(shù)編碼,一般都是用一個(gè)偽隨機(jī)數(shù)發(fā)生器,在高級(jí)語言中通常就random()函數(shù)生成個(gè)體;若選擇的編碼方式是二進(jìn)制編碼,一般是按照概率生成一個(gè)個(gè)體中的每個(gè)1或是0;若是字符編碼的,通常就是轉(zhuǎn)化一下,通常也是將特定的字符替換成某一數(shù)字,生成該字母序列個(gè)體同樣也就轉(zhuǎn)化為生成該數(shù)字序列。

  (3)適應(yīng)度評(píng)價(jià)函數(shù)的軟件實(shí)現(xiàn):適應(yīng)度函數(shù)是用來進(jìn)行個(gè)體評(píng)價(jià),判斷個(gè)體適應(yīng)性能優(yōu)劣的方法,該數(shù)值通常是作為個(gè)體選擇的依據(jù),對(duì)整個(gè)算的運(yùn)行,算法的性能有重要的影響。

  在軟件實(shí)現(xiàn)時(shí),通常是將該函數(shù)設(shè)計(jì)成一個(gè)獨(dú)立的函數(shù)或是子過程,在每個(gè)需要重新計(jì)算個(gè)體適應(yīng)值的地方只要調(diào)用該函數(shù)就可以。

  (4)遺傳算子的軟件實(shí)現(xiàn):遺傳算子主要有選擇、交叉和變異3大算子。

  選擇算子就是按一定概率從群體中選擇M對(duì)個(gè)體,作為雙親用于繁殖后代,產(chǎn)生的新個(gè)體加入下一代種群。選擇過程體現(xiàn)了自然界適者生存的思想。軟件實(shí)現(xiàn)時(shí),一般是每次選擇時(shí)都產(chǎn)生1個(gè)隨機(jī)數(shù),以隨機(jī)數(shù)是否小于某一特定的數(shù)作為是否選擇的判斷條件。

  雜交算子就是對(duì)于選中的用于繁殖的每一對(duì)個(gè)體,將雙親的基因型在某個(gè)位置斷開,相互交換編碼。軟件實(shí)現(xiàn)時(shí),一般是先按照上面的選擇中的方法選擇2個(gè)個(gè)體,對(duì)于二進(jìn)制編碼的隨機(jī)的在個(gè)體中選擇1個(gè)或2個(gè)位置,進(jìn)行交換。對(duì)于實(shí)數(shù)編碼,一般是產(chǎn)生2個(gè)和惟一的隨機(jī)數(shù),然后將上面的2個(gè)個(gè)體按這2個(gè)隨機(jī)數(shù)為比例求乘積和。

  變異算子是按一定的概率從種群中選擇若干個(gè)個(gè)體。對(duì)于選中的個(gè)體,隨機(jī)選擇某一位進(jìn)行取反操作(二進(jìn)制編碼)或是對(duì)個(gè)體進(jìn)行微小的調(diào)整,加上或是減去某個(gè)數(shù)。軟件實(shí)現(xiàn)時(shí),對(duì)于二進(jìn)制編碼,一般先產(chǎn)生一個(gè)隨機(jī)數(shù),判斷該隨機(jī)數(shù)與某一個(gè)特定的數(shù)之間的大小,若小于該數(shù)就對(duì)個(gè)體中某一位或是幾位進(jìn)行取反操作;對(duì)于實(shí)數(shù)編碼一般是以概率對(duì)個(gè)體進(jìn)行微調(diào)。

2.2 硬件結(jié)構(gòu)設(shè)計(jì)

2.2.1 從軟件實(shí)現(xiàn)抽象硬件模塊

  要實(shí)現(xiàn)演化算法的硬件化,必須將演化算法的各個(gè)部分都獨(dú)立的在FPGA板上實(shí)現(xiàn)。在具體對(duì)演化算法實(shí)現(xiàn)模塊劃分的過程中必須遵循這樣一個(gè)原則:“功能相近的,操作類似的部分劃分在一個(gè)模塊中”。因此,根據(jù)上面對(duì)演化算法軟件實(shí)現(xiàn)的各個(gè)部分的分析可以做如下的劃分:

  (1)將軟件實(shí)現(xiàn)中初始化種群?jiǎn)为?dú)抽象為硬件實(shí)現(xiàn)時(shí)的pop_initial模塊;

  (2)將軟件實(shí)現(xiàn)中適應(yīng)度評(píng)價(jià)單獨(dú)抽象為硬件實(shí)現(xiàn)時(shí)的fitness模塊;

  (3)將軟件實(shí)現(xiàn)中選擇操作單獨(dú)抽象為硬件實(shí)現(xiàn)時(shí)的choose模塊;

  (4)將軟件實(shí)現(xiàn)中交叉、變異抽象為硬件實(shí)現(xiàn)時(shí)的crossover_mutation模塊;

  (5)為了進(jìn)行個(gè)體的讀寫還需要2個(gè)內(nèi)存模塊,分別保存?zhèn)€體和其適應(yīng)值;

  (6)為了使這么多模塊互相之間相互協(xié)作的完成任務(wù)還需要一個(gè)控制模塊control模塊,類似與軟件實(shí)現(xiàn)中的CPU協(xié)調(diào)控制程序的運(yùn)行。

2.2.2 硬件系統(tǒng)整體結(jié)構(gòu)圖及解釋

  (1)硬件系統(tǒng)整體結(jié)構(gòu)圖

  硬件系統(tǒng)整體結(jié)構(gòu)圖如圖1所示。

 

  (2)系統(tǒng)各模塊功能解釋如下:

  Control模塊 該模塊好比軟件實(shí)現(xiàn)的時(shí)候的CPU控制著整個(gè)系統(tǒng)的協(xié)調(diào)工作。它的主要功能是產(chǎn)生一些控制信號(hào),控制各個(gè)模塊的啟動(dòng)、停止,并為各個(gè)模塊的同步提供協(xié)調(diào)信號(hào)。具體講:它提供各個(gè)模塊的時(shí)鐘信號(hào),同步各個(gè)模塊;接收來自Random1模塊的2個(gè)隨機(jī)地址,從RAM模塊中選擇個(gè)體和其對(duì)應(yīng)的適應(yīng)值將其傳到Choose模塊;接收來自Choose模塊和Crossover_mutation模塊的狀態(tài)信號(hào),控制其發(fā)出的對(duì)其他模塊的控制信號(hào);控制多路數(shù)據(jù)選擇器、Initial模塊和RAM模塊的啟動(dòng)等。

  Initial模塊 該模塊即是初始化模塊,它內(nèi)部主要是由一個(gè)隨機(jī)數(shù)模塊構(gòu)成的,用來產(chǎn)生一定數(shù)量的隨機(jī)數(shù)序列作為初始種群。

  Fitness模塊 該模塊用來計(jì)算個(gè)體的適應(yīng)值。一般根據(jù)軟件實(shí)現(xiàn)中適應(yīng)值函數(shù)的不同,該模塊內(nèi)部主要是由一些加法器、鎖存器和乘法器構(gòu)成(在中)。

  Choose模塊 該模塊主要實(shí)現(xiàn)選擇2個(gè)個(gè)體的功能。當(dāng)該模塊啟動(dòng),并從存儲(chǔ)模塊接受2個(gè)個(gè)體和其適應(yīng)值后,采用聯(lián)賽競(jìng)爭(zhēng)機(jī)制選擇兩者中的1個(gè)進(jìn)入下一模塊,如此再選擇1次,選擇2個(gè)要進(jìn)入交叉變異模塊的個(gè)體。

  交叉變異模塊 該模塊在啟動(dòng)后,接收Choose模塊傳來的2個(gè)個(gè)體,并按照隨機(jī)數(shù)模塊產(chǎn)生的隨機(jī)數(shù)確定交叉點(diǎn),進(jìn)行交叉和變異。

  多路數(shù)據(jù)選擇模塊 對(duì)進(jìn)入fitness模塊的個(gè)體進(jìn)行分時(shí)控制。

  Ramdom1模塊 該模塊為選擇模塊選擇個(gè)體和適應(yīng)值提供2個(gè)隨機(jī)的地址。

  Ramdom2模塊 該模塊為交叉變異模塊提供交叉和變異的概率。

  Ram模塊 主要是用于保存?zhèn)€體和其適應(yīng)值。具體實(shí)現(xiàn)時(shí),我們常用了Altera公司提供的IP core生成2個(gè)雙端口的ram。

  (3)系統(tǒng)總執(zhí)行過程:系統(tǒng)通過Control模塊中的一個(gè)始終上升沿啟動(dòng),隨后啟動(dòng)Intial模塊產(chǎn)生初始種群,并對(duì)其產(chǎn)生的個(gè)體進(jìn)行計(jì)數(shù),在達(dá)到規(guī)定的種群數(shù)量后停止Intial模塊,控制模塊控制多路數(shù)據(jù)選擇器對(duì)Intial模塊選通,并讓產(chǎn)生的初始個(gè)體進(jìn)入Fitness模塊計(jì)算適應(yīng)值,并存入相應(yīng)的RAM地址中;接著控制模塊啟動(dòng)Choose模塊,Ramdom1模塊隨機(jī)的產(chǎn)生2個(gè)地址,并選擇該地址中的個(gè)體作為選擇的個(gè)體,運(yùn)用聯(lián)賽選擇選擇其一,如此選擇2次,產(chǎn)生2個(gè)用于Crossover_mutation模塊的個(gè)體,Crossover_mutation模塊在Ramdom2模塊產(chǎn)生的隨機(jī)數(shù)控制下對(duì)2個(gè)個(gè)體實(shí)施交叉變異,產(chǎn)生2個(gè)個(gè)體,控制模塊選通多路數(shù)據(jù)選擇模塊對(duì)Crossover_mutation模塊選通,使產(chǎn)生的新個(gè)體通過Fitness模塊將個(gè)體和適應(yīng)值存入RAM中相應(yīng)的位置。接著長(zhǎng)運(yùn)行上述過程一直到產(chǎn)生規(guī)定數(shù)量的個(gè)體,控制模塊結(jié)束整個(gè)系統(tǒng)的運(yùn)行。

  (4)硬件實(shí)現(xiàn):整個(gè)系統(tǒng)用VHDL語言編程實(shí)現(xiàn)上述各功能模塊,在AlteraⅡ5.0環(huán)境下進(jìn)行仿真。選用Altera公司CycloneⅡ型號(hào)的FPGA系列進(jìn)行設(shè)計(jì)。Ram塊用Altera IP core中的雙端口RAM。

3 實(shí) 驗(yàn)

  在本部分中,首先對(duì)上述提到的各個(gè)模塊進(jìn)行獨(dú)立的仿真,然后再將其運(yùn)用在一個(gè)函數(shù)的優(yōu)化問題上,并與其他同問題軟件實(shí)現(xiàn)的算法進(jìn)行比較。

  (1)以下對(duì)上述提到的模塊進(jìn)行獨(dú)立測(cè)試時(shí)候的仿真圖如圖2所示:

 

  圖2為初始化模塊仿真波形圖。從圖中可以看出,當(dāng)復(fù)位信號(hào)reset initial有效以后,立即對(duì)“r1_initial信號(hào)”和“r2_initial信號(hào)”賦初值,然后在下一個(gè)時(shí)鐘的上升沿(5 ns處),初始化開始,每次產(chǎn)生2個(gè)個(gè)體。

  圖3為Fitness模塊仿真圖,適應(yīng)度模塊足個(gè)邏輯模塊,只要輸入的個(gè)體發(fā)生改變,其輸出也就相應(yīng)改變。圖3即為仿真后的波形圖,此時(shí)輸出信號(hào)的右側(cè)有值。上述實(shí)現(xiàn)的是f(x)=-∣x∣的求值,這里可以看到:當(dāng)ina_fitness為“000000001”(實(shí)數(shù)1)和inb_fitness為“000000011”(實(shí)數(shù)3)時(shí)候,outa_fitness為“100000001”(實(shí)數(shù)-1)、outb_fitness為“100000011”(實(shí)數(shù)-3)。

 

  圖4為Random模塊仿真圖。圖4中左側(cè)的是信號(hào)名稱,中間是信號(hào)的值,右側(cè)是信號(hào)的波形圖。由圖4可以看出,在復(fù)位信號(hào)reset_radom2未變高之前,輸出的2個(gè)隨機(jī)數(shù)的值是初始值0;當(dāng)復(fù)位信號(hào)有效后,2個(gè)輸出立即由0轉(zhuǎn)為2個(gè)非0的輸出。

 

  圖5是選擇模塊開始進(jìn)入工作狀態(tài)前后的仿真波形圖。當(dāng)current|_state為current_state_idle時(shí),系統(tǒng)還處于初始化階段,start_choose信號(hào)為“0”,當(dāng)start_choose信號(hào)為“1”時(shí),狀態(tài)機(jī)轉(zhuǎn)入current_state_st1狀態(tài),選擇開始,outa信號(hào)與outb信號(hào)開始有值,在狀態(tài)current_state_st2時(shí),進(jìn)行第一次選擇。

(2)實(shí)驗(yàn)

  下面將上述各個(gè)模塊合在一起,構(gòu)成一個(gè)完整的系統(tǒng),對(duì)以下函數(shù)進(jìn)行優(yōu)化,并進(jìn)行一定的說明。

 

  圖6是用基于FPGA的演化算法對(duì)上述函數(shù)進(jìn)行優(yōu)化后得到的最優(yōu)結(jié)果。從上面可以看到,由上述方法得到的最優(yōu)個(gè)體是“11111010”,最差個(gè)體是“11111010”。

 

  用VC++設(shè)計(jì)實(shí)現(xiàn)了上面函數(shù)的優(yōu)化過程,同時(shí)軟件采用的交叉和變異操作與上面提到的方法類似,算法運(yùn)行參數(shù)也相同,并在同一系統(tǒng)環(huán)境下實(shí)現(xiàn):賽揚(yáng)1.7,內(nèi)存256 MB。軟硬件運(yùn)行結(jié)果比較如表1所示。

 

4 結(jié) 語

  本文從演化算法的軟件實(shí)現(xiàn)到演化算法的硬件化,詳細(xì)的闡釋如何用Altera公司的CycloneⅡ型號(hào)的FPGA,并用VHDL實(shí)現(xiàn)一種比較先進(jìn)的演化算法,并用該硬件化演化算法求解一函數(shù)優(yōu)化問題。演化算法的硬件化極大地提高演化算法的運(yùn)行速度,為演化算法在實(shí)時(shí)場(chǎng)合的運(yùn)用提供了一種可能性。

 



關(guān)鍵詞: 函數(shù)優(yōu)化

評(píng)論


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

關(guān)閉