基于遺傳算法解決多故障診斷問題

張舒

（西北工業(yè)大學(xué) 陜西 西安 710072）

遺傳算法的設(shè)計(jì)靈感來自于大自然的進(jìn)化現(xiàn)象。遺傳算法通常用來在優(yōu)化問題或分類問題中提供有效的、具有較大搜索空間的搜索機(jī)制。遺傳算法運(yùn)行的基本模式是，對一個(gè)由個(gè)體組成的種群，對每個(gè)個(gè)體進(jìn)行評價(jià)，然后根據(jù)他們的適應(yīng)度數(shù)值選擇能夠存活到下一代的個(gè)體，該選擇過程具有隨機(jī)性。然后，像在大自然中的進(jìn)化一樣，適應(yīng)度較高的個(gè)體具有更高的存活率，也具有更大的幾率進(jìn)行個(gè)體的交叉和變異以產(chǎn)生新一代的種群。在經(jīng)過連續(xù)數(shù)代進(jìn)化直至種群中最佳個(gè)體的適應(yīng)度不再提高時(shí)，這個(gè)最佳個(gè)體很有可能就是我們要尋求的問題的最優(yōu)解[1]。

1 多故障診斷問題的背景

醫(yī)學(xué)中的多故障診斷問題（Multiple Fault Diagnosis，MFD）的目的是根據(jù)病人的一系列病狀來診斷出一系列病因。本文采用的數(shù)學(xué)模型是“基于概率的因果模型（Probabilistic Causal Model，PCM）”[2]。在PCM中，多故障診斷問題被歸結(jié)為一個(gè)四元空間，其中，

*D是一個(gè)代表一系列病因的有限非空集合

*M是一個(gè)代表一些列病狀的有限非空集合

*C是一個(gè)代表一個(gè)關(guān)系的集，它是D×M的一個(gè)子集。這個(gè)關(guān)系將病因與癥狀關(guān)聯(lián)起來，用符號表示出來，即C中的（d，m），表示病因d可以引起癥狀m。

*M+是M的子集，它包含了所有顯現(xiàn)出來的癥狀（即從病人身上可以觀察到的癥狀）。需要加以說明的是，不屬于集合M+的癥狀被認(rèn)為是病人身上不具有的。

另外，一個(gè)DI是一個(gè)“診斷”，它是D的一個(gè)子集，代表引起集合M+中所有癥狀的所有可能的病因。DI的這個(gè)定義使它可以被表示成一個(gè)字位串，其中的每一位表示一種病因，當(dāng)該位為1時(shí)表示該病因在診斷中存在，當(dāng)該位為0時(shí)表示該病因在診斷中不成立。當(dāng)癥狀集合M+中的每一個(gè)癥狀都與病因集合DI中的至少一個(gè)病因有一個(gè)關(guān)聯(lián)C時(shí)，我們稱DI“覆蓋”M+。同M+一樣，不屬于集合DI中的病因被認(rèn)為是在診斷中不成立的。

L（DI，M+）代表相對可能性，它由3個(gè)參數(shù)的乘積而決定，即 L1L2L3，其中：

L1是DI集合中的病因引起M+中的癥狀的可能性。當(dāng)一個(gè)診斷中不能包含M+內(nèi)所有的癥狀時(shí)（即“非包含癥狀”），其L1的值為0，因此L值也為0。不幸的是，因此這個(gè)機(jī)制也否定了接下來對該非包含癥狀的討論。

為了允許遺傳算法能對非包含癥狀進(jìn)行對比和討論，我們對相對可能性做了一個(gè)微小的變化，從而使非包含癥狀有確切的適應(yīng)度數(shù)值，而非一律為零。這個(gè)微小的變化就是將因果系數(shù)cij設(shè)定為在數(shù)值上與0或者1極為相近 （比如0.000 001或者 0.999 999），而非為0或者為1。

如式（2）所示，L2是DI中的病因沒有引起M+之外的病狀的可能性，即集合M-M+中的病狀。L2是基于與DI中所有病因相關(guān)聯(lián)的病狀在病人身上確實(shí)存在的系數(shù)值。

