可變長圖編碼的電路演化設計方法

周勤 尹玲 張斐 李文浩 宋業(yè)明 李耘

(1.東莞理工學院 計算機科學與技術學院，廣東東莞 523808；2.東莞理工學院 機械工程學院，廣東東莞 523808；3.電子科技大學(深圳)高等研究院 人工智能工業(yè)創(chuàng)新研究中心，廣東深圳 518110)

利用先進的電子設計自動化(electronic design automation，EDA)工具，可以方便地進行集成數(shù)字電路的設計。然而，模擬電路設計仍然受到缺乏自動設計工具的困擾，許多模擬電路模塊，即使是小規(guī)模的，仍然需要有經(jīng)驗的專家在傳統(tǒng)方法下進行設計[1]。因此，如何在有限的資源下設計出最優(yōu)的模擬電路已成為越來越重要的問題。模擬電路演化是電子信息硬件演化領域中重要的一環(huán)，是為了解決傳統(tǒng)方法難以處理的復雜功能電路需求而提出的。近來，谷歌的研究人員證明，通過使用人工智能(AI)技術，可以在一天甚至數(shù)個小時內(nèi)完成過去需要幾個星期的電路自動設計過程[2]。

常見的模擬電路自動化方案是使用進化算法對電路結構、元器件類型和元器件值進行優(yōu)化，從而得到更為高效的電路模型[3]。Sussman[4]于1975年提出使用啟發(fā)式檢驗方法來處理復雜的直流偏置電路分析問題。Koza等人[5]提出利用電路構建程序樹來對電路結構進行表征，但他們沒有考慮電路結構的封閉性，從而產(chǎn)生了大量不可正確仿真的非法電路。Goh等人[6]根據(jù)節(jié)點、類型、元器件值三部分直接對電路進行編碼，該方法編碼雖然簡單易于實現(xiàn)、可表示拓撲結構范圍廣，但編碼過程沒有對非法電路拓撲進行處理，因此仍然會產(chǎn)生大量非法電路，浪費電路仿真時間。Lohn等人[7]利用軌跡(trail)編碼對電路節(jié)點進行約束，雖然避免了非法電路的產(chǎn)生，但同時也降低了可表示電路拓撲的范圍。何勁松等人[8]利用圖的生成過程來表征電路構建過程，提出了圖編碼方式，該編碼方式在保證電路拓撲合法的情況下，盡可能多地保留了可表示電路拓撲的范圍。但其所采用的簡單遺傳算法無法直接對不同編碼長度的電路個體直接進行交叉操作，且無法避免交叉過程中非法電路的產(chǎn)生。

基于上述分析，本文提出了一種可變長圖編碼的電路演化方法，能夠?qū)Σ煌幋a長度的電路進行表示和演化，確保交叉操作所新產(chǎn)生的電路個體仍然是有效電路，并且通過設計不同的變異概率和變異策略，實現(xiàn)對電路宏觀結構和元器件參數(shù)進行同步優(yōu)化，進一步加快演化算法的收斂速度。

1 電路拓撲和可變長圖編碼

在電路分析中，研究者們通常以圖論為指導來設計電路結構圖，當忽略元件的值時，幾乎所有的電路結構都可以用無向圖來表示[9]。本節(jié)將基于圖編碼[8]的方式來描述電路結構在圖論中的對應表現(xiàn)形式，并詳細介紹如何以生成閉合無向圖的方式產(chǎn)生可用電路編碼，其中電路編碼包含了電路拓撲結構、元器件類型和參數(shù)信息，演化算法通過對編碼進行選擇、交叉、變異等操作來實現(xiàn)電路的自動化設計。

1.1 電路結構的拓撲圖表示

本小節(jié)將描述電路結構在封閉無向圖中的表示，以及如何創(chuàng)建從簡單到復雜的結構圖，并通過一定的策略來保持圖的封閉性。在電路圖論中，任何電路都可以用元器件和導線來表示，在忽略電路元件的情況下，電路結構圖可以被映射成一個特殊的無向圖，其中電路中的節(jié)點和導線分別與圖論的頂點和邊對應，圖中兩個頂點之間的任何一條邊都代表構成實際電路的一個元件，對應關系如圖1所示。

圖1 電路結構的封閉無向拓撲圖

