改進(jìn)的量子遺傳算法及其在WMSN覆蓋優(yōu)化中的應(yīng)用*

嚴(yán) 英，郭 劍，孫力娟

（1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210046；2.南京郵電大學(xué)計(jì)算機(jī)技術(shù)研究所 南京 210003）

1 引言

遺傳算法 （genetic algorithm，GA）是進(jìn)化計(jì)算的一個(gè)分支，也是軟計(jì)算的關(guān)鍵技術(shù)之一。它本質(zhì)上是一種隨機(jī)搜索算法，在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、圖像處理、網(wǎng)絡(luò)優(yōu)化等領(lǐng)域獲得了廣泛的應(yīng)用[1～2]。但是應(yīng)用GA算法來解決實(shí)際問題時(shí)，人們也遇到了不少困難。最常見的問題就是遺傳算法的收斂速度緩慢，且常常收斂于局部最優(yōu)解。為了解決這個(gè)問題，研究者也提出了不少改進(jìn)[3～4]。Han等人[5]首次將量子計(jì)算的相關(guān)概念引入到遺傳算法的框架中，提出了量子遺傳算法（quantum genetic algorithm，QGA）[6，7]。QGA算法對(duì)GA算法的編碼方式與演化操作都進(jìn)行了改進(jìn)，使得算法的收斂速度大大加快，但算法收斂到局部最優(yōu)解的問題仍然沒有很好地解決。

本文對(duì)QGA算法進(jìn)行了研究，針對(duì)QGA算法早熟的問題，從算法機(jī)制的角度進(jìn)行了分析。QGA算法每次迭代時(shí)，以一個(gè)最優(yōu)染色體來指導(dǎo)群體的進(jìn)化，破壞了染色體的多樣性，使得算法很容易收斂到局部最優(yōu)解。本文分析了這種方法的不足，改進(jìn)了QGA的信息交流方式，進(jìn)而提出了一種基于精英組的量子遺傳算法 （elite group based quantum genetic algorithm，EQGA）。最后，本文將 EQGA 用于無線多媒體傳感器網(wǎng)絡(luò) （wireless multimedia sensor network，WMSN）的覆蓋優(yōu)化問題，通過對(duì)比實(shí)驗(yàn)驗(yàn)證了EQGA的性能。

2 量子遺傳算法

QGA是在GA基礎(chǔ)上發(fā)展起來的一種隨機(jī)搜索算法。為了進(jìn)行區(qū)別，本文將傳統(tǒng)的QGA算法稱為標(biāo)準(zhǔn)量子遺傳算 法 （standard quantum genetic algorithm，SQGA）。在SQGA中，染色體的編碼和演化操作需要借助于量子計(jì)算的相關(guān)工具，下面分別進(jìn)行介紹。

2.1 量子比特編碼

SQGA算法使用量子比特來表示一個(gè)基因位。量子比特的表示如式（1）所示，其中，α、β∈C，且滿足|α|2+|β|2=1：

|α|2、|β|2分別表示|0>、|1>狀態(tài)出現(xiàn)的概率。可以看出，與經(jīng)典的二進(jìn)制比特不同，量子比特并不是一個(gè)確定的|0>態(tài)或|1>態(tài)，而是這兩種狀態(tài)的概率疊加。

染色體的編碼如式（2）所示，其中，m是染色體含有的基因數(shù)，k是每個(gè)基因所含有的量子比特?cái)?shù)，αxy、βxy的意義與前面相同：

2.2 演化操作

在SQGA中，染色體主要有量子變異和量子旋轉(zhuǎn)兩種進(jìn)化操作。量子變異操作的過程如式（3）所示，量子旋轉(zhuǎn)操作的過程如式（4）所示：

其中，(α,β)、(α′,β′)分別為調(diào)整前與調(diào)整后的量子比特。式（4）中的θ是量子旋轉(zhuǎn)的角度。

2.3 算法流程

SQGA的流程如下：

（1）設(shè)置 SQGA算法的參數(shù)，如迭代次數(shù)、變異概率等；

（2）初始化種群；

