軟硬件協(xié)同的遺傳算法設(shè)計(jì)

聶 鑫，殷若蘭，劉海峰

(1.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430205；2.武漢工程大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北 武漢 430205；3.華為技術(shù)有限公司，廣東 深圳 518000)

0 引 言

遺傳算法是Holland在1975年提出的一種概率搜索算法[1]。遺傳算法通過有組織地然而是隨機(jī)的信息交換來重新結(jié)合那些適應(yīng)性好的串。類似于生物的進(jìn)化，遺傳算法作用于類似于基因的二進(jìn)制串上，通過尋找好的二進(jìn)制串來求解問題。在每一代中，算法使用上一代適應(yīng)值較好的個(gè)體通過雜交變異的方式生成一個(gè)新的種群。由于它不是直接作用于解空間，所以不受搜索空間的限制，同時(shí)也不需要豐富的先驗(yàn)知識，以及其內(nèi)含的天然并行性。因此遺傳算法作為一種有效的優(yōu)化算法在多個(gè)領(lǐng)域得到了應(yīng)用。

目前遺傳算法的應(yīng)用研究中存在若干問題：算法的執(zhí)行效率低下、算法收斂速度慢以及算法無法找到最優(yōu)解(即算法過早收斂)。對于后兩個(gè)問題，不少學(xué)者通過不斷的改進(jìn)算法的因子以及算法的整體結(jié)構(gòu)，或者是將算法與其他新算法進(jìn)行融合來提高算法的收斂速度。針對算法執(zhí)行效率低下的問題，現(xiàn)在也有不少學(xué)者試圖使用硬件化的方式來實(shí)現(xiàn)遺傳算法[2-4]，或者在大型的工作站中利用遺傳算法所具有的天然并行性來解決，這些方法都取得了一定的效果。這些方法在一定程度上也代表了今后遺傳算法的發(fā)展方向，同時(shí)也為遺傳算法在更多領(lǐng)域甚至在實(shí)際場合種應(yīng)用創(chuàng)造了條件。

軟硬件協(xié)同設(shè)計(jì)(hardware/software co-designing)的思想是在硬件和軟件設(shè)計(jì)過程中盡最大限度地利用其協(xié)同作用來滿足系統(tǒng)的要求。自從軟硬件協(xié)同思想提出以后，一直備受國內(nèi)外研究者的關(guān)注，關(guān)于軟硬件協(xié)同設(shè)計(jì)領(lǐng)域的研究也十分活躍。到目前為止，國內(nèi)外學(xué)者已經(jīng)在此方面做過很多研究[5-7]，比如在遙感影像的實(shí)時(shí)效應(yīng)，音頻編碼算法，Lattice譯碼算法，數(shù)字電路仿真，系統(tǒng)的模擬、仿真和調(diào)試等方面都使用過軟硬件協(xié)同設(shè)計(jì)方法，并且獲得比使用傳統(tǒng)的設(shè)計(jì)方法更好的效果。因此利用軟硬件協(xié)同設(shè)計(jì)方法不僅可以提高求解問題的效率，同時(shí)可以擴(kuò)寬其應(yīng)用領(lǐng)域，進(jìn)一步推動軟硬件協(xié)同設(shè)計(jì)的發(fā)展等。FPGA的快速發(fā)展，也為軟硬件協(xié)同工作搭建了平臺[8]，使得軟硬件協(xié)同處理成為了可能。

國內(nèi)外在軟硬件協(xié)同處理遺傳算法方面的研究還很少?？紤]到純硬件或者純軟件實(shí)現(xiàn)的遺傳算法在各自的優(yōu)點(diǎn)上面可以互補(bǔ)，通過軟硬件協(xié)同工作的遺傳算法同時(shí)具有硬件的高效性以及軟件的通用性。這種遺傳算法部署方便，開發(fā)成本低，效率高，功耗小，具有可移植性。為遺傳算法在更多領(lǐng)域應(yīng)用提供了一定的參考價(jià)值。

1 遺傳算法參數(shù)設(shè)計(jì)

1.1 遺傳算法操作

遺傳算法通過“適者生存”這種指導(dǎo)思想對種群進(jìn)行操作。具體就表現(xiàn)為遺傳算法不斷地通過雜交操作、變異操作以及選擇操作使得適應(yīng)值較壞的個(gè)體逐漸被淘汰。最后種群會逐漸地向最優(yōu)解的方向收斂。下面就對文中采用的遺傳算法中的一些基本操作進(jìn)行介紹[9-11]。

(1)編碼操作。

