基于Rollout算法的模擬電路測點選擇

黃以鋒 景 博 穆舉國

(空軍工程大學(xué)工程學(xué)院1，陜西 西安 710038;空軍駐西安地區(qū)軍事代表局2，陜西 西安 710077)

0 引言

測點選擇問題是模擬電路故障診斷和可測性設(shè)計過程中的一個關(guān)鍵問題，得到了國內(nèi)外學(xué)者的廣泛關(guān)注。孫秀斌［1］、胡梅［2］、汪鵬［3］等人分別提出了采用可測性測度和故障隔離度等方法進行測點選擇。故障字典法是一種重要的模擬電路故障診斷方法。

在故障字典法中，測點的選擇是一個非常重要的環(huán)節(jié)，其目的是在故障都可隔離的前提下，選擇測點數(shù)量最小的測點集。最小測點集問題已被證明是NP-hard問題［4］，隨著模擬電路復(fù)雜度的提高，求取全局最優(yōu)解將遇到計算爆炸問題。

目前，人們在局部最優(yōu)算法的研究方面已有不少成果。Prasad［4］等提出了三種包含法和一種排除法;Starzyk［5］等提出了一種基于信息熵的方法;Yang［6］等在信息熵理論的基礎(chǔ)上提出了基于啟發(fā)式圖搜索的方法;Golonek［7］、Zhang［8－9］等使用現(xiàn)代優(yōu)化算法求取模擬電路的最小測點集。

Rollout算法是Bertsekas提出的一種用于組合優(yōu)化問題的計算方法，并已被應(yīng)用于隨機調(diào)度和順序測試等領(lǐng)域［10］。本文采用Rollout算法來解決模擬電路的測點選擇問題。在整數(shù)編碼故障字典的基礎(chǔ)上，以信息熵算法為基礎(chǔ)算法［5］，采用Rollout算法構(gòu)建了一種新的測點選擇算法。理論分析和仿真試驗表明，該算法的計算效果優(yōu)于信息熵算法。

1 問題描述

1.1 模糊集

由于模擬電路中的元件存在容差，在電路正常狀態(tài)下和各種故障狀態(tài)下，測點的電壓不是一個確定的值，而是一個連續(xù)的小區(qū)間。這些小區(qū)間可能重疊，使該測點無法區(qū)分重疊的多個狀態(tài)。為解決這個問題，可根據(jù)各個狀態(tài)的測點電壓區(qū)間，將電壓分為若干個模糊域;測點電壓區(qū)間落入某個模糊域的所有故障狀態(tài)(包括正常狀態(tài))組成一個模糊集，然后依次用整數(shù)對模糊集進行編碼。

1.2 整數(shù)編碼故障字典

對所有測點的模糊集進行劃分、編碼后，可根據(jù)故障狀態(tài)、測點和模糊集間的關(guān)系建立整數(shù)編碼故障字典，其中F={f0，f1，…，fm}為故障狀態(tài)集(包括正常狀態(tài))，T={t1，t2，…，tn}為可用測點集，dij為模糊集的整數(shù)編碼。

1.3 測點優(yōu)選目標(biāo)

在故障字典中，若故障狀態(tài)fa和fb分別屬于測點tj的不同模糊集，則fa和fb可被測點tj隔離。若任意兩個故障狀態(tài)都可被某個測點隔離，則故障狀態(tài)都可隔離。

測點選擇的目的是在故障狀態(tài)都可隔離的前提下，選擇測點數(shù)量最小的測點集Ta。

式中:T為可用測點集;Tk為可隔離所有故障狀態(tài)的測試集;|Tk|為測點集Tk中測點的個數(shù)。

2 測點選擇方法

2.1 基于熵的測點選擇方法

基于信息熵的測點選擇方法，根據(jù)測點提供的信息量越大越有利于故障隔離的原理，不斷選擇信息量最大的測點組成優(yōu)化的測試集，直至所有的故障都被隔離［5］。

根據(jù)信息理論，假設(shè)測點tj將故障狀態(tài)集F劃分為k個模糊集，則tj提供的關(guān)于F的信息量為:

式中:f為要隔離的所有故障狀態(tài)的個數(shù);Fij為測點tj的模糊集中編碼為i的模糊集包含的元素個數(shù)。

定義熵E(j)為:

顯然，選擇信息量最大的測點等價于選擇熵E(j)最小的測點。

信息熵算法計算的大致過程是首先用所有可用測點將故障狀態(tài)集F劃分為多個模糊集，用式(3)分別計算各個測點的熵，選擇熵最小的測點tj;然后更新tj劃分的各個子集的可用測點集和故障狀態(tài)集，再用式(3)計算各個子集，選擇熵最小的測點;不斷循環(huán)計算，直至所有故障狀態(tài)都被隔離。

2.2 基于Rollout算法的測點選擇方法

Rollout算法是建立在另一種算法基礎(chǔ)上的一種一步前向回溯算法。該算法不是一種最優(yōu)算法，但其計算效果較基礎(chǔ)算法好。

采用Rollout算法選擇模擬電路測點的具體步驟如下。

①假設(shè)要測試的模擬電路的故障狀態(tài)集為F0，可用測點集為T0，則初始化節(jié)點 F={F0}，可用測點集T={T0}。

②首先用測點集T中的每個測點tq將節(jié)點F中的所有故障狀態(tài)集分別劃分為多個子集，所有包含元素大于1個的子集組成節(jié)點Fq，對節(jié)點Fq中的所有子集xqj，用信息熵算法計算對應(yīng)的優(yōu)化測點集Tqj;然后用式(4)計算節(jié)點Fq的優(yōu)化測點集Tq。

式中:|xqj|為故障狀態(tài)子集xqj中元素的個數(shù)。

③比較測點集T中每個測點對應(yīng)的優(yōu)化測點集中測點的個數(shù)，按照式(5)，選擇最小測點集對應(yīng)的測點。若有多個最小測點集，則選擇其中序號最小的測點ta。

式中:|Tq|為測點集Tq中測點的個數(shù)。

④將測點ta加入到測點集Tmin。比較ta對應(yīng)的節(jié)點Fa，若節(jié)點Fa為空集，計算結(jié)束，Tmin就是優(yōu)化后的最小測試集;否則，定義節(jié)點F=Fq，T為原測點集刪除測點ta后的測點集，重復(fù)步驟②～④。

在Rollout算法的計算過程中，每前進一步，都用信息熵算法進行試探并選擇最優(yōu)的結(jié)果，不難分析出，Rollout算法的計算結(jié)果優(yōu)于信息熵算法。

節(jié)點Fj的與或樹如圖1所示。

圖1 節(jié)點Fj的與或樹Fig.1 The AND/OR tree of node Fj

圖1中，F(xiàn)j為樹的任意一個可擴展節(jié)點。對于節(jié)點Fj，信息熵算法和Rollout算法都能計算出一個優(yōu)化測試點。假設(shè)ti為信息熵算法計算出的優(yōu)化測試點，Ti為節(jié)點Fi對應(yīng)的測點集，ta為Rollout算法計算出的優(yōu)化測試點，Ta為節(jié)點 Fa對應(yīng)的測點集。在Rollout算法中，需要用信息熵算法作試探性的前向搜索，如假設(shè)選擇了一個測試點ti，然后用信息熵算法計算出測點集Fi，得到優(yōu)化測點集中測點的數(shù)量。同理，可計算出若選擇其他測點將得到的優(yōu)化測點集中測點的數(shù)量，選擇數(shù)量最小測點的ta。所以選擇測點ta，將得到的優(yōu)化測點集中測點的個數(shù)一定會小于或等于選擇測點ti，即:

下面用兩個實例來說明Rollout算法的詳細計算過程。

實例1來自于文獻［4］的例1，該電路共有9個故障狀態(tài)和4個可用測點。用Rollout算法計算實例1的具體過程如圖2所示，其中虛線的橢圓表示節(jié)點，實線的橢圓表示狀態(tài)集，長方形的方框表示選擇相應(yīng)測點后計算出的優(yōu)化測點集，0、1、2、3表示選擇相應(yīng)測點后計算出的優(yōu)化測點集中測點的個數(shù)。采用Rollout算法的計算步驟如下。

