蜂群搜索的量子比特旋轉算法及其應用

樊俊杰，袁 博

（北京交通大學 經濟管理學院，北京 100044）

0 引言

優化求解即為系統最優化問題，距今約2500年前的古希臘建筑美學探討并被廣泛應用的黃金分割點，就是系統最優化的學術發軔。而后，阿基米德（Archimedes）“圓面積最大”理論、牛頓與G.W.萊布尼茨的“實值函數極值法”，為系統最優化的微積分方法開辟了道路，至此，系統最優化的古典方法論得以形成。系統最優化的近代發展以最優計劃理論等為代表。這些系統最優化的理論成果對后續的控制科學、運籌管理學、運用數學等學科的發展起到了重要催促作用。從方法論角度考察，最優化方法主要包括梯度下降法、擬牛頓法、共軛梯度法、拉格朗日乘數法及啟發式優化方法。梯度下降法將負梯度位置方向當做趨勢搜索方向，凸函數解將構成梯度下降法的全局解；擬牛頓法借助正定矩陣模擬牛頓法中Hessian之逆矩陣，以簡化運算復雜度；共軛梯度法則利用一階導數規則，以達消除梯度下降法收斂慢及擬牛頓法需計算Hesse逆矩陣之缺陷，具有步收斂特性；啟發式優化法又叫經驗規則法，它擬根據經驗規則進行方法發現，以找到解決具體問題的方法，該法包括經典模擬退火方法、蟻群算法、遺傳算法及粒子群算法等。

人工蜂群算法（artificial bee colony，ABC）是啟發式優化算法中的一種，該算法由土耳其埃爾吉耶斯大學教授Karaboga（2005）[1]提出，其中心思想是擬借助蜂群個體的分工、交流與協作,以優化完成花粉的采集任務。在人工蜂群算法中，蜂群實施迭代搜索的最小分工單位由引領蜂、跟隨蜂和偵察蜂3個基本角色組成:引領蜂搜索粉源并與跟隨蜂分享該信息；跟隨蜂按照引領蜂共享的信息，實施集中采粉；當原有粉源質量下降或數量縮減時，引領蜂轉變成偵察蜂，繼續尋求新的粉源，之后又轉成引領蜂。可見，角色轉換是人工蜂群算法的獨特機制。其中，優化算法的優良解取決于引領蜂導向；優化收斂速度的提高取決于跟隨蜂的采粉能力；系統全局最優的獲得取決于偵察蜂的粉源辨識能力。在優化算法發展過程中，人工蜂群算法又得到了諸學者的改進與拓展。Akay&Karaboga（2007）[2]在ABC基本模型基礎上置入控制搜索擾動維數的修改率MR參數，給出了ABC自適應調整擾動幅度方法；Alatas[3]通過植入混沌映射機制以增強算法參數的自適應性，提高了全局搜索能力，加速了優化的收斂速度；Rajasekhar等（2011）運用柯西正態分布規則，制定了基于Levy函數變異的人工蜂群改進算法；在混合算法方面，Mustafa（2013）[4]將人工蜂群ABC算法與粒子群優化PSO算法優化組合，以獲取搜索全局最優解；Kurban等（2009）[5]集卡爾曼濾波、RBF神經網絡一道，與ABC算法聯立，設計出一種高效的RBF算法；康飛等（2009）[6]引入概率突跳模擬退火機制，設計出文化退火人工蜂群算法；段海濱等（2010）、楊淑云等（2015）[7]通過引入量子旋轉矩陣，提出了一種量子衍生蜂群算法，并將其運用到油藏水淹層測井項目優化中，顯示了該優化算法的適用性與可靠性。

本文將在現有研究成果基礎上，在量子衍生蜂群算法上調整量子比特參數，并通過量子比特的繞軸旋轉，以獲取蜂群個體優化搜索。據此將該拓展算法運用到配送中心的選址優化組合與設計中，以進一步豐富系統優化算法理論。

1 蜂群搜索的量子比特旋轉算法

首先闡釋人工蜂群算法。參與主體由引領蜂Ne1、跟隨蜂Nu及偵察蜂Ne2構成，蜜蜂總數Ns=Ne1+Ne2+Nu，一個食物源（粉源）對應一個可能解，解的優化程度與食物源適應值成正比。令搜索空間維度為D，所以其搜索空間為S=RD，則食物源 i（i=1，2，...，Ns）可由xi=(xi1，xi2，...，xiD)表達。所以，目標函數f:S→R+的最優解獲取方式如下：引領蜂搜索粉源并與跟隨蜂分享該信息；跟隨蜂按照引領蜂共享的信息，按照一定概率實施集中采粉；當原有粉源質量下降或數量縮減時，引領蜂轉變成偵察蜂，繼續尋求新的粉源，之后轉成引領蜂，如果再次搜索到的粉源適應值大于先前粉源適應值，則先前粉源被取代。人工蜂群算法將實施若干次上述循環以搜索到最優解。食物源vij生成機制由以下公式給出：

