引入演化效率因子的演化算法設計

吳會叢 于潔

摘 要：隨著電子芯片技術的發展，電路系統不斷向高集成度和智能化發展。在復雜電磁場環境的各種干擾下，對信息化電子系統的穩定性和可靠性要求越來越高，電子系統的可靠性及自主容錯能力成為電路設計所面臨的新挑戰。為提高惡劣情況下電路的抗干擾能力，提出將分析得到的演化效率因素作為算法的影響因子，引入到演化算法的適應度函數中，對算法進行提高和改進。研究結果表明，在單點短路和斷路故障仿真實驗中，引入演化效率因子的演化算法的平均無故障概率分別為0.754和0.853。與傳統的演化算法相比，兩者分別提高了16.4%和14%；與自適應算法相比，兩者分別提高了6.7%和5%，證明在受擾或局部損傷的情況下，引入演化效率因子能夠有效提升電路系統的魯棒性及容錯抗擾能力。研究結果對改進電路設計的強化及完善有一定的參考價值。

關鍵詞：電子電路；演化效率；演化算法；電路設計；容錯能力

中圖分類號：TP275 文獻標志碼：A

文章編號：1008-1542（2018）03-0275-07

隨著電子應用技術的高速發展和系統設計的復雜化，電磁防護等設備的可靠性和有效性面臨著嚴峻考驗，電子電路設計技術已經越來越受到相關企業和研究人員的重視[1-4]。但是傳統的電路設計方法出現了設計過程繁瑣、抗干擾能力差等諸多問題。演化硬件（evolvable hardware，EHW）技術從硬件的進化、適應和修復方面給電路設計帶來了嶄新的解決方案，主要通過演化算法（evolutionary algorithms，EAS）和目標模型來設計所需要的電子電路系統以及電路模塊[5-9]。

電路演化是電路設計的重要部分，許多研究者從演化方法上對電路的容錯能力進行分析研究[10-14]。與傳統容錯方法相比，進化方法依賴于人們的先驗知識，能提高電路設計的效率并為實現電路自動化設計提供保障[15]。為了提高演化過程的搜索效率和速度，很多研究者對傳統的演化算法進行了改進。文獻[7]介紹了遺傳算法的啟發式搜索方法，該方法利用合成電路提高了電路的容錯能力；文獻[10]將自適應HereBoy算法運用于遺傳算法群體，利用兩位二進制乘法器，為電路進化過程中前期出現的局部最優和后期的適應度變化緩慢問題提供了解決方法，證明了較傳統方法電路進化的收斂速度和種群多樣性獲得提高；文獻[12]采用近似Pareto分布熵及其變化評估種群的進化狀態，以此為反饋信息來設計進化策略，算法表現出較好的收斂性和多樣性。

本文基于搜索空間和尋優過程進行研究，利用演化效率的變化影響電路的演化進程，將電路演化效率作為一個因子，引入到適應度函數中，指導電路高效準確地向異構方向演化，縮短了電路演化的周期，提高了異構電路個體的尋優概率。

1 電路演化設計

電路演化設計是在可進化硬件研究的基礎上，將電路進行編碼，利用演化算法對其進行搜索，尋找出符合要求的電路結構的過程。

1.1 演化設計流程

演化算法是借鑒于生物體的進化過程，模擬自然界生物的世代生存規律，通過子代個體之間基因的遺傳（選擇、交叉和變異）規則，滿足“優勝劣汰”“適者生存”的叢林法則。利用演化算法，將其應用于編碼空間，通過對其編碼的遺傳操作達到尋找最優解的目的[16-18]。電路演化過程流程圖如圖1所示。

