聶 鑫,殷若蘭,劉海峰
(1.智能機器人湖北省重點實驗室,湖北 武漢 430205;2.武漢工程大學 計算機科學與工程學院,湖北 武漢 430205;3.華為技術有限公司,廣東 深圳 518000)
遺傳算法是Holland在1975年提出的一種概率搜索算法[1]。遺傳算法通過有組織地然而是隨機的信息交換來重新結合那些適應性好的串。類似于生物的進化,遺傳算法作用于類似于基因的二進制串上,通過尋找好的二進制串來求解問題。在每一代中,算法使用上一代適應值較好的個體通過雜交變異的方式生成一個新的種群。由于它不是直接作用于解空間,所以不受搜索空間的限制,同時也不需要豐富的先驗知識,以及其內含的天然并行性。因此遺傳算法作為一種有效的優化算法在多個領域得到了應用。
目前遺傳算法的應用研究中存在若干問題:算法的執行效率低下、算法收斂速度慢以及算法無法找到最優解(即算法過早收斂)。對于后兩個問題,不少學者通過不斷的改進算法的因子以及算法的整體結構,或者是將算法與其他新算法進行融合來提高算法的收斂速度。針對算法執行效率低下的問題,現在也有不少學者試圖使用硬件化的方式來實現遺傳算法[2-4],或者在大型的工作站中利用遺傳算法所具有的天然并行性來解決,這些方法都取得了一定的效果。這些方法在一定程度上也代表了今后遺傳算法的發展方向,同時也為遺傳算法在更多領域甚至在實際場合種應用創造了條件。
軟硬件協同設計(hardware/software co-designing)的思想是在硬件和軟件設計過程中盡最大限度地利用其協同作用來滿足系統的要求。自從軟硬件協同思想提出以后,一直備受國內外研究者的關注,關于軟硬件協同設計領域的研究也十分活躍。到目前為止,國內外學者已經在此方面做過很多研究[5-7],比如在遙感影像的實時效應,音頻編碼算法,Lattice譯碼算法,數字電路仿真,系統的模擬、仿真和調試等方面都使用過軟硬件協同設計方法,并且獲得比使用傳統的設計方法更好的效果。因此利用軟硬件協同設計方法不僅可以提高求解問題的效率,同時可以擴寬其應用領域,進一步推動軟硬件協同設計的發展等。FPGA的快速發展,也為軟硬件協同工作搭建了平臺[8],使得軟硬件協同處理成為了可能。
國內外在軟硬件協同處理遺傳算法方面的研究還很少。考慮到純硬件或者純軟件實現的遺傳算法在各自的優點上面可以互補,通過軟硬件協同工作的遺傳算法同時具有硬件的高效性以及軟件的通用性。這種遺傳算法部署方便,開發成本低,效率高,功耗小,具有可移植性。為遺傳算法在更多領域應用提供了一定的參考價值。
遺傳算法通過“適者生存”這種指導思想對種群進行操作。具體就表現為遺傳算法不斷地通過雜交操作、變異操作以及選擇操作使得適應值較壞的個體逐漸被淘汰。最后種群會逐漸地向最優解的方向收斂。下面就對文中采用的遺傳算法中的一些基本操作進行介紹[9-11]。
(1)編碼操作。
遺傳算法不是直接作用于解空間,而是作用于一種編碼方式。編碼是使用遺傳算法時要解決的首要問題,也是設計遺傳算法時的關鍵步驟,因為設計遺傳算子是建立在編碼基礎之上的。不同的編碼方式所對應的遺傳算子是完全不同的。遺傳算法中一般使用位串編碼與實數編碼兩種方式。眾所周知在所有生物中,基因決定了一個生物的種類以及生物的形態。而這種基因就好比是一類數據的集合。使用位串編碼就可以很好地模擬基因。
考慮到二進制編碼在硬件系統中實現方便的特性,在本設計中使用了該編碼方式。同時為了確保算法的精度,二進制串的長度i設定為50。
(2)雜交操作。
雜交操作是遺傳算法中遺傳操作的一部分。同生物界中一樣,雜交操作可以在一定程度上保持父代個體所具有的適應值。遺傳算法中的雜交操作一般有點式雜交與均勻雜交兩種方式。
在本設計中,考慮到所使用的種群大小為128以及方便FPGA的實現,設計使用單點式雜交操作。
(3)變異操作。
變異操作較雜交操作相對簡單。在一般的遺傳算法中,變異操作是按照一定的概率n發生的。變異操作在整個遺傳算法中起到輔助性搜索的作用。當變異概率n過大時,可能就會破壞種群較好的模式。當n過小時,就會使得算法產生新個體能力下降與過早成熟。當變異操作發生時,隨機的在基因片段中選取一點或者多點進行編譯操作。具體操作就是按位取反。
本設計中由于采用了單點式的雜交方式,并且種群并不是很大,所以這里采用的變異方式為在種群的128個個體中每次選取1個個體進行變異操作。
(4)選擇策略。
在遺傳算法中,選擇策略也起著相當重要的作用。不同的選擇策略導致了不同的選擇壓力。較大的選擇壓力使得較優的個體能在種群中獲得更多的復制數目。使得種群更快收斂。而較小的選擇壓力則使得種群收斂速度較慢,但使得算法獲得全局最優解的概率增大。
比較常見的選擇有繁殖池策略、輪盤策略、精英選擇策略等。繁殖池策略就是根據個體的適應值計算出其在種群中的相對適應值,根據相對適應值進行復制操作。適應值越高的個體復制的個數越多。然后在復制個體中進行遺傳操作。并且使用子代完全替換父代。
在本設計中,使用μ+γ的選擇策略:在父代中選擇μ個產生γ個子代,然后從μ+γ個個體中選擇μ個最優個體替換父代。具體操作是當子代生成進行完評價之后,每次都用子代和父代中的最好個體去替換舊個體,從而增大選擇壓力,使得種群更快收斂。由于本設計中變異概率較大,從而也在一定程度上緩解了種群陷入局部最優解的狀況。
(5)適應值評價。
遺傳算法中,適應值是評價種群個體好壞的標準,是遺傳算法中收斂的驅動力。在遺傳算法中,具有優秀適應值的個體將在種群中獲得更多的生存機會。不同的問題有著不同形式的適應值評價函數。但是一般來說適應值評價方式有兩種,一種是選取結果的最大值,另外一種則是選取結果的最小值。
在本設計中,使用選取最大值的方式。
(6)算法終止。
遺傳算法的終止是通過提前設定的參數來確定的。一般使用遺傳算法所解決的問題都是運算復雜度高的類型。可能只知道解的空間范圍。一般來說,遺傳算法的終止條件有多種。一種是無論算法是否找到最優解,當算法執行N代后則停止。使用此種方法的遺傳算法運行時間比較穩定,因為它運行的代數是個確定的數字。數字N的大小在該方法中比較重要。首先,如果N較小,算法可能得不到最優解就停止。另一方面,如果N較大,雖然找到最優解的概率變大,但是如果算法在早期就達到穩定狀態,那么就浪費了后續運行的時間。另外一種方法是跟蹤每代運行的最優個體,如果該最優個體在N代內不發生變化,算法就會停止。數字N的大小在該方法中同樣比較重要,如果N較小,可能算法只是在局部的最優解收斂,并不是全局的最優解。如果N較大,也會造成運行時間的浪費。該方法的好處是至少可以確定獲得局部最優解。缺點則是算法的運行時間不確定。
在本設計中,為了保證尋找到局部最優解,采用第二種方法。
在本設計中,使用Xilinx公司的FPGA作為開發平臺。Xilinx公司FGPA芯片主要由6部分組成,即可編程輸入輸出單元、時鐘管理、基本可編程邏輯單元、布線資源、塊RAM、底層功能單元和硬核。
Virtex系列是Xilinx的高端產品,這個系列的產品一般性能好,速度快,并且板載更多硬核。Virtex-II Pro系列是在Virtex-II的基礎上增強了嵌入式處理功能,內嵌了Power PC 405內核,還包括了先進的主動互聯技術,以解決高性能系統所面臨的挑戰。Virtex-II Pro系列的主要特征如下:
(1)采用了1.5 V核電壓,4輸入LUT。
(2)420 MHz的始終技術,內置多達12個DCM模塊。
(3)支持20多種I/O接口標準。
(4)增加多個3.125 Gb/s速率的Rocket串行收發器。
(5)內置18x18位乘法器模塊。
(6)內嵌PowerPC 405硬核處理器。
本設計中使用的Virtex-II Pro系列型號為XC2VP30,因為該型號的FPGA提供了板載CPU,配合Xilinx公司的EDK工具可以很方便地進行軟件開發,方便軟硬件協同設計的實現。該型號的FGPA的主要性能特征如表1所示。

