李盼池,楊淑云,劉顯德,潘俊輝,肖 紅,曹茂俊

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,大慶 163318)

量子衍生布谷鳥搜索算法①

李盼池,楊淑云,劉顯德,潘俊輝,肖 紅,曹茂俊

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,大慶 163318)

為提高布谷鳥搜索算法的尋優(yōu)能力,通過在經(jīng)典布谷鳥搜索算法中入量子計(jì)算機(jī)制,提出了一種量子衍生布谷鳥搜索算法.該算法采用量子比特編碼個(gè)體,采用泡利矩陣確定旋轉(zhuǎn)軸,采用Levy飛行原理確定旋轉(zhuǎn)角度,采用量子比特在Bloch球面上的繞軸旋轉(zhuǎn)實(shí)現(xiàn)個(gè)體更新.標(biāo)準(zhǔn)函數(shù)極值優(yōu)化的實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)布谷鳥搜索算法相比,該算法的搜索能力確有明顯提升.

仿生智能優(yōu)化;群智能優(yōu)化;布谷鳥算法;量子衍生優(yōu)化;算法設(shè)計(jì)

2009年,英國劍橋大學(xué)學(xué)者提出了一種新的啟發(fā)式智能優(yōu)化算法:布谷鳥搜索算法(cuckoo search algorithm,CS)[1].該算法基于布谷鳥尋找鳥巢放置鳥蛋的行為和鳥類飛行的Levy行為建立搜索機(jī)制.近幾年來,國內(nèi)學(xué)者已對(duì)布谷鳥算法展開深入研究.2011年,西安工程大學(xué)王凡提出了基于高斯擾動(dòng)的布谷鳥算法[2],有效提高了算法的收斂速度.2012年,中國礦業(yè)大學(xué)的李明提出了布谷鳥和差分進(jìn)化相融合的優(yōu)化算法[3],有效提高了原算法的優(yōu)化能力.隨后在理論算法方面,先后提出了基于細(xì)菌覓食行為中的趨化搜索策略的布谷鳥全局優(yōu)化算法[4],具有動(dòng)態(tài)慣性策略的布谷鳥搜索算法[5],多目標(biāo)布谷鳥搜索算法[6,7],基于多種群粒子群和布谷鳥搜索的聯(lián)合尋優(yōu)算法[8],基于梯度的自適應(yīng)快速布谷鳥搜索算法[9],基于種群特征反饋的布谷鳥搜索算法[10].在算法應(yīng)用方面,布谷鳥搜索算法已成功應(yīng)用在飛行器容錯(cuò)控制[11],人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練[12],水庫優(yōu)化調(diào)度[13],干擾資源分配[14]等眾多應(yīng)用領(lǐng)域.

盡管后前國內(nèi)外文獻(xiàn)已提出多種有關(guān)布谷鳥搜索算法性能的改進(jìn)策略,然而有關(guān)量子計(jì)算與布谷鳥搜索的融合研究尚不多見.本文提出一種新穎的量子衍生布谷鳥搜索算法,其編碼機(jī)制為采用帶兩個(gè)相位參數(shù)量子比特編碼個(gè)體,尋優(yōu)機(jī)制為采用量子比特在Bloch球面上的繞軸旋轉(zhuǎn)模擬布谷鳥的搜索行為.其中旋轉(zhuǎn)角度采用Levy飛行策略決定.采用CEC2013的28個(gè)標(biāo)準(zhǔn)測試函數(shù)做為優(yōu)化對(duì)象,仿真結(jié)果驗(yàn)證了提出算法的優(yōu)越性.

1 布谷鳥搜索算法

標(biāo)準(zhǔn)布谷鳥搜索算法是通過模擬布谷鳥借窩產(chǎn)蛋的繁殖習(xí)性有效求解最優(yōu)化問題的全局搜索算法.該算法中,一個(gè)鳥巢代表一個(gè)候選解,首先基于當(dāng)前解采用Levy飛行得到新解,然后根據(jù)鳥蛋被發(fā)現(xiàn)的概率丟棄一些現(xiàn)有的解,并重新生成相同數(shù)后的新解.最后進(jìn)行種群評(píng)估,更新全局最優(yōu)解,完成一次迭代.

布谷鳥搜索算法采用Levy飛行理論產(chǎn)生新解,具體方法為:

其中a0是常數(shù)(通常取0.01),Xb是當(dāng)前最優(yōu)解.

綜合式(1)-式(4),在 Levy 隨機(jī)搜索中,布谷鳥算法采用下式生成新解:

按發(fā)現(xiàn)概率丟棄部分解之后,采用隨機(jī)游走方式重新生成與丟棄數(shù)后相同的新解:

2 量子衍生布谷鳥搜索算法

本節(jié)提出一種量子衍生布谷鳥搜索算法(Quantum Inspired Cuckoo Search Algorithm,QICS),包括個(gè)體的編碼機(jī)制和搜索機(jī)制兩部分,下面分別予以介紹.

2.1 QICS的編碼機(jī)制

(1)基于量子比特的鳥巢編碼

在QICS中,鳥巢采用基于Bloch球面描述的量子比特編碼.設(shè)鳥巢數(shù)量為 N,空間維數(shù)為 D,記第 t代種群為,則第 i個(gè)鳥巢的初始編碼可寫為:

(2)量子鳥巢到經(jīng)典鳥巢的變換

對(duì)于量子比特編碼的鳥巢,只有轉(zhuǎn)換為具體的數(shù)值向量才能評(píng)價(jià)解的優(yōu)劣,這可以通過對(duì)量子鳥巢的投影測量及解空間變換獲得.具體方法為首先采用泡利矩陣對(duì)量子鳥巢實(shí)施投影測量得到Bloch球面上的坐標(biāo)鳥巢,然后通過解空間變換,將這些坐標(biāo)鳥巢映射為具體的鳥巢位置.泡利矩陣的定義式為:

(3)坐標(biāo)鳥巢的解空間變換

在QICS中,每個(gè)量子鳥巢都對(duì)應(yīng)到三個(gè)坐標(biāo)鳥巢,然而這三個(gè)坐標(biāo)鳥巢并不是彼此獨(dú)立的.這是因?yàn)槿咧g存在的約束關(guān)系.因此若一組坐標(biāo)(例如xij)較優(yōu),則另外兩組(yij,zij)一般會(huì)較差.因此在QICS中,對(duì)于第i個(gè)量子鳥巢測量之后得到的三個(gè)坐標(biāo)鳥巢我們只采用

2.2 QICS的搜索機(jī)制

在QICS中,搜索機(jī)制采用量子比特在Bloch球面上的繞軸旋轉(zhuǎn)實(shí)現(xiàn),其中旋轉(zhuǎn)角度采用Levy飛行理論決定,旋轉(zhuǎn)軸采用泡利矩陣決定.具體旋轉(zhuǎn)方法如下.

(1)基于Levy飛行理論產(chǎn)生新解

根據(jù)量子計(jì)算原理,旋轉(zhuǎn)算子為一個(gè)二維酉矩陣,該矩陣由旋轉(zhuǎn)軸、旋轉(zhuǎn)角度共同決定.

其中a0為控制參數(shù)(通常取0.1),為服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)按式(4)計(jì)算.

其中t為迭代步數(shù).

(2)基于發(fā)現(xiàn)概率的拋棄解的補(bǔ)充

在QICS中,依鳥巢被宿主發(fā)現(xiàn)的概率舍棄一些解,同時(shí)補(bǔ)充相同數(shù)量的新解,以保持種群規(guī)模不變.這一過程本質(zhì)上是一種類似于差分進(jìn)化策略的局部搜索.具體實(shí)現(xiàn)方法為,首先生成一個(gè)均勻分布的隨機(jī)數(shù),若該隨機(jī)數(shù)小于發(fā)現(xiàn)概率,則拋棄當(dāng)前解,同時(shí)補(bǔ)充新解.補(bǔ)充方法如下:

2.3 QICS的終止條件

關(guān)于群智能優(yōu)化算法的終止條件,通常有多種.例如精度控制:當(dāng)優(yōu)化結(jié)果達(dá)到某一精度閾值,算法終止;誤差控制,當(dāng)優(yōu)化結(jié)果與精確結(jié)果的絕對(duì)誤差小于給定閾值,算法終止;進(jìn)化速度控制:若連續(xù)若干代優(yōu)化結(jié)果無變化,算法終止;步數(shù)控制:若尋優(yōu)步數(shù)達(dá)到限定步數(shù),算法終止.本文提出的QICS采用步數(shù)控制作為終止條件.