首先進行初始化，初始時，節(jié)點F中只有一個故障狀態(tài)集 F0={f0，f1，…，f8}，可用測點集 T={t1，t2，t3，t4};然后用4個測點展開節(jié)點F中的狀態(tài)集，得到4個子節(jié)點，并用式(4)計算各子節(jié)點的優(yōu)化測點集，由于測點t4對應(yīng)的優(yōu)化測點集{t1，t2}最小，測點t4被選中;最后將測點t4加入測點集Tmin，更新F和T，重復(fù)第②步到第④步，直至計算結(jié)束。最終得到優(yōu)化測點集Tmin={t4，t1，t2}。若用信息熵算法進行計算，得到的優(yōu)化測試集為{t1，t2，t3，t4}。

圖2 實例1的計算結(jié)果Fig.2 The computing result of example 1

實例2來自于文獻［4］的例5，該電路共有19個故障狀態(tài)和11個可用測點。電路圖和電路的整數(shù)編碼故障字典詳見文獻［4］。圖3展示了實例2的計算過程。從圖3可以看出，在節(jié)點的展開過程中，依次選擇了測點 t11、t1、t5和 t9，優(yōu)化測試集為{t1，t5，t9，t11}，與信息熵算法的計算結(jié)果一致。

圖3 實例2的計算結(jié)果Fig.3 The computing result of example 2

3 試驗分析

為了比較算法的計算效果，在英特爾雙核處理器E2140、內(nèi)存 1 GB 和 Windows XP，Matlab7.1環(huán)境下，編寫了信息熵算法和Rollout算法的Matlab程序。

隨機生成1～10個具有100個故障狀態(tài)、40個測點和6個模糊集的故障字典，然后分別用信息熵算法和Rollout算法計算這10個故障字典的優(yōu)化測點集。在采用Rollout算法計算得出的優(yōu)化測點集中，測點數(shù)量最多為5個，而信息熵算法得出的測點數(shù)量最少為10個。因此，Rollout算法的計算效果明顯優(yōu)于信息熵算法。在計算時間方面，信息熵算法用時不到0.1 s，Rollout算法也僅需3 s。

為了說明故障狀態(tài)、可用測點集和模糊集對兩種算法計算效果的影響，進行了以下3組試驗。3組試驗結(jié)果如圖4所示。

圖4 不同情況下的計算結(jié)果Fig.4 The computing results under different cases

①隨機產(chǎn)生8個故障狀態(tài)為100個、可用測點為40個、模糊集分別為3～10的故障字典，分別用信息熵算法和Rollout算法計算出優(yōu)化測點集，求得優(yōu)化測點集中測點的個數(shù)，從而得到測點個數(shù)與模糊集個數(shù)之間的關(guān)系曲線。為了更準確地描述它們之間的關(guān)系，重復(fù)計算5組故障字典，得到測點個數(shù)的平均值與模糊集個數(shù)之間的關(guān)系曲線如圖4(a)所示。

②隨機產(chǎn)生5組故障字典，每組故障字典由12個故障字典組成。這12個故障字典的故障狀態(tài)都為100個，模糊集都為6個，可用測點個數(shù)分別為20個、25個、…、75個。分別用信息熵算法和Rollout算法計算出優(yōu)化測點集，求得優(yōu)化測點集中測點個數(shù)的平均值，得到該平均值與可用測點個數(shù)之間的關(guān)系曲線如圖4(b)所示。

③隨機產(chǎn)生5組故障字典，每組故障字典由9個故障字典組成。這9個故障字典的測點個數(shù)都為40個，模糊集都為6個，故障狀態(tài)個數(shù)分別為30個、45個、…、150個。分別用信息熵算法和Rollout算法計算出優(yōu)化測點集，求得優(yōu)化測點集中測點個數(shù)的平均值，得到該平均值與故障狀態(tài)的個數(shù)之間的關(guān)系曲線如圖4(c)所示。

