胡 燕，王慧琴，黃東宇，馬宗方

(西安建筑科技大學a.管理學院;b.信息與控制工程學院，西安 710055)

1 概述

火災的燃燒過程是一個強非線性動力學系統(tǒng)，火災燃燒狀態(tài)變化受到可燃物的數(shù)量、種類和燃燒區(qū)域風速等諸多因素制約，具有很強的模糊及隨機特性。現(xiàn)有的在特定條件下人為設定火焰在圖像上表現(xiàn)單個或某幾個特征信息作為識別依據的算法使得火災探測算法的推廣能力大受影響。對于模式識別，重復和不重要的特征項不但不會提高算法的分類能力，反而會使特征組合的分類能力下降。當輸入的特征項增加時，分類器要求的訓練樣本數(shù)量會呈指數(shù)關系增長［1］。因此，在對火焰辨識中，有必要強調特征選擇的顯著性度量，力求在不失可靠性的情況下，簡化特征模型和減少冗余計算。

分支定界搜索法、前向/后向序貫和極大-極小選擇［2］等是常用的特征選擇算法，存在沒有把知識與分類有機地聯(lián)系在一起，難以分析、發(fā)現(xiàn)和推理數(shù)據間的關系［3］。粗糙集(Rought Set，RS)［4］是1982 年提出的一種處理模糊不確定型的數(shù)學算法，核心內容是屬性約簡，即保持信息系統(tǒng)分類能力不變導出與原始數(shù)據具有相同決策能力的最小集合。它無需提供問題所需處理數(shù)據集合之外的任何先驗信息，對問題的不確定描述或處理是比較客觀的，然而求解最小屬性約簡被證實是一個NP 難題［5］。遺傳算法(Genetic Algorithm，GA)是受生物進化論啟發(fā)而提出的一種基于適者生存機制的隨機優(yōu)化算法，具有較強的全局尋優(yōu)性能，具有較高的并行處理能力。不少學者將GA應用于解決粗糙集中的屬性約簡。

這些研究主要集中在改進算法的復雜度和加入啟發(fā)式信息等方面［6］，為了使尋優(yōu)結果盡可能逼近最優(yōu)解，但卻不能保證獲得的屬性子集是最簡的。因此，本文結合粗糙集和遺傳算法各自的特點，利用粗糙集思想定義遺傳算法適應度函數(shù)，設計自適應交叉和變異算子，將動態(tài)裁剪相似個體和補充新個體的策略引入到種群更新中，增加染色體的多樣性，解決傳統(tǒng)GA 早熟問題。

2 粗糙集

在粗糙集理論中，對象的知識是通過指定對象的基本特征(屬性)和它們的特征值(屬性值)來描述的。一個知識表達系統(tǒng)定義為:

定義1 對于屬性集P?R(R=A∪D)，對象X，Y?U，P 上的不可分辨關系為:

定義2 設論域U 上的2 個等價關系簇為P 和Q，Q 的P 正域定義為則稱Q以γ 依賴于P(P 以γ 支持于Q)，記為:

(1)當γ=1 時，決策Q 完全由條件P 確定。

(2)當0 ＜γ ＜1 時，決策Q 部分由條件P 確定。

(3)當γ=0 時，決策Q 完全獨立于P。

定義3 對于?c∈C，若c 滿足pos{C-c}(D)=pos{C}(D)，則稱c 是C 中D 不必要的，否則c 是C 中D 必要的，所有必要的屬性構成的子集為C 的一個約簡，所有C 的屬性約簡的交集稱為C 的核:

對于核，有:

3 遺傳屬性約簡的特征選擇算法

參數(shù)編碼、初始群體的設定、適應度函數(shù)設計、遺傳操作和控制參數(shù)設定是遺傳算法的5 個基本要素，其中，編碼、適應度函數(shù)和遺傳算子的設計是實現(xiàn)整個GA 的關鍵。將RS 屬性約簡的思想引入到GA 中，在GA 的每個關鍵環(huán)節(jié)融合RS 的設計理念，從而解決火焰圖像特征隨監(jiān)控場景變化的自適應選擇問題。

3.1 參數(shù)編碼