L3是一個(gè)概率，它代表存在某個(gè)概率非常大（即非常常見）的病因dj在一個(gè)包含它的集合DI中起到異常大的作用的可能性。

2 遺傳算法在MFD問題中的實(shí)現(xiàn)

在本MFD問題研究中，共有10中病狀與25中可能的病因，因此對210=1 024種可能的病狀組合，共有225=33 554 432種可能的病因組合。本文中只考慮1 023種病狀組合，而忽略所有病狀都不存在的那種情況。因此，對于遺傳算法的個(gè)體表示，我們用一個(gè)10位的字位串來表示一個(gè)診斷，其中的每一位都表示一種病因。如前文所述，每一位為0或者1時(shí)分別代表該對應(yīng)病因在診斷中存在或者不存在。表1中列出了本系列實(shí)驗(yàn)中遺傳算法參數(shù)的設(shè)置。

表1 遺傳算法參數(shù)設(shè)置Tab.1 Experiment set up for the GA

在上述的兩種選擇機(jī)制中，具有較高適應(yīng)度值的個(gè)體具有更高的概率被選中來產(chǎn)生下一代個(gè)體。在賭盤選擇機(jī)制中，每個(gè)個(gè)體被選中的概率與它的適應(yīng)度數(shù)值成正比[3]，如同現(xiàn)實(shí)中的賭盤一樣，每一個(gè)區(qū)域被選中的比例與其在整個(gè)賭盤所占的面積成正比。同時(shí)，在競爭選擇中，根據(jù)競爭規(guī)模大小隨機(jī)選擇若干個(gè)體進(jìn)行適應(yīng)度值比較，勝出者將被選中作為父母來產(chǎn)生下一代個(gè)體。

遺傳算法中最重要的操作符之一是交叉操作，與現(xiàn)實(shí)進(jìn)化中的兩性交叉相對應(yīng)。交叉操作最主要的兩個(gè)屬性是交叉類型與交叉概率。本項(xiàng)研究中主要探索了兩類交叉操作，即一點(diǎn)交叉與兩點(diǎn)交叉。一點(diǎn)交叉在兩個(gè)作為父母的個(gè)體的同一位置選中一點(diǎn)，將點(diǎn)的同一邊的基因段進(jìn)行一次個(gè)體間互換，產(chǎn)生的兩個(gè)新的個(gè)體作為子代來代替父母個(gè)體。兩點(diǎn)交叉相當(dāng)于將同樣一對個(gè)體進(jìn)行兩次一點(diǎn)交叉操作，即將兩個(gè)個(gè)體中分別找到對應(yīng)的兩個(gè)點(diǎn)（即一共4個(gè)點(diǎn)），將兩點(diǎn)之間的對應(yīng)基因段在兩個(gè)個(gè)體間互換，從而產(chǎn)生兩個(gè)新的個(gè)體作為子代[4]。

最優(yōu)保留機(jī)制的原則是在子代種群中找到適應(yīng)度數(shù)值最低的一個(gè)或幾個(gè)，并將之替換成前一代種群中適應(yīng)度數(shù)值最高的一個(gè)或幾個(gè)個(gè)體。最優(yōu)保留機(jī)制既有優(yōu)勢也有劣勢，其優(yōu)勢為它使遺傳算法記錄已找到的最優(yōu)個(gè)體，從而加快算法的收斂；其劣勢為增加遺傳算法收斂于局部最優(yōu)個(gè)體的風(fēng)險(xiǎn)。因此，在本研究中對具有最優(yōu)保留機(jī)制和不具有最優(yōu)保留機(jī)制的兩種參數(shù)配置進(jìn)行了相關(guān)實(shí)驗(yàn)。

實(shí)驗(yàn)對表1所列出的參數(shù)配置選擇了32種組合。針對遺傳算法自身的隨機(jī)性質(zhì)，對于每種參數(shù)配置組合，本研究將遺傳算法運(yùn)行10次，因此本項(xiàng)研究一共運(yùn)行了320次遺傳算法從而得到不同的實(shí)驗(yàn)結(jié)果并進(jìn)行相應(yīng)的統(tǒng)計(jì)與分析。每一次運(yùn)行對1023個(gè)可能的病狀組合M+中的每一個(gè)進(jìn)行測試，并將得出的結(jié)果與現(xiàn)實(shí)中的數(shù)據(jù)進(jìn)行對比，從而形成一個(gè)信度測試。本文對實(shí)驗(yàn)結(jié)果中各種參數(shù)配置的運(yùn)行結(jié)果進(jìn)行了曲線比較與分析。