2.4 QICS的實(shí)施方案

關(guān)于本文提出的QICS,具體實(shí)施方案如下.

Step1.初始化:鳥蛋被巢主鳥發(fā)現(xiàn)的概率 Pa;種群規(guī)模 NP;空間維數(shù) D;限度步數(shù) M;初始種群.

Step2.計(jì)算目標(biāo)函數(shù)值,記錄最優(yōu)解,置步數(shù) t=0.

Step3.主循環(huán)開始

Step3.1.所有個(gè)體執(zhí)行Levy飛行;

Step3.2.所有個(gè)體按概率Pa替換為新解;

Step3.3.更新全局最優(yōu)解;t=t+1;若 t>M,轉(zhuǎn)Step4;否則轉(zhuǎn) Step3.1.

Step4.保存全局最優(yōu)解,結(jié)束.

3 對(duì)比實(shí)驗(yàn)

3.1 測試函數(shù)

采用CEC2013定義的28個(gè)標(biāo)準(zhǔn)函數(shù)[16]作為優(yōu)化對(duì)象,如表1所示.其中(S)表示該函數(shù)的變量是可分離的,(N)表示變量是不可分離的,n表示該函數(shù)由其他n個(gè)基本函數(shù)復(fù)合而成,所有函數(shù)均為極小值優(yōu)化.

3.2 對(duì)比方案

為體現(xiàn)所提出的QICS算法的優(yōu)良性能,所有函數(shù)的優(yōu)化結(jié)果將與普通布谷鳥搜索算法(CS)[1]、基于高斯擾動(dòng)的布谷鳥搜索算法(Gauss-based Cuckoo Search Algorithm,GCS)[2],混合 CS 算法的 DE 算法(CSDE)[3]進(jìn)行對(duì)比.為保證對(duì)比結(jié)果客觀公正,四種算法采用相同的種群規(guī)模.考慮到群智能優(yōu)化算法具有隨機(jī)性,為盡量提高對(duì)比結(jié)果的可信度,所有函數(shù)的維數(shù)均取D=30維,且每個(gè)函數(shù)均用4種算法各自獨(dú)立優(yōu)化30次,取30次優(yōu)化的平均結(jié)果作為對(duì)比指標(biāo).

3.3 參數(shù)設(shè)置

關(guān)于本文提出的QICS,除入量子計(jì)算機(jī)制外,并未增加新的控制參數(shù),其控制參數(shù)個(gè)數(shù)與普通CS是相同的.關(guān)于這些算法的參數(shù)設(shè)置:發(fā)現(xiàn)概率Pa=0.25;種群規(guī)模NP=50;空間維數(shù)D=30;CS-DE中的交叉概率Pc=0.9,加權(quán)因子F=0.5.

3.4 對(duì)比結(jié)果

由于本文提出的QICS,需要計(jì)算旋轉(zhuǎn)矩陣,計(jì)算量較大,因此首先考察相同迭代步數(shù)下QICS與CS的優(yōu)化性能對(duì)比.迭代步數(shù)取1000,每個(gè)函數(shù)采用兩種算法分別優(yōu)化30次的平均結(jié)果對(duì)比如表2所示.

在表2中,粗體數(shù)字表示該結(jié)果優(yōu)于對(duì)比算法的結(jié)果.由此可知,全部 28 個(gè)函數(shù)中,QICS 有 27 個(gè)函數(shù)的優(yōu)化結(jié)果優(yōu)于CS,只有第15個(gè)函數(shù)的優(yōu)化結(jié)果劣于CS.實(shí)驗(yàn)結(jié)果充分展示了QICS的優(yōu)勢.以函數(shù)5、8、10、24為例,兩種算法30次優(yōu)化的平均結(jié)果隨迭代步數(shù)的變化情況如圖1所示.

表2 QICS和CS每個(gè)函數(shù)30次優(yōu)化的平均結(jié)果對(duì)比

圖1 兩種算法30次優(yōu)化的平均結(jié)果對(duì)比

為充分驗(yàn)證QICS的優(yōu)勢,有必要在相同運(yùn)行時(shí)間下對(duì)比優(yōu)化結(jié)果.因此,在下面的仿真中,在保持QICS迭代步數(shù)不變(仍然為1000步)的前提下,將CS、GCS、CS-DE三種算法的迭代步數(shù)均設(shè)為5000步,然后將每種算法分別獨(dú)立運(yùn)行30次,四種算法的平均結(jié)果對(duì)比如表3所示.

