量子群智能優化算法綜述

安家樂，劉曉楠，何 明，宋慧超

信息工程大學 數學工程與先進計算國家重點實驗室，鄭州 450000

大自然為解決現實世界的問題提供了很多靈感，在與最優化問題領域結合的過程中誕生了群智能優化算法[1]。最優化問題即在一定約束條件的限制下尋找滿足需求的最優解，是典型的NP難問題。在現實生活中最為常見的就是離散的組合優化問題，如旅行商問題、背包問題、圖著色問題、車輛路徑問題等[2]。傳統的優化算法通常是用來解決目標函數表達式已知的最優化問題，如梯度下降法、牛頓法等[3]。但在最優化問題日益復雜的現在，由于目標函數連續性差、微分難度大等原因，傳統的優化算法已經無法滿足需求，尤其是很多問題并沒有確定的目標函數表達式或者函數不唯一。在這種情況下，群智能優化算法展現出了它強大的能力。其歷史可以追溯到20世紀60年代進化策略的出現以及70年代遺傳算法的誕生[4]，在20世紀90年代取得了迅猛發展。在過去的二三十年間，大量的群智能優化算法被提出，典型的有蟻群優化算法、粒子群優化算法、人工蜂群算法以及螢火蟲算法等等[5～10]。它們在解決最優化問題上有著很好的表現，但隨著研究問題的日益復雜，在求解過程中仍存在計算時間過長以及易陷入局部最優等不足。

量子計算是一個快速發展的領域，其概念最早是在20世紀80年代由Feynman提出[11]，一經提出便引起諸多學者的廣泛關注，近年來在許多方向上取得了突破。量子計算的基礎是量子比特，與經典計算機的0、1比特不同，量子比特位可以處于0和1的疊加態?；诹孔佑嬎悛氂械寞B加、糾纏以及干涉等特性，量子算法展現出了天然的并行性以及在一些問題上實現指數加速的潛力，較成功的算法有Shor算法以及Grover算法等[12-13]。在最優化領域，也出現了量子計算與群智能優化算法結合而成的量子群智能優化算法。量子群智能優化算法的歷史最早可以追溯到1996年，文獻[14]首次提出將量子計算和遺傳算法結合，形成了全新的量子遺傳算法，用于解決TSP難題。但是，文章所提出的算法并沒有很好的利用量子計算。直到2000年，文獻[15]才正式提出了量子遺傳算法，用于解決0-1背包問題。相比之前的算法，文獻[15]首次引入了量子比特和量子旋轉門的概念分別實現染色體進行編碼和更新。遺傳算法雖然嚴格來說不屬于群智能優化算法，但兩者十分相似，有著極為特殊的聯系。因此，量子遺傳算法的誕生也掀起了量子計算與群智能優化算法結合的熱潮。

經過二十多年的蓬勃發展，許多量子群智能優化算法被提出。這些算法主要包括：Sun等[16]的量子粒子群優化（quantum particle swarm optimization，QPSO）算法、李盼池等[17]的連續量子蟻群算法（quantum ant colony algorithm，QACA）、唐濤[18]的量子人工魚群算法（quantum artificial fish swarm algorithm，QAFSA）、Gao等[19]的量子蜂群優化（quantum bee colony optimization，QBCO）算法等。一些新的基于量子特性的群智能優化算法也隨之出現，包括：量子布谷鳥搜索算法[20]（quantum cuckoo search algorithm，QCSA）、量子混合蛙跳算法[21]（quantum shuffled frog leaping algorithm，QSFLA）、量子螢火蟲算法[22]（quantum firefly algorithm，QFA）、量子蝙蝠算法[23]（quantum bat algorithm，QBA）等，未來也將會有更多的新型算法被提出。

很多研究基于最基礎的量子群智能優化算法進行了許多改進，提出了很多變體，并應用于解決不同領域的現實世界問題。算法的研究大多關注于解決難題，包括信號處理、控制系統、生物醫學工程、電力系統、安全、數據通信、安全、計算機網絡等領域。根據不同的量子群智能優化算法具有的不同特性，對它們進行理論分析、改進以及組合。許多研究者也研究了這些算法的參數設置，以獲得更好的性能。

在接下來的內容中，本文將聚焦于介紹各類量子群智能優化算法，比較它們的不同方面，并系統的總結面臨的問題與挑戰。