本系統(tǒng)所構(gòu)建的遺傳算法中關(guān)鍵代碼如下：

Listpopulation=new List（）；

ListnewPopulation=new List（）；

for （int i=0； i

GAEntry entry=new GAEntry（）；

entry.Evaluate（entry.Similarity）；

population.Add（entry）；

}

int stable=0， count=0；

double prevBest=SaveBest（population， count， writer）；

double curBest=0；

Int limit=gaParams.IsElitism?gaParams.PopulationSize-1:gaParams.PopulationSize；

while （TermCriteria （stable， gaParams.StableGenerations，count， gaParams.Generations））{

while （newPopulation.Count

GAEntry parentA=GetParent（population， gaParams）；

GAEntry parentB=GetParent（population， gaParams）；

GAEntry child=GAEntry.GetChild（parentA， parentB，gaParams）；

child.Evaluate（child.Similarity）；

newPopulation.Add（child）；

}

if（gaParams.IsElitism）{

curBest= （from p in population select p.Fitness）.Max（）；

newPopulation.Add（（from p in population where p.Fitness==curBest select p）.ToList（）[0]）；

}

population.Clear（）；

population=newPopulation；

newPopulation=new List（）；

curBest=SaveBest（population， ++count， writer）；

if（prevBest==curBest） stable++；

else if（curBest>prevBest） {prevBest=curBest； stable=0；}

}

3 實(shí)驗(yàn)結(jié)果與分析

圖1為兩種選擇機(jī)制（競爭選擇和賭盤選擇）的最優(yōu)個(gè)體的信度曲線。從中可以看出從概率上講，競爭選擇比賭盤選擇具有更高的信度，即針對MFD問題來講，采用競爭選擇的遺傳算法具有更好的性能。因此我們可以分析得出，在賭盤選擇中，適應(yīng)度較高的個(gè)體永遠(yuǎn)比較低的個(gè)體具有更高的可能性被選中，導(dǎo)致搜索有可能最終收斂于局部最優(yōu)個(gè)體。然而，在競爭選擇中，對于競爭規(guī)模為N的遺傳算法，除了整個(gè)種群中適應(yīng)度最低的N-1個(gè)個(gè)體外，其他的所有個(gè)體都有機(jī)會被選中，并且其選擇壓力小于賭盤選擇中的選擇壓力，因此，收斂于局部最優(yōu)個(gè)體的風(fēng)險(xiǎn)被降低。

圖1 不同的選擇機(jī)制產(chǎn)生的結(jié)果比較Fig.1 Results from different selection methods

圖2 不同的交叉概率所產(chǎn)生的結(jié)果比較Fig.2 Results from different crossover probabilities

從圖2中我們可以看到較高的交叉概率導(dǎo)致結(jié)果中較高的信度。造成這種現(xiàn)象的原因是較高的交叉概率使得種群中個(gè)體具有更高的可能性來提高他們子代的適應(yīng)度，從而使整個(gè)種群進(jìn)化得出信度較高的個(gè)體。然而交叉概率所帶來的影響在不同的選擇機(jī)制下是不同的，比如在競爭選擇中，遺傳算法在交叉概率較低時(shí)性能下降幅度更大。

圖3 不同的變異概率所產(chǎn)生的結(jié)果比較Fig.3 Results from different mutation probabilities

從圖3中我們可以看出，在一定幅度內(nèi)，變異概率越大，實(shí)驗(yàn)結(jié)果的信度越高。然而變異概率的影響也根據(jù)選擇機(jī)制的不同而變化。在競爭選擇中，隨著變異概率的增大，原本產(chǎn)生結(jié)果信度較高的參數(shù)配置將產(chǎn)生信度更高的結(jié)果，原本產(chǎn)生結(jié)果信度較低的參數(shù)配置將產(chǎn)生信度更低的結(jié)果。而在賭盤選擇中，產(chǎn)生結(jié)果的信度一直隨著變異概率的增大而增高。