（3）對(duì)所有染色體進(jìn)行評(píng)估測(cè)量，并記錄最優(yōu)個(gè)體作為群體演化的指導(dǎo)；

（4）根據(jù)當(dāng)前的最優(yōu)染色體，對(duì)所有染色體進(jìn)行量子旋轉(zhuǎn)操作；（5）根據(jù)變異概率對(duì)所有染色體進(jìn)行量子變異操作；（6）如果算法終止條件滿足，則程序運(yùn)行結(jié)束，否則返回步驟（3）。

2.4 量子遺傳算法的不足

SQGA算法的收斂速度大大快于GA算法。其原因除了量子計(jì)算的并行性之外，還有一個(gè)就是染色體更新時(shí)演化目標(biāo)的選擇機(jī)制。在SQGA中，每次只選擇一個(gè)最優(yōu)染色體來指導(dǎo)群體的進(jìn)化。每條染色體進(jìn)化時(shí)都以它作為演化目標(biāo)進(jìn)行旋轉(zhuǎn)操作，這固然增加了最優(yōu)染色體在群體中的影響力，促進(jìn)了優(yōu)秀信息的傳播，并在客觀上加速了算法的收斂，但另一方面，所有染色體都向同一個(gè)體演化，那些帶有合理信息的其他染色體很可能由于暫時(shí)的適應(yīng)度不高而被淘汰，于是算法很容易收斂到局部最優(yōu)解。SQGA的信息傳播結(jié)構(gòu)如圖1所示。

圖1 SQGA的信息傳播結(jié)構(gòu)

3 基于精英組的量子遺傳算法

3.1 設(shè)計(jì)思想

從前面的分析可以知道，每次進(jìn)化只使用一個(gè)染色體來指導(dǎo)整個(gè)種群是不合適的，這會(huì)導(dǎo)致其他染色體所帶有的合理信息不能在種群中保留，從而破壞了染色體的多樣性。本文對(duì)此進(jìn)行了改進(jìn)，提出了EQGA算法。EQGA使用多個(gè)染色體來指導(dǎo)群體的進(jìn)化，這樣既可以保證染色體的多樣性，算法也不容易收斂到局部解。EQGA的信息傳播結(jié)構(gòu)如圖2所示。

圖2 EQGA的信息傳播結(jié)構(gòu)

3.2 染色體精英組

在EQGA算法中，將這些最優(yōu)的染色體稱為染色體精英組。下面介紹精英染色體的產(chǎn)生、維護(hù)以及如何對(duì)種群的進(jìn)化發(fā)揮影響。

（1）精英組的產(chǎn)生

精英染色體也是由適應(yīng)度函數(shù)評(píng)判產(chǎn)生。對(duì)染色體進(jìn)行評(píng)估、測(cè)量之后，選擇適應(yīng)度最高的t個(gè)染色體加入精英組即可。

這里最主要的問題是t值的確定。如果t值過大，不僅計(jì)算產(chǎn)生精英組的開銷較大，算法的收斂速度也會(huì)變慢，反之，如果t值過小，算法又將收斂到局部最優(yōu)解。通過分析與實(shí)驗(yàn)后認(rèn)為，t值的大小與求解問題相關(guān)。如果解空間的局部最優(yōu)點(diǎn)很多，且幅度變化較大，那么算法陷入局部最優(yōu)的可能性較大，需要適當(dāng)增大t的值；如果解空間的變化較為平緩，且局部最優(yōu)點(diǎn)不多，那么t的值可以相對(duì)減小。

（2）精英組的維護(hù)

由于種群中的染色體在每次迭代中都會(huì)發(fā)生更新，因此精英組中的成員也應(yīng)該同步進(jìn)行更新，以反映種群的進(jìn)化。EQGA算法的精英組中一直保留了t條染色體。每次評(píng)估完染色體之后，EQGA首先選出t條染色體，然后與精英組中的t條染色體比較，從中選擇最優(yōu)的t條予以保留。

（3）精英組對(duì)種群進(jìn)化的指導(dǎo)

