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

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

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

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

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

1 電路拓?fù)浜涂勺冮L圖編碼

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

1.1 電路結(jié)構(gòu)的拓?fù)鋱D表示

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

圖1 電路結(jié)構(gòu)的封閉無向拓?fù)鋱D

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

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

1.2 圖編碼方法

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

表1 演化電路元件編碼

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

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

1)當(dāng)指令為1(connecting-two-nodes)且節(jié)點(diǎn)為1和2時(shí)，在節(jié)點(diǎn)1和節(jié)點(diǎn)2之間插入一個(gè)電感元件作為新邊；

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

3)新插入的節(jié)點(diǎn)將節(jié)點(diǎn)1和節(jié)點(diǎn)2對(duì)應(yīng)的邊拆分兩個(gè)新邊，其中節(jié)點(diǎn)1和節(jié)點(diǎn)3所在邊對(duì)應(yīng)了原有的電感元件，而節(jié)點(diǎn)3和節(jié)點(diǎn)2所在邊對(duì)應(yīng)了新插入的一個(gè)電感元件；

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

2 可變長圖編碼演化算法

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

圖3 可變長演化圖編碼的電路設(shè)計(jì)流程

2.1 種群初始化

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

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

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

2.2 適應(yīng)度評(píng)估

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

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

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

(1)

2.3 電路圖編碼交叉算子

不同電路拓?fù)渲邪碾娐饭?jié)點(diǎn)數(shù)量往往是不同的，傳統(tǒng)的單/多點(diǎn)交叉算子無法保證在交叉生成的新個(gè)體仍然為合法電路。圖編碼交叉算子使用兩個(gè)電路個(gè)體中所擁有的公共節(jié)點(diǎn)作為分割點(diǎn)，分別對(duì)電路個(gè)體編碼進(jìn)行交叉位置計(jì)算，并將個(gè)體截?cái)酁閮刹糠?，使得前一部分編碼不會(huì)包含公共節(jié)點(diǎn)以外的電路節(jié)點(diǎn)，從而保證了交叉之后的新個(gè)體仍然是有效的封閉電路。電路圖編碼交叉算子實(shí)現(xiàn)流程如下。

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

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

③隨機(jī)選擇一個(gè)小于Nc的節(jié)點(diǎn)編號(hào)作為交叉開始節(jié)點(diǎn)Ns。

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

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

2.4 多策略變異

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

①對(duì)于5個(gè)指令編碼位，分別獨(dú)立設(shè)置每個(gè)位置的突變概率Pmi，i∈[1-5]。

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

③變異結(jié)束后，對(duì)發(fā)生突變的值進(jìn)行合理性檢驗(yàn)，確保突變后編碼能夠生成有效電路結(jié)構(gòu)。

3 在電子設(shè)計(jì)自動(dòng)化中的應(yīng)用實(shí)例

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

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

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

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

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

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

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

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

4 結(jié)語

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