遺傳算法不是直接作用于解空間，而是作用于一種編碼方式。編碼是使用遺傳算法時(shí)要解決的首要問題，也是設(shè)計(jì)遺傳算法時(shí)的關(guān)鍵步驟，因?yàn)樵O(shè)計(jì)遺傳算子是建立在編碼基礎(chǔ)之上的。不同的編碼方式所對應(yīng)的遺傳算子是完全不同的。遺傳算法中一般使用位串編碼與實(shí)數(shù)編碼兩種方式。眾所周知在所有生物中，基因決定了一個(gè)生物的種類以及生物的形態(tài)。而這種基因就好比是一類數(shù)據(jù)的集合。使用位串編碼就可以很好地模擬基因。

考慮到二進(jìn)制編碼在硬件系統(tǒng)中實(shí)現(xiàn)方便的特性，在本設(shè)計(jì)中使用了該編碼方式。同時(shí)為了確保算法的精度，二進(jìn)制串的長度i設(shè)定為50。

(2)雜交操作。

雜交操作是遺傳算法中遺傳操作的一部分。同生物界中一樣，雜交操作可以在一定程度上保持父代個(gè)體所具有的適應(yīng)值。遺傳算法中的雜交操作一般有點(diǎn)式雜交與均勻雜交兩種方式。

在本設(shè)計(jì)中，考慮到所使用的種群大小為128以及方便FPGA的實(shí)現(xiàn)，設(shè)計(jì)使用單點(diǎn)式雜交操作。

(3)變異操作。

變異操作較雜交操作相對簡單。在一般的遺傳算法中，變異操作是按照一定的概率n發(fā)生的。變異操作在整個(gè)遺傳算法中起到輔助性搜索的作用。當(dāng)變異概率n過大時(shí)，可能就會破壞種群較好的模式。當(dāng)n過小時(shí)，就會使得算法產(chǎn)生新個(gè)體能力下降與過早成熟。當(dāng)變異操作發(fā)生時(shí)，隨機(jī)的在基因片段中選取一點(diǎn)或者多點(diǎn)進(jìn)行編譯操作。具體操作就是按位取反。

本設(shè)計(jì)中由于采用了單點(diǎn)式的雜交方式，并且種群并不是很大，所以這里采用的變異方式為在種群的128個(gè)個(gè)體中每次選取1個(gè)個(gè)體進(jìn)行變異操作。

(4)選擇策略。

在遺傳算法中，選擇策略也起著相當(dāng)重要的作用。不同的選擇策略導(dǎo)致了不同的選擇壓力。較大的選擇壓力使得較優(yōu)的個(gè)體能在種群中獲得更多的復(fù)制數(shù)目。使得種群更快收斂。而較小的選擇壓力則使得種群收斂速度較慢，但使得算法獲得全局最優(yōu)解的概率增大。

比較常見的選擇有繁殖池策略、輪盤策略、精英選擇策略等。繁殖池策略就是根據(jù)個(gè)體的適應(yīng)值計(jì)算出其在種群中的相對適應(yīng)值，根據(jù)相對適應(yīng)值進(jìn)行復(fù)制操作。適應(yīng)值越高的個(gè)體復(fù)制的個(gè)數(shù)越多。然后在復(fù)制個(gè)體中進(jìn)行遺傳操作。并且使用子代完全替換父代。

在本設(shè)計(jì)中，使用μ+γ的選擇策略：在父代中選擇μ個(gè)產(chǎn)生γ個(gè)子代，然后從μ+γ個(gè)個(gè)體中選擇μ個(gè)最優(yōu)個(gè)體替換父代。具體操作是當(dāng)子代生成進(jìn)行完評價(jià)之后，每次都用子代和父代中的最好個(gè)體去替換舊個(gè)體，從而增大選擇壓力，使得種群更快收斂。由于本設(shè)計(jì)中變異概率較大，從而也在一定程度上緩解了種群陷入局部最優(yōu)解的狀況。

(5)適應(yīng)值評價(jià)。

遺傳算法中，適應(yīng)值是評價(jià)種群個(gè)體好壞的標(biāo)準(zhǔn)，是遺傳算法中收斂的驅(qū)動力。在遺傳算法中，具有優(yōu)秀適應(yīng)值的個(gè)體將在種群中獲得更多的生存機(jī)會。不同的問題有著不同形式的適應(yīng)值評價(jià)函數(shù)。但是一般來說適應(yīng)值評價(jià)方式有兩種，一種是選取結(jié)果的最大值，另外一種則是選取結(jié)果的最小值。

在本設(shè)計(jì)中，使用選取最大值的方式。

(6)算法終止。

