量子衍生螢火蟲搜索算法?

劉顯德于瑞芳李濱旭趙思遠李盼池

（東北石油大學(xué)計算機與信息技術(shù)學(xué)院大慶163318）

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

仿生智能優(yōu)化；群智能優(yōu)化；螢火蟲算法；量子衍生優(yōu)化；算法設(shè)計

Class NumberTP183

1 引言

2008年，英國劍橋大學(xué)學(xué)者提出了一種新的啟發(fā)式智能優(yōu)化算法：螢火蟲搜索算法（Firefly Search Algorithm，F(xiàn)A）［1］。它源于對螢火蟲群體行為的簡化和模擬，是一種高級啟發(fā)式算法。該算法通過螢火蟲個體之間的相互吸引達到尋優(yōu)的目的，是一種基于群體搜索的隨機優(yōu)化算法，具有概念簡單、結(jié)構(gòu)清晰、控制參數(shù)少、易于實現(xiàn)等優(yōu)點。目前對螢火蟲算法的理論研究尚處于初級階段。在算法的改進方面，文獻［2］提出了變步長螢火蟲算法，改進了標準螢火蟲算法在所有迭代步中采用固定步長的缺陷；文獻［3］提出了控制參數(shù)的自適應(yīng)改進策略，有效解決了控制參數(shù)難以合理確定的問題；文獻［4］提出了基于搜索空間對稱尋優(yōu)的改進策略，在一定程度上提升了算法的收斂速度；文獻［5］提出了帶有鄰域搜索策略的改進方法，有效提升了優(yōu)化解的精度。在與其他算法的融合方面，文獻［6～7］分別提出了與模糊集、粗糙集融合的新方法。在算法的應(yīng)用方面，已分別應(yīng)用于分類器集成修剪［8］、圖像檢索［9］、水位波動預(yù)報［10］、心臟病預(yù)測［11］、支持向量機參數(shù)優(yōu)化［12］、蛋白質(zhì)網(wǎng)絡(luò)動態(tài)預(yù)測［13］等許多不同領(lǐng)域，并取得了良好的優(yōu)化效果。

盡管目前國內(nèi)外文獻已提出多種有關(guān)螢火蟲搜索算法性能的改進策略，然而有關(guān)量子計算與螢火蟲搜索的融合研究尚不多見。本文提出一種新穎的量子衍生螢火蟲搜索算法，其編碼機制為采用帶兩個相位參數(shù)量子比特編碼個體，尋優(yōu)機制為采用量子比特在Bloch球面上的繞軸旋轉(zhuǎn)模擬螢火蟲的搜索行為。采用CEC2013的28個標準測試函數(shù)做為優(yōu)化對象，仿真結(jié)果驗證了提出算法的優(yōu)越性。

本文提出一種新穎的基于NEQR描述的量子彩色圖像加密方案。首先將彩色圖像采用NEQR模型描述，采用24個量子比特描述像素的顏色值，然后采用受控旋轉(zhuǎn)門使顏色比特隨機旋轉(zhuǎn)，進而實現(xiàn)量子圖像的加密。盡管加密過程較為簡單，然而經(jīng)典計算機上的仿真結(jié)果表明，與其他同類算法比較，提出方案的加密效果是較為理想的。

2 螢火蟲搜索算法

螢火蟲搜索算法的核心思想是螢火蟲受大于自身亮度的同伴吸引，進而向著同伴前進，借以提高自身亮度，以期找到最優(yōu)的空間位置。為便于描述，首先給出不同螢火蟲之間相對亮度和吸引度的定義。

定義1相對亮度：螢火蟲i對螢火蟲j的相對亮度為

式中Ii為螢火蟲i的絕對亮度，具體數(shù)值等于螢火蟲i所處位置的目標函數(shù)值，γ為熒光吸收系數(shù)，可設(shè)為某一常數(shù)，rij=||xi-xj||為個體i和j之間的距離。式（1）表明，熒光亮度會隨著距離的增加而衰減，這恰好模擬了熒光在空氣介質(zhì)中傳輸時被吸收的行為。

定義2個體吸引度：個體i對j的吸引度定義為下式