表1 Virtex-II Pro XC2VP30
使用軟硬件協同的方式可以結合軟硬件各自的優點,對設計進行進一步的優化。綜合軟硬件各自的優點,采用軟硬件協同的工作方式實現的系統,將系統中一些底層簡單而重復,特別是能夠并行化的工作交由硬件完成,將具有通用性,串行的工作交由軟件完成,不僅可以提升系統的效率,縮短系統的開發周期,并且使得系統具有可重用性。在軟硬件協同中,如何劃分軟硬件具體工作是一件重要的事[12]。因為這涉及到設計的運行效率以及具體實現的功能。對遺傳算法軟硬件劃分確定,硬件部分為總控模塊、初始化模塊、交叉選擇模塊、變異模塊、評價模塊。軟件部分為隨機數模塊和適應值評價模塊。整個系統的設計圖如圖1所示。

圖1 系統設計圖
在設計平臺中,CPU(PowerPC)時鐘頻率(300 MHz)與FPGA提供的時鐘頻率(100 MHz)不一致,并且在CPU上運行的軟件程序完成所需要的時鐘周期數是不確定性的。由于在本設計中存在許多軟件層面與硬件層面的信息交互,為了保證信息交互的同步性、可靠性,必須設計一個通信協議來確保數據的正確性。本設計中軟硬件信息交互中可能存在的問題大致如下:
(1)由于PowerPC時鐘頻率較快,如果軟件端的請求只發送一次,而在時序控制的系統中硬件響應事件僅在時鐘上升沿或者下降沿的時刻響應信號的變化,這就有可能導致硬件無法獲取啟動信號。
(2)同樣由于PowerPC時鐘頻率較快,如果一直發送請求,直到硬件返回數據停止,那么就有可能使硬件響應軟件多次,出現硬件無法正常工作等錯誤。
(3)由于FPGA處理數據較快,當硬件完成工作之后,如果在軟件未就緒的情況下通知軟件,就會出現信號丟失,導致整個系統出錯。
(4)由于系統PowerPC時鐘頻率與FPGA時鐘頻率不一致,可能會使信號無法采集,從而使某一方面無限等待,導致系統的死機。
基于以上種種可能發生的異常,必須設計一種可靠的協議[13-14]。鑒于以上描述問題與網絡通信中出現的問題有一定程度的相似性,并且網絡通信中的復雜程度要遠大于這里,故考慮借鑒網絡通信中的可靠性傳輸協議,即TCP協議。TCP協議通過3次握手協議確保通信雙方數據傳輸的可靠性。本設計借鑒3次握手的方式,設計通信協議,如圖2所示。
在本設計中,在雜交模塊、變異模塊、初始化模塊以及總控模塊中都使用了該協議來確保軟硬件雙方信息交互的正確性。

