[發明專利]一種固定極性Reed-Muller邏輯電路極性搜索方法

有效

• 申請號: 201710539610.2
• 申請日: 2017-07-04
• 公開（公告）號: CN107330201B
• 公開（公告）日: 2020-09-18
• 發明（設計）人: 肖利民;何振學;李明哲;霍志勝
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F30/327
• 分類號: G06F30/327
• 代理公司: 北京金恒聯合知識產權代理事務所 11324
• 代理人: 李強

本發明提供的一種FPRM邏輯電路極性搜索方法，利用新的二進制差分進化算法來搜索FPRM邏輯電路的最佳極性，與基于遺傳算法的FPRM邏輯電路極性搜索方法相比，增強了逃脫局部最優和避免早熟的能力，提高了收斂速度和極性搜索的效率。包括以下步驟：1讀取Boolean邏輯電路；2輸入進化參數；3隨機生成初始種群，其中，極性被編碼為二進制個體；4執行改進的二進制隨機變異操作；5執行二項交叉操作；6獲得目標個體及其試驗個體的FPRM表達式；7計算目標個體及其試驗個體的適應度值；8執行貪婪選擇操作和精英保留策略；9若當前進化代數小于最大進化代數，則順序執行步驟4至步驟8；否則輸出最佳極性。

技術領域

本發明涉及Reed-Muller邏輯電路極性優化領域，尤其涉及一種基于新的二進制差分進化算法的固定極性Reed-Muller邏輯電路極性搜索方法。

背景技術

邏輯電路既可以用基于AND/OR/NOT運算的Boolean邏輯表示，也可以用基于AND/XOR或OR/XNOR運算的Reed-Muller(RM)邏輯表示。對于諸如算術電路、奇偶校驗電路和通信電路等電路而言，與用Boolean邏輯表示相比，RM邏輯表示在功耗、面積和速度等方面具有較大的優勢。固定極性RM(Fixed Polarity RM,FPRM)表達式是一種較為流行的標準RM表達式。對于一個n變量的邏輯函數來說，它具有2ⁿ個不同極性的FPRM表達式。極性直接決定FPRM表達式的繁簡，進而影響電路的性能。因此，如何在可接受的時間范圍內，從巨大的極性優化空間中搜索出對應某一電路性能最優的最佳極性，已成為FPRM邏輯電路優化領域的研究熱點。

遺傳算法是一種基于生物進化理論和遺傳學機理的概率搜索算法，因其具有實現簡單、魯棒性高、擴展性好等特點，使得它在FPRM邏輯電路極性優化領域得到了廣泛應用。然而，遺傳算法存在以下缺陷：

(1)遺傳算法自身的選擇操作使種群的方差和熵朝著減小的方向進化，從而降低了種群的多樣性；

(2)遺傳算法本質上是一種隨機搜索優化算法，當問題規模較大或問題較為復雜時，造成搜索空間急劇增大。此外，群體分散性和收斂性互相矛盾，造成收斂速度較慢；

(3)當種群中的個體適應度差別不大時，子代種群中的新個體也相差不大，使得搜索過程無法有效進行，基于適應度的選擇機制趨向于純粹的隨機選擇，從而陷入局部最優。

由于受遺傳算法自身缺陷的影響，使得基于遺傳算法的FPRM邏輯電路極性搜索方法存在種群多樣性差、收斂速度慢、易陷入局部最優等問題，難以滿足中大規模FPRM邏輯電路快速、有效搜索最佳極性的需要。因此，亟需研究一種能快速收斂至全局最優解的極性搜索方法。

差分進化算法是一種新興的進化計算技術，已成為進化算法的一個重要分支。它利用兩個以上父代個體的差分矢量線性組合生成新一代個體，進而將更多的父代信息遺傳給下一代。與遺傳算法相比，差分進化算法具有受控參數少、簡單易用和收斂速度快等優點。然而，傳統差分進化算法主要用于求解連續變量的全局優化問題，無法求解像FPRM邏輯電路極性搜索這樣的離散二進制編碼組合優化問題。

發明內容

為解決上述問題，本發明提供了一種FPRM邏輯電路極性搜索方法。本方法利用一種新的二進制差分進化算法來搜索FPRM邏輯電路的最佳極性，增強了逃脫局部最優和避免早熟的能力，提高了收斂速度和極性搜索的效率。

具體來說，本發明提供了一種FPRM邏輯電路極性搜索方法，該方法包括：

步驟1，讀取Boolean邏輯電路；

步驟2，輸入進化參數；

步驟3，隨機生成初始種群，其中，極性被編碼為二進制個體；

步驟4，執行改進的二進制隨機變異操作；

步驟5，執行二項交叉操作；