其中，k≠i，rij∈[-1，1]為服從均勻分布的隨機數，旨在決定搜索域xij的邊界。隨著搜索迭代次數的增多，xij與xkj越趨近，最終兩者適應值一致，最優解得以獲得。跟隨蜂按照共享信息選擇采蜜點，其選擇采蜜點的概率為：

其中，fiti為食物源i的適應值。令為新粉源的第j維度量,rand(0，1)∈[0，1]為一隨機量，蜂群個體經過limit次迭代后，轉換成偵察蜂后，以式（2）獲得新食物源：

在新食物源Xi和現有食物源Vi之間擇優算子記作Ts:S2→S,其概率分布為:

記錄新食物源適應值fiti及相應個體（x1，x2，...，xD），采蜜蜂經過Limit次迭代搜索后，如果新食物源適應值fitx大于現成食物源適應值fitv，則選擇新食物源Xi，否則保留原食物源Vi，并重新初始化該蜂群。

1.1 量子比特及其繞軸旋轉空間解

量子概念（Quantum）最早由德國物理學家M·普朗克（1900）提出，它是現代物理學的重要概念，量子表意為“相當數量的某物質”。“量子比特”是量子信息的基本單位，一個量子比特|?即為一個Hilbert空間的二能級量子體系，其數學表達式為：

一個量子比特可由下圖向量點A(ax，ay，az)表征，點P為球面上任一點，于是一個量子比特可描述多種狀態。此時有：ax=cosφsinθ，ay=sinφsinθ，az=cosθ，轉換為向量形式為：

圖1 量子比特的繞軸旋轉圖[7]

將量子比特概念運用到蜂群優化中，可通過定義一個量子比特，并使其在圖1球面上繞特定軸旋轉，以達至目標比特。反映在向量數學上，繞軸旋轉就是改變兩個角參數θ、φ，即實現θA→θB、φA→φB的轉變。于是，根據李盼池等（2012）[8]的研究,可以定義：

令A(ax，ay，az)、B(bx，by，bz)分別為Bloch球面上的任兩點（A≠B），則在Bloch球面上，從A到B的最短路徑旋轉軸為Raxis=A×B。根據量子理論，量子比特繞軸n=[nx，ny，nz]旋轉δ角的旋轉矩陣為（I為單位矩陣）：

所以，滿足向量式的條件是：

即量子比特旋轉矩陣為Mij。令蜂群總體數Ns，第t代群族P=[p1(t)，p2(t)，pNs(t)]。于是，在量子比特表征，蜂群個體pi(0)可表述為D為優化空間維。由上述，量子比特經旋轉軸Raxis(i，j)實施Mij矩陣變換，可得的Bloch坐標 (x，y，z)，如下：

在此，i=1，2，...，N，j=1，2，D。可見，(x，y，z)的3維坐標代表一個3維優化解。而且每個解均由坐標X(xij，yij，zij)描述。令維度j的解區間在[Minj，Maxj]之間，則量子比特旋轉的空間解為：

在此，i=1，2，...，Ns;j=1，2，...，D。

1.2 蜂群搜索的量子比特算法實施

首先，按采蜜蜂群初始化排序，令前Ne個個體為采蜜蜂，則Nu=Ns-Ne為跟蹤蜂。根據公式（2）與公式（3），令第i食物源對應變量為xi(t)，隨機選取xj(t)、xk(t)，（i≠j≠k），按上述量子原理，再令轉向的旋轉軸為Raxis(i，j)，旋轉角為δik(t)，旋轉后食物源記為→(t)。于是有：

接下來，令跟蹤蜂的選擇概率為p(p=pi)=f(pi)/置。按照式（9），如果＞pi，有=pi，此時搜索次數search=0；如果＜pi，此時的搜索次數還沒有達到極值Limit，則有search=search+1。蜂群整體實施一次搜索即稱實施一次迭代。蜂群迭代一次，系統進行一次優化運算，每次都生成一個函數值。該算法到限定次數Limit次數為終止條件，最后得出系統最優解。