EQGA的染色體更新也主要借助于量子旋轉(zhuǎn)操作實(shí)現(xiàn)。與SQGA不同的是，EQGA在選擇演化目標(biāo)時(shí)并不使用固定的一條染色體，而是從精英組中隨機(jī)選擇一條。這樣就保證了染色體的多樣性。

3.3 EQGA算法的流程

EQGA算法的流程如下。

（1）設(shè)置EQGA算法的參數(shù)，如迭代次數(shù)、變異概率、精英染色體數(shù)目t等。

（2）初始化種群。

（3）對(duì)所有染色體進(jìn)行評(píng)估測(cè)量，并更新精英組中的t條染色體。

（4）對(duì)每個(gè)染色體進(jìn)行量子旋轉(zhuǎn)更新操作。每次更新時(shí)，隨機(jī)從精英組的t條染色體中選取一條作為演化目標(biāo)。

（5）根據(jù)變異概率對(duì)所有染色體進(jìn)行量子變異操作。

（6）如果算法滿足終止條件，則程序運(yùn)行結(jié)束，否則返回步驟（3）。

可以看出，EQGA算法只是在更新精英組時(shí)計(jì)算量有所加大，但算法的復(fù)雜度并沒有增加。

4 EQGA算法在WMSN覆蓋優(yōu)化中的應(yīng)用

4.1 EQGA算法的應(yīng)用

為了驗(yàn)證EQGA算法的性能，本文將其應(yīng)用于無線多媒體傳感器網(wǎng)絡(luò)中的覆蓋優(yōu)化問題。

WMSN是一種具有廣泛用途的網(wǎng)絡(luò)，它可以部署在多種場(chǎng)合，對(duì)各種環(huán)境信息進(jìn)行采集和監(jiān)控。WMSN主要由多媒體節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)都有一定的監(jiān)控范圍。通常這個(gè)范圍可以用一個(gè)扇形表示，如圖3所示。其中，O表示傳感器節(jié)點(diǎn)，扇形半徑R稱為監(jiān)控距離，扇形角α稱為監(jiān)控視角，扇形對(duì)角線稱為監(jiān)控方向。一般情況下，網(wǎng)絡(luò)部署后節(jié)點(diǎn)位置不可再發(fā)生變化，但節(jié)點(diǎn)的監(jiān)控方向可以通過旋轉(zhuǎn)攝像頭來進(jìn)行調(diào)整。

由于部署的不合理和節(jié)點(diǎn)電量耗盡等原因，網(wǎng)絡(luò)中會(huì)出現(xiàn)大量的監(jiān)控重疊與監(jiān)控盲區(qū)。前者浪費(fèi)了節(jié)點(diǎn)的監(jiān)控能力，后者降低了網(wǎng)絡(luò)的監(jiān)控質(zhì)量，這兩種情況都應(yīng)當(dāng)避免。為此，需要對(duì)網(wǎng)絡(luò)進(jìn)行覆蓋優(yōu)化處理，以擴(kuò)大網(wǎng)絡(luò)的監(jiān)控范圍。

在不增加節(jié)點(diǎn)的情況下，覆蓋優(yōu)化的主要手段就是通過調(diào)整各節(jié)點(diǎn)的監(jiān)控方向來實(shí)現(xiàn)，其原理如圖4所示。

使用EQGA算法來求解各節(jié)點(diǎn)的最佳監(jiān)控方向。

編碼時(shí)，每個(gè)基因就代表一個(gè)節(jié)點(diǎn)的監(jiān)控方向。因此，染色體一共由n個(gè)基因組成，其中，n是網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。

在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)，結(jié)合具體問題，使用網(wǎng)絡(luò)覆蓋率來評(píng)價(jià)染色體的性能。由于重疊區(qū)域的形狀為非規(guī)則圖形，因此直接計(jì)算覆蓋率很困難。所以進(jìn)行了近似處理，在監(jiān)控區(qū)域中以等距離的方式抽取離散點(diǎn)，如圖5所示。

設(shè)一共取了psum個(gè)點(diǎn)，其中被扇形覆蓋了pcoverd個(gè)，則網(wǎng)絡(luò)的覆蓋率為：

式（5）為染色體的適應(yīng)度評(píng)估函數(shù)。

