黃以鋒 景 博 穆舉國(guó)

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

0 引言

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

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

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

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

1 問(wèn)題描述

1.1 模糊集

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

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

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

1.3 測(cè)點(diǎn)優(yōu)選目標(biāo)

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

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

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

2 測(cè)點(diǎn)選擇方法

2.1 基于熵的測(cè)點(diǎn)選擇方法

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

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

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

定義熵E(j)為:

顯然，選擇信息量最大的測(cè)點(diǎn)等價(jià)于選擇熵E(j)最小的測(cè)點(diǎn)。

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

2.2 基于Rollout算法的測(cè)點(diǎn)選擇方法

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

采用Rollout算法選擇模擬電路測(cè)點(diǎn)的具體步驟如下。

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

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

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

③比較測(cè)點(diǎn)集T中每個(gè)測(cè)點(diǎn)對(duì)應(yīng)的優(yōu)化測(cè)點(diǎn)集中測(cè)點(diǎn)的個(gè)數(shù)，按照式(5)，選擇最小測(cè)點(diǎn)集對(duì)應(yīng)的測(cè)點(diǎn)。若有多個(gè)最小測(cè)點(diǎn)集，則選擇其中序號(hào)最小的測(cè)點(diǎn)ta。

式中:|Tq|為測(cè)點(diǎn)集Tq中測(cè)點(diǎn)的個(gè)數(shù)。

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

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

節(jié)點(diǎn)Fj的與或樹(shù)如圖1所示。

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

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

下面用兩個(gè)實(shí)例來(lái)說(shuō)明Rollout算法的詳細(xì)計(jì)算過(guò)程。

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

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

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

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

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

3 試驗(yàn)分析

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

［3］汪鵬，楊士元.模擬電路故障診斷測(cè)試節(jié)點(diǎn)優(yōu)選新算法［J］.計(jì)算機(jī)學(xué)報(bào)，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］張超杰，賀國(guó)，梁述海，等.基于改進(jìn)粒子群算法的模擬電路測(cè)試點(diǎn)選擇［J］.華中科技大學(xué)學(xué)報(bào):自然科學(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.