遺傳算法的終止是通過提前設(shè)定的參數(shù)來確定的。一般使用遺傳算法所解決的問題都是運(yùn)算復(fù)雜度高的類型?？赡苤恢澜獾目臻g范圍。一般來說，遺傳算法的終止條件有多種。一種是無論算法是否找到最優(yōu)解，當(dāng)算法執(zhí)行N代后則停止。使用此種方法的遺傳算法運(yùn)行時(shí)間比較穩(wěn)定，因?yàn)樗\(yùn)行的代數(shù)是個(gè)確定的數(shù)字。數(shù)字N的大小在該方法中比較重要。首先，如果N較小，算法可能得不到最優(yōu)解就停止。另一方面，如果N較大，雖然找到最優(yōu)解的概率變大，但是如果算法在早期就達(dá)到穩(wěn)定狀態(tài)，那么就浪費(fèi)了后續(xù)運(yùn)行的時(shí)間。另外一種方法是跟蹤每代運(yùn)行的最優(yōu)個(gè)體，如果該最優(yōu)個(gè)體在N代內(nèi)不發(fā)生變化，算法就會停止。數(shù)字N的大小在該方法中同樣比較重要，如果N較小，可能算法只是在局部的最優(yōu)解收斂，并不是全局的最優(yōu)解。如果N較大，也會造成運(yùn)行時(shí)間的浪費(fèi)。該方法的好處是至少可以確定獲得局部最優(yōu)解。缺點(diǎn)則是算法的運(yùn)行時(shí)間不確定。

在本設(shè)計(jì)中，為了保證尋找到局部最優(yōu)解，采用第二種方法。

1.2 軟硬件平臺簡介

在本設(shè)計(jì)中，使用Xilinx公司的FPGA作為開發(fā)平臺。Xilinx公司FGPA芯片主要由6部分組成，即可編程輸入輸出單元、時(shí)鐘管理、基本可編程邏輯單元、布線資源、塊RAM、底層功能單元和硬核。

Virtex系列是Xilinx的高端產(chǎn)品，這個(gè)系列的產(chǎn)品一般性能好，速度快，并且板載更多硬核。Virtex-II Pro系列是在Virtex-II的基礎(chǔ)上增強(qiáng)了嵌入式處理功能，內(nèi)嵌了Power PC 405內(nèi)核，還包括了先進(jìn)的主動互聯(lián)技術(shù)，以解決高性能系統(tǒng)所面臨的挑戰(zhàn)。Virtex-II Pro系列的主要特征如下：

(1)采用了1.5 V核電壓，4輸入LUT。

(2)420 MHz的始終技術(shù)，內(nèi)置多達(dá)12個(gè)DCM模塊。

(3)支持20多種I/O接口標(biāo)準(zhǔn)。

(4)增加多個(gè)3.125 Gb/s速率的Rocket串行收發(fā)器。

(5)內(nèi)置18x18位乘法器模塊。

(6)內(nèi)嵌PowerPC 405硬核處理器。

本設(shè)計(jì)中使用的Virtex-II Pro系列型號為XC2VP30，因?yàn)樵撔吞柕腇PGA提供了板載CPU，配合Xilinx公司的EDK工具可以很方便地進(jìn)行軟件開發(fā)，方便軟硬件協(xié)同設(shè)計(jì)的實(shí)現(xiàn)。該型號的FGPA的主要性能特征如表1所示。

表1 Virtex-II Pro XC2VP30

2 軟硬件協(xié)同的系統(tǒng)設(shè)計(jì)

2.1 硬件劃分

使用軟硬件協(xié)同的方式可以結(jié)合軟硬件各自的優(yōu)點(diǎn)，對設(shè)計(jì)進(jìn)行進(jìn)一步的優(yōu)化。綜合軟硬件各自的優(yōu)點(diǎn)，采用軟硬件協(xié)同的工作方式實(shí)現(xiàn)的系統(tǒng)，將系統(tǒng)中一些底層簡單而重復(fù)，特別是能夠并行化的工作交由硬件完成，將具有通用性，串行的工作交由軟件完成，不僅可以提升系統(tǒng)的效率，縮短系統(tǒng)的開發(fā)周期，并且使得系統(tǒng)具有可重用性。在軟硬件協(xié)同中，如何劃分軟硬件具體工作是一件重要的事[12]。因?yàn)檫@涉及到設(shè)計(jì)的運(yùn)行效率以及具體實(shí)現(xiàn)的功能。對遺傳算法軟硬件劃分確定，硬件部分為總控模塊、初始化模塊、交叉選擇模塊、變異模塊、評價(jià)模塊。軟件部分為隨機(jī)數(shù)模塊和適應(yīng)值評價(jià)模塊。整個(gè)系統(tǒng)的設(shè)計(jì)圖如圖1所示。