通過遺傳算子對個體電路不斷演化，按照編碼方式進行解碼轉換為電路，對元件簡化組合，采用仿真軟件對其進行模擬，通過適應度的計算尋找出適應能力最優的電路。從父代和子代個體中，對個體適應度進行排序，選擇優異的個體；兩兩實現單點交叉，產生新的個體；對這些存在的個體進行一定概率的單點突變，計入總個體，并對其進行適應度評價。如果演化后的適應值趨于穩定且在規定演化次數之內，此時演化成功，停止迭代；否則，當演化次數超過規定次數的上限，此時演化失敗，停止迭代。從這些最優的電路結構中尋找結構差異大但功能相同的電路，進行故障仿真測試。

1.2 編碼方式

在電路優化的設計過程中，通常會利用不同的編碼方式（常見電路演化設計編碼方式如表1所示）對電路的可變部分進行編碼和解碼。本文利用網表編碼（如圖2所示）的連接方式對演化電路進行編碼，[KG*3]電路的拓撲結構以及參數值的變化在一定范圍內隨機波動。由于網表編碼元件連接的多樣性，以及簡單的編碼方式，使電路具有豐富的結構，從而可以在編碼空間中產生結構多樣性的電路，形成初始種群。然后通過遺傳算子（選擇算子、交叉算子、變異算子）對種群進行操作，從而產生新的個體。

2 模型構建

模擬電路演化的最終目的是尋找出容錯能力強的電路系統，如何尋找出最佳的冗余電路系統成為解決問題的關鍵。當系統的每個支路電路結構相同時，稱其為同構冗余組合電路。在這種情況下，由于其結構完全相同，即使故障概率隨機發生，但是在極端環境下，時時對電路系統進行影響，發生故障的概率較大。當系統的每個支路電路結構不同時，稱其為異構冗余組合電路。這種情況下，因其結構不同，對于同一錯誤同時發生故障的概率下降，整個系統更加穩定，容錯能力和抗干擾能力較強[19-21]。

組合最佳的異構冗余電路系統采用傳統的三模冗余系統[22]（如圖 3所示）。即由3個相同的功能模塊電路和1個表決器組成，每個功能模塊都有相同的輸入，針對3個模塊對于輸入的處理得到3個輸出，由表決器進行表決，對結果進行輸出。因此，在三模冗余系統中，異構冗余組合電路發生故障的概率低于同構冗余電路發生故障的概率。

為了進一步提高電路的穩定性，改進電路系統的自容錯能力，采用擴大模塊間的異構度來提高電路系統在不同錯誤發生時模塊間的異構容錯效率，即在特定故障模式干擾下，使模塊之間輸出的錯誤位具有交錯性，只要不同時出現2個相同的錯誤，就能夠屏蔽掉故障模塊的錯誤，以期進行冗余表決后仍能保持系統正確。當錯誤出現在不同位置時進行非相關性糾正，提高了系統的可靠性、安全性以及容錯能力。本文異構冗余系統通過最大化故障狀況下錯誤模式的差別來實現容錯性能，保障故障發生后能夠及時處理，并不影響系統的正常運行，如表2所示。

表2中，a組為3個電路模塊每位輸出均為正確值00…001；b組為第3個模塊在第1位輸出為錯誤，而由于前2個模塊的相同位輸出正確，所以表決器選擇0輸出正確；c組發生2個位的錯誤輸出，但是不在同一個位置上，即分別位于第1位和第2位，所以經過表決器表決，系統輸出仍為正確值；d組中2個位的錯誤發生在同1位，即同時發生在第1位上，表決器無法輸出正確值，因此d組是錯誤輸出。通過這樣設計可以使系統在小故障下依然正常工作，對于處在復雜環境中的電路系統保持穩定運行有很大的作用。

3 算法改進設計

電路演化過程中，適應度評估起著至關重要的作用。在生物學中，適應度是判斷生物體或者生物種群所具有的各項特征對環境的適應性，只有在達到一定適應能力的條件下，其后代才能得以生存。本文通過控制進化的收斂速度，增加種群選擇的多樣性，使其達到在保留優異個體的同時，給予相對較差個體一定的生存空間，從而滿足多樣化結構種群和算法并行，能夠在全局中尋找最優解。根據對電路演化適應度曲線的分析，發現電路演化過程存在一定的趨勢，將該方向作為因子引入適應度函數，控制電路演化。根據對電路解碼后染色體適應度的計算，判別所得電路與目標電路的相似程度。相似程度越高，說明所得電路越接近目標電路，愈滿足設計要求。