1 量子群智能優化算法概覽

本章對基于量子群智能的計算算法的研究工作進行簡要介紹。概略分析了幾種經典的量子群智能優化算法：量子蟻群算法、量子粒子群算法、量子人工魚群算法、量子人工蜂群算法、量子布谷鳥搜索算法，以及部分新型量子群智能優化算法：量子混合蛙跳算法、量子螢火蟲算法和量子蝙蝠算法等典型的量子群智能算法，其部分特點如表1所列。這些算法有著不同的操作方式和控制參數。但是，基于量子群智能的計算算法的基本操作通常都包括初始化、更新、求值和選擇。表2則對這些算法的優缺點以及應用場景進行展示。

表1 幾種典型的量子群智能優化算法的特性Table 1 Characteristics of several typical quantum swarm intelligence optimization algorithms

表2 算法的優缺點及應用場景Table 2 Advantages，disadvantages and application scenarios of algorithms

2 典型的量子群智能優化算法

本章對前一章中概覽的量子群智能優化算法分別進行了更為詳細的介紹，并對其研究現狀和改進思路做出了綜述。

2.1 量子蟻群算法

量子蟻群算法（QACA）是由經典的蟻群算法與量子計算思想結合而成的。與螞蟻本身類似，蟻群算法基于由信息素實現的蟻群內部間接的信息交換。量子蟻群算法則是在蟻群算法的基礎上，使用量子比特對螞蟻群體進行編碼，量子旋轉門等進行更新。量子蟻群算法最早由Narayanan和Moore定義，在2008年為了解決連續空間中的優化問題，由李盼池等[17]首次實現，也是第一次引入了利用量子非門實現的變異操作。與解決組合優化問題不同，這時的連續量子蟻群算法（CQACA）中螞蟻釋放的信息素是位于當前所在的位置點的，而并非其經過的全部路徑。CQACA是具有啟發性的，它為后續的應用以及算法的變體提供了一個框架。隨著優化問題及現實情況的不斷變化，李盼池等[17]的文章也被頻繁引用和改進。目前，QACA已經廣泛應用于最短路徑問題（short path problem，SPP）、旅行商問題（traveling salesman problem，TSP）、圖著色問題（graph coloring problem，GCP）和0-1背包問題（0-1 knapsack problem，0-1KP）等NP難問題[24～27]。

在量子蟻群算法中，針對不同問題首先用m個量子比特對每條路徑的信息素進行初始化編碼，最多可以同時處于2m個狀態。一只螞蟻遇到節點的岔路口時，可以檢測到不同路徑的信息素濃度，在運動之后也會增強所選路徑的信息素濃度，一只螞蟻的運動軌跡被鄰近的螞蟻根據信息素的濃度觀測到。信息素越多，螞蟻選擇這條路徑的可能性越大，信息素濃度的更新由量子旋轉門完成，最終由蟻群共同標記出一條最短路徑。

2.1.1 研究現狀及應用

Chen等[28]結合量子進化算法和蟻群算法，將螞蟻的位置信息用量子Bloch球面坐標進行了編碼，并設計了一種新的旋轉方法進行更新，在對TSP等問題的仿真上取得了較好的效果。王靈等[29]提出一種自適應的旋轉角更新策略，在算法的不同階段使用不同大小的旋轉角對種群進行更新，算法前期旋轉角較大以加快搜索速度，算法后期根據收斂情況減小旋轉角的度數，避免在最優值附近橫跳，提升了收斂的準確性。李絮等[30]則利用量子信息糾纏和干涉的特性引入了一種量子交叉策略，促進種群內部的信息交流，增加種群的多樣性，只在算法陷入停滯狀態時使用，避免算法陷入局部最優無法跳出。賈瑞玉等[31]針對QACA求解較大規模問題時易陷入停滯狀態，提出了一種混合量子蟻群算法，設計了一種新的變換鄰域準則對求得的解進行優化，避免陷入局部最優，仿真結果表明，該算法在面對較大規模問題時具有更好的收斂速度和求解精度。張程程[32]將Hadamard門引入變異機制，不再使用傳統的非門實現個體變異，在旋轉過程中不僅實現了賦值互換，還改變了其大小，擴大了種群多樣性。Xia等[33]為實現多目標的路徑規劃，利用多條啟發式信息確定螞蟻的遷移規則和遷移概率，通過量子位對信息素進行編碼，量子信息素通過算法中的局部和全局更新規則進行更新。