圖1 系統(tǒng)設(shè)計(jì)圖

2.2 交互協(xié)議

在設(shè)計(jì)平臺中，CPU(PowerPC)時(shí)鐘頻率(300 MHz)與FPGA提供的時(shí)鐘頻率(100 MHz)不一致，并且在CPU上運(yùn)行的軟件程序完成所需要的時(shí)鐘周期數(shù)是不確定性的。由于在本設(shè)計(jì)中存在許多軟件層面與硬件層面的信息交互，為了保證信息交互的同步性、可靠性，必須設(shè)計(jì)一個(gè)通信協(xié)議來確保數(shù)據(jù)的正確性。本設(shè)計(jì)中軟硬件信息交互中可能存在的問題大致如下：

(1)由于PowerPC時(shí)鐘頻率較快，如果軟件端的請求只發(fā)送一次，而在時(shí)序控制的系統(tǒng)中硬件響應(yīng)事件僅在時(shí)鐘上升沿或者下降沿的時(shí)刻響應(yīng)信號的變化，這就有可能導(dǎo)致硬件無法獲取啟動信號。

(2)同樣由于PowerPC時(shí)鐘頻率較快，如果一直發(fā)送請求，直到硬件返回?cái)?shù)據(jù)停止，那么就有可能使硬件響應(yīng)軟件多次，出現(xiàn)硬件無法正常工作等錯(cuò)誤。

(3)由于FPGA處理數(shù)據(jù)較快，當(dāng)硬件完成工作之后，如果在軟件未就緒的情況下通知軟件，就會出現(xiàn)信號丟失，導(dǎo)致整個(gè)系統(tǒng)出錯(cuò)。

(4)由于系統(tǒng)PowerPC時(shí)鐘頻率與FPGA時(shí)鐘頻率不一致，可能會使信號無法采集，從而使某一方面無限等待，導(dǎo)致系統(tǒng)的死機(jī)。

基于以上種種可能發(fā)生的異常，必須設(shè)計(jì)一種可靠的協(xié)議[13-14]。鑒于以上描述問題與網(wǎng)絡(luò)通信中出現(xiàn)的問題有一定程度的相似性，并且網(wǎng)絡(luò)通信中的復(fù)雜程度要遠(yuǎn)大于這里，故考慮借鑒網(wǎng)絡(luò)通信中的可靠性傳輸協(xié)議，即TCP協(xié)議。TCP協(xié)議通過3次握手協(xié)議確保通信雙方數(shù)據(jù)傳輸?shù)目煽啃?。本設(shè)計(jì)借鑒3次握手的方式，設(shè)計(jì)通信協(xié)議，如圖2所示。

在本設(shè)計(jì)中，在雜交模塊、變異模塊、初始化模塊以及總控模塊中都使用了該協(xié)議來確保軟硬件雙方信息交互的正確性。

圖2 通信協(xié)議

2.3 通信端口設(shè)計(jì)

為了讓軟件與硬件能夠正常通信，除了協(xié)議之外還需要有一個(gè)共同的通道。因此需要在FPGA上建立部分寄存器來模擬通信的通道。依據(jù)通信協(xié)議中所需要的狀態(tài)信號以及通信數(shù)據(jù)的需要，共建立10個(gè)32位的寄存器。寄存器作用分別描述如下：

(1)寄存器0：該寄存器保存著軟件端給硬件端的所有信號。信號依次如下：

Start：啟動信號，通知硬件啟動，該信號使用寄存器0中的第0位即 reg0[0];

Stop：停止信號，當(dāng)系統(tǒng)有特殊需要時(shí)可能所發(fā)出的停機(jī)信號，通過該信號通知硬件停機(jī)。該信號使用寄存器0中的第1位即 reg0[1];

Cal_done：適應(yīng)值評價(jià)完成信號。通過該信號來告知硬件適應(yīng)值評價(jià)結(jié)束，并且已經(jīng)存放在相應(yīng)位置。該信號使用寄存器0中的第2位即 reg0[2];

ini_sg_done：初始化完成信號。通過該信號來告知硬件初始化工作完成。該信號使用寄存器0中的第3位即 reg0[3];

rand_done：隨機(jī)數(shù)產(chǎn)生完成信號。通過該信號告知硬件隨機(jī)數(shù)產(chǎn)生完成。該信號使用寄存器0中的第4位即 reg0[4]。

(2)寄存器1：該寄存器保存著硬件端給軟件端的所有信號。信號依次如下：

rand_reg：隨機(jī)數(shù)請求信號，該信號使用寄存器1中的第5位即 reg1[5];

cal_req：適應(yīng)值評估請求信號，該信號使用寄存器1中的第3位即 reg1[3];