以上3組試驗結(jié)果表明，Rollout算法計算出的測點個數(shù)都小于信息熵算法，且Rollout算法的曲線較平滑，說明計算結(jié)果較穩(wěn)定。

另外，從圖4(a)可以看出，隨著模糊集數(shù)量的增加，Rollout算法的優(yōu)化測點數(shù)量有明顯減少的趨勢，信息熵算法不明顯，這說明隨著模糊集數(shù)量的增加，Rollout算法的優(yōu)勢更突出。從圖4(b)可以看出，隨著可用測點數(shù)量的增加，Rollout算法的優(yōu)化測點數(shù)量有減少的趨勢，而信息熵算法不明顯，這說明隨著可用測點數(shù)量的增加，Rollout算法的優(yōu)勢在擴大。在圖4(c)中，信息熵算法的曲線上升的速度明顯大于Rollout算法，說明隨著故障狀態(tài)數(shù)量的增加，Rollout算法的優(yōu)勢更明顯。

4 結(jié)束語

故障字典法是模擬電路的一種常用的故障診斷方法，測點選擇是該方法中的一個重要環(huán)節(jié)，其目的是在故障都可隔離的前提下，選擇測點數(shù)量最小的測點集。本文針對最小測點集問題，在整數(shù)編碼故障字典和信息熵算法的基礎(chǔ)上建立了基于Rollout算法的測點選擇方法，給出了算法的詳細計算步驟，并通過實例展示了算法的詳細計算過程。

本文通過理論分析，證明了Rollout算法的計算效果優(yōu)于信息熵算法。試驗結(jié)果也表明Rollout算法的計算效果優(yōu)于信息熵算法，而且隨著故障字典復(fù)雜度的提高，優(yōu)勢更加明顯。本文提出的方法計算效果較好、計算時間短，可用于復(fù)雜模擬電路的測點選擇，同時對模擬電路的可測性設(shè)計也具有一定的參考價值。

［1］孫秀斌，陳光禑，謝永樂.模擬集成電路的測試節(jié)點選擇［J］.電子信息學(xué)報，2004，26(4):645 －650.

［2］胡梅，王紅，楊士元，等.模擬電路軟故障診斷測試節(jié)點優(yōu)選的仿真研究［J］.系統(tǒng)仿真學(xué)報，2009，21(12):3837 －3841.

［3］汪鵬，楊士元.模擬電路故障診斷測試節(jié)點優(yōu)選新算法［J］.計算機學(xué)報，2006，29(10):1781 －1785.

［4］Prasad V C，Badu N S C.Selection of test nodes for analog fault diagnosis in dictionary approach［J］.IEEE Transactions on Instrumentation and Measurement，2000，49(6):1289 －1297.

［5］Starzyk J A，Liu D，Liu Z H，et al.Entropy-based optimum test points selection for analog fault dictionary techniques［J］.IEEE Transactions on Instrumentation and Measurement，2004，53(3):754 －761.

［6］Yang Chenglin，Tian Shulin，Long Bing.Application of heuristic graph search to test-points selection for analog fault dictionary techniques［J］.IEEE Transactions on Instrumentation and Measurement，2009，58(7):2145－ 2158.

［7］Golonek T，Rutkowski J.Genetic-algorithm-based method for optimal analog test points selection ［J］.IEEE Transactions on Circuits and Systems II:Express Briefs，2007，54(2):117 －121.

［8］Zhang Chaojie，He Guo，Liang Shuhai.Test point selection of analog circuits based on fuzzy theory and ant colony algorithm［C］∥IEEE AUTOTESTCON 2008，Salt Lake City，2008.

［9］張超杰，賀國，梁述海，等.基于改進粒子群算法的模擬電路測試點選擇［J］.華中科技大學(xué)學(xué)報:自然科學(xué)版，2009，37(11):31 －34.

［10］Tu F，Pattipati K R.Rollout strategy for sequential fault diagnosis［J］.IEEE Transactions on Systems，Man and Cybernetics-Part A:Systems and Humans，2003，33(1):86 －99.