通過在基本量子蟻群算法的基礎上進行適當修改和對一些步驟的改進適配，量子蟻群算法已經被應用于各種不同的優化問題，如故障診斷[34]、WSN[35]、AGVS路徑規劃[36]、醫療圖像閾值分割[37]、油田水淹層識別[38]、壓力容器優化[39]等等?？梢园l現，這些改進過的量子蟻群算法在有效性和效率方面比經典的蟻群算法好得多，量子蟻群算法在這些領域已經顯示出了其巨大優勢，并將被廣泛地應用于新的領域和問題。對改進QACA的總結見表3。

表3 改進量子蟻群算法的優缺點和應用Table 3 Advantages and disadvantages of improved quantum ant colony algorithms and its applications

2.1.2 QACA總結及其局限性

量子蟻群算法將量子計算引入了蟻群算法，利用量子信息的并行特性以較小的種群規模更充分的利用搜索空間，通過量子旋轉增加種群的多樣性，應對蟻群算法易陷入局部最優的缺點。量子蟻群算法的核心在于引入量子編碼和量子旋轉門的概念，但其仍只是蟻群算法的一種優化，本質還是蟻群算法，并不能完全避免蟻群算法固有的缺陷。現有的優化多從編碼方式、量子門構造、旋轉角策略調整以及引入新操作等方面進行改進，以加快搜索速度并提高算法的穩定性，提高算法的全局搜索能力和局部搜索的有效性。

目前量子蟻群算法在簡單組合優化問題上成果顯著，但是如果是通過簡單的投影測量及變換解空間的方式將量子位轉換成經典比特位，那么算法將不適合多參數優化以及高精度計算。因此對適用于高維優化問題的量子蟻群算法的研究是頗為重要的。同時，對其數學理論方面的研究尚不完善，無論是參數設置還是收斂性的理論分析都停留在淺顯的層面。缺少基礎領域的理論使得算法的研究與優化無法真正的腳踏實地，因此算法的數學理論層面更需要研究者們關注。

2.2 量子粒子群優化算法

與量子蟻群算法相似，量子粒子群優化（QPSO）算法是由量子計算和群智能優化算法之一的粒子群優化算法結合而成。粒子群優化算法源于對鳥群、魚群自然行為的模擬，是粒子群基于內部協作來搜索全局最優點的過程。2004年，Sun等[16]針對粒子群優化算法智能程度低、易早熟等缺點，首次提出了量子粒子群優化算法，利用具有量子特性的粒子對群體智能行為進行模擬。目前，量子粒子群優化算法已經被應用于解決各種復雜的優化問題，例如網絡入侵檢測[40]、電力系統[41]、支持向量機[42]和圖像處理[43]等等。

量子粒子群優化算法的最大優點是相較其他量子群智能優化算法，其算法結構十分簡單，易于實現，主要在于其控制參數少。除去種群規模、迭代次數等基本參數，需要人為進行設置的只有一個收縮擴張系數β。并且由于粒子具有量子特性，其運動不受軌道約束，能夠更好地進行全局搜索。

2.2.1 研究現狀及應用

近年來，研究者們提出了各種量子粒子群優化算法模型。Radha和Gopalakrishnan[44]利用全面搜索策略概念對QPSO做出改進，通過駐留搜索策略尋找新粒子來防止由于過強的吸引導致的過早收斂，同樣的通過綜合搜索策略識別新粒子，提出了IQPSO（improved quantum particle swarm optimization）與LSM結合用于提高醫學圖像分割的穩定性和細致性。Zhao等[45]基于差分進化算法的快速收斂性和遺傳算法算法交叉算子的粒子多樣性，提出了一種差分進化交叉量子粒子群優化（differential evolution-crossover quantum particle swarm optimization，DE-CQPSO）算法，提高全局搜索能力，提供一種改進的自適應方法來控制交叉概率的更新，克服QPSO算法收斂的不穩定性和在特殊情況下陷入局部最優的偶然性，并用以解決環境經濟調度問題。金鵬[46]提出了一種勢阱長度自適應并且融合了社會學習和萊納飛行的QPSO（ALSL-QPSO）算法，利用社會學習策略更新非最優粒子，加強算法的全局搜索能力，同時通過萊納飛行策略解決最優粒子不更新的問題，提高了種群多樣性，再實現自適應的調節勢阱長度，進一步提高算法的全局搜索能力和局部挖掘能力。趙國新等[47]利用差分策略影響粒子位置的更新，使粒子更好地向最優位置靠近，引入Levy飛行策略增加種群的多樣性，降低了算法陷入局部最優的可能，同時自適應的調整收縮-擴張系數β，增強算法前期搜索速度以及后期的收斂精度。對改進QPSO算法的總結見表4。