式中β0為最大吸引力，即在光源處（rij=0）螢火蟲的吸引力。通?？梢匀ˇ?=1，γ和rij的含義同上。

在螢火蟲i的引力作用下，螢火蟲j向著i移動，并更新自身位置，具體更新方法如下式所示

式中t為迭代步數(shù)，xi和xj為個體i和j的位置向量，α∈(0, 1)為常數(shù)或隨迭代步數(shù)逐代減小，εj為隨機分布的隨機數(shù)向量，具體可取高斯分布或均勻分布。εj本質(zhì)上是一種變異行為，以增強種群多樣性防止早熟收斂。

3 量子衍生螢火蟲搜索算法

本節(jié)提出一種量子衍生螢火蟲搜索算法（Quantum Inspired Firefly Search Algorithm，QIFA），包括個體的編碼機制和搜索機制兩部分，下面分別予以介紹。

3.1 QIFA的編碼機制

1）基于量子比特的螢火蟲位置編碼

在QIFA中，螢火蟲的空間位置采用基于Bloch球面描述的量子比特編碼。設(shè)螢火蟲數(shù)目為N，空間維數(shù)為D，記第t代種群為P(t)=[p1(t), p2(t),…, pN(t)]T，則第i個螢火蟲位置pi(0)的初始編碼可寫為

2）量子個體到經(jīng)典個體的變換

對于采用量子比特編碼的螢火蟲，只有轉(zhuǎn)換為具體的數(shù)值向量才能評價位置（候選解）的優(yōu)劣，這可以通過對量子螢火蟲的投影測量及解空間變換獲得。具體方法為首先采用泡利矩陣對量子螢火蟲實施投影測量得到其在Bloch球面上的坐標位置，然后通過解空間變換，將這些坐標映射為該螢火蟲具體所在的空間位置。泡利矩陣的定義式為

對于第i個螢火蟲上的第j個量子比特φij，其投影測量計算式為

其中i=1, 2,…, N; j=1, 2,…, D。

此時，Xi=[xij]，Yi=[yij]，Zi=[zij]即為螢火蟲在Bloch球面上的坐標位置。

3）坐標位置的解空間變換

在QIFA中，每個量子螢火蟲都對應(yīng)到三個坐標位置，然而這三個坐標位置并不是彼此獨立的。這是因為三者之間存在++=1的約束關(guān)系。因此若一組坐標（例如xij）較優(yōu)，則另外兩組(yij,zij)一般會較差。因此在QIFA中，對于第i個量子螢火蟲測量之后得到的三個坐標位置Xi=[xij]，Yi=[yij]，Zi=[zij]，我們只采用Xi=[xij]。

由于xij∈[-1, 1]，因此需要進行解空間變換。記第j維優(yōu)化空間的取值區(qū)間為[Minj,Maxj]，則解空間變換如下式所示。

其中i=1, 2,…, N；j=1, 2,…, D。

此時[Xi1, Xi2, ... , XiD]即為第i只螢火蟲在尋優(yōu)空間的實際位置。

3.2QIFA的搜索機制

在QIFA中，搜索機制采用量子比特在Bloch球面上的繞軸旋轉(zhuǎn)實現(xiàn)，其中旋轉(zhuǎn)角度采用式（2）定義的個體吸引度計算，旋轉(zhuǎn)軸采用泡利矩陣決定。具體旋轉(zhuǎn)方法如下。

1）基于量子比特饒軸旋轉(zhuǎn)的位置更新

令φik(t)和φjk(t)分別為第i個螢火蟲和第j

個螢火蟲中第k個量子比特，在Bloch球面上的對應(yīng)點分別為Pik=[pikx, piky, pikz]和Pjk=[pjkx, pjky,pjkz]。若個體j優(yōu)于個體i，則使φik(t)向著φjk(t)移動。根據(jù)量子力學(xué)原理，量子比特在Bloch球面上的移動可以通過使其繞著某個軸旋轉(zhuǎn)實現(xiàn)。由文獻［14］可知，旋轉(zhuǎn)軸可按下式定義：

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

