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

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

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

（東北石油大學計算機與信息技術學院大慶163318）

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

仿生智能優化；群智能優化；螢火蟲算法；量子衍生優化；算法設計

Class NumberTP183

1 引言

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

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

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

2 螢火蟲搜索算法

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

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

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

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

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

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

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

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

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

3.1 QIFA的編碼機制

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

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

2）量子個體到經典個體的變換

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

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

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

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

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

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

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

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

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

3.2QIFA的搜索機制

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

1）基于量子比特饒軸旋轉的位置更新

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

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

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

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

其中β0為控制參數（通常取0.1），γ為常數，通?？扇?.0。

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

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

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

其中t為迭代步數。

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

2）基于量子比特隨機旋轉的局部搜索

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

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

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

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

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

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

3.3QIFA的終止條件

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

3.4QIFA的實施方案

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

Step2計算目標函數值，記錄種群最優解，置當前步數t=0。

Step3主循環開始

Step3.1所有個體執行位置更新；

Step3.2所有個體執行局部搜索；

Step3.3更新種群最優解；t=t+1；

若t＞Maxgen，轉Step4；

否則轉Step3.1。

Step4保存種群最優解，結束。

4 對比實驗

4.1測試函數

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

表1 28個CEC'13測試函數簡介

4.2對比方案

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

4.3參數設置

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

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

4.4對比結果

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

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

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

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

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

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

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

4.5對結果的分析

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

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

5 結語

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

［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，Fehmi 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，Fei Wang，FangXiang 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日

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

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