令R為懲罰系數（足夠大），設定懲罰系數的目的在于淘汰適應值很大的超范圍解，于是，根據以上算法，得出配送中心適應值函數：

2 蜂群搜索的量子比特旋轉算法運用實例

根據上述蜂群搜索的量子比特旋轉算法，設定多配送中心選址優化方法如下：

（1）設定系統搜索迭代次數（最大迭代次數為limit）；

（2）運用公式（10）計算需求點（潛在配送中心）的適應值，并對每個潛在的配送點Xi(i=1，2，...，N)根據公式（9）進行配送中心配置，賦予其實數1~m(m為配送中心數），再對其規整處理；

（3）按公式（2）產生新配送中心Vi，并對Vi實施規整化處理，根據公式（10）計算新的配送中心適應值，再根據公式（9）比較新的配送中心與現有配送中心適應值，前者大于后者則Xi=Vi；

（4）根據公式（3）計算新配送中心替代現有配送中心的概率qi，再根據公式（8）得出一個配送中心優化解；

（5）重復上述步驟（2）至步驟（4），獲得若干個配送中心優化解；

（6）綜合所有的配送中心優化解，得出最終的配送中心優化配置解。

本文給出以下案例：假設存在一個具有12個需求點的物流配送網絡系統，相鄰需求點間距離見表1所示，優化任務就是從中建立3個配送中心。另外，各需求點的需求量及在各需求點設立配送中心的初始投資成本如表2所示；各中心的配送容量均為21個單位（注：實驗參數設置如下：種群規模為120，迭代次數為3000）。跟蹤蜂最開始為采蜜蜂pi，然后搜索新位

表1 需求點間距離

表2 各需求點相關參數

表3 最優配送方案

從表3中可以看出，運用量子比特蜂群算法求解此配送中心的選址方案為：將需求點1建成第Ⅰ個配送中心，需求點3建成第Ⅱ個配送中心，需求點10建成第Ⅲ個配送中心。這樣的配置將使得配送中心系統整體成本最小，方案最優。事實上，該算法具有優于粒子群優化算法的諸多特性，同時與非量子比特蜂群算法（即一般人工蜂群算法）相比，也具有精度高、迭代次數少的優勢。

3 結束語

自古以來，系統最優化問題就成了人類孜孜以求的學術主題。牛頓、G.W.萊布尼茨等學者開辟的系統最優化古典方法論更是為最優化問題提供了廣闊的數理空間。而后，系統最優化問題衍生出很多有代表性的經典算法，如擬牛頓法、共軛梯度法、拉格朗日乘數法、模擬退火法、蟻群算法、遺傳算法及粒子群優化算法等。21世紀以來，土耳其學者Karaboga教授又提出一種人工蜂群算法，該算法擬模擬蜂群個體的分工、交流與協作,以達到任務分配之優化目的。繼而，諸多學者在此基礎上又提出了諸多人工蜂群改進算法。蜂群搜索的量子比特旋轉算法就是其改進算法之一。本文將在現有蜂群搜索的量子比特旋轉算法基礎上，作進一步的參數調整與修正，以高效率獲取搜索優化值。最后將該拓展算法運用到配送中心的選址優化組合與設計中，實例研究證實了本算法的理論優越性與實證有效性。

參考文獻：

[1] Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Opti?mization[R].Computers Engineering Department，Engineering Facul?ty，Erciyes University，2005．

[2] Karaboga D,Basturk B.A Powerful and Efficient Algorithm for Nu?merical Function Optimization:Artificial Bee Colony Algorithm[J].Journal of Global Optimization,2007,(39).

[3] Alatas B.Chaotic Bee Colony Algorithms for Global Numerical Optimi?zation[J].Expert Systems With Applicants,2010,37(8).

[4] Mustafa S K,Mesut G A Recombination-based Hybridization of Parti?cle Swarm Optimization and Artificial Bee Colony Algorithm for Con?tinuous Optimization Problems[J].Applied Soft Computing,2013，4(13).

[5] Kurban T,Bedok E.A Comparison of RBF Neural Network Training Algorithms for Inertial Sensor Based Terrain Classification[J].Sen?sors,2009,(9).

[6] 康飛,李俊杰,許青.改進人工蜂群算法及其在反演分析中的應用[J].水電能源科學,2009,27(1).

[7] 楊淑云,李盼池.量子衍生蜂群算法的設計與實現[J].系統仿真學報,2015，(7).

[8] 李盼池,王海英,宋考平.量子勢阱粒子群優化算法的改進研究[J].物理學報,2012,61(6).