基于GA-QPSO算法的傳感器陣列多目標(biāo)優(yōu)化研究*

孔宇航，陶 洋，梁志芳

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

電子鼻(electronic nose,E-nose)系統(tǒng)是氣體檢測(cè)的有效分析工具之一，主要由三個(gè)部分組成：傳感器陣列、信號(hào)預(yù)處理和模式識(shí)別系統(tǒng)[1]。其中，對(duì)廣譜化合物產(chǎn)生響應(yīng)的傳感器陣列是關(guān)鍵組成部分，傳感器陣列的響應(yīng)直接決定了模式識(shí)別系統(tǒng)的輸入質(zhì)量。傳感器陣列優(yōu)化通常按照一定的策略從原始傳感器陣列中選擇具有較好特性的傳感器從而組成新的傳感器陣列，精簡(jiǎn)后的陣列包含更少的傳感器，節(jié)省了構(gòu)造成本，但保證同時(shí)具有更好的檢測(cè)效果。

近年來(lái)傳感器陣列優(yōu)化的研究方法不斷涌現(xiàn)。Sun H等人[2]利用Wilks統(tǒng)計(jì)方法通過(guò)分析傳感器特征的主成分，計(jì)算陣列中各個(gè)傳感器的貢獻(xiàn)度，從而對(duì)傳感器進(jìn)行篩選或淘汰。Jia P F等人[3]提出了遺傳量子行為粒子群優(yōu)化(genetic algorithm quantum-behavior particle swarm optimization，GA-QPSO)方法，引入重要性因子法計(jì)算傳感器的貢獻(xiàn)權(quán)重，同時(shí)對(duì)粒子群算法改進(jìn)，最終實(shí)現(xiàn)對(duì)傳感器陣列和分類器的同步優(yōu)化。常美茁[4]利用15只氣體金屬氧化物傳感器，通過(guò)相關(guān)性分析找出了存在冗余信息的傳感器組合，然后使用區(qū)分性能值的方法剔除冗余傳感器組合中區(qū)分性能值小對(duì)應(yīng)的傳感器。

本文首先通過(guò)聚類分析預(yù)估傳感器陣列的大小。再將傳感器的選擇性和差異性作為影響傳感器陣列的兩個(gè)重要因素，提出一種多目標(biāo)優(yōu)化的場(chǎng)景，利用信息熵的原理構(gòu)造目標(biāo)函數(shù)。然后引入遺傳算法(genetic algorithm,GA)的交叉和變異操作，二者概率的變化采用一種自適應(yīng)參數(shù)調(diào)整機(jī)制，對(duì)QPSO算法改進(jìn)后尋求帕累托最優(yōu)解集，找到對(duì)應(yīng)具有高選擇性和差異性的傳感器組合子集。

1 相關(guān)工作

1.1 聚類分析

聚類分析是根據(jù)目標(biāo)之間的相似性對(duì)其進(jìn)行分類，屬于無(wú)監(jiān)督機(jī)器學(xué)習(xí)范圍之內(nèi)的方法[5]。對(duì)于給定的一組數(shù)據(jù)，運(yùn)用聚類分析的方法將各個(gè)數(shù)據(jù)點(diǎn)劃分為不同的組別，依據(jù)相似性理論比較某個(gè)空間中的距離來(lái)決定：數(shù)據(jù)點(diǎn)之間的距離越小，它們的性質(zhì)就越相似。其中層次聚類分析運(yùn)用離差平方和建立矩陣，其思想是如果某個(gè)樣本分類正確，那么同類樣本之間的離差平方和的值較小，而不同類樣本之間的離差平方和的值較大。

利用層次聚類中的離差平方和方法初步分析并評(píng)估初始傳感器陣列中所有傳感器的近似群體，這為后續(xù)傳感器陣列規(guī)模大小的選擇提供參考依據(jù)。

1.2 多目標(biāo)優(yōu)化函數(shù)構(gòu)造

大多數(shù)優(yōu)化問(wèn)題涉及多個(gè)目標(biāo)，這些目標(biāo)同樣重要，而且可能存在相互沖突的關(guān)系。多目標(biāo)優(yōu)化通過(guò)在目標(biāo)之間找到一組非支配解來(lái)處理問(wèn)題，因?yàn)椴皇苋魏纹渌鉀Q方案支配的解是帕累托(Pareto)最優(yōu)解[6]。解決多目標(biāo)優(yōu)化問(wèn)題一般包括兩個(gè)步驟[7]：1)利用相關(guān)搜索算法尋找由不同目標(biāo)解組成的Pareto最優(yōu)解集；2)采用更高層次的信息準(zhǔn)則對(duì)這些解進(jìn)行評(píng)價(jià)和選擇。

