硬件化演化算法在函數優化上的運用

1 引 言

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

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

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

2 演化算法硬件化構造

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

2.1 演化算法的軟件實現思路

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

　　軟件實現各個部分含義為：

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

　　由于目前的高級語言基本上都支持所有的數據類型，包括：整型、實數型、字符型等，所以上面的各種數據類型基本上都可以實現。

　　(2)初始化種群的軟件實現：初始種群的生成也就是隨機地產生N個個體組成1個初始種群，該種群代表一些可能解的集合。

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

　　(3)適應度評價函數的軟件實現：適應度函數是用來進行個體評價，判斷個體適應性能優劣的方法，該數值通常是作為個體選擇的依據，對整個算的運行，算法的性能有重要的影響。

　　在軟件實現時，通常是將該函數設計成一個獨立的函數或是子過程，在每個需要重新計算個體適應值的地方只要調用該函數就可以。

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

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

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

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

2.2 硬件結構設計

2.2.1 從軟件實現抽象硬件模塊

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

　　(1)將軟件實現中初始化種群單獨抽象為硬件實現時的pop_initial模塊；

　　(2)將軟件實現中適應度評價單獨抽象為硬件實現時的fitness模塊；

　　(3)將軟件實現中選擇操作單獨抽象為硬件實現時的choose模塊；

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

　　(5)為了進行個體的讀寫還需要2個內存模塊，分別保存個體和其適應值；

　　(6)為了使這么多模塊互相之間相互協作的完成任務還需要一個控制模塊control模塊，類似與軟件實現中的CPU協調控制程序的運行。

2.2.2 硬件系統整體結構圖及解釋

　　(1)硬件系統整體結構圖

　　硬件系統整體結構圖如圖1所示。

　　(2)系統各模塊功能解釋如下：

　　Control模塊 該模塊好比軟件實現的時候的CPU控制著整個系統的協調工作。它的主要功能是產生一些控制信號，控制各個模塊的啟動、停止，并為各個模塊的同步提供協調信號。具體講：它提供各個模塊的時鐘信號，同步各個模塊；接收來自Random1模塊的2個隨機地址，從RAM模塊中選擇個體和其對應的適應值將其傳到Choose模塊；接收來自Choose模塊和Crossover_mutation模塊的狀態信號，控制其發出的對其他模塊的控制信號；控制多路數據選擇器、Initial模塊和RAM模塊的啟動等。

　　Initial模塊 該模塊即是初始化模塊，它內部主要是由一個隨機數模塊構成的，用來產生一定數量的隨機數序列作為初始種群。

　　Fitness模塊 該模塊用來計算個體的適應值。一般根據軟件實現中適應值函數的不同，該模塊內部主要是由一些加法器、鎖存器和乘法器構成(在函數優化中)。

　　Choose模塊 該模塊主要實現選擇2個個體的功能。當該模塊啟動，并從存儲模塊接受2個個體和其適應值后，采用聯賽競爭機制選擇兩者中的1個進入下一模塊，如此再選擇1次，選擇2個要進入交叉變異模塊的個體。

　　交叉變異模塊 該模塊在啟動后，接收Choose模塊傳來的2個個體，并按照隨機數模塊產生的隨機數確定交叉點，進行交叉和變異。

　　多路數據選擇模塊 對進入fitness模塊的個體進行分時控制。

　　Ramdom1模塊 該模塊為選擇模塊選擇個體和適應值提供2個隨機的地址。

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

　　Ram模塊 主要是用于保存個體和其適應值。具體實現時，我們常用了Altera公司提供的IP core生成2個雙端口的ram。

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

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

3 實 驗

　　在本部分中，首先對上述提到的各個模塊進行獨立的仿真，然后再將其運用在一個函數的優化問題上，并與其他同問題軟件實現的算法進行比較。

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

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

　　圖3為Fitness模塊仿真圖，適應度模塊足個邏輯模塊，只要輸入的個體發生改變，其輸出也就相應改變。圖3即為仿真后的波形圖，此時輸出信號的右側有值。上述實現的是f(x)=-∣x∣的求值，這里可以看到：當ina_fitness為“000000001”(實數1)和inb_fitness為“000000011”(實數3)時候，outa_fitness為“100000001”(實數-1)、outb_fitness為“100000011”(實數-3)。

　　圖4為Random模塊仿真圖。圖4中左側的是信號名稱，中間是信號的值，右側是信號的波形圖。由圖4可以看出，在復位信號reset_radom2未變高之前，輸出的2個隨機數的值是初始值0；當復位信號有效后，2個輸出立即由0轉為2個非0的輸出。

　　圖5是選擇模塊開始進入工作狀態前后的仿真波形圖。當current|_state為current_state_idle時，系統還處于初始化階段，start_choose信號為“0”，當start_choose信號為“1”時，狀態機轉入current_state_st1狀態，選擇開始，outa信號與outb信號開始有值，在狀態current_state_st2時，進行第一次選擇。

(2)實驗

　　下面將上述各個模塊合在一起，構成一個完整的系統，對以下函數進行優化，并進行一定的說明。

　　圖6是用基于FPGA的演化算法對上述函數進行優化后得到的最優結果。從上面可以看到，由上述方法得到的最優個體是“11111010”，最差個體是“11111010”。

　　用VC++設計實現了上面函數的優化過程，同時軟件采用的交叉和變異操作與上面提到的方法類似，算法運行參數也相同，并在同一系統環境下實現：賽揚1.7，內存256 MB。軟硬件運行結果比較如表1所示。

4 結 語

　　本文從演化算法的軟件實現到演化算法的硬件化，詳細的闡釋如何用Altera公司的CycloneⅡ型號的FPGA，并用VHDL實現一種比較先進的演化算法，并用該硬件化演化算法求解一函數優化問題。演化算法的硬件化極大地提高演化算法的運行速度，為演化算法在實時場合的運用提供了一種可能性。