表3 四種算法每個(gè)函數(shù)30次優(yōu)化的平均結(jié)果對(duì)比

在表3中,QICS列的粗體數(shù)字表示該結(jié)果是四種算法中最優(yōu)的.而其他三列中的粗體數(shù)字表示該結(jié)果優(yōu)于QICS算法.由此可知,QICS優(yōu)于CS的函數(shù)個(gè)數(shù)為24個(gè),優(yōu)于GCS的函數(shù)個(gè)數(shù)為22個(gè),優(yōu)于CSDE的函數(shù)個(gè)數(shù)為20個(gè).實(shí)驗(yàn)結(jié)果表明QICS明顯優(yōu)于三種對(duì)比算法.

3.5 對(duì)結(jié)果的分析

在28個(gè)測試函數(shù)中,前5個(gè)函數(shù)為單峰函數(shù),這類函數(shù)尋優(yōu)難度較低,除變量不可分離的F2外,對(duì)于其他4個(gè),QICS均優(yōu)于對(duì)比算法.對(duì)于15個(gè)基本多峰函數(shù)函數(shù)F6-F20,除F11和F17外都是變量不可分離的.這些函數(shù)尋優(yōu)難度較大,除 F14-F16 外,對(duì)于其他12個(gè),QICS均優(yōu)于對(duì)比算法.對(duì)于最后8個(gè)變量不可分離的復(fù)合函數(shù),尋優(yōu)難度最大,此時(shí)QICS仍有4個(gè)函數(shù)優(yōu)于對(duì)比算法.實(shí)驗(yàn)結(jié)果進(jìn)一步揭示了量子計(jì)算機(jī)制的入對(duì)尋優(yōu)能力提高的促進(jìn)作用.

QICS的優(yōu)良性能在于其編碼方式和尋優(yōu)機(jī)制.首先,基于Bloch球面描述的量子比特的編碼機(jī)制,將優(yōu)化變量的每一維數(shù)值,都映射為Bloch球面上的某一點(diǎn).這樣就將傳統(tǒng)方法中優(yōu)化變量在優(yōu)化空間每一維上的線性搜索,轉(zhuǎn)化為Bloch球面上的搜索.根據(jù)Bloch球面性質(zhì),優(yōu)化空間中全局最優(yōu)解每一維的數(shù)值,都對(duì)應(yīng)于Bloch球面上的一個(gè)圓周.只要搜索到該圓周上的任意一點(diǎn),都等價(jià)于找到了該維的全局最優(yōu)解.因此這種編碼方式在一定程度上提高了QICS獲得全局最優(yōu)解的概率.第二,QICS的搜索機(jī)制采用了量子比特繞軸旋轉(zhuǎn)的方法,這種方法可以自動(dòng)實(shí)現(xiàn)量子比特的兩個(gè)相位參數(shù)θ和的最佳匹配,從而保證了量子比特在Bloch球面上沿著最短路徑向著目標(biāo)位置逼近,而基于Levy飛行理論的旋轉(zhuǎn)角度確定方法,有效提高了種群的多樣性,一定程度上可以避免早熟收斂,從以進(jìn)一步提升了QICS的搜索能力.

4 結(jié)論

經(jīng)典布谷鳥搜索算法的搜索能力有待于進(jìn)一步提高.本文嘗試將量子計(jì)算機(jī)制入經(jīng)典布谷鳥搜索算法,用量子比特編碼鳥巢位置,用量子比特在Bloch球面上的繞軸旋轉(zhuǎn)代替經(jīng)典布谷鳥搜索算法在優(yōu)化空間中的隨機(jī)游動(dòng),以期較大幅度地提高其優(yōu)化能力.實(shí)驗(yàn)結(jié)果表明,這種嘗試是成功的,新算法的確呈現(xiàn)出明顯優(yōu)于原算法的性能,從而揭示出,在原算法中入量子計(jì)算機(jī)制,是提高其優(yōu)化性能的有效途徑.

1 Yang XS,Deb S.Cuckoo search via Levy flights.Proc.of World Congress on Nature &Biologically Inspired Computing.India.2009.210–214.