表4 改進量子粒子群優化算法的優缺點和應用Table 4 Advantages and disadvantages of improved quantum particle swarm optimization algorithms and its applications

2.2.2 QPSO算法總結及其局限性

量子粒子群優化算法自提出以來便廣為研究者們所關注，而它在實際應用中也確有其獨特的優越性，最為典型的就是極少的控制參數。然而即使利用量子特性對PSO算法進行了優化，量子粒子群優化算法在實際應用中仍存在著易陷入局部最優、后期收斂精度不穩定等問題。針對以上問題，目前的改進集中在收縮擴張系數β的適應性調整、引入新算子以及融合其他策略和思想。目前研究取得了一定的成果，但是優化算法沒有最好，只有更好，針對QPSO算法仍有許多有待進一步研究的方向。例如：理論研究方面，算法的收斂性分析以及收斂速度的估計；算法的全局搜索性能和算法不可避免的會陷入局部最優方面，可以考慮利用QPSO算法易與其他算法和策略融合的特性，汲取其他方法的優點進一步改善算法的性能；應用方面，仍需進一步的拓寬QPSO算法在各個領域的應用。

2.3 量子人工魚群算法

量子人工魚群算法（QAFSA）最初由唐濤[18]在2008年提出，將量子行為引入了人工魚群算法，使量子算法強大的全局搜索能力和人工魚群算法的局部搜索能力相結合。在一片水域中，魚群最密集的地方一般就是附近營養物質最充沛的地方，人工魚群算法模擬魚群覓食、聚群、追尾等行為，找到營養物質最豐富的全局最優點。而QAFSA則采用量子編碼表示個體的位置，量子計算特有的疊加和坍塌能帶來更豐富的種群，量子旋轉門利用當前最優個體的信息對魚群進行更新，并引入量子變異、災變等操作以緩解早熟等現象。結果證明，QAFSA在求解優化問題上有較好的性能，在聚類挖掘、信號檢測、動態路徑誘導等方面[48]得到了廣泛的應用。

2.3.1 研究現狀及應用

相比于前兩種算法，目前國外對QAFSA的研究工作開展的較少，不過國內方面為了適應不同的優化問題，研究人員提出了各種改進的QAFSA模型，并以此引出了不少工程應用。王林川等[49]針對輸電網絡網架的優化規劃建立數學模型，利用魚群算法強大的局部搜索能力與量子算法混合，構造出探索和挖掘比較平衡的QAFSA對輸電網規劃問題求解，每次生成新個體便進行約束條件校驗和剔除，在24節點系統上的實驗結果表明該算法的可行性和有效性。張鍇[50]對魚群的視野和步長進行自適應改進，在算法運行的不同階段動態的決定魚群個體的視野和步長，提高算法的收斂速度和精度，同時設計了反饋-吞食行為用以去除魚群中對算法執行貢獻微小的個體，使得每次迭代更為高效，最終將算法應用于求解動態路徑誘導問題，證明其可行有效。行鴻彥等[51]將變異操作引入量子人工魚群算法，每次迭代后選出適應度較小的個體按照變異概率實現個體位置的隨機跳動，提出了一種基于QGAFSA的隨機共振微弱信號檢測方法，將隨機共振問題轉化為多參數同步尋優問題，利用QGAFSA進行尋優，實現微弱信號的增強。李根[52]提出了一種基于量子人工魚群的半監督模糊核聚類算法，用于解決基于傳統模糊C均值聚類的網絡入侵檢測模型分類效果不佳等問題，適用于并行執行架構。對改進QAFSA算法的總結見表5。

