1、V ol.15, No.9 ©2004 Journal of Software 軟 件 學 報 1000-9825/2004/15(091345 一種求解極小診斷的遺傳模擬退火算法黃 杰+, 陳 琳, 鄒 鵬(國防科學技術大學 計算機學院, 湖南 長沙 410073 A Compounded Genetic and Simulated Annealing Algorithm for Computing Minimal DiagnosisHUANG Jie+, CHEN Lin, ZOU Peng(School of Computer, National University of D

2、efense Technology, Changsha 410073, ChinaReceived 2004-03-17; Accepted 2004-05-09Huang J, Chen L, Zou P. Computing minimal diagnosis by compounded genetic and simulated annealing algorithm. Journal of Software, 2004,15(9:13451350.Abstract : Model-Based diagnosis is an active branch of Artificial Int

3、elligent. The method is a NP-Hard problem, resolving minimal hitting sets from minimal conflict sets. A compounded genetic and simulated annealing algorithm is put forward by mapping hitting sets problem to 0/1 integer programming problem. After providing the genetic simulated annealing (GSA algorit

4、hm, the efficiency and accuracy of GSA algorithm is tested and compared. The GSA algorithm is not only far more efficient than the traditional one, but also can save 1/3 to 1/2 time than the GA algorithm when the number of conflict sets is more than 35. It can get 98% to 100% minimal diagnosis in mo

5、st conditions.Key words: model-based diagnosis; minimal diagnosis; conflict set; hitting set; genetic algorithm; simulatedannealing摘 要: 基于模型的診斷方法是人工智能領域發展起來的一個十分活躍的分支. 在該方法中, 由極小沖突集求解極小擊中集的過程是一個NP-Hard 問題. 盡管人們提出了不少算法, 但是各種算法的效率仍然不是十分理想. 通過將該問題映射到0/1整數規劃問題, 提出了將遺傳算法與模擬退火算法相結合的問題求解思想. 在給出遺傳模擬退火(genet

6、ic simulated annealing,簡稱GSA 算法和算法各個參數的同時, 對算法的性能和求解精度進行了測試.GSA 算法不僅比傳統的算法效率有很大的提高, 而且在沖突集基數大于35的情況下, 較單獨使用GA 的算法在效率上提高約1/31/2.在求解精度上,GSA 算法在大多數情況下能夠求出98%100%的極小診斷. 關鍵詞: 基于模型的診斷; 極小診斷; 沖突集; 擊中集; 遺傳算法; 模擬退火 Supported by the National Natural Science Foundation of China under Grant No.90104020 (國家自然科學基

7、金; the National High-Tech Research and Development Plan of China under Grant No.2001AA113020 (國家高技術研究發展計劃(863; the National Grand Fundamental Research 973 Program of China under Grant No.G1999032703 (國家重點基礎研究發展規劃(973作者簡介: 黃杰(1976, 男, 陜西西安人, 博士生, 主要研究領域為分布式計算, 故障診斷; 陳琳(1976, 女, 博士生, 主要研究領域為系統管理, 智能診斷

8、; 鄒鵬(1957, 男, 教授, 博士生導師, 主要研究領域為分布式系統, 自主計算.1346Journal of Software 軟件學報 2004,15(9中圖法分類號: TP18 文獻標識碼: A 故障診斷是通過對系統觀察的結果來查找系統可能發生失效構件的過程. 故障診斷得出的可能失效的構件要能夠解釋系統表現出來的癥狀. 失效構件的集合要盡可能地小, 這種診斷結果才有意義. 否則, 假設系統所有的構件失效, 當然可以解釋系統失效時所表現出的所有不一致. 由Reiter 1首先提出的基于模型的診斷技術是一種十分有效的, 并且廣泛應用的故障診斷方法學. 如何以這種診斷方法為基礎, 快速地

9、求解極小診斷一直是人們十分關注的話題. 通常先求出所有的極小沖突集, 再通過極小沖突集求解極小診斷. 但是, 這通常是一個NP-Hard 問題. 文獻1提出了通過為沖突集建立HS-tree 的方法來求解極小診斷. 文獻2通過求解極小沖突集, 并在極小沖突集的限制下給出了另一種優化的求解極小診斷方法. 文獻3給出了求解極小沖突集的邏輯算法, 但是沒有提出自己的極小診斷求解算法. 文獻4通過對模型重新進行描述, 給出了形式化的高效算法. 文獻5提出了通過將系統分割為多個MEC(minimal evaluation chains來求解極小沖突集的思想, 但沒有給出更優化的極小診斷求解算法. 文獻6通

10、過改進HS-tree, 提出了一種BHS-tree 求解診斷的方法. 特別是文獻7,通過使用遺傳算法, 極大地提高了通過沖突集求解極小診斷的時間復雜性和空間復雜性. 它可以在100代內求解出95%的極小診斷, 使得極小診斷的求解時間和空間復雜度大大減少. 本文在改進文獻7中的遺傳算法的基礎上, 提出遺傳算法與模擬退火算法相結合的思想. 遺傳算法把握總體搜索的方向較強, 但是局部搜索能力較差. 而模擬退火算法具有較強的局部搜索能力, 同時又能夠避免搜索過程陷入局部最優解. 將這兩種方法結合可以加快極小診斷的求解過程. 通過將極小診斷問題映射到0/1整數規劃問題, 來預測退火算法的冷卻溫度, 從而

11、將遺傳算法和模擬退火算法結合起來. 在這種算法下, 不僅問題求解速度較文獻7有很大提高, 而且求解精度也有一定的提高. 文章最后給出了相關的算法測試和比較.1 問題描述基于模型的故障診斷的基本思想是, 通過為系統建立一種診斷模型來預測系統的行為(背景知識SD. 如果系統觀測到的行為(OBS與預期的行為不符, 我們就利用已經建立起來的模型和觀測的結果導出候選診斷8. 下面給出基于模型的故障診斷技術的基本概念和思想.定義1. 一個系統被定義為一個序偶SD , COMP . SD 代表系統的邏輯描述, 它是一個一階語句的集合, COMP 是系統中構件的集合.定義2. 關于SD , COMP , OB

12、S 的診斷是一個關于構件的集合COMP , 且SD OBS Ab (c |c ¬Ab (c |c COMP 是協調的, 其中OBS 代表對系統狀態和行為的一次觀察, 它也是一個一階語句的集合. Ab 代表某個構件發生異常.定義3. 是SD , COMP , OBS 的一個極小診斷, 當且僅當關于極小.定義4. CC 是SD , COMP , OBS 的一個沖突集(conflict set,如果CC COMP 且SD OBS Ab (c |c CC 是不協調的. 如果不存在SD , COMP , OBS 的沖突集CC , 使得CC CC 成立, 則稱CC 為極小沖突集.定義5. 設CH

13、 是一個冪集, 對于, 若任意的S CH , H S , 則稱H 為CH 的一個擊中集. 若H 的任意子集都不是CH 的擊中集, 則稱H 為CH 的一個極小擊中集.S CHH U S 定理13. 是SD , COMP , OBS 的一個極小診斷, 當且僅當是SD , COMP , OBS 的所有極小沖突集構成的冪集的極小擊中集.2 極小診斷的遺傳模擬退火算法為了提高從極小沖突集求解極小診斷的效率, 就需要挖掘該問題中更多的約束和更多的背景知識. 文獻9中提出將極小擊中集問題映射到布爾滿足問題和0/1整數規劃問題的思想.首先, 定義一個n 的與系統關聯的0/1矩陣m ×1,1( ij

14、i m j n A a =. 通過這個定義, A 的每一行對應一個子集, 每一列對應一個系統中的構件. 設向量(1,., i A i m =代表矩陣A 的每一行, 1ij a =表示子集i A 包含構件j , 否則表黃杰 等:一種求解極小診斷的遺傳模擬退火算法 1347 示子集i A 不包含構件j . 同樣, 定義一個0/1向量x =(x 1, x 2,x n , 當1j x =時表示構件j 屬于擊中集x , 否則表示構件j 不屬于擊中集.=m i nj 11r m r x i x 1n i ik =定理2. x 是|1. i A i m =的擊中集, 當且僅當T T Ax b , 其中b =

15、(1,1,1m .定義n 上的范數|1,|x |1=. 定義=n j j x 1|m ×n 上的范數|1,|A |1=ij a |. 由定理2不難證明|A |1×|x |1|Ax T |1|b T |1=m (1 由式(1知|x |1m /|A |1 (2不等式(2指出了極小擊中集基數的下限. 這個下限對于我們快速求解極小診斷十分重要. 根據上述分析, 我們給出求解極小診斷的遺傳模擬退火算法.用二值向量代表集合, 則擊中集的染色體編碼為(, 12,., m x x x 的形式, 其中. 下面給出遺傳算法部分的算子.01i x =或交叉算子. 對于染色體(, 12,., m

16、x x x 和, 隨機地選取一個整數12(, ,., m y y y 0r m <, 它們產生的后代為(x 1, x 2,x r , y r +1,y m 和(y 1, y 2,y r , x r +1,x m .變異算子. 對于染色體12(, ,., m x x x , 隨機地選取一個整數0<, 變異后的個體為, 其中.,., ,., (1m rx x x r x =1反轉算子. 染色體12(, ,., m x x x 反轉后的染色體為11(, ,., m m x x x .適應度函數. f (x i =|Ax i |1/|x i |1, 適應度函數( i f x 反映了當個體擊

17、中的沖突集越多和i x 的范數越小時, 它的適應度越強的特性. 不難看出, 這種適應度的評價是符合事實, 并且是合理的.選擇算子. 同時使用最優保存策略和賭輪選擇法10, 從n 個中間群體中選擇適應度最優的1/5個體復制到下一代中. 其余的個體按照1n i i k k P f f=為選取概率被復制到下一代個體中.為了加快搜索速度和增強算法的局部搜索能力, 同時還需要使用模擬退火算法. 將單個個體的能量評估函數被定義為E (x =(|x |1m /|A |1 /f (x . 設初始溫度T 0=|x |1. 同時, 求解過程中的集合基數如果不滿足不等式(2,我們就可以認為退火算法中的溫度達到冷卻狀

18、態.下面給出求解極小診斷的遺傳模擬退火算法.算法1. Genetic simulated annealing (GSA.(1 初始化進化計數器.(2 隨機產生初始群體, 初始規模為m /|A |( P t 1(為大于1的系數.(3 以概率進行個體間的交叉操作:( (t P Crossover t P .(4 以概率進行個體變異操作:( (t P Mutation t P .(5 以概率進行個體反轉操作:( (t P Invertion t P .(6 調用個體模擬退火算法:( (t P nnealing SimulatedA t P .(7 通過f (x i =|Ax i |1/|x i |1

19、評估中個體的適應度.(t P (8 將適應度最優的1/5個體直接復制到下一代中, 按照k P f f =為選取概率選擇其余的個體到下一代中, 產生下一代. (1 P t +(9 若連續10代中包含的擊中集沒有變化, 則判斷這些擊中集是否為極小擊中集并輸出結果. 否則轉(3. 算法2. Simulated annealing (SA.(1 設置初始溫度T 0=|x |1和循環計數器t .0(2 隨機地將向量x 中個為1的位反轉, 其中n 3(log / / (2+=t A m x T n t , 從而產生新個體x .(3 計算能量的增量=E (x E (x , 若0, 則接受新個體, 否則以概率

20、p =exp(E (x E (x /T (x 接受新個體, 如果拒絕新個體, 則轉(2,重新退火.1348 Journal of Software 軟件學報 2004,15(9(4 若新個體的溫度 (/ (min 1x T A m x T =或者t >, 則算法結束, 否則1t t +并轉(2.3 算法說明和分析算法1中使用f (x i =|Ax i |1/|x i |1作為適應度評價函數, 分子|Ax i |1是個體擊中沖突集的數目,|Ax i |1同( i f x 成正比關系, 即在個體包含構件數目一定的情況下,|Ax i |1越大, 說明i x 的適應度越強. 分母|x i |1同

21、( i f x 成反比關系, 反映了在擊中的沖突集一定的情況下, 個體所代表的集合基數越小, 越有可能成為極小集中集的特性. 正確的適應度評價函數使得算法可以準確地把握搜索的方向.在選擇算子設計中, 算法1同時使用了最優保存策略和賭輪選擇法. 最優保存策略使得最好的1/5個體不被淘汰. 對于其余的中間個體采用賭輪選擇法, 這樣的選擇既不丟失最好的中間個體, 同時按比例保留了各個適應度上的個體, 這使得搜索避免陷入局部最優點.盡管算法1具有把握搜索方向好和在一定程度上避免陷入局部最優的特性. 但是無論是交叉算子、變異算子, 還是反轉算子, 都不能使算法快速地向正確的方向收斂. 事實上, 也很難設

22、計出這樣快速收斂的算子. 因為這些算子既不知道搜索的方向, 也不知道以什么樣的速度收斂能夠快速地達到目標, 同時又不丟失太多正確的解.算法1(GSA的第6步使用模擬退火算法使整個算法在搜索粒度上加大. 以溫度的下限1/ (A m x T 為標準, 避免不必要的搜索. 在算法2(SA的第2步, 使用的降溫方式為 3(log / / ( (211+=+t A m x T x t t T . 圖1是這種降溫方式在幾種不同參數下的折線圖. T 0=50, T min =20 T 0=50, T min =10 T 0=50, T min =3Fig.1 Temperature decreasing c

23、urve in variant condition圖1 不同情況下的降溫曲線可以看出, 這種降溫方式使得個體溫度越高降溫越快, 個體溫度越低降溫越慢. 這樣, 越是接近目標, 搜索粒度就越是細化. 通過大量的實驗表明, 在通常情況下, 通過15步的退火過程, 個體的溫度達到或者接近于最低溫 度而基本達到冷卻狀態. 因此, 在實際應用中, 選擇退火的最大步長15=. 算法2以(/ / ( (x f A m x T x E =為函數評估新個體的能量. 這個函數反映了在個體適應度不變情況下, 越是接近最低溫度, 個體的能量就越少, 同時也反映了在個體溫度不變情況下, 適應度越強, 個體能量越低. 為

24、了確保正確的搜索方向, 避免搜索陷入局部最優, 在個體降溫后對其能量進行評估. 若個體的能量減少, 則直接接受這一事實, 這也是我們所期望的. 若能量增加, 則以概率p =exp(E (x E (x /T (x 接受. 如果拒絕能量的增加, 則對個體重新進行退火. 算法要能夠以一定的概率接受能量的暫時增加才能避免搜索陷入局部最優. 圖2是這種降溫方式在實際測試中能量的變化折線圖. 其中, 初始溫度T x 0( 50=, 冷卻溫度為, 沖突集的數目為15,3個個體的能量變化和降溫折線圖如圖2所示. 圖2中實線為能量變化線, 虛線為溫度變化線.min ( 10T x =正如文獻7中指出,HS-tr

25、ee 6的空間復雜度為O m , 其中為沖突集的平均基數, 為系統中的構件總數.BHS-tree ( n m n 6的空間復雜度為. 不難看出, 采用GSA 的空間復雜度為.(2 n O ( O n 采用GSA 算法求解不僅能夠發揮遺傳算法的優勢, 把握正確的搜索方向, 而且可以發揮模擬退火算法快速收斂的優勢. 同時, 模擬退火算法部分的設計還能夠使搜索避免過早地收斂于局部最優狀態. 合理的評估函數以及算法的各個參數設計極大地提高了算法在實際應用中的效果.黃杰 等:一種求解極小診斷的遺傳模擬退火算法1349 Fig.2 Energy and temperature curve of variant individual圖2 不同個體的能量和溫度曲線文獻7中已經將GA 算法與HS-tree 和BHS-tree 等非遺傳算法的