ini_reg：初始化請求信號，該信號使用寄存器1中的第1位即 reg1[1];

done：算法運(yùn)行結(jié)束信號，該信號使用寄存器1中的第4位即 reg1[4]。

(3)寄存器2～3保存需要進(jìn)行適應(yīng)值計(jì)算的個(gè)體。

(4)寄存器4～5保存初始化生成的個(gè)體。

(5)寄存器6～7保存最優(yōu)個(gè)體。

(6)寄存器8保存軟件評價(jià)出的適應(yīng)值結(jié)果。

(7)寄存器9保存由軟件生成的隨機(jī)數(shù)。

3 軟硬件協(xié)同的平臺實(shí)現(xiàn)

3.1 硬件模塊

如圖1所示，需要實(shí)現(xiàn)的硬件模塊為總控模塊、雜交模塊、變異模塊、評價(jià)選擇模塊、片上內(nèi)存模塊、片上內(nèi)存選擇讀取模塊、初始化模塊。對平臺設(shè)計(jì)中的硬件化模塊進(jìn)行功能仿真。仿真工具選擇使用Xilinx ISE自帶仿真器。

使用Xilinx ISE自帶仿真器進(jìn)行仿真之前，必須要建立測試硬件功能的激勵(lì)文件。ISE提供了兩種不同的方式。第一種是基于HDL測試代碼，建立一個(gè)Verilog Test Fixture類型的文件，將這個(gè)文件與待測試文件相關(guān)聯(lián)，然后根據(jù)不同的測試目的編寫激勵(lì)代碼。這種方法工作量較大，并且修改較復(fù)雜。另外一種方式就是基于波形的測試代碼，建立一個(gè)testbench波形文件，一樣也將這個(gè)文件與待測模塊進(jìn)行關(guān)聯(lián)。系統(tǒng)會根據(jù)模塊的輸入輸出顯示一個(gè)波形文件，用戶可以通過修改這個(gè)波形文件的輸入信號直觀地改寫測試的激勵(lì)文件。最后在系統(tǒng)的Behavioral Simulation 狀態(tài)中運(yùn)行Xilinx ISE自帶仿真器，就可以顯示波形文件。本設(shè)計(jì)中采用第二種測試方法。

本設(shè)計(jì)硬件部分的工作流程是由總控模塊來控制的。軟件層面的隨機(jī)數(shù)模塊和適應(yīng)值計(jì)算模塊，硬件層面的初始化模塊、交叉選擇模塊、變異選擇模塊、評價(jià)模塊都與總控模塊進(jìn)行著信息的交互。因此總控模塊是整個(gè)設(shè)計(jì)的核心部分，就好比計(jì)算機(jī)內(nèi)部的CPU，控制著整個(gè)設(shè)計(jì)的流程以及數(shù)據(jù)的流向，各模塊也都是在總控模塊的控制信號下有序地工作。對本設(shè)計(jì)硬件部分的設(shè)計(jì)而言，整個(gè)系統(tǒng)的工作狀態(tài)都體現(xiàn)在總控模塊上。各個(gè)子模塊通過總控模塊的控制信號進(jìn)行信息的交互。

該模塊提供各個(gè)模塊之間調(diào)用的控制信號，從而控制整個(gè)遺傳算法的流程以及數(shù)據(jù)的流向，協(xié)調(diào)各個(gè)模塊有序地工作?？偪啬K由一個(gè)大狀態(tài)機(jī)構(gòu)成，狀態(tài)分別為IDLE、INIT、CROSS、MUT、VALUE和STOP?？偪啬K通過狀態(tài)機(jī)的方式來控制其他模塊。狀態(tài)機(jī)如圖3所示。

圖3 系統(tǒng)運(yùn)行狀態(tài)機(jī)

如圖3所示，本模塊中共有6個(gè)狀態(tài)。