表5 改進量子人工魚群算法的優缺點和應用Table 5 Advantages and disadvantages of improved quantum artificial fish swarm algorithm and its applications

2.3.2 QAFSA總結及其局限性

目前針對量子人工魚群算法的改進做出的研究仍然較少，與其他量子群智能優化算法相似，關于它的改進也主要集中在加快收斂速度、提高收斂精度以及防止陷入局部最優等問題上。量子人工魚群算法具有一個顯著的缺點就是當魚群中個體數量較少時，無法體現其優勢，魚群的增大可以提高搜索速度，但同時也會加大存儲開銷，影響算法運行效果?；谝陨蠁栴}，現有的文章多是在視野和步長的調整、魚群行為的增加與優化等方面進行研究。相比于對算法的改進，其在應用層面的發展更為顯著。

2.4 量子蜂群優化算法

量子蜂群優化（QBCO）算法最早是由Gao等[53]在2011年提出的，將Karaboga和Basturk[7]提出的人工蜂群算法（ABC）與量子計算相結合。自然界中，蜂群中的蜜蜂通過搖擺舞來傳遞蜜源的方向和距離等詳細信息，借由這種群體之間的信息交換，蜂群能夠找到附近的優質蜜源。ABC算法便是模擬蜂群這種覓食行為，QBCO算法則是在這種覓食機制的基礎上，使用量子信息對蜜源進行編碼以增加最優解的個數，并通過量子旋轉門實現算法過程中的蜜源更新。與其他的量子群智能優化算法相比，QBCO算法的顯著優點在于每次迭代都會將全局搜索和局部搜索相結合，收斂速度快，魯棒性強。目前，QBCO在聚類分析、圖像處理以及多目標優化問題等方面得到了一定的應用。

2.4.1 研究現狀及應用

鄧斯凱和毛戈[54]針對配電網多目標優化重構問題，用QBCO算法和Pareto支配關系進行求解，并將算法應用到標準IEEE 33節點配電網和加入分布式電源的配電網進行重構測試，測試結果表明了該算法的可行性。Gao等[53]將提出的QBCO算法用于解決CDMA（code division multiple access）系統在脈沖噪聲存在下的魯棒多用戶檢測問題，實驗結果表明，所設計的魯棒檢測器在誤碼率（BER）等方面均比以往的檢測器有所提升。在提出QBCO算法三年后，Gao等[55]為了更有效地解決離散優化問題，又提出了一種基于膜激發的量子蜂群優化算法（membrane-inspired quantum bee colony optimization，MQBCO），將膜計算理論引入QBCO，每個基礎膜內包含一定數量的個體，膜將其與環境隔開，但不同膜之間也有著其通信規則且不限制個體的運動，文章還證明了MQBCO的全局收斂性能和有效性，隨后將該算法用于解決認知無線電系統的決策引擎問題。Huo等[56]提出了一種改進的布洛赫量子人工蜂群（improved Bloch quantum artificial bee colony，IBQABC）算法，采用量子Bloch球坐標對蜜源信息進行三維編碼，擴展了全局最優解的數量，并對更新策略做出相應改變，動態調整旋轉角度，提高算法收斂速度以及跳出停滯狀態的能力，并實際用于解決多層次圖像閾值分割的問題，取得了不錯的效果。同時，還有侯國蓮和弓林娟[57]將QBCO算法作為聚類算法的前提部分辨識，提高了聚類速度，并應用于智能發電運行控制系統發電機組建模中，表現出良好的通用性和適應性。高相銘等[58]為解決多峰MPPT控制問題，將混沌搜索機制引入量子蜂群算法以選擇最優SVR參數，提出了混沌量子蜂群算法CQABC，利用混沌搜索的特性將陷入局部最優的個體通過Logistic映射迭代產生混沌序列，提取序列中最優位置，使得算法能夠繼續有效運轉。對改進QBCO算法的總結見表6。

表6 改進量子人工蜂群算法的優缺點和應用Table 6 Advantages and disadvantages of improved quantum bee colony algorithms and its applications

2.4.2 QBCO算法總結及其局限性