圖2 通信協議
為了讓軟件與硬件能夠正常通信,除了協議之外還需要有一個共同的通道。因此需要在FPGA上建立部分寄存器來模擬通信的通道。依據通信協議中所需要的狀態信號以及通信數據的需要,共建立10個32位的寄存器。寄存器作用分別描述如下:
(1)寄存器0:該寄存器保存著軟件端給硬件端的所有信號。信號依次如下:
Start:啟動信號,通知硬件啟動,該信號使用寄存器0中的第0位即 reg0[0];
Stop:停止信號,當系統有特殊需要時可能所發出的停機信號,通過該信號通知硬件停機。該信號使用寄存器0中的第1位即 reg0[1];
Cal_done:適應值評價完成信號。通過該信號來告知硬件適應值評價結束,并且已經存放在相應位置。該信號使用寄存器0中的第2位即 reg0[2];
ini_sg_done:初始化完成信號。通過該信號來告知硬件初始化工作完成。該信號使用寄存器0中的第3位即 reg0[3];
rand_done:隨機數產生完成信號。通過該信號告知硬件隨機數產生完成。該信號使用寄存器0中的第4位即 reg0[4]。
(2)寄存器1:該寄存器保存著硬件端給軟件端的所有信號。信號依次如下:
rand_reg:隨機數請求信號,該信號使用寄存器1中的第5位即 reg1[5];
cal_req:適應值評估請求信號,該信號使用寄存器1中的第3位即 reg1[3];
ini_reg:初始化請求信號,該信號使用寄存器1中的第1位即 reg1[1];
done:算法運行結束信號,該信號使用寄存器1中的第4位即 reg1[4]。
(3)寄存器2~3保存需要進行適應值計算的個體。
(4)寄存器4~5保存初始化生成的個體。
(5)寄存器6~7保存最優個體。
(6)寄存器8保存軟件評價出的適應值結果。
(7)寄存器9保存由軟件生成的隨機數。
如圖1所示,需要實現的硬件模塊為總控模塊、雜交模塊、變異模塊、評價選擇模塊、片上內存模塊、片上內存選擇讀取模塊、初始化模塊。對平臺設計中的硬件化模塊進行功能仿真。仿真工具選擇使用Xilinx ISE自帶仿真器。
使用Xilinx ISE自帶仿真器進行仿真之前,必須要建立測試硬件功能的激勵文件。ISE提供了兩種不同的方式。第一種是基于HDL測試代碼,建立一個Verilog Test Fixture類型的文件,將這個文件與待測試文件相關聯,然后根據不同的測試目的編寫激勵代碼。這種方法工作量較大,并且修改較復雜。另外一種方式就是基于波形的測試代碼,建立一個testbench波形文件,一樣也將這個文件與待測模塊進行關聯。系統會根據模塊的輸入輸出顯示一個波形文件,用戶可以通過修改這個波形文件的輸入信號直觀地改寫測試的激勵文件。最后在系統的Behavioral Simulation 狀態中運行Xilinx ISE自帶仿真器,就可以顯示波形文件。本設計中采用第二種測試方法。
本設計硬件部分的工作流程是由總控模塊來控制的。軟件層面的隨機數模塊和適應值計算模塊,硬件層面的初始化模塊、交叉選擇模塊、變異選擇模塊、評價模塊都與總控模塊進行著信息的交互。因此總控模塊是整個設計的核心部分,就好比計算機內部的CPU,控制著整個設計的流程以及數據的流向,各模塊也都是在總控模塊的控制信號下有序地工作。對本設計硬件部分的設計而言,整個系統的工作狀態都體現在總控模塊上。各個子模塊通過總控模塊的控制信號進行信息的交互。
該模塊提供各個模塊之間調用的控制信號,從而控制整個遺傳算法的流程以及數據的流向,協調各個模塊有序地工作。總控模塊由一個大狀態機構成,狀態分別為IDLE、INIT、CROSS、MUT、VALUE和STOP。總控模塊通過狀態機的方式來控制其他模塊。狀態機如圖3所示。

