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

摘 要：針對用軟件實(shí)現(xiàn)的演化算法普遍存在的執(zhí)行速度慢、不能滿足實(shí)時應(yīng)用需求等特點(diǎn)，這里使用基于Altera公司的Cyclone Ⅱ型號的FPGA，及用VHDL實(shí)現(xiàn)一種比較先進(jìn)的演化算法，并詳細(xì)給出硬件實(shí)現(xiàn)的一體化操作和仿真步驟，從演化算法的軟件實(shí)現(xiàn)到演化算法的硬件化；以及用此硬件化演化算法求解一些函數(shù)的優(yōu)化問題。實(shí)驗結(jié)果表明，用這種硬件化的演化算法可以大大提高演化算法的運(yùn)算速度、同時收斂速度快、效果好，為演化算法在實(shí)時場合的運(yùn)用提供了一種可能性。

關(guān)鍵詞：演化算法；函數(shù)優(yōu)化；FPGA；VHDL

Application of Hardware-based Genetic Algorithm in Function Optimization

HANG Jinzhu1，HU himin2，PAN Weifeng2

(1.School of Electronic Information，Wuhan University，Wuhan，430072，China;

2.School of Information Engineering，Jiangxi University of Science Technology，Ganzhou，341000，ChinaAbstract：Considering the shortcomings of slow speed and inability to meet the requirements of real-time occasions by using evolutionary algorithms which are realized by software to solve real-world problems，this paper proposes a Hardware-based Genetic Algorithm (HBGA which is realized by VHDL and Cyclone Ⅱ FPGA.Based on the proper initial and control to form a new optimization，we give out the operation and mutilation steps in detail.Which through evolutionary algorithm are realized by procedure to hardware.We apply HBGA to solve some function optimization problems to verify the effect of HBGA.And numerical experiments show that this kind of hardware-based genetic algorithm improves the speed of algorithm greatly，so good a effect provides a probability for the application of genetic algorithm on real-time occasions.

eywords：evolutionary algorithm;function optimization;FPGA;VHDL

1 引 言

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

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

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

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

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

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

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

軟件實(shí)現(xiàn)各個部分含義為：

(1 編碼的軟件實(shí)現(xiàn)：編碼是演化算法求解問題的前提，因為演化算法一般不直接處理問題空間中的變量，而只能通過編碼將問題空間轉(zhuǎn)化為解空間。目前比較流行的編碼技術(shù)包括：二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼、符號編碼、排列編碼、二倍體編碼、DNA編碼、混合編碼、二維染色體編碼和矩陣編碼等。

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

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

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

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

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

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

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

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

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

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

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

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

(1 將軟件實(shí)現(xiàn)中初始化種群單獨(dú)抽象為硬件實(shí)現(xiàn)時的pop_initial模塊；

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

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

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

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

(6 為了使這么多模塊互相之間相互協(xié)作的完成任務(wù)還需要一個控制模塊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)的時候的CPU控制著整個系統(tǒng)的協(xié)調(diào)工作。它的主要功能是產(chǎn)生一些控制信號，控制各個模塊的啟動、停止，并為各個模塊的同步提供協(xié)調(diào)信號。具體講：它提供各個模塊的時鐘信號，同步各個模塊；接收來自Random1模塊的2個隨機(jī)地址，從RAM模塊中選擇個體和其對應(yīng)的適應(yīng)值將其傳到Choose模塊；接收來自Choose模塊和Crossover_mutation模塊的狀態(tài)信號，控制其發(fā)出的對其他模塊的控制信號；控制多路數(shù)據(jù)選擇器、Initial模塊和RAM模塊的啟動等。

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

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

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

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

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

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

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

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

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

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

3 實(shí) 驗

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

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

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

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

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

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

(2 實(shí)驗

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