傳感器陣列優(yōu)化通常選擇具有高靈敏度的傳感器，因?yàn)榭梢蕴峁╆P(guān)于每種氣體所包含的最多的相關(guān)信息。但是傳感器相互之間往往存在交叉敏感特性，含有冗余信息。此外，傳感器靈敏度的差異性越高，其模式區(qū)分越明顯。所以同時(shí)將傳感器靈敏度的差異性作為影響陣列優(yōu)化的因素之一。

對(duì)于區(qū)分N類氣體的分類任務(wù)，假定初始陣列中傳感器個(gè)數(shù)為M，優(yōu)化后的傳感器個(gè)數(shù)為K(K≤M)，將所有的傳感器靈敏度Sij形成一個(gè)初始矩陣。構(gòu)造兩個(gè)目標(biāo)函數(shù)，目標(biāo)函數(shù)1是由靈敏度矩陣中列的信息熵組成，對(duì)于傳感器j，其選擇性越高，靈敏度矩陣第j列的熵值就越??；目標(biāo)函數(shù)2是由靈敏度矩陣中行的信息熵組成，對(duì)于氣體i，其差異性越大，靈敏度矩陣第i列的熵值就越小。

以傳感器選擇性構(gòu)造目標(biāo)函數(shù)1：

1)計(jì)算第j列中元素的總和，并對(duì)Sij歸一化處理

(1)

式中i和j分別為氣體類別和傳感器，j的值在優(yōu)化過(guò)程中動(dòng)態(tài)確定。

2)計(jì)算每個(gè)選定傳感器j的信息熵

(2)

3)獲取N類氣體分析物獲得的最大信息熵

Hmax=logN

(3)

4)構(gòu)造K個(gè)基于信息熵的傳感器選擇性的目標(biāo)函數(shù)1

(4)

與上同理，構(gòu)造N個(gè)基于信息熵的傳感器差異性的目標(biāo)函數(shù)2

(5)

以上兩個(gè)目標(biāo)函數(shù)的值均在[0,1]范圍內(nèi)，最小化這兩個(gè)目標(biāo)函數(shù)將分別獲得最大的選擇性和多樣性。即在多目標(biāo)優(yōu)化中使用目標(biāo)函數(shù)，所得的傳感器陣列可以提供最相關(guān)的信息。

1.3 QPSO算法

QPSO算法[8]是一種量子模型的概率化PSO算法。其原理是將粒子尋優(yōu)空間看成量子力學(xué)中的勢(shì)阱，將粒子的尋優(yōu)過(guò)程看作勢(shì)場(chǎng)中粒子向勢(shì)能最低點(diǎn)移動(dòng)的過(guò)程。QPSO算法的公式為

Xid(t+1)=pbest_id+α·|mbest_id-Xid|·ln(1/u)

=φ(t)·Pbest_id+(1-φ(t))·pgd+

α·|mbest_id-Xid|·ln(1/u)

(6)

式中pbest_id為每個(gè)粒子的局部吸引子，mbest_id為Pbest_id的平均值，Pbest_id為當(dāng)前迭代中的第i個(gè)粒子的最優(yōu)位置，u為(0,1)之間的隨機(jī)量，α為收縮—膨脹系數(shù)，T為總迭代次數(shù)，t為當(dāng)前迭代次數(shù)。

2 基于遺傳量子行為粒子群優(yōu)化算法

GA[9]是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。在GA中，個(gè)體不僅可以共享有用的片段，還可以共享無(wú)用的片段。PSO算法并沒(méi)有GA中交叉、變異的操作過(guò)程從而獲得更好的新個(gè)體，更多的是體現(xiàn)在追蹤單個(gè)粒子和共享群體最優(yōu)信息來(lái)實(shí)現(xiàn)向最優(yōu)空間搜索的形式，但容易陷入局部最優(yōu)。在PSO算法中加入GA中的交叉和變異步驟，可以跳過(guò)這個(gè)局部最優(yōu)解，尋求全局最優(yōu)解。