4.2 仿真測(cè)試

在MATLAB環(huán)境下進(jìn)行了仿真測(cè)試。首先隨機(jī)生成了多組WMSN測(cè)試場(chǎng)景用例。在這些測(cè)試用例中，場(chǎng)景大小300×300 m2固定不變，節(jié)點(diǎn)的感知半徑為40 m，視角大小為 π/6，節(jié)點(diǎn)數(shù)量分別為 30、60、90、120、150、180和 210個(gè)。對(duì)于每個(gè)測(cè)試用例，分別使用GA、SQGA和EQGA進(jìn)行監(jiān)控方向的最優(yōu)解計(jì)算，并記錄平均值和最優(yōu)值。3種算法的相關(guān)設(shè)置如表1所示。

表1 算法參數(shù)

圖6是節(jié)點(diǎn)數(shù)為150個(gè)時(shí)，3種算法求出的最優(yōu)解比較，從圖中可以看出，EQGA算法的效果最好。

圖6中各算法最優(yōu)解的進(jìn)化過程如圖7所示。GA算法求出的解與SQGA接近，但算法收斂速度較慢。SQGA算法在開始階段的進(jìn)化速度很快，但是40次迭代之后進(jìn)化速度明顯降低，說明此時(shí)SQGA算法停滯于局部最優(yōu)解，無法再找到更好的結(jié)果。EQGA算法的進(jìn)化速度優(yōu)于GA，且程序運(yùn)行至150次迭代時(shí)最優(yōu)解仍在更新，因此它找到的解最好。這主要是因?yàn)樗褂昧硕鄠€(gè)最優(yōu)染色體來指導(dǎo)群體的進(jìn)化，算法不容易早熟。

3種算法更全面的比較如圖8和圖9所示。圖8是3種算法每個(gè)場(chǎng)景的平均結(jié)果演示，圖9是3種算法每個(gè)場(chǎng)景的最優(yōu)結(jié)果演示。通過比較可以發(fā)現(xiàn)，EQGA算法求出的解比GA算法和SQGA算法都要好。

5 結(jié)束語

標(biāo)準(zhǔn)量子遺傳算法使用一個(gè)染色體來指導(dǎo)種群的進(jìn)化，算法的收斂速度較快，但極易陷入局部最優(yōu)解，本文針對(duì)這個(gè)缺陷進(jìn)行了研究，提出了改進(jìn)的量子遺傳算法EQGA。EQGA使用一組染色體來指導(dǎo)種群的進(jìn)化，能夠很好地保持種群的多樣性，因而求出的解更優(yōu)。對(duì)于WMSN覆蓋優(yōu)化問題的測(cè)試表明，EQGA算法達(dá)到了設(shè)計(jì)的目標(biāo)。

1 Barolli A,Takizawa M,Xhafa F,et al.Application of genetic algorithms for QoS routing in mobile ad-hoc networks:a survey.In:Proceedings of International Conference on Broadband,Wireless Computing Communication and Applications,Fukuoka,Japan,2010

2 Knysh D S,Kureichik V M.Parallel genetic algorithms:a survey and problem state of the art.International Journal of Computer and Systems Sciences,2010,49(4):579～589

3 Li,Nan,Luo Yi.An improved co-evolution genetic algorithm for combinatorial optimization problems.Lecture Notes in Computer Science,2011,6 728(1):506～513

4 郭鵬,程文明,張則強(qiáng).求解具有惡化工件單機(jī)調(diào)度問題的改進(jìn)遺傳算法.西南交通大學(xué)學(xué)報(bào),2011,46(3):506～511

5 Han K H.Genetic quantum algorithm and its application to combinatorial optimization problem.In:IEEE Proceedings of the 2000 Congress on Evolutionary Computation, LA Jolla,California,USA,2000

6 Xiao J,Yan Y P,Zhang J,et al.A quantum-inspired genetic algorithm for k-means clustering.Expert Systems with Applications,2010,37(7):4 966～4 973

7 Gu J W,Gu M Z,Cao C W,et al.A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem.Computers&Operations Research,2010,37(5):927～937