整個(gè)系統(tǒng)的工作流程為：系統(tǒng)復(fù)位或者上電后進(jìn)入IDLE狀態(tài)，系統(tǒng)在START信號為0的時(shí)候則在IDLE狀態(tài)保持等待。當(dāng)系統(tǒng)得到START=1后，轉(zhuǎn)入INIT初始化狀態(tài)；INIT狀態(tài)工作未完成時(shí)，INIT_DONE一直等于0，并且保持在INIT狀態(tài)繼續(xù)工作。當(dāng)初始化工作完成后發(fā)出INIT_DONE=1信號，系統(tǒng)轉(zhuǎn)入CROSS狀態(tài)；在雜交操作未完成之前，CROSS_DONE一直保持為0，并且保持在CROSS狀態(tài)繼續(xù)工作。當(dāng)交叉操作完成后發(fā)出CROSS_DONE=1信號，系統(tǒng)轉(zhuǎn)入MUT狀態(tài)；在變異操作未完成之前，MUT_DONE一直保持為0，并且保持在MUT狀態(tài)繼續(xù)工作。當(dāng)變異操作完成后發(fā)出MUT_DONE=1信號，系統(tǒng)轉(zhuǎn)入EVALUE狀態(tài)；評價(jià)操作完成后進(jìn)行停止?fàn)顟B(tài)判斷，如果滿足停止條件，則發(fā)出STOP=1信號，系統(tǒng)轉(zhuǎn)入STOP狀態(tài)，否則發(fā)出STOP=0信號并轉(zhuǎn)入CROSS狀態(tài)，繼續(xù)進(jìn)行循環(huán)操作；系統(tǒng)完成STOP狀態(tài)要做的工作后無條件轉(zhuǎn)入IDLE狀態(tài)。

3.2 軟件模塊

(1)隨機(jī)數(shù)模塊。

該模塊提供了遺傳算法流程中初始化模塊中個(gè)體生成、雜交選擇模塊的個(gè)體選擇和雜交點(diǎn)選擇、變異選擇模塊的個(gè)體選擇和變異點(diǎn)選擇。該模塊采用Xilinx公司擴(kuò)展的C語言實(shí)現(xiàn)。具體實(shí)現(xiàn)表現(xiàn)為一個(gè)函數(shù)。函數(shù)有一個(gè)控制參數(shù)。函數(shù)返回為所需求的隨機(jī)數(shù)值。軟硬件交互協(xié)議的部分由調(diào)用該函數(shù)的部分控制實(shí)現(xiàn)。函數(shù)的內(nèi)部具體實(shí)現(xiàn)為根據(jù)控制參數(shù)來判斷硬件所需的隨機(jī)數(shù)的范圍。

(2)適應(yīng)值評價(jià)模塊。

該模塊的功能為完成遺傳算法整個(gè)流程中的適應(yīng)值評估工作，也就是所需要解決問題的具體描述。該模塊采用Xilinx公司擴(kuò)展的C語言實(shí)現(xiàn)。具體實(shí)現(xiàn)表現(xiàn)為一個(gè)函數(shù)。函數(shù)的參數(shù)為控制參數(shù)以及需要進(jìn)行適應(yīng)值評價(jià)的個(gè)體(具體表現(xiàn)為一個(gè)50維數(shù)組)。函數(shù)返回為該個(gè)體的適應(yīng)值。軟硬件交互協(xié)議的部分由調(diào)用該函數(shù)的部分控制實(shí)現(xiàn)。函數(shù)的內(nèi)部具體實(shí)現(xiàn)為針對所求問題對二進(jìn)制編碼形式的個(gè)體進(jìn)行相應(yīng)的計(jì)算。

3.3 硬件算法IP核建立

由于設(shè)計(jì)中所有硬件化模塊之間存在種種的外在以及內(nèi)在聯(lián)系，本設(shè)計(jì)中將所有的硬件化模塊打包生成一個(gè)硬件IP核。IP核的生成使用Xilinx公司的EDK工具提供的IPIF接口。

使用EDK工具的硬件IP核生成向?qū)陆ㄒ粋€(gè)IP核，在生成過程中同時(shí)選擇生成使用該IP核時(shí)所需要的寄存器，共10個(gè)32位寄存器。使用總控模塊作為整個(gè)IP核的次頂層模塊。在向?qū)峁┑捻攲幽K中將總控模塊進(jìn)行添加，并且將寄存器與總控模塊的輸入輸出端口進(jìn)行連接。IP核資源使用情況如圖4所示。

圖4 遺傳算法IP核資源使用情況

從圖4中可以看到，硬件IP核占用資源較少，占用整個(gè)系統(tǒng)資源不到18%。說明硬件部分實(shí)現(xiàn)體積較小并且功耗較小。IP核的使用可以極大程度地簡化開發(fā)者的工作量，并且由于IP核可配置，所以為后續(xù)設(shè)計(jì)提供了可擴(kuò)展空間。

3.4 FPGA工程平臺搭建

使用EDK軟件新建工程，在新建工程向?qū)r(shí)選擇開發(fā)板型號以及速度等信息。然后再根據(jù)本設(shè)計(jì)中的具體需求，添加PowerPC、內(nèi)存、開關(guān)等基本設(shè)備。然后再往設(shè)計(jì)中添加新建的遺傳算法IP核。并且將IP核的數(shù)據(jù)通訊綁定在OPB高速總線上。因?yàn)楸驹O(shè)計(jì)中采用了更加直觀的視頻輸出結(jié)果，所以還需要在平臺中添加視頻輸出IP核，并加入相應(yīng)的驅(qū)動程序。最后根據(jù)開發(fā)板用戶使用手冊將管腳進(jìn)行綁定。至此硬件開發(fā)環(huán)境搭建完成。