由于電路中出現(xiàn)串聯(lián)的情況是較為頻繁的，所以在電路圖的表示中允許兩點之間存在多條邊。此外，為了保持電路結構的封閉性，生成圖中的每個節(jié)點必須連通不少于兩個分量，且保證在規(guī)則電路中不存在懸浮節(jié)點，因此在映射的特殊無向圖中頂點的度不能小于2。一般來說，電路中元器件的數(shù)量不超過節(jié)點數(shù)的5倍，對于邊數(shù)較少的圖，使用鄰接表進行存儲能夠節(jié)約更多的存儲空間。本文所使用的圖編碼采用鄰接表來對電路結構圖進行存儲，有利于降低演化算法的編碼長度和計算復雜度。

文獻[8]設計了兩種圖編碼方法的編碼指令，分別對應電路設計中常用的串聯(lián)和并聯(lián)操作。第一條指令是connecting-two-nodes，用來選擇兩個已有的節(jié)點并用新邊連接，對應于電路設計的并聯(lián)操作，其中新產(chǎn)生的邊對應了新插入的一個電路元件。另一個是inserting-new-node指令，用來在兩個已有節(jié)點之間插入一個新節(jié)點，新節(jié)點將原有節(jié)點對應的邊拆分為兩個新邊，對應于電路設計中的串聯(lián)操作，其中一條新邊對應原有的電路元件，另一條新邊對應新插入的電路元件。在執(zhí)行inserting-new-node命令之前，應該檢查被選擇的兩個節(jié)點之間是否存在邊，確保在創(chuàng)建新節(jié)點之前，被插入節(jié)點之間至少存在一條邊，否則插入新的節(jié)點時會破壞圖的封閉性。

1.2 圖編碼方法

可變長圖編碼方法使用一組操作指令實現(xiàn)對電路元件的修改，通過使用多組操作指令實現(xiàn)對完整電路的表示，且電路中元件數(shù)量和操作指令數(shù)量呈正相關。操作指令是一個由指令、節(jié)點1、節(jié)點2、元器件類型和元器件參數(shù)組成的五位實數(shù)編碼，每個編碼位置的解釋如表1所示。第一個編碼位置表示為1(connecting-two-nodes)或2(inserting-new-node)的兩種操作指令中的其中一種。第二和第三個編碼位置分別表示兩個互不相同的候選節(jié)點，且候選節(jié)點編碼來自于生成圖中已經(jīng)存在的節(jié)點集中。在電路初始階段，節(jié)點集中只有0和1，分別代表地端和電源端。第四個位置代表三種基本元件類型之一，其值為1(電阻)，2(電容)或3(電感)。最后的位置代表電子元器件在E24系列標準組件庫中的索引值，對于不同的元器件類型，其索引范圍是不同的。

表1 演化電路元件編碼

大部分電路都可以通過上述的電路編碼來完成表示，例如圖2所示。該初始電路由僅包含電壓源和負載電阻的電路模板構成，其中包含的節(jié)點有輸入節(jié)點1、輸出節(jié)點2和接地節(jié)點0。一個從電源到負載之間功能電路的生成過程如下例所示：

圖2 用圖指令方法在電源與負載之間生成功能電路的圖過程

1)當指令為1(connecting-two-nodes)且節(jié)點為1和2時，在節(jié)點1和節(jié)點2之間插入一個電感元件作為新邊；

2)其次，對于2(inserting-new-node)指令，在完成節(jié)點之間邊的存在性檢查后，創(chuàng)建一個新的節(jié)點3插入到節(jié)點1和節(jié)點2之間；

3)新插入的節(jié)點將節(jié)點1和節(jié)點2對應的邊拆分兩個新邊，其中節(jié)點1和節(jié)點3所在邊對應了原有的電感元件，而節(jié)點3和節(jié)點2所在邊對應了新插入的一個電感元件；

4)最后，執(zhí)行指令1，在節(jié)點3和節(jié)點0之間插入一個電容。

2 可變長圖編碼演化算法

演化算法是電路自動進化設計的重要組成部分，本文提出的可變長圖編碼演化算法是基于標準遺傳算法[10]進行設計的。算法的潛在解由多組操作指令組成的圖編碼進行表示，通過評估潛在解的適應度，然后對潛在解進行選擇、可變長圖編碼交叉、多策略變異等操作得到更優(yōu)解，其算法流程如圖3所示。下文將對圖中主要模塊進行詳細介紹。

圖3 可變長演化圖編碼的電路設計流程

2.1 種群初始化

