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

張舒

（西北工業大學 陜西 西安 710072）

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

1 多故障診斷問題的背景

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

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

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

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

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

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

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

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

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

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

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

2 遺傳算法在MFD問題中的實現

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

表1 遺傳算法參數設置Tab.1 Experiment set up for the GA

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

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

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

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

本系統所構建的遺傳算法中關鍵代碼如下：

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 實驗結果與分析

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

圖1 不同的選擇機制產生的結果比較Fig.1 Results from different selection methods

圖2 不同的交叉概率所產生的結果比較Fig.2 Results from different crossover probabilities

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

圖3 不同的變異概率所產生的結果比較Fig.3 Results from different mutation probabilities

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

圖4 有、無最佳保留機制時的結果比較Fig.4 Results with and without elitism

從圖4中可以看出，當使用最優保留機制時，遺傳算法可以達到更好的性能。尤其是在采用競爭選擇機制的遺傳算法中，最優保留機制可以大幅度降低出現低信度結果的可能性。最優保留機制可以在父代與子代之間保存適應度最高的個體的傳播，以避免它在變異作用過程中消失。然而如前所述，最優保留機制不應該被盲目使用，尤其是對于保留最優個體數目較大的機制。其原因是最優保留機制常?？梢栽斐蛇z傳算法的提前收斂，也就是說搜索會停止在局部最優值上。

圖5 不同的競爭規模所產生的結果比較Fig.5 Results of different tournament sizes

從圖5中我們可以看出實驗結果的信度隨著競爭選擇的競爭規模增大而降低。因此我們可以得出的結論是，隨著競爭規模增大，選擇壓力增大，更多數量的低適應度個體失去被選中的機會，種群的多樣性整體逐漸降低，從而會增加種群局部收斂的風險。

4 結束語

文中成功地將遺傳算法應用到醫學中的MFD問題中，并對遺傳算法不同的參數配置產生的影響進行了比較與分析。通過實驗得出，當遺傳算法的參數設置控制在一定范圍內時，競爭規模較小的競爭選擇、概率較大的兩點交叉、較高的變異率以及較大的種群數量可以獲得最佳的結果。本文的研究在醫學領域具有較強的實用價值，其所用技術也對遺傳算法的具有良好的理論參考價值。

[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]玄光男，程潤偉.遺傳算法與工程優化[M].北京：清華大學出版社，2004.

[5]張瑩，肖軍，李天.基于遺傳優化的模糊PID控制器在水加藥中的應用[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].電子設計工程，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.