在平臺完成綜合布局布線生成可下載文件之后，啟動SDK工具進(jìn)行軟件端程序模塊的搭建。在SDK工作環(huán)境下新建一個(gè)C語言環(huán)境的工程，將隨機(jī)數(shù)模塊、適應(yīng)值評價(jià)模塊以及軟硬件交互協(xié)議軟件部分在該工程下整合。系統(tǒng)所需要的內(nèi)存地址數(shù)據(jù)由xparameters.h文件提供。在系統(tǒng)停機(jī)之后將算法停機(jī)之后的結(jié)果通過視頻輸出。最后編譯整個(gè)工程，并且將程序代碼片段及數(shù)據(jù)片段存放位置指定與片上內(nèi)存，將程序使用堆棧等其他數(shù)據(jù)設(shè)置內(nèi)存中存儲。將SDK工程產(chǎn)生的ELF文件與硬件平臺產(chǎn)生的下載文件使用系統(tǒng)自帶工具進(jìn)行聯(lián)合，生成新下載文件。使用IMPACT工具將生成的文件下載到開發(fā)板中或者使用IMPACT工具新建CF卡啟動引導(dǎo)文件完成整個(gè)設(shè)計(jì)。

4 數(shù)值計(jì)算應(yīng)用實(shí)例

在科學(xué)研究中，數(shù)值計(jì)算[15]是一類經(jīng)常遇到的問題，通常這類問題的復(fù)雜度較高，使用普通的算法計(jì)算時(shí)間較長。使用遺傳算法解決數(shù)值問題可以起到較好的效果。但是軟件實(shí)現(xiàn)的遺傳算法執(zhí)行效率低下，所以可以使用軟硬件協(xié)同工作的方式在不改變算法通用性的基礎(chǔ)上加快算法的收斂速度。

4.1 二進(jìn)制問題中的應(yīng)用

二進(jìn)制問題是一類可以有效驗(yàn)證遺傳算法功能正確性的基本問題。設(shè)計(jì)中使用的問題為計(jì)算二進(jìn)制串中“1”的個(gè)數(shù)。1的個(gè)數(shù)越多，效果越優(yōu)。由于初始化個(gè)體為隨機(jī)初始化，所以在初始化個(gè)體中0與1的比例接近1∶1，必須通過不斷的雜交和變異才可以獲得最優(yōu)解。因?yàn)閭€(gè)體串長為50，所以最優(yōu)解為50個(gè)1。使用軟硬件協(xié)同的遺傳算法解決該問題只需要改寫軟件端的適應(yīng)值函數(shù)，無需對硬件進(jìn)行修改。

二進(jìn)制問題運(yùn)行效果如圖5所示。

從圖5可以看出，算法可以正確找到最優(yōu)解，運(yùn)行的代數(shù)為1 272，去除用于判斷終止條件的500代，算法共運(yùn)行700多代。整個(gè)算法運(yùn)行時(shí)間為4.2秒。

圖5 二進(jìn)制問題運(yùn)行效果

4.2 背包問題中的應(yīng)用

0-1背包問題是生活中比較常見的一類問題。該類問題描述為有一體積無限大的背包，但是該背包只能容納一定重量的貨物。如果你有一組貨物，每種貨物有著不同的重量以及價(jià)格，所求問題是如何在這些貨物中選取適當(dāng)?shù)呢浳?貨物個(gè)數(shù)沒有限制)，使這個(gè)背包在指定的重量范圍內(nèi)，商品的價(jià)值最高。在本設(shè)計(jì)中，個(gè)體二進(jìn)制串長為50。所以使用的貨物總數(shù)為50個(gè)。在適應(yīng)值評價(jià)時(shí)，50個(gè)貨物與二進(jìn)制串的二進(jìn)制位相對應(yīng)，如果該二進(jìn)制位為“1”則該貨物被選取，為“0”則不選取。最后累加選取貨物的重量與價(jià)值。首選判斷貨物總重量，如果總重量大于設(shè)定的最大重量，就將適應(yīng)值設(shè)置為-1。否則就將適應(yīng)值設(shè)置為貨物的總價(jià)值。

設(shè)物品的價(jià)值為P，重量為S，背包容量為C，分別有：

P={220，208，198，192，180，180，165，162，160，158，155，130，125，122，120，118，115，110，105，101，100，100，98，96，95，90，88，82，80，77，75，73，70，69，66，65，63，60，58，56，50，30，20，15，8，5，3，1，1}

