一種新的基于真值表分解技術的電路加速演化策略（自動化）
一種新的基于真值表分解技術的電路加速演化策略（自動化）
孟亞峰， 張峻賓，蔡金燕
（軍械工程學院電子與光學工程系，石家莊050003）
摘要：硬件演化技術在電路演化過程中具有自組織、自適應、自修復性能，具有重要的工程應用價值，硬件演化技術能夠實現的核心就是演化算法。目前中等規模及大規模電路演化的時候存在演化速度慢等缺陷，直接影響電路演化的時效性。提出了一種新穎的電路加速演化策略，即基于真值表分解的電路演化策略，從不同的角度對電路演化算法進行了改進，有別于常規的改進演化算法。通過對典型電路進行仿真分析，證明了所提出的加速演化策略的有效性，并且具有重要的應用價值。
關鍵詞：硬件演化；電路演化；演化算法；真值表分解技術；加速演化
中圖分類號：TP301.6 文章編號：1671-637X(2016)04 -0062 -04
0 引言
隨著電子技術的不斷發展，為提高電子電路在各種復雜、惡劣環境的自適應性，近年來興起了一種新穎技術——硬件演化( Evolvable Hardware，EHW)技術。
硬件演化公式可表示為硬件演化=可編程邏輯器件+演化算法。硬件演化是以演化算法為組合優化和全局搜索的工具，通過模擬進化來獲得預期的電路或系統結構。
正因如此，采用EHW技術，能夠使電路具有自適應、自組織、自修復的能力?？删幊踢壿嬈骷?/font>( Program-mable Logic Device，PLD)是EHW的硬件基礎，而演化算法( Evolutionary Algorithm，EA)是EHW技術能否實現的關鍵。
目前，EA存在演化速度慢、容易陷入局部最優等缺陷，因而對EA進行改進是現在的一個研究熱點。改進的目標都是為了加速EA的收斂、減少迭代次數，而較多采用遺傳算法及其改進算法和粒子群算法及其改進算法，或者是采用動態變異率演化算法副。在針對大規模電路進行演化的時候，目前主流演化算法的策略為分而治之。
本文針對組合邏輯電路演化過程中真值表所表現出來的特點，提出了一種基于真值表分解技術加速電路演化的策略，并進行了仿真分析。1 真值表分解技術加速演化電路基本策略。
在實現演化算法的過程中，當面臨大規模的真值表的口寸候，演化電路的規模將隨真值表輸入端個數的增加呈指數增加。但是，演化收斂的速度將隨真值表規模的增加呈指數降低，因此提高具有大規模真值表的電路演化速度將顯得格外重要。對真值表進行必要的拆分，能夠在很大程度上提高演化算法的收斂速度。
為了解決復雜電路快速演化問題，TORRESEN J將“分而治之”思想引入到EHW技術之中，而拆分真值表技術是分而治之( divide-and-conquer)的深化，在演化過程中，結合二元判決圖( Binary Decision Diagram，BDD)，將真值表實行一層一層的剝離。
在對真值表進行拆分的時候，不能拆分得太細，因為實現同樣功能的電路拓撲結構可能不一樣，拆分得太細就不能表現出電路結構的多樣性。例如有如下的電路布爾函數：Y1=AB+AC，Y2 =A(B+C)，如圖1所示。
從Y1和Y2可以看出，雖然它們有相同的具體功能，但是電路結構完全不一樣，所消耗的硬件資源也不一樣，各有各的特點。不能直接判定哪一種電路結構好，哪一種電路結構差，需要根據具體的問題環境，找出所需要的電路結構。如果采用真值表分解技術將真值表全部進行分解，將只能得到一種固定不變的電路結構；如果采用真值表分解技術同EHW技術相結合，不僅可以演化出相同功能的不同結構的電路，還能加速電路的演化。
為了有利于演化算法的展開，使演化算法的自適應、自組織特點得到有效的發揮，本文采用的方法是將真值表拆分到只剩4個輸入組合為止，剩余的4個輸入端再采用演化算法進行演化，得到最終的目標電路。拆分至4個輸入端的另一個參考依據是目前主流FP-GA的查找表(Look-up Table，LUT)具有4個輸入端，且目前FPGA被作為硬件演化的硬件平臺。
雖然FPGA的LUT相當于一個ROM，能夠直接存儲任意4輸入1輸出的真值表，本文為了更好地在電路設計過程中對演化算法的自適應自組織特性進行展示，對剩余未拆分電路采用演化算法進行設計。
在基于真值表分解技術的電路演化過程中，根據BDD原理，將大規模電路拆解成了關聯度較小的小規模電路，將純粹的電路演化過程變成了電路演化和BDD的有效結合過程。而小規模電路在電路演化的時候，約束條件較少，相對于大規模電路的電路演化搜索到目標電路編碼將比較容易，演化算法迭代次數將大幅度縮減，同時收斂速度也將加快。
本文中演化算法采用遺傳離散粒子群算法( Ge-netic Algorithm Discrete Particle Swarm Optimization,GADPSO)。CADPSO演化算法是將遺傳算法(GeneticAlgorithm，GA)的交叉、變異融合于離散粒子群算法( Discrete Particle Swarm Optimization, DPSO)之中，(GA算法在優化問題方面限制很小，對目標函數及約束要求很低，具有較強的魯棒性和適應性，雖然收斂速度比較慢，但是能夠較好地克服尋優過程中易陷入局部最優的缺點。然而DPSO搜索速度較快，因此將GA算法和DPSO算法相結合能克服相互的缺陷，將GADPSO演化算法引入電路演化，能夠極大地減少演化目標電路編碼所需要消耗的時間。能明顯提高粒子群的多樣性，有助于改善DPSO算法的收斂速度和收斂精度。
2 加速演化策略的步驟
任何一個真值表均能表示成一個布爾函數。首先
完成真值表拆分之后，緊接著施加GADPSO演化算法，如圖2所示。
GADPSO演化算法實現的步驟如下所述。
選擇、交叉、變異操作。
4)更新各個粒子的位置和速度。
5)計算每一個粒子的適應度值，并和全局最優值進行比較，對全局最優值進行更新。
6)根據計算出的適應度值判斷算法是否滿足收斂標準，如果滿足，則輸出最終粒子編碼；如果不滿足，則轉入步驟3）。
7) GADPSO算法結束。
3 仿真驗證與分析
為了驗證所提出的基于真值表分解技術在電路演化過程中的有效性，選取帶進位的兩位加法器作為典型電路進行仿真研究，其真值表如表1所示。由于篇幅的關系，表1中只列出了真值表的部分輸入輸出關系。其輸入從00000 -直到11111，一共32個組合。
在進行真值表分解的時候，由演化算法進行輸入端的分離。根據約束條件，演化算法將A1輸入端選出，A1有“0”，“1”兩種取值，取“0”的時候為A1，取“1”的時候為A1，以此為標準將真值表劃分為兩部分。對于剩下的輸入端仍然采用劃分A1的標準進行分解，直至未分解的輸入端剩余4個即可。由于表1本身只有5個輸入端，因而只需要拆分一次真值表即可。
在演化過程中設置適應度函數為
采用GADPSO算法進行20次仿真分析，同時設置GADPSO算法的相關參數。令初始化樣本數，N=40，變異率pd=0. 05，交叉率pc=0.95，交叉算子采用2點交叉，變異算子采用2點變異。
最后得到仿真數據如圖3所示。
從圖3中可以清晰地看出，在20次仿真分析中，采用真值表分解技術實現電路演化的平均演化迭代次數都遠遠小于直接對真值表進行電路演化。
并且數據統計表明：基于真值表部分分解平均演化迭代次數是3407次，然而，沒有采用真值表部分分解技術的平均演化迭代次數是16 915次。
前者只對真值表進行了一次分解，即待演化的目標電路分解成了兩個子電路，并結合式(1)，演化出目標電路的布爾函數。通過仿真對比分析，可以看出真值表分解技術能夠極大地加速演化算法的收斂速度，在仿真中，基于真值表分解技術在加速電路演化方面的有效性也得到了證明。
4結論
本文從不同的視角，提出了一種基于真值表分解的加速電路演化策略，有別于常規的改進演化算法。通過仿真分析，證明了所提出的策略在電路加速演化方面的有效性，同時保證了電路的多樣性，此技術的優勢在組合電路的演化方面得到了很好的體現。
