基于多修改點胚胎鍵合圖的模擬電路自動設(shè)計
2009-01-01 00:00:00李少波王娟娟強建寧
計算機應用研究 2009年2期
（貴州大學 省部共建教育部現(xiàn)代制造技術(shù)重點實驗室， 貴陽 550003）
摘 要：采用鍵合圖表示電路系統(tǒng)，研究了基于兩種不同胚胎鍵合圖的模擬電路進化設(shè)計方法。該方法利用遺傳編程開放式拓撲搜索的特點，模擬一組特征值，并用鍵合圖和遺傳編程對該組初始胚胎進行進化，總結(jié)了兩種結(jié)構(gòu)對進化設(shè)計結(jié)果的影響，得出由三個可修改點胚胎進化的電路優(yōu)于由一個可修改點胚胎進化的電路，三個可修改點胚胎進化具有更平衡的結(jié)構(gòu)。最后進化設(shè)計了一個模擬帶阻濾波器，進一步證明了該方法的可行性和有效性。
關(guān)鍵詞：鍵合圖；遺傳編程；自動設(shè)計；開放式設(shè)計；多修改點胚胎；模擬電路
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)02047203
Automated synthesis of analog circuitbased on multimodified site embryo bond graphs
LI Shaobo，WANG Juanjuan，QIANG Jianning
(Key Laboratory of Advanced Manufacturing Technology， Guizhou University， Guiyang 550003， China)
Abstract:
By using bond graph to represent the circuit system，this paper studied the automated synthesis of analog circuit based on two types of embryo bond graphs. Using the openended search of genetic programming， this method simulated a group of eigenvalues， evolved two embryos combining of the bond graphs and genetic programming.Investigated the influence of two structures in automated synthesis， and found the circuit evolved by embryo with three modifiable sites， whose structure was more balanced，was prior to that with one modifiable site. Finally，evolved an analog band stop filter with automated synthesis and proved the feasibility and efficiency of this method.
Key words:bond graph；genetic programming(GP)；automated synthesis；openended design；multimodified site embryo；analog circuit
現(xiàn)今基于遺傳編程（GP）的自動設(shè)計主要集中于模擬電路設(shè)計和控制器設(shè)計。在模擬電路自動設(shè)計方面，以斯坦福大學的Koza教授為首已經(jīng)有大量的相關(guān)研究。在控制器設(shè)計方面，Koza教授已經(jīng)成功進化出具有實際應用水平的控制器[1，2]。Lohn等人為簡化電路生成過程，采用針對格形電路結(jié)構(gòu)的軌跡（trail）編碼，并將三極管作為（第三端固定連接的）雙端元件使用，使運算量顯著減少，但仍需在工作站網(wǎng)絡(luò)上運行[3]。本課題項目組在前期的工作中，通過將機械、電子、控制等部分組成的復雜機電系統(tǒng)的設(shè)計問題映射為模型設(shè)計空間的拓撲結(jié)構(gòu)和參數(shù)的搜索問題，研究了基于遺傳編程的控制方框圖和功率鍵合圖的混合拓撲搜索算法、設(shè)計相關(guān)的遺傳編程的編碼、操作算子以及適應度函數(shù)，初步進行了基于進化遺傳編程和功率鍵合圖、方框圖的機電混合系統(tǒng)仿真的自動設(shè)計系統(tǒng)[4，5]。
采用遺傳編程進行物理系統(tǒng)的建模與自動設(shè)計已經(jīng)有一些成功的例子[4~10]，但其缺陷是拓撲結(jié)構(gòu)的搜索空間具有很大的局限性。本文提出的方法可以用于突破以上方法的局限性，本文研究采用鍵合圖來表示電路系統(tǒng)模型，采用遺傳編程來進行空間搜索設(shè)計。鍵合圖是一種多域的建模工具，用來分析和設(shè)計動力系統(tǒng)，尤其是混合的多域系統(tǒng)，利用鍵合圖開放式設(shè)計探索的一個好處是，在電路中復雜的循環(huán)類型可以轉(zhuǎn)換成為樹狀結(jié)構(gòu)，用鍵合圖的1節(jié)點（串聯(lián)）和0節(jié)點（并聯(lián)）的概念，往往容易演變?yōu)橐话銌栴}。遺傳編程對于開放式的拓撲搜索是一個強大的工具，將這兩種方法結(jié)合起來設(shè)計復雜的電路系統(tǒng)將會得到更好的實現(xiàn)。
1 采用鍵合圖的電路進化設(shè)計
1.1 電路進化設(shè)計的基本方法
電路進化設(shè)計，是將電路的結(jié)構(gòu)和參數(shù)等作為染色體加以編碼，而個體的適應度定義為其行為（即電路的輸入輸出特性）與預期結(jié)果的符合程度，通過進化計算求得滿足功能要求的解。電路進化設(shè)計的流程與進化計算基本相同，編碼方案、進化算法和適應度評估方法是其主要的關(guān)鍵技術(shù)。
在編碼方面，有兩種編碼方法：a）直接編碼。將可重配置器件或系統(tǒng)的配置位串（configuration bit string） 作為染色體進行二進制編碼進化的結(jié)果可直接用于硬件的配置[11]。b）間接編碼。采用抽象的表達方式，將樹或語法等作為染色體，其進化的結(jié)果需經(jīng)過解碼再用于器件或系統(tǒng)的配置。具體采用何種進化算法應視所設(shè)計電路的特點而定，以遺傳算法和遺傳編程最為常用[12]。由于電路進化設(shè)計可以探索較常規(guī)方法更為廣闊的設(shè)計空間，獲得更好的設(shè)計結(jié)果，也無須任何先驗知識，可以做常規(guī)方法難以處理的復雜電路設(shè)計問題，很少需要人工干預，對使用者的要求較低，便于推廣和降低設(shè)計成本等，因而已成為國際性的研究熱點。Koza等人利用GP技術(shù)所做的工作代表了模擬電路進化設(shè)計的現(xiàn)有水平[7]。
1.2 鍵合圖結(jié)構(gòu)
一個典型的GP 系統(tǒng)通常進化樹而不是直接進化圖。鍵合圖通常不是樹，而是包括很多環(huán)路，不能直接將鍵合圖編碼為GP 的染色體。設(shè)計者必須提供胚胎鍵合圖，通過執(zhí)行每一個進化生成的GP 樹，可以對胚胎鍵合圖進行操作形成候選設(shè)計方案。將鍵合圖結(jié)構(gòu)的GP函數(shù)集和終止集定義為有四種類型的函數(shù)：a）Add函數(shù)，只能應用在節(jié)點處，添加C，I，R元件；b）Insert函數(shù)，應用在鍵上，在鍵上插入一個0節(jié)點或一個1節(jié)點；c）Replace函數(shù)，應用于節(jié)點，更改元件的類型或C，I，R元件的相應的參數(shù)值；d）Arithmetic函數(shù)，執(zhí)行算術(shù)運算和用來決定相關(guān)元件的數(shù)值。終止集：endnode，終止當前可修改點的生長。一些典型的操作——add_R（1通口電阻），insert_J0（0節(jié)點），詳細說明如下：
在圖1中，R（或I/C）元件可通過add函數(shù)加到已經(jīng)存在的節(jié)點處。這個函數(shù)用一個連接鍵添加一個節(jié)點。三種元件也可以分別要求附加的參數(shù)值（ERC——暫時的隨機常量），該節(jié)點允許含有其他數(shù)值運算節(jié)點，從而形成數(shù)值計算子樹，通過交叉變異，可以用于給新添加的R（或I/C）提供合適的參數(shù)。Insert_J0函數(shù)只能應用到鍵上，在給定的可修改點處執(zhí)行插入0節(jié)點（圖2），在節(jié)點R和1節(jié)點之間插入一個0節(jié)點將生成一個新的鍵合圖。這樣，在新的鍵合圖中將生成三個新的可修改點。在每一個可修改點處，根據(jù)其類型應用不同的函數(shù)進化。
1.3 結(jié)合鍵合圖和遺傳編程
遺傳編程是遺傳算法的擴展。遺傳編程的一個鮮明的特點是，它可以進化可變長度的開放式的結(jié)構(gòu)，如電腦程序，所以它能廣泛使用于開放式設(shè)計的問題。在進化一個程序樹時，用一個發(fā)育強烈型遺傳編程方法來描述[4]，其先序的執(zhí)行將使一個給定的最小胚胎鍵合圖，生長成為一個復雜的設(shè)計方案。
對于一個用鍵合圖表示的系統(tǒng)，需要明確目標系統(tǒng)的物理“胚胎”模型，這在設(shè)計過程中是不變的。隨之將建立樹的初始種群，將胚胎作為公共的初始點。對于每一棵樹（個體），都進行鍵合圖分析。分析包括因果關(guān)系分析和狀態(tài)方程分析，結(jié)果分配在個體的適應度里。然后評價種群，進行遺傳操作——選擇、交叉、變異、生成的新個體也將被評價，這種鍵合圖分析和遺傳操作反復進行，直到滿足最終的條件。得出最好的鍵合圖將作為物理實現(xiàn)。
由GP樹表示的鍵合圖采用先序的執(zhí)行方式， 通過執(zhí)行圖3所示的GP樹程序，操縱拓撲和參數(shù)的每一步，進化胚胎。一個胚胎鍵合圖通過評價迭代應用、交叉、變異和選擇操作，進化成一個復雜的鍵合圖。鍵合圖GP樹，重要的因素是標記胚胎，函數(shù)集以及可修改點的類型，這些因素都將影響搜索的效率。Add_J_CI_R：添加一個1節(jié)點（若當前的可修改點為0節(jié)點）或者添加一個0節(jié)點（若當前的可修改點為1節(jié)點）到當前可修改點處，左孩子繼承引入的可修改點，右孩子則用添加節(jié)點作為新的可修改點。一般地，0節(jié)點附上一個電阻和一個電容，1節(jié)點附上一個電阻和一個電感，形成因果關(guān)系適定的初始變量。
2 算法設(shè)計及對比分析
2.1 算法描述及流程
下面以兩種類型的胚胎鍵合圖模型作為初始的生長點，如圖4所示。其中：（a）表示帶有一個可修改點的胚胎鍵合圖；（b）表示帶有三個可修改點的胚胎鍵合圖。每個用矩形盒子框起來的節(jié)點表示初始的可修改點，胚胎中固定的元件允許定義系統(tǒng)的輸入與輸出，評價其特征值（由狀態(tài)空間方程得出）產(chǎn)生一個系統(tǒng)。在GP樹中執(zhí)行這些點，明確構(gòu)造的步驟。
整體算法的流程如圖5所示。給定一個鍵合圖模型，它的適應度評價按下列步驟進行：
a）從鍵合圖模型中得到狀態(tài)空間模型的矩陣A；
b）計算出矩陣A的特征值；
c）比較計算結(jié)果的特征值與目標特征值，根據(jù)程序1的設(shè)定，計算相對距離測量誤差。
在0~1，按照以下衡量規(guī)則，通過規(guī)范測量誤差計算鍵合圖的適應度值。
if distance/order <0.1 then
fitness = 0.1 /(0.1+distance/order)
else fitness = 5.05 /(10+distance/order)
其中， order是儲能元件的值（電容器和電感器）。
程序1 計算兩套特征值之間的距離
輸入：目標特征值集合(xti，yti)，i=1，…，Ot。其中Ot是目標特征值的數(shù)目。
候選特征值集合(xi，yi)，i=1，…，Oc。其中Oc是候選特征值的數(shù)目。
輸出：在兩個特征值集合之間計算相關(guān)的距離。
如果候選集Oc不同于目標集合Ot，則返回∞；
否則計算目標特征值的平均距離lave，lave=Oti=1li，li是所有的不匹配目標特征值標簽ith的長度， distance← 0
for i=1 to Ot
找一個不匹配的候選特征值j，它是最接近目標特征值i的值，將其（候選特征值j）標記為匹配的
distance←distance+(xj-xti)2+(yj-yti)2/lave
其中：(xj，yj)是候選特征值；(xti，yti)是當前目標特征值i。
end for
return distance
2.2 實驗分析
以典型的4特征值問題為例，其目標特征值為-1+2i，-1-2i，-2+i，-2i。由上面介紹的兩種初始胚胎進化。
GP參數(shù)如下所示：
代數(shù)——500；種群大小——2 500；最大深度——17；選擇概率——Tournament(size=7)；交叉概率——0.9；變異概率——0.1。
由一個可修改點的初始胚胎模型進化的鍵合圖模型如圖6所示，一個1節(jié)點和六個元件（兩組C，I，R）被加到圖4（a）進化方法的胚胎鍵合圖模型中，總結(jié)了這種解決方案和目標的平均距離差，結(jié)構(gòu)和參數(shù)的信息。相對應地，在另外一組運行中，由三個可修改點的初始胚胎圖4 （b）進化得出的拓撲結(jié)構(gòu)，如圖7所示。兩個C元件、兩個I元件和一個R元件由1節(jié)點和0節(jié)點進化得出，這個結(jié)果不同于一個可修改點的胚胎進化的結(jié)果，結(jié)構(gòu)相對簡單，顯得更平穩(wěn)一些，然而，胚胎的形式和GP算子的設(shè)計在自動設(shè)計的過程中影響都非常大。
從鍵合圖對應的電路圖以及其對應的幅頻特性和相頻特性分析，得出以下結(jié)論：由以上兩種方式生成的電路圖，根據(jù)其幅頻特性和相頻特性曲線所示，圖8對應的電路在帶阻范圍內(nèi)，衰減至500 mV（沒有達到0），其相頻特性也不夠平坦，存在相移；而圖9對應的電路在帶阻范圍內(nèi)其幅度衰減至0，帶阻效果較好，在帶通范圍內(nèi)相頻特性也較好。由此看來，由三個可修改點胚胎的進化得出的電路要優(yōu)于由一個可修改點胚胎進化得出的電路，其具有更平衡的結(jié)構(gòu)，采用多種用鍵合圖表示的拓撲形式在滿足特定的設(shè)計目標時是可行的。
2.3 設(shè)計實例
模擬8組特征值問題：
1+1i，-1+1i，-2+3i，2+10i，-5+3i，5+3i，-12+4i，12+4i，采用上述的算法設(shè)計思想，以三個可修改點的初始胚胎開始進化，驗證一個帶阻濾波器，GP參數(shù)如下：
代數(shù)——1 000；種群大小——1 000；最大深度——17；選擇概率——Tournament(size=7)；交叉概率——0.4；變異概率——0.05。
其進化設(shè)計的鍵合圖以及對應的電路圖如圖10所示。由此設(shè)計的電路元件數(shù)、鍵數(shù)、節(jié)點數(shù)相對較小，冗余度也比較低，由幅頻特性和相頻特性曲線得出，在帶通范圍內(nèi)，相移和幅值基本為1，相移為0，帶阻中心點幅值為0，曲線下降率較大，此帶阻濾波器進化效果較好。另外，根據(jù)多次實驗統(tǒng)計，由三個可修改點胚胎進化設(shè)計時，電容器和電感器是成對進化的。
3 結(jié)束語
本文結(jié)合遺傳編程和鍵合圖，利用遺傳編程開方式設(shè)計的特點，研究了兩種可修改點胚胎鍵合圖進化設(shè)計電路的方法，總結(jié)得出由三個可修改點胚胎進化的電路要優(yōu)于由一個可修改點胚胎進化的電路，三個可修改點胚胎進化具有更平衡的結(jié)構(gòu)。胚胎的形式和GP算子的使用對自動設(shè)計的形式都會造成很大的影響。然而，在生成設(shè)計的過程中，為了滿足特定的設(shè)計目標，并維持其良好的拓撲特性，對進化過程的關(guān)注是非常有必要的。實驗證明，遺傳編程搜索的可能性在自動設(shè)計方法中是真正可行的?；谶z傳編程的鍵合圖開放式的結(jié)構(gòu)搜索，為模擬電路的自動設(shè)計提供了新的方法，也為傳統(tǒng)的動態(tài)系統(tǒng)的創(chuàng)新設(shè)計提供了新的思路與方法。
參考文獻：
［1］
KOZA J R，BENNETT I I I，F(xiàn)ORREST H，et al.Automatic design of analog electrical circuits using genetic programming[C]//CARTWRIGHT，HUGH.Proc of Intelligent Data Analysis in Science. Oxford: Oxford University Press，2000:172202.
[2]KOZA J R，KEANE M A，YU J，et al.Automatic creation ofhumancompetitive programs and controllers by means of genetic programming[J].Genetic Programming and Evolvable Machines，2000(12)：121164.
[3]LOHN J D，COLOMBANO S P.A circuit representation technique for automated circuit design[J]．IEEE Trans on Evolutionary Computation，1999，3(3)：205219.
[4]李少波，胡建軍.基于遺傳編程（GP）與鍵合圖的機電系統(tǒng)自動設(shè)計[J].系統(tǒng)仿真學報，2002（11）:15131516.
[5]LI Shaobo，CHEN Xi，HU Jianjun.Sustainable HFC genetic algorithms based with adaptive migration structure[C]//Proc of IEEE International Conference on Wireless Communications， Networking and Mobile Computing.2007:653657.
[6]LI Shaobo，HU Jianjun.Evolving vibration absorbers based on gene-tic programming and bond graphs[C]//Proc of International Confe-rence on Computational Intelligence and Security.[S.l.]:IEEE Press，2006:202207.
[7]KOZA J R，BENNETT F H，ANDRE D，et al.Automated synthesis of analog electrical circuits by means of genetic programming[J].IEEE Trans on Evolutionary Computation，1997，1(2):109128.
[8]CHEN Yuehui，YANG Bo， ABRAHAM A.Flexible neural trees ensemble for stock index modeling[J].Neurocomputing，2007，70(46):697703.
[9]TAY E，F(xiàn)LOWERS W，BARRUS J.Automated generation and analysis of dynamic system designs[J].Research in Engineering Design，1998(10):1529.
[10]ABRAHAM A，JAIN R，THOMAS J，et al.DSCIDS:distributed soft computing intrusion detection system[J].Journal of Network and Computer Applications，2007，30(1):8198.
[11]趙曙光.可編程邏輯器件原理、開發(fā)及應用[M].西安：西安電子科技大學出版社，2000.
[12]YAO X，HIGUICHI T.Promises and challenges of evolvable hardware[J].IEEE Trans on Systems Man and Cybernetics—Part C: Applications and Reviews，1999，29(1):8797.