在QIFA中，旋轉(zhuǎn)角度采用式（2）定義的個體吸引度計算。令為Pik和Pjk之間的夾角，則φik(t)的旋轉(zhuǎn)角度可按下式設(shè)計：

其中β0為控制參數(shù)（通常取0.1），γ為常數(shù)，通常可取1.0。

至此，當(dāng)前量子比特φik(t)在Bloch球面上，繞軸Rij轉(zhuǎn)向目標比特φjk(t)的旋轉(zhuǎn)矩陣為

其中I為單位矩陣，σ=[σx, σy, σz]。

φik(t)轉(zhuǎn)向φjk(t)的旋轉(zhuǎn)操作為

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

在螢火蟲i上所有D個量子比特更新之后，進行投影測量、解空間變換、計算目標函數(shù)值。

2）基于量子比特隨機旋轉(zhuǎn)的局部搜索

在經(jīng)典螢火蟲算法的位置更新式（3）中的最后一項，實際上是也是一種局部搜索策略。在QIFA中，該策略可以用量子比特在Bloch球面上的隨機旋轉(zhuǎn)實現(xiàn)。對于每一個螢火蟲，首先繞著X軸、Y軸、Z軸之一（具體可隨機選擇）旋轉(zhuǎn)一個幅度逐代減小的隨機角度生成新個體，然后采用貪婪策略更新螢火蟲位置。下面給出具體的實現(xiàn)方法。

在Bloch球面上，量子比特繞X軸、Y軸、Z軸旋轉(zhuǎn)δ弧度的旋轉(zhuǎn)矩陣分別為

令φij(t)為第i個量子螢火蟲中第j個量子比特，首先按下式計算旋轉(zhuǎn)角度：其中Maxgen為限定迭代步數(shù)，θ0為轉(zhuǎn)角初值，rnd為區(qū)間（0，1）內(nèi)均勻分布的隨機數(shù)。

由式（15）可知，顯然，δij的幅度隨迭代步數(shù)逐代減小，這一方面體現(xiàn)了隨迭代步數(shù)的增加，局部開發(fā)能力的增強，同時也與普通FA位置更新式（3）中隨機項的作用是一致的。

然后在X軸、Y軸、Z軸之中隨機選擇一軸Rλ(δ)，λ=X或Y或Z，執(zhí)行旋轉(zhuǎn)操作其中t為迭代步數(shù)。

在螢火蟲i上所有D個量子比特全部更新之后，進行投影測量、解空間變換、計算目標函數(shù)值，最后采用貪婪策略實施螢火蟲i的更新。即若φi(t)優(yōu)于φi(t)則φi(t+1)=φi(t)，否則φi(t+1)=φi(t)。

3.3QIFA的終止條件

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

3.4QIFA的實施方案

關(guān)于本文提出的QIFA，具體實施方案如下。Step1初始化：種群規(guī)模N；空間維數(shù)D；限度步數(shù)Maxgen；控制參數(shù)β0、γ，轉(zhuǎn)角初值θ0，個體初始位置。

Step2計算目標函數(shù)值，記錄種群最優(yōu)解，置當(dāng)前步數(shù)t=0。

Step3主循環(huán)開始

Step3.1所有個體執(zhí)行位置更新；

Step3.2所有個體執(zhí)行局部搜索；

Step3.3更新種群最優(yōu)解；t=t+1；

若t＞Maxgen，轉(zhuǎn)Step4；

否則轉(zhuǎn)Step3.1。

Step4保存種群最優(yōu)解，結(jié)束。

4 對比實驗

4.1測試函數(shù)

采用CEC2013定義的28個標準函數(shù)［15］作為優(yōu)化對象，如表1所示。其中（S）表示該函數(shù)的變量是可分離的，（N）表示變量是不可分離的，n表示該函數(shù)由其他n個基本函數(shù)復(fù)合而成，所有函數(shù)均為極小值優(yōu)化。

表1 28個CEC'13測試函數(shù)簡介

4.2對比方案