粒子采用交叉和變異操作過(guò)程中的概率值采用動(dòng)態(tài)調(diào)整機(jī)制進(jìn)行更新，即

(7)

(8)

式中 參數(shù)Pc1和Pm1為交叉概率的最大值和變異概率的最大值。fmax和favg為最大適應(yīng)度值和平均適應(yīng)度值。f′和f為局部最佳適應(yīng)度值和當(dāng)前最佳適應(yīng)度值。

在多目標(biāo)優(yōu)化傳感器的前提下，一種基于遺傳量子行為粒子群優(yōu)化(GA-QPSO)算法用于搜索可行解空間的最優(yōu)解，算法的全流程步驟如下：

輸入：初始化粒子群種群，最大迭代次數(shù)等參數(shù)；

輸出：非支配Pareto解集；

過(guò)程：

1)隨機(jī)初始化粒子種群、粒子維度、遺傳算子中的交叉概率Pc，變異概率Pm，迭代次數(shù)T；

2)用起始位置對(duì)粒子進(jìn)行初始化；

3)計(jì)算每個(gè)粒子的適應(yīng)度值，將適應(yīng)度值與其經(jīng)歷過(guò)的最好位置pbest進(jìn)行比較，如果優(yōu)于pbest，則將其作為當(dāng)前的最好位置pbest。對(duì)于每個(gè)群體，將其適應(yīng)度值與群體所經(jīng)歷過(guò)的最好位置gbest進(jìn)行比較，如果優(yōu)于gbest，則將其作為群體最優(yōu)位置；

4)對(duì)全局進(jìn)行初步搜索，式(6)更新粒子位置；

5)計(jì)算當(dāng)前種群平均適應(yīng)度值，對(duì)適應(yīng)度值大于平均適應(yīng)度的粒子予以選擇保留，對(duì)于小于平均適應(yīng)度的粒子根據(jù)式(7)和式(8)進(jìn)行交叉、變異操作；

6)重新評(píng)估新生成的粒子，再次計(jì)算其適應(yīng)度值并更新pbest和gbest；

7)若迭代次數(shù)大于等于T，轉(zhuǎn)到步驟(8)，否則轉(zhuǎn)到步驟(3)，直至滿足終止條件為止；

8)把群體最優(yōu)位置轉(zhuǎn)換為對(duì)應(yīng)的Pareto最優(yōu)子集。

3 實(shí)驗(yàn)驗(yàn)證與分析

3.1 數(shù)據(jù)集介紹

本文中的數(shù)據(jù)集是來(lái)自加州大學(xué)圣地亞哥分校實(shí)驗(yàn)室的Huerta R等人在家庭環(huán)境的條件下采集而來(lái)，該傳感器陣列一共包含8個(gè)MOX金屬氣體傳感器。傳感器陣列長(zhǎng)期放置于實(shí)驗(yàn)人員的家中，數(shù)據(jù)集包含3種共100個(gè)不同條件的時(shí)間序列：葡萄酒、香蕉和背景活動(dòng)。其中，包括葡萄酒的36種響應(yīng)記錄，香蕉的33種響應(yīng)記錄，背景活動(dòng)的31種響應(yīng)記錄。

3.2 實(shí)驗(yàn)設(shè)置

本文的實(shí)驗(yàn)環(huán)境為MATLAB R2016a。在提出的GA-QPSO算法中，初始粒子種群設(shè)置為20，最大迭代次數(shù)為1 000，粒子維度為30，在搜索空間中隨機(jī)初始化粒子位置。Pc1的初始值為0.9，Pc2為0.6，Pm1為0.1，Pm1為0.001。對(duì)樣本進(jìn)行分類使用支持向量機(jī)(support vector machine，SVM)，核函數(shù)選用基于徑向基函數(shù)(radial basis function,RBF)。

3.3 實(shí)驗(yàn)分析

由于傳感器陣列中某些響應(yīng)之間存在相關(guān)性，這些傳感器提供的信息之間可能存在冗余。首先通過(guò)聚類分析中的離差平方和方法評(píng)估傳感器大致可分為幾類，即潛在的傳感器最優(yōu)組合的數(shù)量。使用SPSS Statistics 20軟件對(duì)該過(guò)程進(jìn)行分析，所得的結(jié)果用樹(shù)狀圖表示，如圖1所示。數(shù)據(jù)集中涉及到的8只傳感器之間的相似度均在90 %以上，說(shuō)明某些傳感器響應(yīng)之間的確存在共線性。8只傳感器大致分為4組：A組(傳感器S1和S3)，B組(傳感器S2)，C組(傳感器S4，S7，S8)，D組(傳感器S5，S6)。因此，最優(yōu)傳感器陣列可能需要4個(gè)左右的傳感器數(shù)量以區(qū)分目標(biāo)氣體。