量子人工蜂群算法引入量子計算的概念，在一定程度上提高了蜂群算法的多樣性和計算能力，但仍未能取得足夠滿意的效果。主要因為未充分利用量子編碼的特性，以及量子蜂群更新過程的不穩定性。根本原因則在于對算法理論的研究和推導無法支撐起應用，而這也是量子群智能優化算法的通病，是所有這類算法未來研究的一個重要方向。目前針對該算法的改進也相對較少，多是將其作為其他方法的尋優部分來解決實際問題，研究者應更好的利用其在高維空間表現良好的優勢對算法做出針對性改進，增強蜂群更新過程的穩定性，提升算法的尋優性能。

2.5 量子布谷鳥搜索算法

量子布谷鳥搜索算法（QCSA）是Layeb[20]提出的一種較新的量子群智能優化算法，已經應用于很多優化以及工程問題。QCSA的前身是布谷鳥搜索算法（CSA），CSA的靈感來源于一些布谷鳥在宿主鳥類的巢內產卵并由宿主鳥幫助孵化的自然現象。在自然界中，部分布谷鳥已經可以產出模仿一些鳥類宿主蛋的顏色和圖案的蛋，大大減少產出的蛋被拋棄的幾率。在CSA中，巢中的每一個蛋便代表著問題的一種解決方案，一個布谷鳥蛋則代表一種新的解決方案，其算法思想就是用新的、更好的布谷鳥蛋取代巢中不那么好的蛋[59]。最簡單的情況就是每個巢只有一個蛋，擴展開來就是每個巢中的多個蛋代表一組解。

在QCSA中，設置完種群大小、迭代次數等基本參數后，首先要對宿主鳥巢進行量子編碼產生初始解，再利用CSA中的萊維飛行搜索機制更新鳥巢的位置，并使用量子旋轉門對發現的劣質鳥巢進行二次更新，最后采用局部鄰域搜索算法對全局最優解進行優化[60]。

2.5.1 研究現狀及應用

原始的QCSA已經被修改或者與其他算法進行混合，以解決不同的優化問題。一些涉及不同領域的復雜優化問題已經通過使用原始QCSA或者其變體得到了解決。Kartous等[59]基于全局/局部混合算法的隨機漸進對齊方法來構造初始種群，提出了一種新的QCSA以解決生物信息學領域中主要問題之一的多序列比對（multiple sequence alignment，MSA）問題。杜傳報等[61]則結合膜結構和QCSA，提出了膜量子布谷鳥搜索算法以解決無線雙通道Ad Hoc網絡中頻譜資源分配優化的問題，算法使用量子信息編碼鳥巢表示問題的潛在解，通過布谷鳥尋窩產卵的演化方法在基礎膜中尋求單目標最優解，通過膜間信息共享和非支配解等級排序在Pareto前端解中求出多目標最優解。張東寅等[62]在原始的QCSA每次迭代的優化值附近引入了混沌局部搜索，生成混沌序列并借此在最優鳥巢附近隨機生成一個新鳥巢，提出了一種融入量子計算和混沌局部搜索策略的改進布谷鳥算法，并針對IEEE 118節點系統的最優潮流計算問題進行仿真計算，得到了一種新的求解方法。劉志剛等[63]在QCSA中引入量化正交交叉策略，對發現個體和量子Pauli-Z門變異個體實施量化正交交叉操作，在正交區域中實施局部精細搜索，并應用到泥頁巖多礦物組分反演問題中，反演精度有顯著提升。Boushaki等[64]提出了一種新的用于數據聚類的量子混沌布谷鳥搜索（QCCS）算法，利用非齊次更新來擴展CS能力，同時采用混沌映射代替初始階段的隨機性，提高收斂速度。試驗結果表明，提出的QCCS算法在內外聚類質量方面均明顯優于標準布谷鳥搜索算法等8個已知算法。對改進QBCO算法的總結見表7。

表7 改進量子布谷鳥搜索算法的優缺點和應用Table 7 Advantages and disadvantages of improved quantum cuckoo search algorithms and its applications

2.5.2 QCSA總結及其局限性

量子布谷鳥搜索算法自提出起受到了許多研究者的關注，對其進行的研究也相對較多。它的主要優勢在于模型簡單、參數較少、通用性強，但是它也存在收斂速度較慢、易陷入局部最優等問題。隨著研究的不斷深入，研究者對以上問題都提出了不同的解決方案和改進思路，目前QCSA及其改進算法在實際應用中的表現良好，進一步優化則可著眼于改進種群的編碼方式、在搜索階段引入新的策略和思想形成混合算法等方面。

