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

黃以鋒 景 博 穆舉國

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

0 引言

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

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

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

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

1 問題描述

1.1 模糊集

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

1.2 整數編碼故障字典

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

1.3 測點優選目標

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

測點選擇的目的是在故障狀態都可隔離的前提下，選擇測點數量最小的測點集Ta。

式中:T為可用測點集;Tk為可隔離所有故障狀態的測試集;|Tk|為測點集Tk中測點的個數。

2 測點選擇方法

2.1 基于熵的測點選擇方法

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

根據信息理論，假設測點tj將故障狀態集F劃分為k個模糊集，則tj提供的關于F的信息量為:

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

定義熵E(j)為:

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

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

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

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

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

①假設要測試的模擬電路的故障狀態集為F0，可用測點集為T0，則初始化節點 F={F0}，可用測點集T={T0}。

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

式中:|xqj|為故障狀態子集xqj中元素的個數。

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

式中:|Tq|為測點集Tq中測點的個數。

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

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

節點Fj的與或樹如圖1所示。

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

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

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

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

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

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

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

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

3 試驗分析

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

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

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

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

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

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

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

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

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

4 結束語

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

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

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

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

［3］汪鵬，楊士元.模擬電路故障診斷測試節點優選新算法［J］.計算機學報，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］.華中科技大學學報:自然科學版，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.