遺傳算法不能直接處理問題空間的參數(shù)，需要通過一定的編碼規(guī)則把要求問題的可行解表示成遺傳空間的染色體或者個體［7］?；鹧孀R別屬于二分類問題。在對火焰特征集合進行屬性約簡之前需要對其進行離散化處理，將特征值轉化成0 或1 整數(shù)，從數(shù)值表型形式上看更接近遺傳算法中的二進制編碼形式，因此，選用二進制編碼算法對火焰圖像特征參數(shù)進行數(shù)值空間轉換。具體做法是:采用固定長度的二進制符號串表示種群的個體，等位基因由符號集{0，1}構成，其中，1 表示選擇其對應的條件屬性;0 表示不選擇其對應的條件屬性。若1011010100 表示一個長度為10 的個體，則對應選擇的屬性子集為{a1，a3，a4，a6，a8}。

3.2 適應度函數(shù)

適應度函數(shù)是評價染色體優(yōu)劣的唯一確定性標準，決定群體的進化方向。由屬性約簡的定義可知，適應度函數(shù)的設計受2 個因素影響:(1)屬性的分類能力:條件屬性對決策屬性的支持度盡可能大。(2)染色體中含1 的數(shù)量:屬性的個數(shù)盡可能少，這樣被選中的概率才會越大。根據上述2 個指標，定義新的適應度函數(shù)為:

其中，m 表示條件屬性的個數(shù);card(x)表示每個個體中1 的個數(shù);γC(D)表示條件屬性集C 對決策屬性D的支持度，由定義2 計算可以得到。γC(D)越大說明條件屬性與決策屬性的相關性越大，在保證約簡后得到的屬性個數(shù)小的同時使屬性間的相關性較小。從式(6)可知，個體中所包含條件屬性越少，以及條件屬性與決策屬性的相關性越大，則適應度值越大。

3.3 遺傳算子

遺傳算子包括選擇操作、交叉操作和變異操作。這里選用適應度比例算法(輪盤賭法)進行個體選擇，根據每個個體適應度的值從中選擇較大者進入新的種群，體現(xiàn)了自然界優(yōu)勝劣汰的自然法則［8］。個體被選中的概率為:

其中，F(xiàn)i表示第i 個個體的適應度值;n 表示群體的規(guī)模。

交叉操作中的交叉概率pc控制交叉算子的使用頻率，使解達到最有希望的全局最優(yōu)解區(qū)域。變異操作中的變異概率pm控制變異算子的使用頻率，決定了GA 的局部搜索能力。在標準的GA 中，一般情況下pc和pm是固定的，憑經驗選取，其取值直接影響算法的收斂性。過大的pc和pm使GA 退化成隨機搜索算法的可能性也越大;pc和pm取值過小，算法容易過早收斂于局部最優(yōu)解。而適應度值大的個體表明其基因優(yōu)，在遺傳操作中希望其優(yōu)秀的基因被保留到子代中，因此，可以讓pc和pm隨適應度值自適應調整。調整公式為:

3.4 動態(tài)相似個體裁剪和新個體補充

當群體中的個體非常相似，群體的多樣性急劇減少，群體缺乏有效等位基因，在遺傳算子作用下不能生成高階競爭模式，會出現(xiàn)“早熟”現(xiàn)象［9］。通過對鄰近個體進行適當?shù)男藜?，減少基因的單一性:對每個個體，尋找最近鄰，計算2 個個體之間的相似度S(用歐氏距離表示)，S 小于閾值T，認為2 個個體相似，刪除適應度值較小者。經裁剪相似個體操作后，種群規(guī)模減小，為了保證群體規(guī)模，采用最優(yōu)保持策略［10］添加新的個體，動態(tài)地解決了種群因缺乏多樣性而陷入局部最優(yōu)解的問題。

改進的GA-RS 火焰圖像特征選擇算法流程如圖1 所示。

圖1 改進的GA-RS 火焰圖像特征選擇算法流程

4 仿真實驗分析

4.1 數(shù)據集測試

樣本數(shù)據是根據國家標準《GB 15631-2008》在大空間環(huán)境下白天和夜晚自行拍攝的視頻，以庚烷、汽油、煤油、柴油、酒精、汽油與煤油按照10:1 的混合液作為點火材料;打火機火、蠟燭火、探照燈、警燈、手電筒、運動的車燈、環(huán)形燈和白熾燈為干擾源，數(shù)據集共500 個樣本，部分截圖如圖2 所示。

圖2 數(shù)據集部分視頻截圖

4.2 改進的特征選擇算法有效性分析

利用火焰圖像分割算法提取可疑目標，用c1，c2，c3，c4，c5，c6和有火/無火表示圓形度、尖角數(shù)、紅綠分量面積比、面積變化率等6 種特征和決策結果，論域U={x1，x2，…，x200}，條件屬性C={c1，c2，c3，c4，c5，c6}，決策屬性D=syggg00，當d=1 時表示有火情況，當d=0 時表示無火情況。