3.1 演化效率因子的引入

尋找全局最優解成為研究的一個方向。為了得到最佳的電路組合異構模塊，根據傳統的電路演化方法進行研究，通過分析電路演化進程以及電路適應度效率的變化趨勢，得到演化效率，反映了電路演化的一種方向趨勢，將其反作用于適應度函數，作為影響因子來指導電路向電路異構的方向進行演化，從而得到最佳的異構同功能電路模塊，進而組合成最佳的異構冗余電路系統。電路演化的適應度曲線如圖4所示。根據演化的適應度對其演化效率進行分析，尋找出電路演化的方向，得到演化的效率曲線如圖5所示。

對演化效率曲線進行多維函數擬合，得到演化效率因子E（x）近似函數表達式見式（1），其中G為最大演化代數，k，q，p為演化效率因子中參變量，k的取值是[0.5，1），q，p的取值是（0，0.5）。

式（1）表示，種群接近c代時，電路的演化效率有一個變化的極值點，在c代之前，電路演化效率逐漸升高，表示電路演化搜索的范圍不斷擴大，體現了很好的種群多樣性；在c代之后，電路演化效率逐漸減小，表示電路演化搜索的范圍擴大，速度有所減慢。所以演化效率更多地放在了局部細化選優上，為了防止陷入局部最優，這種演化效率的變化平滑而緩慢，盡力保持電路尋優的穩定性和準確性。

式（2）為演化電路適應度函數表達式，目標相應曲線為f（x），實際響應曲線為g（x），對兩條曲線進行偏差積分，從而獲得它們的面積值，該值越小，演化電路的適應能力越好，所得的曲線越接近演化目標。根據式（1）和式（2）對電路演化過程的電路適應度函數進行轉化，表示如式（3）所示。將演化效率因子E（x）引入，更好地表示出電路演化過程的特點，從而指導電路演化向著異構方向進化。式（3）表示，Fit（x）是將演化效率反作用原適應度F（x）的結果，E（x）是其動態變化的收斂因子。利用E（x）的變化決定了選擇的強制性，當收斂因子越大，原有適應度較高的個體的新適應度就與其他個體的新適應度相差越大，即增加了選擇個體的多樣性，加速了進化進程，避免陷入局部最優解。

3.2 異構選擇

電路演化過程中同一個輸入取得相同的輸出結果，可以擁有多種具有相同功能但是結構差異較大的優異個體電路，在這些個體電路中尋找出最佳的個體電路進行異構冗余組合，使其能夠保證在系統發生故障的情況下，子電路仍舊可以實現電路的功能，保障其正常運行。

基于電路編碼可以得到不同類型的電路組集，這些拓撲結構不同的設計是電路組合的優化。相同組件的參與，不同的拓撲結構可能產生不同的電路特性。根據所產生的結構，從中選擇出結構不同但功能相同的個體。對這些選擇出來的電路進行異構評估從而選取最優個體，進行異構系統組合，從而提升電路容錯效率。

4 實驗結果及分析

按照前述的編碼方式對可演化器件進行編碼，適應度采用傳統的演化算法、自適應算法和引入演化效率因子的改進算法，對譯碼器進行電路進化。根據編碼方案初始化父代染色體電路，初始化種群為10個；對染色體按照一定的比率進行演化算子操作，本實驗按照10%的變異率進行位變異操作，40%的交叉概率進行隨機非對稱單點交叉，50%的選擇概率進行個體遺傳選擇操作。演化算法的演化參數設計如表3所示。

按照解碼方法將染色體轉換成電路并對電路進行仿真測試，根據適應度函數進行個體適應度值計算，并根據個體適應度值對電路個體進行排序，然后按照一定的保留比例，選擇進入下一代繼續進行遺傳操作的個體。電路演化過程中，記錄每代個體的適應度值，并求每代平均適應度值，根據3種演化算法對電路演化進程的適應度值記錄計算并顯示，如圖6所示。從圖中可以看出，本文改進算法的演化進程多樣性表現更好，并且比傳統的算法和自適應算法的收斂速度快，較傳統算法收斂效率提高了7.4%，較自適應算法收斂效率提高了2.1%。從保持多樣性和提高收斂角度分析，改進算法對于電路演化有良好的尋優效果，能夠更好地找到同功能異構度大的電路模塊。

分別在基于傳統算法、自適應算法和改進算法的電路演化實驗中，選擇最后一代的最優種群中的3個電路，作為三模冗余電路系統的相關度模塊，進行組合冗余系統。仿真復雜電磁環境下，針對電路系統可能遇到的故障模型，同時對3個冗余電路系統進行單點短路故障和斷路故障模擬。

4.1 短路故障

在單點短路故障仿真中，隨機在系統中短路同一個元件，并測試整個電路系統的譯碼器真值表，記錄實際響應，并與真值表中的期望響應信號進行對比，計算無故障概率。重復實驗20次，計算平均無故障概率，作為短路故障仿真，2個系統的無故障概率表示電路系統一定的容錯能力，如圖7所示。

從圖7可以看出，基于傳統算法的演化異構組合系統的20次平均無故障概率為64.8%，基于自適應算法的演化異構組合系統的20次平均無故障概率為70.7%，基于引入演化效率因子的改進算法的演化異構組合系統的20次平均無故障概率為75.4%，較傳統算法異構系統提高了 16.4%，較自適應算法異構系統提高了6.7%。說明基于引入演化效率因子的改進算法的電路演化異構冗余電路系統對短路故障有較好的抗干擾能力，引入演化效率因子的改進算法有助于提高電路演化異構冗余系統的容錯能力和穩定性。

4.2 斷路故障

在斷路故障仿真中，隨機在系統中斷路相同的2個元件，并測試整個電路系統的譯碼器真值表，記錄實際響應，并與真值表中的期望響應信號進行對比，計算無故障概率。重復實驗20次，計算平均無故障概率，作為斷路故障仿真，2個系統的無故障概率表示電路系統具有一定的容錯能力，如圖8所示。

從圖8可以看出，基于傳統算法的演化異構組合系統的20次平均無故障概率為74.8%，基于自適應算法的演化異構組合系統的20次平均無故障概率為81.2%，引入演化效率因子的改進算法的演化異構組合系統的20次平均無故障概率為85.3%，較傳統算法異構系統提高了14%，較自適應算法異構系統提高了5%。說明引入演化效率因子的改進算法的電路演化異構冗余電路系統對斷路故障有較好的抗干擾能力，改進算法有助于提高電路演化異構冗余系統的容錯能力和穩定性。

4.3 結果分析

利用電路演化的種群多樣性特點，分析演化效率因素對算法進程的影響，將演化效率作為影響因子引入到演化算法的適應度函數中。通過演化得到多個滿足條件且拓撲結構不同的優秀個體電路，進行電路的異構冗余組合，得到引入演化效率因子的改進異構冗余系統，并與傳統冗余系統和自適應算法冗余系統進行故障模式的仿真測試。綜合上述實驗與結果，引入演化效率因子的改進算法的異構冗余電路系統與傳統冗余電路系統相比，在短路故障下的平均無故障概率提高了16.4%，在斷路故障下的平均無故障概率提高了14%；比自適應算法冗余電路系統在短路故障下的平均無故障概率提高了6.7%，在斷路故障下的平均無故障概率提高了5%。實驗結果證明，引入演化效率因子的改進算法對于電路異構組合的系統有更好的隨機容錯能力和魯棒性，使電路系統在復雜的電磁環境中能夠更穩定地發揮其功能。

5 結 語

基于傳統演化算法和數值擬合方法，提出了一種引入演化效率因子的演化電路算法，將分析得到的演化效率因素作為算法的影響因子，引入到適應度函數中，在保持良好種群多樣性的前提下，提高了算法的收斂速度和尋優效率。利用三模冗余系統，選擇結構差異較大的異構電路進行冗余集成，通過模擬仿真實驗驗證得到，基于演化效率因子的改進算法演化得到的電路模塊，經過異構組合生成的三模冗余電路系統，較傳統的演化算法及自適應算法的異構組合電路系統有更好的容錯能力和魯棒性。本文所采用的方法雖然提高了電路系統的無故障概率，但還存在不足之處，將從數字電路和模擬電路2個方面改進電路的設計方法，把電路系統的容錯性能及穩定性作為后續研究的重點。

參考文獻/References：

[1] KIM K J， CHO S B. Automated synthesis of multiple analog circuits using evolutionary computation for redundancy-based fault-tolerance[J]. Applied Soft Computing， 2012， 12（4）：1309-1321.

[2] YAO X，HIGUICHI T. Promises and challenges of evolvable hardware[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C： Applications and Reviews， 1999， 29（1）：87-97.

[3] 張峻賓， 蔡金燕， 孟亞峰. 面向復雜電磁環境的容錯電路系統設計技術[J]. 西安交通大學學報， 2017， 51（2）：53-59.

ZHANG Junbin， CAI Jinyan， MENG Yafeng. A design technology of fault tolerance circuit systems facing complex electromagnetic environments[J]. Journal of Xian Jiaotong University， 2017， 51（2）：53-59.

[4] ZHANG Meng， HE Jingsong. Vector analysis on the fault-tolerant abilities of combined analog circuit systems[C]// International Congress on Image and Signal Processing， Biomedical Engineering and Informatics.Datong： IEEE， 2017：2020-2025.

[5] 吳會叢， 王曉紅， 宋學軍， 等. 演化硬件（EHW）的研究進展[J]. 河北工業科技， 2007， 24（1）：49-53.

WU Huicong， WANG Xiaohong， SONG Xuejun， et al. Research progress of evolvable hardware（EHW）[J]. Hebei Journal of Industrial Science and Technology， 2007， 24（1）：49-53.

[6] 陳亞洲， 張冬曉， 田慶民， 等. 某型無人機數據鏈系統HEMP輻照效應[J]. 高電壓技術， 2016， 42（3）：959-965.

CHEN Yazhou， ZHANG Dongxiao， TIAN Qingmin， et al. HEMP radiation effects on unmanned aerial vdehicle data link system[J]. High Voltage Engineering， 2016， 42（3）： 959-965.

[7] 張曉芳， 李智， 牛軍浩. 基于演化硬件的多目標進化算法的研究[J]. 微電子學與計算機， 2016， 33（9）：119-123.

ZHANG Xiaofang， LI Zhi， NIU Junhao. Research of multi-objective optimization evolutionary algorithm based on evolvable hardware[J]. Microelectronics & Computer， 2016， 33（9）：119-123.

[8] HUANG Zaisheng， HE Jingsong. An evolutionary design model for reducing the ripple of analog filter[C]//2015 11th International Conference on Natural Computation. Zhangjiajie：IEEE， 2015：1103-1108.

[9] 甄然， 司超， 吳學禮， 等. 基于改進粒子群算法的飛行器沖突解脫方法研究[J]. 河北科技大學學報， 2016， 37（5）：491-496.

ZHEN Ran， SI Chao， WU Xueli， et al. Study of the aircraft conflict resolution method based on modified particle swarm optimization[J]. Journal of Hebei University of Science and Technology， 2016， 37（5）：491-496.

[10]吳會叢， 王金澤， 劉春草， 等. 基于自適應HereBoy算法的電路進化設計實驗研究[J]. 河北科技大學學報， 2015， 36（3）：293-299.

WU Huicong， WANG Jinze， LIU Chuncao， et al. Research of circuit evolution design based on adaptive HereBoy algorithm[J]. Journal of Hebei University of Science and Technology， 2015， 36（3）：293-299.

[11]LIN Chao， HE Jingsong. A novel negative-correlation redundancy evolutionary framework based on stochastic ranking for fault-tolerant design of analog circuit[C]// International Conference in Swarm Intelligence. Berlin：[s.n.]， 2013：556-563.

[12]胡旺， YEN G G， 張鑫. 基于 Pareto 熵的多目標粒子群優化算法[J]. 軟件學報， 2014，25 （5）：1025-1050.

HU Wang， YEN G G， ZHANG Xin. Multiobjective particle swarm optimization based on Pareto entropy[J]. Journal of Software， 2014，25（5）：1025-1050.

[13]JIANG Shouda， ZHAO Jiayu， WEI Changan. Design of multifunctional communication card based on reflective memory[C]// NASA/DoD Conference on Evolvable Hardware. [S.l.]：Springer International Publishing， 2016：139-146.

[14]SHLYAKOV A N， KAMENSKIH A N， MAZUNINA E S. Synthesis of fault-tolerance circuits by genetic algorithms[C]// 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering. Petersburg：IEEE， 2017：339-341.

[15]LIU Mingguo， HE Jingsong. Negatively-correlated redundancy circuits evolution： A novel way of robust analog circuit synthesizing[C]// 2010 Third International Workshop on Advanced Computational Intelligence. Suzhou：IEEE， 2010：496-501.

[16]解雙建， 原亮， 滿夢華，等. 基于演化硬件的容錯電路設計與實現[J]. 計算機測量與控制， 2011， 19（10）：2495-2497.

XIE Shuangjian， YUAN Liang， MAN Menghua， et al. Design and realization of fault-tolerant circuit based on evolvable hardware[J]. Computer Measurement & Control， 2011， 19（10）：2495-2497.

[17]康立山， 何巍， 陳毓屏. 用函數型可編程器件實現演化硬件[J]. 計算機學報， 1999， 22（7）：781-784.

KANG Lishan， HE Wei， CHEN Yuping. Evolvable hardware realized with function type programmable device[J]. Chinese Journal of Computers， 1999， 22（7）：781-784.

[18]ZHANG Yang， SMITH S L， TYRRELL A M. Digital circuit design using intrinsic evolvable hardware[C]// NASA/DoD Conference on Evolvable Hardware. Washington：[s.n.]， 2012：55-62.

[19]高桂軍， 王友仁， 姚睿. 系統異構冗余容錯設計研究[J]. 傳感器與微系統， 2007， 26（10）：25-28.

GAO Guijun， WANG Youren， YAO Rui. Research on redundancy and tolerance of system with different structures[J]. Transducer and Microsystem Technologies， 2007， 26（10）：25-28.

[20]施威， 原亮， 解雙建，等. 基于負相關思想的異構電路冗余技術研究[J]. 微電子學與計算機， 2013，30（6）：71-74.

SHI Wei， YUAN Liang， XIE Shuangjian， et al. Research on selective redundancy of evolved circuits using negative correlation[J]. Microelectronics & Computer， 2013，30（6）：71-74.

[21]李志. 模擬電路負相關演化方法及設計[D]. 合肥：中國科學技術大學， 2013.

LI Zhi. Negatively Correlated Evolutionary Method and Design for Analog Circuits[D]. Hefei：University of Science and Technology of China， 2013.

[22]陳州， 倪明. 三模冗余系統的可靠性與安全性分析[J]. 計算機工程， 2012， 38（14）：239-241.

CHEN Zhou， NI Ming. Reliability and security analysis of triple-module redundancy system[J]. Computer Engineering， 2012， 38（14）：239-241.