樊俊杰，袁 博

（北京交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100044）

0 引言

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

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

本文將在現(xiàn)有研究成果基礎(chǔ)上，在量子衍生蜂群算法上調(diào)整量子比特參數(shù)，并通過量子比特的繞軸旋轉(zhuǎn)，以獲取蜂群個體優(yōu)化搜索。據(jù)此將該拓展算法運(yùn)用到配送中心的選址優(yōu)化組合與設(shè)計中，以進(jìn)一步豐富系統(tǒng)優(yōu)化算法理論。

1 蜂群搜索的量子比特旋轉(zhuǎn)算法

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

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

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

在新食物源Xi和現(xiàn)有食物源Vi之間擇優(yōu)算子記作Ts:S2→S,其概率分布為:

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

1.1 量子比特及其繞軸旋轉(zhuǎn)空間解

量子概念（Quantum）最早由德國物理學(xué)家M·普朗克（1900）提出，它是現(xiàn)代物理學(xué)的重要概念，量子表意為“相當(dāng)數(shù)量的某物質(zhì)”?！傲孔颖忍亍笔橇孔有畔⒌幕締挝?，一個量子比特|?即為一個Hilbert空間的二能級量子體系，其數(shù)學(xué)表達(dá)式為：

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

圖1 量子比特的繞軸旋轉(zhuǎn)圖[7]

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

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

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

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

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

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

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

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

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

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

2 蜂群搜索的量子比特旋轉(zhuǎn)算法運(yùn)用實例

根據(jù)上述蜂群搜索的量子比特旋轉(zhuǎn)算法，設(shè)定多配送中心選址優(yōu)化方法如下：

（1）設(shè)定系統(tǒng)搜索迭代次數(shù)（最大迭代次數(shù)為limit）；

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

（3）按公式（2）產(chǎn)生新配送中心Vi，并對Vi實施規(guī)整化處理，根據(jù)公式（10）計算新的配送中心適應(yīng)值，再根據(jù)公式（9）比較新的配送中心與現(xiàn)有配送中心適應(yīng)值，前者大于后者則Xi=Vi；

（4）根據(jù)公式（3）計算新配送中心替代現(xiàn)有配送中心的概率qi，再根據(jù)公式（8）得出一個配送中心優(yōu)化解；

（5）重復(fù)上述步驟（2）至步驟（4），獲得若干個配送中心優(yōu)化解；

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

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

表1 需求點(diǎn)間距離

表2 各需求點(diǎn)相關(guān)參數(shù)

表3 最優(yōu)配送方案

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

3 結(jié)束語

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

參考文獻(xiàn)：

[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ìn)人工蜂群算法及其在反演分析中的應(yīng)用[J].水電能源科學(xué),2009,27(1).

[7] 楊淑云,李盼池.量子衍生蜂群算法的設(shè)計與實現(xiàn)[J].系統(tǒng)仿真學(xué)報,2015，(7).

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