通過文獻［11］的特征量歸類表將6 個特征離散化，將檢測數(shù)據映射到信息系統(tǒng)，初始參數(shù)取值分別為:迭代次數(shù)N=100;種群規(guī)模n=50;pc1=0.85;pm1=0.1;β=0.7;T=1.8。

分別使用火焰6 個特征和支持向量機(Support Vector Machine，SVM)結合(ALL +SVM)、基于支持向量機的圖像型火災探測算法［12］、粗糙集和SVM結合(RS+SVM)，以及遺傳算法、粗糙集、SVM 結合(GA+RS+SVM)的4 種算法對離散化的火災/干擾數(shù)據集進行訓練，訓練樣本是從500 個數(shù)據集中分別隨機選擇100 個有火和干擾樣本，再從剩余中選則部分數(shù)據作為測試樣本，預測結果如表1 所示。

表1 4 種火焰識別算法的實驗結果對比

對表1 實驗結果分析如下:

(1)樣本中特征數(shù)量越多并不表示一定能提高識別精度。特征之間的相關性，冗余或不重要特征彼此之間的干擾很容易降低分類準確率。

(2)固定分類特征組合依賴訓練樣本集，導致識別算法的自適應能力差。但是當訓練樣本集改變，最有效的特征子集也會發(fā)生變化，如果仍然沿用原來的固定3 個特征識別火焰會使算法的識別精度迅速下降。

(3)經特征選擇后，特征數(shù)目均少于原始特征數(shù)目，同時能保持高于原特征集的識別率。RS +SVM 算法特征數(shù)目減少2 個，GA +RS +SVM 算法特征數(shù)目減少3 個。盡管GA+RS+SVM 算法是4 種算法中最耗時的，識別時間最慢達到16.7 s，與前3 種算法相比，平均會多增加6 s～7 s 的運算時間，但是經過GA 優(yōu)化后的RS 算法，擴大了最優(yōu)解的搜索空間，得到的解更加準確，實現(xiàn)了特征的優(yōu)化組合。另外，總的來說，動態(tài)特征對識別率的貢獻大于靜態(tài)特征，主要是因為動態(tài)特征受外界干擾影響較小，獲取的特征值相對較為穩(wěn)定。

5 結束語

火焰圖像特征選取是否合適直接決定分類器的準確率。為了提高火焰探測精度，使火焰圖像特征隨監(jiān)控場景的不同自適應地選擇最佳、最小特征組合，本文提出一種基于改進GA-RS 的火焰圖像特征選擇算法。實驗結果表明，該算法不但減少了特征數(shù)量，還具有較強的泛化能力。

［1］毛罕平，徐貴力，李萍萍.基于遺傳算法的蔬菜缺素葉片圖像特征選擇研究［J］.江蘇大學學報:自然科學版，2003，24(2):1-5.

［2］曾黃麟.粗集理論及其應用［M］.重慶:重慶大學出版社，1998.

［3］趙 勇，方宗德，王侃偉，等.鄰域粗糙集在輪對踏面缺陷圖像特征選擇的應用［J］.計算機測量與控制，2008，16(11):1730-1731，1734.

［4］Pawlak Z.Rough Sets［J］.International Journal of Information and Computer Science，1982，11(5):341-356.

［5］梁 琰，何中市.一種基于粗糙集啟發(fā)式的特征選擇算法［J］.計算機科學，2007，34(6):162-165.

［6］陳 曦，雷 健，傅 明.基于改進遺傳算法的粗糙集屬性約簡算法［J］.計算機工程與設計，2010，31(3):602-604，608.

［7］張 晉，李冬黎，李 平.遺傳算法編碼機制的比較研究［J］.中國礦業(yè)大學學報，2002，31(6):93-96.

［8］邊 霞，米 良.遺傳算法理論及其應用研究進展［J］.計算機應用研究，2010，27(7):2425-2429，2434.

［9］周洪偉，原錦輝，張來順.遺傳算法“早熟”現(xiàn)象的改進策略［J］.計算機工程，2007，33(19):201-203.

［10］張杰慧，何中市，黃麗瓊.基于改進的RS-GA 圖像特征選擇方法［J］.計算機應用，2006，26(10):2372-2374.

［11］胡 燕，王慧琴，秦薇薇，等.基于粗糙集的火災圖像特征選擇與識別［J］.計算機應用，2013，33(3):704-707.

［12］楊娜娟，王慧琴，馬宗方.基于支持向量機的圖像型火災探測算法［J］.計算機應用，2010，30(4):1129-1131，1140.