圖1 數(shù)據(jù)集通過(guò)聚類分析得到的樹(shù)狀圖

表1列出了GA-QPSO算法運(yùn)行后的結(jié)果，包括：種群大小、Pareto解集的數(shù)量、運(yùn)行10次時(shí)間的平均值。結(jié)果表明Pareto解集大多數(shù)集中在傳感器陣列大小為4個(gè)左右，有效驗(yàn)證了聚類分析的結(jié)果。

表1 GA-QPSO算法運(yùn)行實(shí)驗(yàn)結(jié)果

圖2為在構(gòu)造傳感器選擇性相關(guān)的目標(biāo)函數(shù)1和差異性相關(guān)的目標(biāo)函數(shù)2的基礎(chǔ)上，傳感器陣列大小為2,3,4,5,6時(shí)的Pareto解集分布?？梢钥闯?，潛在傳感器的數(shù)量在很大程度上決定了解決方案空間的大小，因此極大地影響了優(yōu)化問(wèn)題的復(fù)雜性。Pareto優(yōu)化解的個(gè)數(shù)隨著陣列大小先增加后減小。由此得出傳感器的Pareto解集主要取決于其解的分布，與陣列大小無(wú)關(guān)。

圖2 優(yōu)化后不同陣列大小下Pareto優(yōu)化解的個(gè)數(shù)

最后，為了驗(yàn)證所提出的GA-QPSO算法用于傳感器陣列多目標(biāo)優(yōu)化。在單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化兩種場(chǎng)景下，將PSO算法、帶權(quán)重的粒子群優(yōu)化(SPSO)算法、QPSO算法作為對(duì)比算法，隨機(jī)選取各自優(yōu)化后的10組Pareto解集。其中，單目標(biāo)優(yōu)化采用傳感器選擇性特性構(gòu)造的目標(biāo)函數(shù)1，然后使用SVM對(duì)目標(biāo)氣體分析物進(jìn)行分類，觀察分類結(jié)果。各算法的分類精度如表2所示。

表2 不同算法下單目標(biāo)和多目標(biāo)優(yōu)化后的結(jié)果

可以看出在單目標(biāo)優(yōu)化場(chǎng)景下，GA-QPSO算法的平均分類精度最高，達(dá)到了79.1 %。同樣在多目標(biāo)優(yōu)化場(chǎng)景下，GA-QPSO算法在全部的對(duì)比算法中平均精度最優(yōu)，達(dá)到了88.3 %，同時(shí)不論何種算法，多目標(biāo)優(yōu)化場(chǎng)景下算法取得的分類精度明顯優(yōu)于同類算法單目標(biāo)優(yōu)化場(chǎng)景下的分類精度。此外，這些算法的分類精度均高于初始陣列傳感器組合的分類精度。為了更直觀地反映優(yōu)化后分類精度的變化，畫(huà)出幾種算法分類精度的對(duì)比，如圖3所示。

圖3 不同算法下單目標(biāo)和多目標(biāo)優(yōu)化后結(jié)果對(duì)比

4 結(jié) 論

傳統(tǒng)的傳感器陣列優(yōu)化采用單目標(biāo)優(yōu)化具有局限性，本文提出了GA-QPSO算法的傳感器陣列多目標(biāo)優(yōu)化研究方法。將傳感器的選擇性和差異性同時(shí)作為優(yōu)化的兩個(gè)準(zhǔn)則構(gòu)造目標(biāo)函數(shù)，然后將量子力學(xué)的思想引入到粒子群算法中，并通過(guò)加入GA中的交叉和變異操作，尋求全局最優(yōu)解。本文算法有效地搜索到可行解空間中的Pareto解集，找到了最優(yōu)的傳感器陣列集合。實(shí)驗(yàn)結(jié)果驗(yàn)證了GA-QPSO算法用于傳感器陣列多目標(biāo)優(yōu)化的有效性，最終用較少數(shù)量的傳感器構(gòu)建了高質(zhì)量的陣列。