2 王凡,賀興時(shí),王燕.基于高斯擾動(dòng)的布谷鳥搜索算法.西安工程大學(xué)學(xué)報(bào),2011,25(4):566–569.

3 李明,曹德欣.混合CS算法的DE算法.計(jì)算機(jī)工程與應(yīng)用,2012,49(9):57–60.

4 馬衛(wèi),孫正興.采用搜索趨化策略的布谷鳥全局優(yōu)化算法.電子學(xué)報(bào),2015,43(12):2429–2439.[doi:10.3969/j.issn.0372-2112.2015.12.013]

5 周歡,李煜.具有動(dòng)態(tài)慣性權(quán)重的布谷鳥搜索算法.智能系統(tǒng)學(xué)報(bào),2015,10(4):645–651.

6 賀興時(shí),李娜,楊新社,等.多目標(biāo)布谷鳥搜索算法.系統(tǒng)仿真學(xué)報(bào),2015,27(4):731–737.

7 楊輝華,謝譜模,張曉鳳,等.求解多目標(biāo)優(yōu)化問題的改進(jìn)布谷鳥搜索算法.浙江大學(xué)學(xué)報(bào)(工學(xué)版),2015,49(8):1600–1608.

8 高云龍,閆鵬.基于多種群粒子群算法和布谷鳥搜索的聯(lián)合尋優(yōu)算法.控制與決策,2016,31(4):601–608.

9 李榮雨,劉洋.基于梯度的自適應(yīng)快速布谷鳥搜索算法.運(yùn)籌學(xué)學(xué)報(bào),2016,20(3):45–56.

10 賈云璐,劉勝,宋穎慧.基于種群特征反饋的布谷鳥搜索算法.控制與決策,2016,31(6):969–975.

11 董朝陽,路遙,江未來,等.基于布谷鳥搜索算法的一類變體飛行器容錯(cuò)控制.航空學(xué)報(bào),2015,36(6):2047–2054.

12 倪百秀,張翠翠,周本達(dá).基于改進(jìn)布谷鳥搜索的人工神經(jīng)網(wǎng)絡(luò)及其性能仿真.江漢大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,43(1):41–50.

13 明波,黃強(qiáng),王義民,等.基于改進(jìn)布谷鳥算法的梯級(jí)水庫優(yōu)化調(diào)度研究.水利學(xué)報(bào),2015,46(3):341–349.

14 李東升,高揚(yáng),雍愛霞.基于改進(jìn)離散布谷鳥算法的干擾資源分配研究.電子與信息學(xué)報(bào),2016,38(4):899–905.

15 Benenti G,Casati G,Strini G.Principles of quantum computation and information (Volume I:Basic Concepts).Singapore:World Scientific Publishing,2004:100–112.

16 Liang JJ,Qu BY,Suganthan PN,et al.Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization.http://www3.ntu.edu.sg/home/EPNSugan/index_files/CEC2013/Definitions%20of%2 0%20CEC%2013%20benchmark%20suite%200117.pdf.

Quantum-Inspired Cuckoo Search Algorithm

LI Pan-Chi,YANG Shu-Yun,LIU Xian-De,PAN Jun-Hui,XIAO Hong,CAO Mao-Jun

(School of Computer &Information Technology,Northeast Petroleum University,Daqing 163318,China)

In order to improve the search ability of the cuckoo search algorithm,this paper proposes a quantum-inspired cuckoo search algorithm by introducing the quantum computing mechanism into the classical cuckoo search algorithm..In the proposed algorithm,the qubits are used to encode individuals,and the Pauli matrixes are employed to determine rotation axis.The Levy flight principle is applied to obtain rotation angle,and the rotation of the qubits on the Bloch sphere is used to update the individuals.The experimental results of extreme optimization of benchmark test functions show that the proposed algorithm is obviously superior to the classical cuckoo search algorithm in optimization ability.

bionic intelligent optimization;swarm intelligence optimization;cuckoo algorithm;quantum-inspired optimization;algorithm design

李盼池,楊淑云,劉顯德,潘俊輝,肖紅,曹茂俊.量子衍生布谷鳥搜索算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):122–127.http://www.c-sa.org.cn/1003-3254/5915.html

①基金項(xiàng)后:黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)后(12541059)

2016-12-19;采用時(shí)間:2017-01-05