圖4 有、無最佳保留機(jī)制時(shí)的結(jié)果比較Fig.4 Results with and without elitism

從圖4中可以看出，當(dāng)使用最優(yōu)保留機(jī)制時(shí)，遺傳算法可以達(dá)到更好的性能。尤其是在采用競爭選擇機(jī)制的遺傳算法中，最優(yōu)保留機(jī)制可以大幅度降低出現(xiàn)低信度結(jié)果的可能性。最優(yōu)保留機(jī)制可以在父代與子代之間保存適應(yīng)度最高的個(gè)體的傳播，以避免它在變異作用過程中消失。然而如前所述，最優(yōu)保留機(jī)制不應(yīng)該被盲目使用，尤其是對于保留最優(yōu)個(gè)體數(shù)目較大的機(jī)制。其原因是最優(yōu)保留機(jī)制常常可以造成遺傳算法的提前收斂，也就是說搜索會停止在局部最優(yōu)值上。

圖5 不同的競爭規(guī)模所產(chǎn)生的結(jié)果比較Fig.5 Results of different tournament sizes

從圖5中我們可以看出實(shí)驗(yàn)結(jié)果的信度隨著競爭選擇的競爭規(guī)模增大而降低。因此我們可以得出的結(jié)論是，隨著競爭規(guī)模增大，選擇壓力增大，更多數(shù)量的低適應(yīng)度個(gè)體失去被選中的機(jī)會，種群的多樣性整體逐漸降低，從而會增加種群局部收斂的風(fēng)險(xiǎn)。

4 結(jié)束語

文中成功地將遺傳算法應(yīng)用到醫(yī)學(xué)中的MFD問題中，并對遺傳算法不同的參數(shù)配置產(chǎn)生的影響進(jìn)行了比較與分析。通過實(shí)驗(yàn)得出，當(dāng)遺傳算法的參數(shù)設(shè)置控制在一定范圍內(nèi)時(shí)，競爭規(guī)模較小的競爭選擇、概率較大的兩點(diǎn)交叉、較高的變異率以及較大的種群數(shù)量可以獲得最佳的結(jié)果。本文的研究在醫(yī)學(xué)領(lǐng)域具有較強(qiáng)的實(shí)用價(jià)值，其所用技術(shù)也對遺傳算法的具有良好的理論參考價(jià)值。

[1]Eberhart R，Shi Y.Computational Intelligence:Concepts to Implementations[M].Morgan Kaufmann Publisher，2009.

[2]Peng Y，Reggia J A.A Probabilistic Causal Model for Diagnostic Problem Solving Part I:Integrating Symbolic Causal Inference with Numeric Probabilistic Inference[J].IEEE Transactions on Systems， Man and Cybernetics，1987，17（2）：146-162.

[3]Potter W，Drucker E，Bettinger P.Diagnosis， Configuration，Planning，and Pathfinding:Experiments in Nature-Inspired Optimization [J].Natural Intelligence for Scheduling，Planning and Packing Problems，2009:267-294.

[4]玄光男，程潤偉.遺傳算法與工程優(yōu)化[M].北京：清華大學(xué)出版社，2004.

[5]張瑩，肖軍，李天.基于遺傳優(yōu)化的模糊PID控制器在水加藥中的應(yīng)用[J].電子設(shè)計(jì)工程，2014（17）：9-12.ZHANG Ying，XIAO Jun，LI Tian.Genetic optimization of fuzzy PIDcontroller in water based dosing[J].Electronic Design Engineering，2014（17）：9-12.

[6]彭濤，周亨，鄧維敏.基于GA-BP神經(jīng)網(wǎng)絡(luò)的柴油機(jī)噪聲品質(zhì)評價(jià)方法[J].電子設(shè)計(jì)工程，2014（17）:111-114.PENGTao，ZHOU Heng，DENG Wei-min.Diesel noise quality evaluation method based on GA-BP neural network[J].Electronic Design Engineering，2014（17）:111-114.