圖3 系統運行狀態機
如圖3所示,本模塊中共有6個狀態。
整個系統的工作流程為:系統復位或者上電后進入IDLE狀態,系統在START信號為0的時候則在IDLE狀態保持等待。當系統得到START=1后,轉入INIT初始化狀態;INIT狀態工作未完成時,INIT_DONE一直等于0,并且保持在INIT狀態繼續工作。當初始化工作完成后發出INIT_DONE=1信號,系統轉入CROSS狀態;在雜交操作未完成之前,CROSS_DONE一直保持為0,并且保持在CROSS狀態繼續工作。當交叉操作完成后發出CROSS_DONE=1信號,系統轉入MUT狀態;在變異操作未完成之前,MUT_DONE一直保持為0,并且保持在MUT狀態繼續工作。當變異操作完成后發出MUT_DONE=1信號,系統轉入EVALUE狀態;評價操作完成后進行停止狀態判斷,如果滿足停止條件,則發出STOP=1信號,系統轉入STOP狀態,否則發出STOP=0信號并轉入CROSS狀態,繼續進行循環操作;系統完成STOP狀態要做的工作后無條件轉入IDLE狀態。
(1)隨機數模塊。
該模塊提供了遺傳算法流程中初始化模塊中個體生成、雜交選擇模塊的個體選擇和雜交點選擇、變異選擇模塊的個體選擇和變異點選擇。該模塊采用Xilinx公司擴展的C語言實現。具體實現表現為一個函數。函數有一個控制參數。函數返回為所需求的隨機數值。軟硬件交互協議的部分由調用該函數的部分控制實現。函數的內部具體實現為根據控制參數來判斷硬件所需的隨機數的范圍。
(2)適應值評價模塊。
該模塊的功能為完成遺傳算法整個流程中的適應值評估工作,也就是所需要解決問題的具體描述。該模塊采用Xilinx公司擴展的C語言實現。具體實現表現為一個函數。函數的參數為控制參數以及需要進行適應值評價的個體(具體表現為一個50維數組)。函數返回為該個體的適應值。軟硬件交互協議的部分由調用該函數的部分控制實現。函數的內部具體實現為針對所求問題對二進制編碼形式的個體進行相應的計算。
由于設計中所有硬件化模塊之間存在種種的外在以及內在聯系,本設計中將所有的硬件化模塊打包生成一個硬件IP核。IP核的生成使用Xilinx公司的EDK工具提供的IPIF接口。
使用EDK工具的硬件IP核生成向導新建一個IP核,在生成過程中同時選擇生成使用該IP核時所需要的寄存器,共10個32位寄存器。使用總控模塊作為整個IP核的次頂層模塊。在向導提供的頂層模塊中將總控模塊進行添加,并且將寄存器與總控模塊的輸入輸出端口進行連接。IP核資源使用情況如圖4所示。