為體現(xiàn)所提出的QIFA算法的優(yōu)良性能，所有函數(shù)的優(yōu)化結(jié)果將與普通螢火蟲搜索算法（FA）［1］、變步長螢火蟲算法（Variable Step Size Firefly Algo?rithm，VSSFA）［2］，按維對稱尋優(yōu)的螢火蟲算法（Op?position and Dimensional based FA，ODFA）［4］進行對比。為保證對比結(jié)果客觀公正，四種算法采用相同的種群規(guī)模?？紤]到群智能優(yōu)化算法具有隨機性，為盡量提高對比結(jié)果的可信度，所有函數(shù)的維數(shù)均取D=30維，且每個函數(shù)均用4種算法各自獨立優(yōu)化30次，取30次優(yōu)化的平均結(jié)果作為對比指標。

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

關(guān)于本文提出的QIFA，引入量子計算機制后，增加了一個控制參數(shù)θ0，同時省略了位置更新式（3）中的隨機項系數(shù)α，因此控制參數(shù)個數(shù)與普通FA是相同的。由于ODFA和FA的控制參數(shù)相同，僅是尋優(yōu)策略不同，因此可以采用相同的參數(shù)。經(jīng)過反復(fù)實驗，最終確定的參數(shù)如下。

四種算法的共性參數(shù)為：種群規(guī)模NP=50；空間維數(shù)D=0；個性參數(shù)設(shè)置為：對于QIFA，β0=0.1，γ=1.0，θ0=0.05π；對于普通FA和OD?FA，α=0.5，β0=1.0，γ=10-5；對于VSSFA，采用文獻［2］中建議的參數(shù)設(shè)置α=0.4，β0=γ=1.0。

4.4對比結(jié)果

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

在表2中，粗體數(shù)字表示該結(jié)果優(yōu)于對比算法的結(jié)果。由此可知，QIFA的所有28個函數(shù)的優(yōu)化結(jié)果均優(yōu)于FA，實驗結(jié)果充分展示了QIFA的優(yōu)勢。以函數(shù)5、8、10、24為例，兩種算法30次優(yōu)化的平均結(jié)果隨迭代步數(shù)的變化情況如圖1所示。

為充分驗證QIFA的優(yōu)勢，有必要在相同運行時間下對比優(yōu)化結(jié)果。因此，在下面的仿真中，在保持QIFA迭代步數(shù)不變（仍然為1000步）的前提下，將FA、VSSFA、ODFA三種算法的迭代步數(shù)均設(shè)為5000步，然后將每種算法分別獨立運行30次，四種算法的平均結(jié)果對比如表3所示。

表2 QIFA和FA每個函數(shù)30次優(yōu)化的平均結(jié)果對比

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

在表3中，QIFA列的粗體數(shù)字表示該結(jié)果是四種算法中最優(yōu)的。而其他三列中的粗體數(shù)字表示該結(jié)果優(yōu)于QIFA算法。由此可知，QIFA優(yōu)于FA的函數(shù)個數(shù)為23個，優(yōu)于VSSFA的函數(shù)個數(shù)為21個，優(yōu)于ODFA的函數(shù)個數(shù)為18個。實驗結(jié)果表明QIFA明顯優(yōu)于三種對比算法。

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

4.5對結(jié)果的分析

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

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

5 結(jié)語

普通螢火蟲搜索算法是仿生智能優(yōu)化領(lǐng)域的新成員，其搜索能力有待于進一步提高。本文嘗試將量子計算機制引入螢火蟲搜索算法，用量子比特編碼個體位置，用量子比特在Bloch球面上的繞軸旋轉(zhuǎn)代替經(jīng)典螢火蟲搜索算法在優(yōu)化空間中的隨機游動，以期較大幅度地提高其優(yōu)化能力。實驗結(jié)果表明，這種嘗試是成功的，新算法的確呈現(xiàn)出明顯優(yōu)于原算法的性能，從而揭示出，在原算法中引入量子計算機制，是提高其優(yōu)化性能的有效途徑。

［1］Yang X S.Nature-inspired metaheuristic algorithm［M］. London：Luniver Press，2008，148-172.

［2］Shuhao Yu，Shenglong Zhu，Yan Ma，Demei Mao.A vari-able step size firefly algorithm for numerical optimiza?tion［J］.Applied Mathematics and Computation，2015，263（15）：214-220.