S={80，82，85，70，72，70，66，50，55，25，50，55，40，48，50，32，22，60，30，32，40，48，50，32，22，60，30，32，40，38，35，32，25，28，30，22，50，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，4，4，2，1}

C=1 000

使用軟硬件協(xié)同的遺傳算法解決該問題同樣只需要改寫軟件端的適應(yīng)值函數(shù)，無需對硬件進(jìn)行修改。本問題經(jīng)過優(yōu)化的遺傳算法所能獲得的最優(yōu)值為3 103。而使用普通遺傳算法(即本設(shè)計(jì)所采用的遺傳算子)所能獲得的最優(yōu)解為3 031。

背包問題運(yùn)行效果如圖6所示。

圖6 0-1背包問題運(yùn)行效果

從圖6中可以看出，算法獲得的最優(yōu)解為2 906，基本接近解3 031，運(yùn)行的代數(shù)為1 722，去除用于判斷終止條件的500代，算法共運(yùn)行1 000多代。整個(gè)算法運(yùn)行時(shí)間為11秒。

4.3 實(shí)驗(yàn)分析

因?yàn)檫z傳算法是一個(gè)隨機(jī)搜索算法，算法的性能受初始化種群的好壞以及雜交變異的隨機(jī)性影響較大。而以上實(shí)驗(yàn)截圖均是實(shí)驗(yàn)中隨機(jī)獲取的數(shù)據(jù)，并不能代表設(shè)計(jì)的性能以及效果。

為了對軟硬件協(xié)同遺傳算法平臺的性能進(jìn)行分析，本設(shè)計(jì)還利用開發(fā)板上PowerPC實(shí)現(xiàn)了一種純軟件實(shí)現(xiàn)的遺傳算法。為了驗(yàn)證本設(shè)計(jì)的性能，這種實(shí)現(xiàn)方式的遺傳算法在流程和遺傳算子上設(shè)計(jì)都是和本設(shè)計(jì)完全一致的。為了避免由于隨機(jī)數(shù)帶來的偶然性誤差，本實(shí)驗(yàn)得到大量數(shù)據(jù)之后，再對數(shù)據(jù)平均進(jìn)行數(shù)據(jù)統(tǒng)計(jì)。其中二進(jìn)制問題的對比數(shù)據(jù)如表2所示。

表2 二進(jìn)制問題算法運(yùn)行效率對比

0-1背包問題的對比數(shù)據(jù)如表3所示。

表3 0-1背包問題算法運(yùn)行效率對比

從表2中可以看到，本設(shè)計(jì)實(shí)現(xiàn)的算法和其他方式實(shí)現(xiàn)的算法都可以獲得最優(yōu)解，并且收斂速度基本一致。本設(shè)計(jì)相比軟件實(shí)現(xiàn)性能卻有了10倍的提高。從表3中同樣可以看到，本設(shè)計(jì)實(shí)現(xiàn)的算法在處理0-1背包問題時(shí)同樣和其他方式實(shí)現(xiàn)的算法可以獲得近似的最優(yōu)解，并且在收斂代數(shù)上也相差不多。同樣可以發(fā)現(xiàn)，在實(shí)驗(yàn)二中，本設(shè)計(jì)和軟件實(shí)現(xiàn)的遺傳算法運(yùn)行時(shí)間減少將近一半，已經(jīng)有了近100%的提高。因此可以得出結(jié)論，使用軟硬件協(xié)同方式的遺傳算法在保留軟件可移植性的基礎(chǔ)上還可以大幅提升運(yùn)行效率。

5 結(jié)束語

文中介紹了算法平臺設(shè)計(jì)中的軟硬件劃分的依據(jù)、軟硬件劃分的結(jié)果以及設(shè)計(jì)中模塊之間的連接關(guān)系。隨后對設(shè)計(jì)中的各個(gè)硬件模塊的具體實(shí)現(xiàn)做了詳細(xì)的介紹。設(shè)計(jì)了軟硬件之間進(jìn)行信息交互所需要的協(xié)議。最后分別介紹了將硬件化模塊整合成整體遺傳算法IP核、FPGA開發(fā)平臺搭建、軟件平臺搭建、整個(gè)系統(tǒng)整合。

該方法具有軟件的通用性以及硬件的運(yùn)算高效性，并且通過使用IP核節(jié)約了開發(fā)成本以及開發(fā)時(shí)間。理論上使用到遺傳算法的地方均可以使用該方法提高運(yùn)行效率，尤其適合在實(shí)時(shí)性要求較高的場合(例如工業(yè)控制)應(yīng)用。