圖4 遺傳算法IP核資源使用情況
從圖4中可以看到,硬件IP核占用資源較少,占用整個系統資源不到18%。說明硬件部分實現體積較小并且功耗較小。IP核的使用可以極大程度地簡化開發者的工作量,并且由于IP核可配置,所以為后續設計提供了可擴展空間。
使用EDK軟件新建工程,在新建工程向導時選擇開發板型號以及速度等信息。然后再根據本設計中的具體需求,添加PowerPC、內存、開關等基本設備。然后再往設計中添加新建的遺傳算法IP核。并且將IP核的數據通訊綁定在OPB高速總線上。因為本設計中采用了更加直觀的視頻輸出結果,所以還需要在平臺中添加視頻輸出IP核,并加入相應的驅動程序。最后根據開發板用戶使用手冊將管腳進行綁定。至此硬件開發環境搭建完成。
在平臺完成綜合布局布線生成可下載文件之后,啟動SDK工具進行軟件端程序模塊的搭建。在SDK工作環境下新建一個C語言環境的工程,將隨機數模塊、適應值評價模塊以及軟硬件交互協議軟件部分在該工程下整合。系統所需要的內存地址數據由xparameters.h文件提供。在系統停機之后將算法停機之后的結果通過視頻輸出。最后編譯整個工程,并且將程序代碼片段及數據片段存放位置指定與片上內存,將程序使用堆棧等其他數據設置內存中存儲。將SDK工程產生的ELF文件與硬件平臺產生的下載文件使用系統自帶工具進行聯合,生成新下載文件。使用IMPACT工具將生成的文件下載到開發板中或者使用IMPACT工具新建CF卡啟動引導文件完成整個設計。
在科學研究中,數值計算[15]是一類經常遇到的問題,通常這類問題的復雜度較高,使用普通的算法計算時間較長。使用遺傳算法解決數值問題可以起到較好的效果。但是軟件實現的遺傳算法執行效率低下,所以可以使用軟硬件協同工作的方式在不改變算法通用性的基礎上加快算法的收斂速度。
二進制問題是一類可以有效驗證遺傳算法功能正確性的基本問題。設計中使用的問題為計算二進制串中“1”的個數。1的個數越多,效果越優。由于初始化個體為隨機初始化,所以在初始化個體中0與1的比例接近1∶1,必須通過不斷的雜交和變異才可以獲得最優解。因為個體串長為50,所以最優解為50個1。使用軟硬件協同的遺傳算法解決該問題只需要改寫軟件端的適應值函數,無需對硬件進行修改。
二進制問題運行效果如圖5所示。
從圖5可以看出,算法可以正確找到最優解,運行的代數為1 272,去除用于判斷終止條件的500代,算法共運行700多代。整個算法運行時間為4.2秒。