［3］Adil B，F(xiàn)ehmi B O.Adaptive firefly algorithm with chaos for mechanical design optimization problems［J］.Applied Soft Computing，2015，36：152-164.

［4］Prakash V，Deepti A，Tejna P.Opposition and dimensional based modified firefly algorithm［J］.Expert Systems With Applications，2016，44：168-176.

［5］Hui Wang，Wenjun Wang，Xinyu Zhou，et al.Firefly al?go-rithm with neighborhood attraction［J］.Information Sci-ences，2017，（382-383）：374-387.

［6］Manvir K，Smarajit G.Network reconfiguration of un?bal-anced distribution networks using fuzzy-firefly algo?rithm［J］.Applied Soft Computing，2016（49）：868-886.

［7］Jothi G，Hannah I H.Hybrid Tolerance Rough Set-Firefly based supervised featureselection for MRI brain tumor im?age classification［J］.Applied Soft Computing，2016，46：639-651.

［8］Bartosz K.One-class classifier ensemble pruning and weighting with firefly algorithm［J］.Neurocomputing，2015，150：490-500.

［9］Kanimozhi T，Latha K.An integrated approach to region based image retrieval using firefly algorithm and support vectormachine［J］.Neurocomputing，2015，151：1099-1111.

［10］Ozgur K，Jalal S，Sepideh K，et al.A survey of water level fluctuation predicting in Urmia Lake using support vector machine with firefly algorithm［J］.Applied Mathematics and Computation，2015，270：731-743.

［11］Nguyen C L，Phayung M，Herwig U.A highly accurate firefly based algorithm for heart disease prediction［J］. Expert Systems with Applications，2015，42：8221-8231.

［12］Amir H，Hossein B，Saeed R，et al.Firefly optimization algorithm effect on support vector regression prediction improvement of a modified labyrinth side weir's dis?charge coefficint［J］.Applied Mathematics and Computa?tion，2016，274：14-19.

［13］Xiujuan Lei，F(xiàn)ei Wang，F(xiàn)angXiang Wu，et al.Protein complex identification through Markov clustering with firefly algorithm on dynamic protein-protein interaction networks［J］.Information Sciences，2016，329：303-316.

［14］Giuliano B，Giulio C，Giuliano S.Principles of quantum computation and information（Volume I：Basic concepts）［M］.Singapore：World Scientifi，2004.100-112.

［15］Liang JJ，Qu BY，Sugamthan P N，et al.Problems defi?ni-tion and evaluation criteria for the CEC 2013 special ses-siononreal-parameteroptimization［EB/OL］. Http：//www.ntu.edu.sg/home/EPNSugan/index files/CEC 2013/CEC2013.htm.

Quantum-Inspired Firefly Search Algorithm

LIU XiandeYU RuifangLI BinxuZHAO SiyuanLI Panchi
（School of Computer and Information Technology，Northeast Petroleum University，Daqing163318）

In order to improve the search ability of firefly search algorithm，by introducing the quantum computing mechanism into the classical firefly search algorithm，a quantum-inspired firefly search algorithm is proposed.In the proposed algorithm，the qubits are used to encode individuals，the Pauli matrixes are employed to determine rotation axis，the firefly flight principle is app?plied to obtian 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 firefly search algorithm in optimization ability.

bionic intelligent optimization，swarm intelligence optimization，firefly algorithm，quantum-inspired optimiza?tion，algorithm design

TP183

10.3969/j.issn.1672-9722.2017.05.002

2016年11月17日，

2016年12月21日

國家自然科學(xué)基金（編號：61502094）；黑龍江省自然科學(xué)基金（編號：F2015021）；東北石油大學(xué)研究生創(chuàng)新科研項目（編號：YJSCX2016-030NEPU）資助。

劉顯德，男，博士，教授，研究方向：量子智能計算、量子圖像處理。于瑞芳，女，碩士研究生，研究方向：量子智能計算、量子圖像處理。李濱旭，女，碩士研究生，研究方向：量子智能計算。趙思遠，女，碩士研究生，研究方向：量子智能計算。李盼池，男，博士，教授，研究方向：量子智能計算、量子圖像處理。