在圖編碼方法中，一組操作指令對應一個額外元器件的產(chǎn)生，為了靈活地對含有不同元器件數(shù)量的電路拓撲進行表示，本文使用不定長度的基因編碼串來代表一個具體的電路拓撲。與固定長度編碼相比，不定長度編碼具有編碼靈活、內(nèi)存開銷更小、計算更簡單等優(yōu)點。為了保證演化過程中電路結構是有效的個體，在初始化階段對電路結構進行一定的約束，確保隨機產(chǎn)生的結構為合法個體。種群初始化步驟描述如下。

③重復1.2過程，直到元器件數(shù)量等于Nsum。

④重復以上過程K次，最終得到一個規(guī)模為K的種群。

2.2 適應度評估

適應度是描述描述個體性能的主要指標，演化算法可以根據(jù)適應度的大小對個體進行優(yōu)勝劣汰的選擇[11]。圖編碼描述了電路拓撲生成過程，通過執(zhí)行圖編碼指令能夠?qū)€體編碼轉(zhuǎn)換為對應的實際電路，并以網(wǎng)表文件格式[12]進行保存。網(wǎng)表文件是一種描述電路連接關系和元器件參數(shù)的文本文件，能夠在SPICE電路仿真軟件(如：Pspice，Hspice和LTspcie等)中進行模擬仿真，得到電路幅頻響應結果，從而進行電路適應度值計算。適應度評估步驟如下所示。

①根據(jù)第1節(jié)所述的圖編碼方式對電路個體編碼進行解碼，得到包含電路信息的網(wǎng)表文件。

②調(diào)用SPICE電路仿真軟件對網(wǎng)表文件中所含包含的電路進行仿真評估，得到生成濾波器產(chǎn)生的幅頻響應H(jω)。

(1)

2.3 電路圖編碼交叉算子

不同電路拓撲中包含的電路節(jié)點數(shù)量往往是不同的，傳統(tǒng)的單/多點交叉算子無法保證在交叉生成的新個體仍然為合法電路。圖編碼交叉算子使用兩個電路個體中所擁有的公共節(jié)點作為分割點，分別對電路個體編碼進行交叉位置計算，并將個體截斷為兩部分，使得前一部分編碼不會包含公共節(jié)點以外的電路節(jié)點，從而保證了交叉之后的新個體仍然是有效的封閉電路。電路圖編碼交叉算子實現(xiàn)流程如下。

①根據(jù)交叉概率Pc隨機選擇兩個電路編碼進行交叉。

②計算被交叉電路編碼A與B最大公共節(jié)點數(shù)Nc(例如A的最大節(jié)點數(shù)量為10，B為8，那么A與B的最大公共節(jié)點數(shù)Nc=8)。

③隨機選擇一個小于Nc的節(jié)點編號作為交叉開始節(jié)點Ns。

④以Ns在編碼中的第一次出現(xiàn)為界，將編碼分為p1A和p2A兩部分。

⑤通過交叉重組拆分后的編碼形成兩個新的個體newA={p1A,p2B}，newB={p1B,p2A}。

2.4 多策略變異

本文針對編碼位置設計了不同的變異概率以及變異操作，實現(xiàn)結構和元器件參數(shù)的同步優(yōu)化,并采用最優(yōu)精英保留策略，來加快算法收斂速度。

①對于5個指令編碼位，分別獨立設置每個位置的突變概率Pmi，i∈[1-5]。

②當指令類型位發(fā)生突變時，其值由1變?yōu)?或者由2變?yōu)?；當節(jié)點位置編碼發(fā)生突變時，隨機從節(jié)點集Q中選擇一個新的節(jié)點對變異位置編碼進行替換，且新節(jié)點應不同于指令中的另一節(jié)點；當元器件類型發(fā)生突變時，隨機產(chǎn)生新的元器件類型和元器件參數(shù)；當元器件參數(shù)位置編碼發(fā)生突變，隨機從E24標準元器件庫中選擇一個元器件值索引。

③變異結束后，對發(fā)生突變的值進行合理性檢驗，確保突變后編碼能夠生成有效電路結構。

3 在電子設計自動化中的應用實例

