遺傳模擬退火算法

1、V ol.15, No.9 ©2004 Journal of Software 軟 件 學(xué) 報(bào) 1000-9825/2004/15(091345 一種求解極小診斷的遺傳模擬退火算法黃 杰+, 陳 琳, 鄒 鵬(國(guó)防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院, 湖南 長(zhǎng)沙 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摘 要: 基于模型的診斷方法是人工智能領(lǐng)域發(fā)展起來(lái)的一個(gè)十分活躍的分支. 在該方法中, 由極小沖突集求解極小擊中集的過(guò)程是一個(gè)NP-Hard 問(wèn)題. 盡管人們提出了不少算法, 但是各種算法的效率仍然不是十分理想. 通過(guò)將該問(wèn)題映射到0/1整數(shù)規(guī)劃問(wèn)題, 提出了將遺傳算法與模擬退火算法相結(jié)合的問(wèn)題求解思想. 在給出遺傳模擬退火(genet

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

7、金; the National High-Tech Research and Development Plan of China under Grant No.2001AA113020 (國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863; the National Grand Fundamental Research 973 Program of China under Grant No.G1999032703 (國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973作者簡(jiǎn)介: 黃杰(1976, 男, 陜西西安人, 博士生, 主要研究領(lǐng)域?yàn)榉植际接?jì)算, 故障診斷; 陳琳(1976, 女, 博士生, 主要研究領(lǐng)域?yàn)橄到y(tǒng)管理, 智能診斷

8、; 鄒鵬(1957, 男, 教授, 博士生導(dǎo)師, 主要研究領(lǐng)域?yàn)榉植际较到y(tǒng), 自主計(jì)算.1346Journal of Software 軟件學(xué)報(bào) 2004,15(9中圖法分類號(hào): TP18 文獻(xiàn)標(biāo)識(shí)碼: A 故障診斷是通過(guò)對(duì)系統(tǒng)觀察的結(jié)果來(lái)查找系統(tǒng)可能發(fā)生失效構(gòu)件的過(guò)程. 故障診斷得出的可能失效的構(gòu)件要能夠解釋系統(tǒng)表現(xiàn)出來(lái)的癥狀. 失效構(gòu)件的集合要盡可能地小, 這種診斷結(jié)果才有意義. 否則, 假設(shè)系統(tǒng)所有的構(gòu)件失效, 當(dāng)然可以解釋系統(tǒng)失效時(shí)所表現(xiàn)出的所有不一致. 由Reiter 1首先提出的基于模型的診斷技術(shù)是一種十分有效的, 并且廣泛應(yīng)用的故障診斷方法學(xué). 如何以這種診斷方法為基礎(chǔ), 快速地

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

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

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

12、S 的診斷是一個(gè)關(guān)于構(gòu)件的集合COMP , 且SD OBS Ab (c |c ¬Ab (c |c COMP 是協(xié)調(diào)的, 其中OBS 代表對(duì)系統(tǒng)狀態(tài)和行為的一次觀察, 它也是一個(gè)一階語(yǔ)句的集合. Ab 代表某個(gè)構(gòu)件發(fā)生異常.定義3. 是SD , COMP , OBS 的一個(gè)極小診斷, 當(dāng)且僅當(dāng)關(guān)于極小.定義4. CC 是SD , COMP , OBS 的一個(gè)沖突集(conflict set,如果CC COMP 且SD OBS Ab (c |c CC 是不協(xié)調(diào)的. 如果不存在SD , COMP , OBS 的沖突集CC , 使得CC CC 成立, 則稱CC 為極小沖突集.定義5. 設(shè)CH

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

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

15、(1,1,1m .定義n 上的范數(shù)|1,|x |1=. 定義=n j j x 1|m ×n 上的范數(shù)|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指出了極小擊中集基數(shù)的下限. 這個(gè)下限對(duì)于我們快速求解極小診斷十分重要. 根據(jù)上述分析, 我們給出求解極小診斷的遺傳模擬退火算法.用二值向量代表集合, 則擊中集的染色體編碼為(, 12,., m x x x 的形式, 其中. 下面給出遺傳算法部分的算子.01i x =或交叉算子. 對(duì)于染色體(, 12,., m

16、x x x 和, 隨機(jī)地選取一個(gè)整數(shù)12(, ,., m y y y 0r m <, 它們產(chǎn)生的后代為(x 1, x 2,x r , y r +1,y m 和(y 1, y 2,y r , x r +1,x m .變異算子. 對(duì)于染色體12(, ,., m x x x , 隨機(jī)地選取一個(gè)整數(shù)0<, 變異后的個(gè)體為, 其中.,., ,., (1m rx x x r x =1反轉(zhuǎn)算子. 染色體12(, ,., m x x x 反轉(zhuǎn)后的染色體為11(, ,., m m x x x .適應(yīng)度函數(shù). f (x i =|Ax i |1/|x i |1, 適應(yīng)度函數(shù)( i f x 反映了當(dāng)個(gè)體擊

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

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

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

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

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

22、計(jì)出這樣快速收斂的算子. 因?yàn)檫@些算子既不知道搜索的方向, 也不知道以什么樣的速度收斂能夠快速地達(dá)到目標(biāo), 同時(shí)又不丟失太多正確的解.算法1(GSA的第6步使用模擬退火算法使整個(gè)算法在搜索粒度上加大. 以溫度的下限1/ (A m x T 為標(biāo)準(zhǔn), 避免不必要的搜索. 在算法2(SA的第2步, 使用的降溫方式為 3(log / / ( (211+=+t A m x T x t t T . 圖1是這種降溫方式在幾種不同參數(shù)下的折線圖. 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 不同情況下的降溫曲線可以看出, 這種降溫方式使得個(gè)體溫度越高降溫越快, 個(gè)體溫度越低降溫越慢. 這樣, 越是接近目標(biāo), 搜索粒度就越是細(xì)化. 通過(guò)大量的實(shí)驗(yàn)表明, 在通常情況下, 通過(guò)15步的退火過(guò)程, 個(gè)體的溫度達(dá)到或者接近于最低溫 度而基本達(dá)到冷卻狀態(tài). 因此, 在實(shí)際應(yīng)用中, 選擇退火的最大步長(zhǎng)15=. 算法2以(/ / ( (x f A m x T x E =為函數(shù)評(píng)估新個(gè)體的能量. 這個(gè)函數(shù)反映了在個(gè)體適應(yīng)度不變情況下, 越是接近最低溫度, 個(gè)體的能量就越少, 同時(shí)也反映了在個(gè)體溫度不變情況下, 適應(yīng)度越強(qiáng), 個(gè)體能量越低. 為

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

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