2.6 新型量子群智能優化算法

近十年來，由于量子計算的發展以及群智能優化算法理論的不斷進步，一些新穎的量子群智能優化算法被不斷提出，主要包括量子混合蛙跳算法、量子螢火蟲算法以及量子蝙蝠算法等，下面也將分別簡要的對它們做出一些介紹。

2.6.1 量子混合蛙跳算法

量子混合蛙跳算法（QSFLA）2011年由孫沖[21]提出，經典的混合蛙跳算法是模擬自然界中青蛙之間在覓食時的信息交流，而QSFLA則是在此基礎上采用量子信息對青蛙個體進行編碼，并用量子旋轉門進行種群的更新操作。相比經典的混合蛙跳算法，QSFLA不僅在尋優能力以及優化效率上有顯著提升，并且還繼承了經典混合蛙跳算法參數較少、易于實現等優點，缺點則是收斂速度相對來說依舊較慢，同時在面對部分問題時求解易陷入局部最優。

張強等[65]將QSFLA應用于神經網絡的優化中，采用量子Bloch球面坐標對網絡結構、網絡參數和展開項數進行編碼，沿球面兩點間的劣弧進行更新操作，并在抽油機故障診斷和網絡流量預測上進行了實驗，取得不錯效果。陳光宇等[66]采用QSFLA解決含DG的配電網無功優化，將每個可行解（即蛙群中的青蛙）編碼為Bloch球上一點，通過量子旋轉門對蛙群進行更新，并且利用Hadamard門對個體變異以避免早熟收斂，在IEEE 33節點系統上進行仿真實驗，證明了算法的快速和有效性。Wang等[67]提出了一種新的量子啟發蛙跳算法（NQSFLA）用于解決水下聲納圖像檢測問題，算法采用了類內差分和類間差分相結合的適應度函數來更準確地評價蛙的位置，并采用了一種新的進化更新策略將局部搜索分為兩步，先利用相位角編碼最差青蛙個體，亞群中其他個體則正常進化，以此來提高搜索過程中的搜索能力。為了避免QSFLA算法的缺點，他們還提出了一種帶有空間信息模型的模糊隸屬度矩陣，用于去除孤立區域。

2.6.2 量子螢火蟲算法

量子螢火蟲算法（QFA）2014年由張劍飛等[22]提出，經典的螢火蟲算法靈感來源于螢火蟲的顯著特征：閃爍的光。在自然界中，這些光是用來吸引伙伴以及警告捕食者，當兩只螢火蟲之間的距離增加時，光的強度也會降低。螢火蟲算法就是模擬這種發光機制，不斷向更具吸引力的螢火蟲個體移動。QFA則是在此基礎上采用量子信息對螢火蟲個體進行編碼，擴展尋優空間，并采用量子旋轉門對個體位置進行更新。

趙俊麗[68]針對QFA易早熟等缺點，提出了三種組合策略的量子螢火蟲算法：自適應步長策略以解決算法在最優值附近震蕩的問題；廣義精英反向學習策略應對QFA對初始種群分布合理性的依賴；邊界控制策略增加邊界個體的隨機性。采用最小交叉熵作為適應度函數，將三種改進后的QFA應用于圖像分割研究，實驗證明在MSSIM和PSNR方面都取得了顯著提升。Shareef等[69]采用量子啟發二進制螢火蟲算法尋找最佳的網絡重構，并將這種網絡重構方法應用于提高配電系統的電能質量和可靠性。齊學梅等[70]設計了一種新的局部鄰域搜索方法，與QFA相結合，每次迭代時只搜索部分鄰域，極大加快了算法迭代的速度，并將該算法應用于無等待流水調度，驗證了其優越性。Tao等[71]將遺傳算法中交叉和突變的概念引入QFA，通過交換部分量子位實現交叉、改變個體的部分量子位實現突變，以此獲取新的信息來保持種群的多樣性。

2.6.3 量子蝙蝠算法

