再生基因演算法RGA.PPT

應用基因演算法設定狀態機的最佳狀態字串之研究 指導教授：黃世演 學生：廖士權 大綱 緒論 在數位邏輯設計中，如何指定合適的位元字串代表狀態機的狀態設計以化簡電路是個重要的課題。 Amaral 利用基因演算法(GA)來解決此設計最佳化問題。 以Huang提出的DGA、RDGA來改良我們基因演算法的架構 。 適存函數(1/6) 基於狀態關聯性之適存函數：其他學者提出應用於基因演算法之適存函數 基於布林方程式之適存函數：本文提出所改進之適存函數 適存函數(2/6) -基於狀態關聯性之適存函數 加拿大學者Amaral 提出 Desired Adjacency Graph (DAG) 來描述狀態之間的關連性，並提出適存函數如下： Amaral的適存函數僅考慮前後狀態的相關性。 狀態位元字串於電路設計時的邏輯相鄰性更重要。 卡諾圖化簡： 當把指定的狀態位元字串整理成積項之和(SOP, sum of product)的布林方程式形式後，會得到數組(由位元字串長度決定)布林方程式 ，在此我們稱這些布林方程式的集合為 。 基因演算法(1/5) 基因演算法流程圖： 在基因演算法的研究中，Huang使用差異度基因演算法（Diversity Genetic Algorithm，簡稱為DGA）與再生基因演算法（Reviving Genetic Algorithm，簡稱RGA）來改良基因演算法的架構，而RGA又與DGA合併稱為RDGA（Reviving and Diversity Genetic Algorithm）。 差異度基因演算法(DGA) : 自然界中，避免近親交配的情況，以降低遺傳性疾病的機率。 Huang提出Diversity Genetic Algorithm以避免演算法在收斂的過程中不斷地與相似基因組作交配，而提早落入區域最佳解的情況發生。 計算個體間的漢明距離(Hammin distance)。 再生基因演算法(RGA) : Huang根據個體適存能力的不同，而調整其突變率。本文依據RGA理論，將交配後的子代依下列三項規則分成較優、較差、中等三群： 較優的個體群：當子代的適存度平均值高於父代時，取總人口數（父代加子代）前百分之二十中的子代個體為最優秀的個體，並保留其基因組不做突變運算。 較差的個體群：若子代的適存度低於親代適存度平均值者，列為較差勁的個體，並將突變率提高到0.1。 其餘的個體稱為中等，突變率為0.05。 再生與差異度基因演算法(RDGA) : 我們將DGA結合上述的RGA分類，整理成下列六項基因演算法的RDGA演化步驟 ： 設定初始群體個數為n個，亂數產生n組不重複之位元字串為個體。 透過輪盤法加上DGA來挑選個體，成為等待交配運算之對象。 執行交配運算。 執行突變運算，透過RGA方式調整突變率，以產生新的子代 。 計算子代與親代的適存度，並做擇優汰劣，保留下最好的n個個體至下一個世代。 判斷收斂與否，若收歛即停止疊代，否則回到步驟二。 為了驗證Amaral的適存函數是否足以反應電路複雜度，本文分析Amaral所舉範例，列出所有狀態位元字串的設計，並依次比對每一組設計。Amaral所舉的狀態機有五個狀態變化、1 input, 1 output，如圖3所示，本文稱為SM-1。 由排列計算定理可知在m個相異物件中，從中任意取出s個物件加以排列組合，其排列數量為公式(9)。 圖3範例有五種狀態、三個位元(23=8)，故有6720種排列組合。 本文採用圖3的SM-1範例以及ACM/SIGDA benchmarks中的shiftreg、train11、tav、lion9、donfile五種狀態機(其中shiftreg與train11狀態表圖示如圖5、圖6)比較Huang所提出的各種基因演算法（DGA，RDGA）和傳統基因演算法（TGA）的效能。 結論與未來展望 Amaral的適存函數無法反應電路的複雜度。 表1,表2說明了Huang的DGA、RDGA對於狀態機設計的最佳解尋找能力沒有明顯改進，但是在複雜度較高的狀態機設計中，收斂速度能有不錯的表現，最高能提高近五成的收斂效率。 未來可以加入模糊(FUZZY)理論於基因演算法中，以便在物種演化的過程中隨時調整演算法的交配率與突變率。 * 緒論 1 適存函數 2 基因演算法 3 實驗結果 4 結論與未來展望 5 其中 c 是輸入條件的數量， v 是輸出變數的數量，s 是狀態數, Ri 是常數 (1) (2) 適存函數(3/6) -基於狀態關聯性之適存函數 圖 1. 卡諾圖化簡流程 適存函數(4/6) -基於布林方程式之適存函數 適存函數(5/6) -基於布林