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

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

隨著微電子技術(shù)的迅速發(fā)展，大規(guī)模集成電路加工技術(shù)不斷發(fā)展，可編程邏輯器件(PLD問(wèn)世，它由于具有集成度高、速度快、功耗低、價(jià)格低等優(yōu)點(diǎn)在很多領(lǐng)域都日益發(fā)揮著重要的作用。而現(xiàn)場(chǎng)可編程門(mén)陣列(FPGA^［4］是近幾年加入到用戶可編程電路行列的器件，它的設(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等硬件描述語(yǔ)言的不斷完善，用戶只要進(jìn)行行為級(jí)、功能級(jí)的描述，則像Altera Ⅱ等開(kāi)發(fā)環(huán)境會(huì)自動(dòng)將其生成為對(duì)最終硬件進(jìn)行配置的網(wǎng)表文件，開(kāi)發(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ōu)化問(wè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ì)存在什么大的問(wèn)題，但當(dāng)硬件實(shí)現(xiàn)時(shí)，問(wèn)題會(huì)變得比較復(fù)雜。

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

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

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

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

由于目前的高級(jí)語(yǔ)言基本上都支持所有的數(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í)語(yǔ)言中通常就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ù)是用來(lái)進(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ù)或是子過(guò)程，在每個(gè)需要重新計(jì)算個(gè)體適應(yīng)值的地方只要調(diào)用該函數(shù)就可以。

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

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

雜交算子就是對(duì)于選中的用于繁殖的每一對(duì)個(gè)體，將雙親的基因型在某個(gè)位置斷開(kāi)，相互交換編碼。軟件實(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)模塊劃分的過(guò)程中必須遵循這樣一個(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è)體的讀寫(xiě)還需要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è)模塊；接收來(lái)自Random1模塊的2個(gè)隨機(jī)地址，從RAM模塊中選擇個(gè)體和其對(duì)應(yīng)的適應(yīng)值將其傳到Choose模塊；接收來(lái)自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)成的，用來(lái)產(chǎn)生一定數(shù)量的隨機(jī)數(shù)序列作為初始種群。

Fitness模塊 該模塊用來(lái)計(jì)算個(gè)體的適應(yīng)值。一般根據(jù)軟件實(shí)現(xiàn)中適應(yīng)值函數(shù)的不同，該模塊內(nèi)部主要是由一些加法器、鎖存器和乘法器構(gòu)成(在函數(shù)優(yō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模塊傳來(lái)的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í)行過(guò)程：系統(tǒng)通過(guò)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è)體通過(guò)Fitness模塊將個(gè)體和適應(yīng)值存入RAM中相應(yīng)的位置。接著長(zhǎng)運(yùn)行上述過(guò)程一直到產(chǎn)生規(guī)定數(shù)量的個(gè)體，控制模塊結(jié)束整個(gè)系統(tǒng)的運(yùn)行。

(4 硬件實(shí)現(xiàn)：整個(gè)系統(tǒng)用VHDL語(yǔ)言編程實(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)化問(wèn)題上，并與其他同問(wèn)題軟件實(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處，初始化開(kāi)始，每次產(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是選擇模塊開(kāi)始進(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)，選擇開(kāi)始，outa信號(hào)與outb信號(hào)開(kāi)始有值，在狀態(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)行一定的說(shuō)明。