鑒于低通無源濾波器是電路設計中最典型的電路之一，本文通過設計一個負載電容為2.2 μF的RC低通無源濾波器，來對提出的方法進行可行性驗證。實驗所使用的所有元器件都是二端元件，且已經(jīng)存在于LTspice元件庫中，元件參數(shù)參考E24系列標準元件。在實驗中，最大電阻數(shù)和電容數(shù)都設置為25，即程序允許的總元器件數(shù)量最大為50，所設計的濾波器最高階數(shù)為25，理想截止頻率設置為1 000 Hz。針對此截止頻率的設計要求，電路的適應度函數(shù)如上文提到的公式(1)所示。

實驗在Matlab軟件中對電路編碼進行演化和解碼，將解碼之后的電路信息保存為可被仿真軟件識別的網(wǎng)表文件；然后使用LTspice工具對網(wǎng)表文件表示的電路進行仿真評估；最后，該工具將仿真結果返回到Matlab中進行電路對適應度值的計算和進一步的演化。演化過程中，交叉策略的概率設置為0.6，本算法使用[0.1，0.15，0.15，0.2，0.3]的列表來表示不同編碼位置的變異策概率，最大迭代數(shù)設置為200，種群大小設置為100。為了驗證本文提出的方法在電路演化設計中的有效性，實驗采用文獻[8]所使用的簡單遺傳算法作為對照，除簡單遺傳算法的交叉概率設置為0.2以外，其他實驗參數(shù)完全一致。演化過程中的適應度收斂情況如圖4所示。

圖4 最優(yōu)個體適應度變化圖

表2顯示了算法和簡單遺傳算法的對比結果。簡單遺傳算法要求電路個體編碼長度必須一致，因此在初始化時必須對編碼長度較短的個體進行補齊，雖然操作固定長度的編碼更加方便，但其引入了非必要的電路編碼，需要耗費更大的存儲空間。而本文提出所采用的不定長度編碼無需額外的處理，所需存儲空間更小。簡單遺傳算法所使用的交叉算子為隨機單點交叉，其過程雖然簡單快捷，但在執(zhí)行過程中產(chǎn)生了840個無法進行仿真計算的非法電路。文本提出的可變長圖編碼交叉操作，雖然操作更加復雜，但保證了每一個新個體都是有效的電路結構，避免了無效仿真的計算開銷。多策略變異算子能夠同時對電路宏觀結構和元器件參數(shù)進行優(yōu)化，增強了個體變異能力，和單點變異相比，操作更加復雜，參數(shù)調(diào)整更加困難。從仿真時間上可以看出，雖然本文提出的演化算法更加復雜，計算操作更多，但由于程序的主要耗費時間是電路仿真時間，且總的仿真電路數(shù)量相同，因此總的程序執(zhí)行時間差距較小。從表2可以看出雖然兩種方法都能收斂到相近的適應度值，但本文提出的方法僅需18次迭代便可收斂，而簡單遺傳算法則需要81次迭代，這說明本文提出的算法能夠極大地加快電路演化的收斂速度。

表2 可變長圖編碼演化算法和簡單遺傳算法對比

圖5顯示了所生成的最佳低通濾波器電路拓撲圖，圖6顯示了它的幅頻響應結果。從該結果來看，通過可變長圖編碼的演化算法得到的低通濾波器，只需使用5個電容和5個電阻，就能很好地滿足設計要求。在圖5中，低通濾波電路的原理圖是一個簡單的電路原理圖，其元件的數(shù)量滿足元件最大數(shù)目的限制，而且無需進行5個一階RC電路的串聯(lián)或并聯(lián)，使電路的印制或集成方便有效。

圖5 可變長圖編碼的遺傳算法生成的最優(yōu)低通濾波器電路

圖6 生成最優(yōu)濾波器的幅頻響應曲線圖

4 結語

針對不同電路個體的編碼長度不一、常規(guī)優(yōu)化容易產(chǎn)生非法電路結構的問題，提出了一種基于遺傳算法改進的可變長圖編碼演化算法，設計了一種可用于不同編碼長度的交叉操作，并保證了交叉所產(chǎn)生的新個體仍然是有效的電路結構。同時針對不同編碼位置設計了多種變異概率和變異策略，來實現(xiàn)電路宏觀結構和元器件參數(shù)的同步優(yōu)化。最后，通過低通濾波器的演化設計實驗，驗證了該算法的有效性和實用性。結果表明，本文提出的方法能夠很好的解決電路自動化設計過程中易產(chǎn)生非法電路個體的問題，避免無效電路仿真帶來的時間和資源浪費，極大地加快了電路演化收斂速度。