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

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

1 概述

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

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

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

2 粗糙集

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

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

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

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

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

(3)當(dāng)γ=0 時(shí)，決策Q 完全獨(dú)立于P。

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

對(duì)于核，有:

3 遺傳屬性約簡(jiǎn)的特征選擇算法

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

3.1 參數(shù)編碼

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

3.2 適應(yīng)度函數(shù)

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

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

3.3 遺傳算子

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

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

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

3.4 動(dòng)態(tài)相似個(gè)體裁剪和新個(gè)體補(bǔ)充

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

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

圖1 改進(jìn)的GA-RS 火焰圖像特征選擇算法流程

4 仿真實(shí)驗(yàn)分析

4.1 數(shù)據(jù)集測(cè)試

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

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

4.2 改進(jìn)的特征選擇算法有效性分析

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

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

分別使用火焰6 個(gè)特征和支持向量機(jī)(Support Vector Machine，SVM)結(jié)合(ALL +SVM)、基于支持向量機(jī)的圖像型火災(zāi)探測(cè)算法［12］、粗糙集和SVM結(jié)合(RS+SVM)，以及遺傳算法、粗糙集、SVM 結(jié)合(GA+RS+SVM)的4 種算法對(duì)離散化的火災(zāi)/干擾數(shù)據(jù)集進(jìn)行訓(xùn)練，訓(xùn)練樣本是從500 個(gè)數(shù)據(jù)集中分別隨機(jī)選擇100 個(gè)有火和干擾樣本，再?gòu)氖Ｓ嘀羞x則部分?jǐn)?shù)據(jù)作為測(cè)試樣本，預(yù)測(cè)結(jié)果如表1 所示。

表1 4 種火焰識(shí)別算法的實(shí)驗(yàn)結(jié)果對(duì)比

對(duì)表1 實(shí)驗(yàn)結(jié)果分析如下:

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

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

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

5 結(jié)束語

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

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

［2］曾黃麟.粗集理論及其應(yīng)用［M］.重慶:重慶大學(xué)出版社，1998.

［3］趙 勇，方宗德，王侃偉，等.鄰域粗糙集在輪對(duì)踏面缺陷圖像特征選擇的應(yīng)用［J］.計(jì)算機(jī)測(cè)量與控制，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］.計(jì)算機(jī)科學(xué)，2007，34(6):162-165.

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

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

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

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

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

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

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