圖5 二進制問題運行效果
0-1背包問題是生活中比較常見的一類問題。該類問題描述為有一體積無限大的背包,但是該背包只能容納一定重量的貨物。如果你有一組貨物,每種貨物有著不同的重量以及價格,所求問題是如何在這些貨物中選取適當的貨物(貨物個數沒有限制),使這個背包在指定的重量范圍內,商品的價值最高。在本設計中,個體二進制串長為50。所以使用的貨物總數為50個。在適應值評價時,50個貨物與二進制串的二進制位相對應,如果該二進制位為“1”則該貨物被選取,為“0”則不選取。最后累加選取貨物的重量與價值。首選判斷貨物總重量,如果總重量大于設定的最大重量,就將適應值設置為-1。否則就將適應值設置為貨物的總價值。
設物品的價值為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
使用軟硬件協同的遺傳算法解決該問題同樣只需要改寫軟件端的適應值函數,無需對硬件進行修改。本問題經過優化的遺傳算法所能獲得的最優值為3 103。而使用普通遺傳算法(即本設計所采用的遺傳算子)所能獲得的最優解為3 031。
背包問題運行效果如圖6所示。

圖6 0-1背包問題運行效果
從圖6中可以看出,算法獲得的最優解為2 906,基本接近解3 031,運行的代數為1 722,去除用于判斷終止條件的500代,算法共運行1 000多代。整個算法運行時間為11秒。
因為遺傳算法是一個隨機搜索算法,算法的性能受初始化種群的好壞以及雜交變異的隨機性影響較大。而以上實驗截圖均是實驗中隨機獲取的數據,并不能代表設計的性能以及效果。
為了對軟硬件協同遺傳算法平臺的性能進行分析,本設計還利用開發板上PowerPC實現了一種純軟件實現的遺傳算法。為了驗證本設計的性能,這種實現方式的遺傳算法在流程和遺傳算子上設計都是和本設計完全一致的。為了避免由于隨機數帶來的偶然性誤差,本實驗得到大量數據之后,再對數據平均進行數據統計。其中二進制問題的對比數據如表2所示。

表2 二進制問題算法運行效率對比
0-1背包問題的對比數據如表3所示。

表3 0-1背包問題算法運行效率對比
從表2中可以看到,本設計實現的算法和其他方式實現的算法都可以獲得最優解,并且收斂速度基本一致。本設計相比軟件實現性能卻有了10倍的提高。從表3中同樣可以看到,本設計實現的算法在處理0-1背包問題時同樣和其他方式實現的算法可以獲得近似的最優解,并且在收斂代數上也相差不多。同樣可以發現,在實驗二中,本設計和軟件實現的遺傳算法運行時間減少將近一半,已經有了近100%的提高。因此可以得出結論,使用軟硬件協同方式的遺傳算法在保留軟件可移植性的基礎上還可以大幅提升運行效率。
文中介紹了算法平臺設計中的軟硬件劃分的依據、軟硬件劃分的結果以及設計中模塊之間的連接關系。隨后對設計中的各個硬件模塊的具體實現做了詳細的介紹。設計了軟硬件之間進行信息交互所需要的協議。最后分別介紹了將硬件化模塊整合成整體遺傳算法IP核、FPGA開發平臺搭建、軟件平臺搭建、整個系統整合。
該方法具有軟件的通用性以及硬件的運算高效性,并且通過使用IP核節約了開發成本以及開發時間。理論上使用到遺傳算法的地方均可以使用該方法提高運行效率,尤其適合在實時性要求較高的場合(例如工業控制)應用。