量子蝙蝠算法（QBA）2013年由李枝勇[23]提出，經典的蝙蝠算法基于自然界中微型蝙蝠的回聲定位特性。在經典算法中有如下規則：蝙蝠隨機飛行，使用回聲定位感知距離，根據與目標的距離調整波長，響度由最大值逐漸降低到一個最小的恒定值。在QBA中，采用量子信息對蝙蝠位置進行編碼，蝙蝠位置的更新則通過量子旋轉門改變量子位的相位來實現。其優點在于全局和局部搜索能力較為平均，運算速度快，但是其求解精度低以及易陷入局部最優的缺點也同樣明顯。

Huo等[72]通過定義服務空間算子并用量子理論修改蝙蝠算法的定位生成方法，將QBA應用到服務組合問題中，仿真實驗結果表明該算法具有較好的性能。Huang等[73]提出了一種具有平均最佳位置定向的高斯量子蝙蝠算法，該算法利用高斯分布生成隨機數序列，應用高斯分布而不是均勻分布來生成隨機系數提高其避免過早收斂的性能，用于求解數值函數優化問題。實驗表明，在大多數情況下，該算法能夠提供更好的搜索性能。Li等[74]提出了一種混沌云量子蝙蝠算法，該算法利用X條件云發生器提高具有較好適應度個體的收斂速度，在一定迭代次數后對個體進行排序，并將3Dcat映射混沌干擾機制應用在適應度較差的個體上，提高種群多樣性。周志垚等[75]在QBA的基礎上引入自然選擇，同時針對算法的頻率引入優化因子，前期更多的進行全局搜索，后期則提高局部搜索能力。并將該算法應用于化工過程的動態優化問題中，取得了較好的效果。

新型算法改進的優點和應用對比見表8。

表8 新型算法改進的優缺點和應用Table 8 Advantages and disadvantages of new algorithms improvement and its applications

3 主要面臨的問題

量子群智能優化算法的發展迅速，對它的研究多是在應用層面的改進，主要集中在改進種群編碼方式、與其他策略和思想融合形成混合算法并應用于具體問題等。但是時至今日，量子群智能優化算法的理論基礎依舊不夠完善。而理論分析對于我們深入理解算法的機理有著重要作用，對算法進行收斂性和穩定性分析有助于其進一步的發展。并且，從理論分析角度對算法的性能進行評測也更有說服力和學術價值。

對于一個優化算法來說，對其進行收斂性分析是十分必要的。目前的研究狀況表明，建立一個可以對量子群智能優化算法進行理論分析的一般框架的數學模型十分困難，已經提出并實現的這類算法大多沒有進行系統的收斂證明，這也限制了它們在現實優化問題上的進一步應用。同時，當一種算法被用于解決一個或一類新問題時，對算法的進行適應性改進以及選擇最優的參數設置十分重要。但是目前的參數設置都只是經驗性的，或者說是針對某一實驗大量測試后選擇的，那么如何從理論角度給出算法最優參數設置的選擇依據，也是需要進一步研究的問題。

目前在不同量子群智能優化算法的優缺點方面的對比不夠清晰，多是對幾個算法進行嘗試性實驗，在理論層面不具有說服力，這直接導致了使用者在應用這類算法時的選擇困難。因此，需要建立一個標準的復雜性分析以及其他性能指標評估與分析的模型，更清晰的列出不同算法的優缺點，既有助于研究者更針對性的對算法性能做出改進與提升，同時也可以減輕使用者的選擇負擔。

除理論分析方面需要尋求突破以外，由于通用量子計算機的落地還比較遙遠，在目前已有文獻中的算法應用實現過程都是在經典計算機模擬并簡化實現的，模擬實現相比現有量子計算原型機的復雜情況來說過于理想化，效果或有提升但并不顯著。如果想探索算法短期內在現有機器上的實現，可以結合具體機器和問題在經典計算機上進行更符合實際的研究，如添加噪聲、半衰期等概念。但要想更好地發揮量子群智能優化算法在實際應用中的性能，未來還需要依托于通用量子計算機的實現。

4 結束語

本文回顧了量子群智能優化算法的由來和發展史，對當前典型的量子群智能優化算法的原理、實現過程、改進以及在具體優化問題上的應用進行了介紹，討論了目前面臨的主要問題與挑戰，并對需要重點研究的方向和方法進行了敘述?？梢灶A見，未來量子群智能優化算法在系統的應用于現實優化問題時，將繼續并更充分地顯示出其突出和不可替代的優勢。