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

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

(東北石油大學 計算機與信息技術學院,大慶 163318)

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

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

(東北石油大學 計算機與信息技術學院,大慶 163318)

為提高布谷鳥搜索算法的尋優能力,通過在經典布谷鳥搜索算法中入量子計算機制,提出了一種量子衍生布谷鳥搜索算法.該算法采用量子比特編碼個體,采用泡利矩陣確定旋轉軸,采用Levy飛行原理確定旋轉角度,采用量子比特在Bloch球面上的繞軸旋轉實現個體更新.標準函數極值優化的實驗結果表明,與傳統布谷鳥搜索算法相比,該算法的搜索能力確有明顯提升.

仿生智能優化;群智能優化;布谷鳥算法;量子衍生優化;算法設計

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

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

1 布谷鳥搜索算法

標準布谷鳥搜索算法是通過模擬布谷鳥借窩產蛋的繁殖習性有效求解最優化問題的全局搜索算法.該算法中,一個鳥巢代表一個候選解,首先基于當前解采用Levy飛行得到新解,然后根據鳥蛋被發現的概率丟棄一些現有的解,并重新生成相同數后的新解.最后進行種群評估,更新全局最優解,完成一次迭代.

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

其中a0是常數(通常取0.01),Xb是當前最優解.

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

按發現概率丟棄部分解之后,采用隨機游走方式重新生成與丟棄數后相同的新解:

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

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

2.1 QICS的編碼機制

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

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

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

對于量子比特編碼的鳥巢,只有轉換為具體的數值向量才能評價解的優劣,這可以通過對量子鳥巢的投影測量及解空間變換獲得.具體方法為首先采用泡利矩陣對量子鳥巢實施投影測量得到Bloch球面上的坐標鳥巢,然后通過解空間變換,將這些坐標鳥巢映射為具體的鳥巢位置.泡利矩陣的定義式為:

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

在QICS中,每個量子鳥巢都對應到三個坐標鳥巢,然而這三個坐標鳥巢并不是彼此獨立的.這是因為三者之間存在的約束關系.因此若一組坐標(例如xij)較優,則另外兩組(yij,zij)一般會較差.因此在QICS中,對于第i個量子鳥巢測量之后得到的三個坐標鳥巢我們只采用

2.2 QICS的搜索機制

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

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

根據量子計算原理,旋轉算子為一個二維酉矩陣,該矩陣由旋轉軸、旋轉角度共同決定.

其中a0為控制參數(通常取0.1),為服從標準正態分布的隨機數按式(4)計算.

其中t為迭代步數.

(2)基于發現概率的拋棄解的補充

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

2.3 QICS的終止條件

關于群智能優化算法的終止條件,通常有多種.例如精度控制:當優化結果達到某一精度閾值,算法終止;誤差控制,當優化結果與精確結果的絕對誤差小于給定閾值,算法終止;進化速度控制:若連續若干代優化結果無變化,算法終止;步數控制:若尋優步數達到限定步數,算法終止.本文提出的QICS采用步數控制作為終止條件.

2.4 QICS的實施方案

關于本文提出的QICS,具體實施方案如下.

Step1.初始化:鳥蛋被巢主鳥發現的概率 Pa;種群規模 NP;空間維數 D;限度步數 M;初始種群.

Step2.計算目標函數值,記錄最優解,置步數 t=0.

Step3.主循環開始

Step3.1.所有個體執行Levy飛行;

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

Step3.3.更新全局最優解;t=t+1;若 t>M,轉Step4;否則轉 Step3.1.

Step4.保存全局最優解,結束.

3 對比實驗

3.1 測試函數

采用CEC2013定義的28個標準函數[16]作為優化對象,如表1所示.其中(S)表示該函數的變量是可分離的,(N)表示變量是不可分離的,n表示該函數由其他n個基本函數復合而成,所有函數均為極小值優化.

3.2 對比方案

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

3.3 參數設置

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

3.4 對比結果

由于本文提出的QICS,需要計算旋轉矩陣,計算量較大,因此首先考察相同迭代步數下QICS與CS的優化性能對比.迭代步數取1000,每個函數采用兩種算法分別優化30次的平均結果對比如表2所示.

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

表2 QICS和CS每個函數30次優化的平均結果對比

圖1 兩種算法30次優化的平均結果對比

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

表3 四種算法每個函數30次優化的平均結果對比

在表3中,QICS列的粗體數字表示該結果是四種算法中最優的.而其他三列中的粗體數字表示該結果優于QICS算法.由此可知,QICS優于CS的函數個數為24個,優于GCS的函數個數為22個,優于CSDE的函數個數為20個.實驗結果表明QICS明顯優于三種對比算法.

3.5 對結果的分析

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

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

4 結論

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

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

2 王凡,賀興時,王燕.基于高斯擾動的布谷鳥搜索算法.西安工程大學學報,2011,25(4):566–569.

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

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

5 周歡,李煜.具有動態慣性權重的布谷鳥搜索算法.智能系統學報,2015,10(4):645–651.

6 賀興時,李娜,楊新社,等.多目標布谷鳥搜索算法.系統仿真學報,2015,27(4):731–737.

7 楊輝華,謝譜模,張曉鳳,等.求解多目標優化問題的改進布谷鳥搜索算法.浙江大學學報(工學版),2015,49(8):1600–1608.

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

9 李榮雨,劉洋.基于梯度的自適應快速布谷鳥搜索算法.運籌學學報,2016,20(3):45–56.

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

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

12 倪百秀,張翠翠,周本達.基于改進布谷鳥搜索的人工神經網絡及其性能仿真.江漢大學學報(自然科學版),2015,43(1):41–50.

13 明波,黃強,王義民,等.基于改進布谷鳥算法的梯級水庫優化調度研究.水利學報,2015,46(3):341–349.

14 李東升,高揚,雍愛霞.基于改進離散布谷鳥算法的干擾資源分配研究.電子與信息學報,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

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

①基金項后:黑龍江省教育廳科學技術研究項后(12541059)

2016-12-19;采用時間:2017-01-05