金 瑾, 王 鵬

(1. 中國科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所， 四川 成都 610041； 2. 中國科學(xué)院大學(xué)， 北京 100049； 3. 西南民族大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 四川 成都 610225)

工業(yè)設(shè)計(jì)、控制、自動(dòng)化等應(yīng)用場景普遍存在優(yōu)化問題.近年來，自然計(jì)算方法解決了大量的優(yōu)化問題.這些算法包括蟻群算法[1]、粒子群算法[2]、差分進(jìn)化算法[3]、人工蜂群算法[4]、煙花算法[5]、頭腦風(fēng)暴算法[6]、象群優(yōu)化算法[7]、教與學(xué)優(yōu)化算法[8]、獅群算法[9]，以及協(xié)方差自適應(yīng)進(jìn)化策略(CMA-ES)[10].

多尺度量子諧振子優(yōu)化算法(MQHOA)是基于量子物理理論提出的自然計(jì)算方法[11]，該算法把優(yōu)化問題通過勢阱等效轉(zhuǎn)化為對薛定諤方程的求解問題.算法主要包含兩個(gè)迭代過程：第一是量子諧振子過程，粒子依據(jù)波函數(shù)的模方，生成滿足一定參數(shù)分布的采樣點(diǎn)，再根據(jù)這些粒子適應(yīng)度值判斷下一次采樣的種群；第二是多尺度過程，尺度按照2n遞減，在每個(gè)量子諧振子過程中，利用目標(biāo)函數(shù)的簡單統(tǒng)計(jì)均值信息，對高能級暫穩(wěn)態(tài)進(jìn)行一定擾動(dòng).

在多尺度過程中，大部分目標(biāo)函數(shù)的信息未能被成功利用，雖然量子隧穿效應(yīng)能夠一定程度上避免算法陷入局部最優(yōu)解，但單純的尺度衰減容易導(dǎo)致算法早熟停滯.針對這一問題，眾多學(xué)者不斷提出改進(jìn)的MQHOA.最新關(guān)于MQHOA的研究主要針對算法中的統(tǒng)計(jì)均值及遷移策略[12].文獻(xiàn)[13]討論多諧振子改進(jìn)的MQHOA，文獻(xiàn)[14]利用群體穩(wěn)定性及更嚴(yán)格的個(gè)體約束來提高算法的收斂速度及魯棒性.這些研究表明，目標(biāo)函數(shù)應(yīng)該保留關(guān)于可行和不可行的關(guān)鍵信息，使用目標(biāo)函數(shù)的信息有助于提高算法的性能，對更好地計(jì)算和評估下一代個(gè)體具有重要作用.基于上述思想，本文提出了歷史數(shù)據(jù)驅(qū)動(dòng)的多尺度量子諧振子優(yōu)化算法(HI-MQHOA).

在MQHOA的兩步迭代過程中，HI-MQHOA通過分析較優(yōu)歷史數(shù)據(jù)提高M(jìn)QHOA的性能；利用目標(biāo)函數(shù)的歷史信息解決MQHOA的收斂問題，運(yùn)用目標(biāo)函數(shù)產(chǎn)生的信息引導(dǎo)算法尋找最優(yōu)解.實(shí)驗(yàn)表明，在給定測試集上，HI-MQHOA優(yōu)于其他MQHOA的改進(jìn)版本和一些主流優(yōu)化算法.基于HI-MQHOA優(yōu)秀的全局搜索性能和快速收斂特性，該算法也適用于大規(guī)模優(yōu)化問題.

1 標(biāo)準(zhǔn)MQHOA

1.1 MQHOA物理模型

量子力學(xué)中波函數(shù)可以體現(xiàn)粒子在空間某位置出現(xiàn)的概率.由文獻(xiàn)[15]可知，薛定諤方程可以描述量子系統(tǒng)，定態(tài)薛定諤方程的表達(dá)式如下：

(1)

式中：E表示量子能級；?表示約化普朗克常數(shù)；m表示粒子質(zhì)量；ΨE(x)為E能級下的本征方程；V(x) 表示勢阱.這里以目標(biāo)函數(shù)f(x)替換薛定諤中的勢阱，即V(x)=f(x)，代入之后的薛定諤方程如式(2)所示：

(2)

由于薛定諤方程通常難以求解，MQHOA通過泰勒展開，用近似方法對復(fù)雜目標(biāo)函數(shù)進(jìn)行逼近.通過泰勒展開的目標(biāo)函數(shù)可以被重寫為式(3)：

(3)

式中：n!表示n的階乘；x0為全局最優(yōu)解；fn(x0)是函數(shù)在x0點(diǎn)的第n階導(dǎo)數(shù).在全局最優(yōu)解的位置f(x0)為常數(shù)，其一階導(dǎo)數(shù)f′(x0)=0，二階導(dǎo)數(shù)f″(x0)>0.假設(shè)當(dāng)(x-x0)足夠小時(shí)高階項(xiàng)可以忽略，則目標(biāo)函數(shù)的二階泰勒展開式可以近似于勢阱，即

(4)

經(jīng)過近似操作后，基態(tài)波函數(shù)的概率密度函數(shù)為

(5)

1.2 MQHOA基本流程

MQHOA包括兩個(gè)過程[11]，即在同一尺度上的量子諧振子過程(QHO過程)和多尺度過程.

QHO過程又包括能級穩(wěn)定和能級過渡過程.能級穩(wěn)定過程實(shí)現(xiàn)了量子系統(tǒng)進(jìn)入一個(gè)相對穩(wěn)定的亞穩(wěn)態(tài)：根據(jù)具體策略生成候選解，計(jì)算出能級穩(wěn)定準(zhǔn)則所需的取值；如果不滿足條件，則繼續(xù)進(jìn)行該能級穩(wěn)定過程，即生成新的解，并重復(fù)計(jì)算和判斷.能級過渡過程通過一定的擾動(dòng)策略，使解空間中當(dāng)前最優(yōu)解發(fā)生變化并移動(dòng)到較好的解位置，從而實(shí)現(xiàn)能級過渡目標(biāo).

多尺度過程的主要作用是，引導(dǎo)算法從高能態(tài)的大范圍搜索到低能態(tài)的小范圍搜索過程.多尺度調(diào)整過程采用了衰減策略，使算法在較小的尺度上重復(fù)從高能量級到基態(tài)的過程；然后，再重復(fù)量子諧振子過程，在新的尺度層面上對解空間進(jìn)行更全面的搜索.多尺度過程提高采樣精度.

2 MQHOA存在的問題及改進(jìn)

在標(biāo)準(zhǔn)的MQHOA中，粒子的QHO過程僅使用了統(tǒng)計(jì)均值信息，而忽略了其他有用信息.本文利用歷史數(shù)據(jù)驅(qū)動(dòng)的方法，提出HI-MQHOA.該算法在兩個(gè)方面優(yōu)于MQHOA及其改進(jìn)算法.以下是詳細(xì)說明.

2.1 基于多元統(tǒng)計(jì)分析改進(jìn)的QHO過程

在MQHOA基礎(chǔ)版中，算法的波函數(shù)被定義為多個(gè)一維正態(tài)分布的疊加，即

(6)

式中：k為初始化粒子的個(gè)數(shù)；xi為第i個(gè)粒子的位置；σs為當(dāng)前搜索尺度.MQHOA在不同維度的搜索中采用相同的尺度，未考慮不同維度的差異；而在實(shí)際的優(yōu)化問題中，不同維度對目標(biāo)函數(shù)的貢獻(xiàn)是不同的.因此，厘清維度之間的差異能夠避免算法進(jìn)行無用的搜索，從而加快算法的收斂.HI-MQHOA針對這一問題，研究多元高斯自帶相關(guān)特性對MQHOA的影響.波函數(shù)在HI-MQHOA中的定義如式(7)所示：

(7)

式中：d是問題的維度；C是多元高斯分布的協(xié)方差矩陣；xi是采樣中心點(diǎn)，一共k個(gè)，其維度為d；k個(gè)采樣種群中的個(gè)體數(shù)為λ.協(xié)方差矩陣可以表示為

(8)

對此，本文提出新的均值向量生成模型.該模型由當(dāng)代信息產(chǎn)生下一代個(gè)體分布參數(shù).首先，按照適應(yīng)度值對個(gè)體進(jìn)行排序：x1

(9)

(10)

uk只與個(gè)體總數(shù)λ和個(gè)體排序位置j有關(guān).加入效用函數(shù)后式(9)變?yōu)?/p>

(11)

由此計(jì)算出的下一代多元高斯分布的協(xié)方差為

(12)

式中，C(g)為當(dāng)代個(gè)體的協(xié)方差，它由上一代個(gè)體計(jì)算得出.歷史數(shù)據(jù)驅(qū)動(dòng)的采樣模型(算法1)見表1.

表1 歷史數(shù)據(jù)驅(qū)動(dòng)的采樣模型(算法1)

2.2 動(dòng)態(tài)調(diào)整的多尺度過程

MQHOA采用固定衰減的多尺度過程，而固定衰減有兩個(gè)不足：一是衰減的系數(shù)一直為0.5，這個(gè)衰減系數(shù)并不會(huì)根據(jù)具體問題發(fā)生變化；二是過早的衰減會(huì)導(dǎo)致算法早熟停滯.因此，HI-MQHOA采用動(dòng)態(tài)機(jī)制調(diào)整的多尺度過程.由上面改進(jìn)QHO過程的分析可知，當(dāng)代個(gè)體根據(jù)適應(yīng)度值排序，根據(jù)均值向量或差值向量生成下一代個(gè)體，由于協(xié)方差自帶尺度信息[17]，因此可以由協(xié)方差矩陣的信息產(chǎn)生動(dòng)態(tài)尺度衰減.動(dòng)態(tài)尺度設(shè)置如下：

(13)

3 HI-MQHOA

本節(jié)探討的偽代碼是基于第2節(jié)關(guān)于多元統(tǒng)計(jì)分析改進(jìn)的QHO過程，以及動(dòng)態(tài)調(diào)整的多尺度過程的闡述.HI-MQHOA偽代碼(算法2)見表2.

表2 HI-MQHOA偽代碼(算法 2)

算法中采樣模型的設(shè)置基于以下考慮：

圖像分析法.圖像分析法的具體操作是將鏡頭獲取的圖像信息進(jìn)行定時(shí)抽幀分析，將時(shí)間分為幾個(gè)區(qū)間，每過一個(gè)區(qū)間進(jìn)行對圖像的分析描點(diǎn)，測量出角度的變化從而分析角速度.

1) 種群的收斂方向.選擇最優(yōu)的部分作為下一代個(gè)體生成的參數(shù)，可以使下一代個(gè)體分布在近似梯度方向上.

2) 算法搜索的范圍.如果最優(yōu)個(gè)體不包含在采樣范圍內(nèi)，則下一次搜索應(yīng)擴(kuò)大種群的搜索范圍；如果采樣范圍內(nèi)包含了最優(yōu)個(gè)體，此時(shí)應(yīng)減小探索的區(qū)域，使算法能夠智能感知最優(yōu)解的范圍.

4 實(shí)驗(yàn)與分析

在HI-MQHOA中，需要設(shè)置的參數(shù)是種群數(shù)k、生成指導(dǎo)信息的參數(shù)α及種群個(gè)體數(shù)λ.對于HI-MQHOA，α的值通常在(0,1)之間，較小的α使算法更快收斂，而較大的α使算法更有效地利用目標(biāo)函數(shù)的值.結(jié)合這些信息，通過驗(yàn)證，當(dāng)α=0.3時(shí)，算法的性能達(dá)到最佳.

本文通過選定的測試函數(shù)集驗(yàn)證HI-MQHOA的有效性[18].該測試函數(shù)集包含常見的單模和多模函數(shù)，測試函數(shù)如表3所示.其中，f1～f5為單模函數(shù)，f6～f14為多模函數(shù)，這些函數(shù)的最優(yōu)解均為0.

表3 測試函數(shù)

在接下來的實(shí)驗(yàn)中，算法的終止條件為最大迭代次數(shù)10 000×d,其中d代表問題的維度.為了排除隨機(jī)性的影響，每個(gè)實(shí)驗(yàn)會(huì)重復(fù)51次.

4.1 參數(shù)選擇及歷史數(shù)據(jù)驅(qū)動(dòng)的有效性驗(yàn)證

為了驗(yàn)證本文算法的有效性，將HI-MQHOA分別與MQHOA和IS-MQHOA進(jìn)行比較.為確保公平，每個(gè)算法的種群數(shù)量設(shè)置與文獻(xiàn)[12]一致，即λ=40.為了測試算法的魯棒性，本文引入成功率(SR)作為測度，SR表示在精度為10-6時(shí)找到最優(yōu)解的比率.

參數(shù){α,λ}的值也是通過實(shí)驗(yàn)來選取.如表5所示，當(dāng)參數(shù)為{0.3,40}時(shí)，HI-MQHOA在函數(shù)f1,f2,f5,f7,f8,f11,f12和f13上解的平均值及方差均優(yōu)于其他算法.參數(shù)為{0.3,40}時(shí)，HI-MQHOA排名第1的次數(shù)為8，{0.2，40}時(shí)為4，{0.1，40}為3；而參數(shù)為{0.3，80}時(shí)HI-MQHOA優(yōu)于其他算法的次數(shù)為0.因此，對于HI-MQHOA來說，并不是種群越大越好.隨著種群規(guī)模的增加，算法的計(jì)算復(fù)雜度會(huì)增加，但尋優(yōu)性能并未隨之變得更好.所以，單純增加種群規(guī)模，提升算法性能的效果是有限的，有時(shí)可能導(dǎo)致性能下降.根據(jù)實(shí)驗(yàn)結(jié)果分析可知， HI-MQHOA所涉及的參數(shù){k,α,λ}的值為{1,0.3,40}.

表4 Wilcoxon 秩檢驗(yàn)實(shí)驗(yàn)結(jié)果

表5 不同參數(shù)下的性能比較

4.2 仿真數(shù)據(jù)對比分析

為了全面分析HI-MQHOA的性能，本文選取以下對比算法：

1) QPSO(quantum PSO): QPSO是一種功能強(qiáng)大的量子行為粒子群優(yōu)化算法，能非常有效地解決小規(guī)模優(yōu)化問題[19].

2) 標(biāo)準(zhǔn)粒子群優(yōu)化算法(standard PSO,SPSO): PSO的標(biāo)準(zhǔn)版本，常被用作測試其他優(yōu)化算法的基準(zhǔn)[20].參數(shù)為：c1=c2=0.5+lnx,w=1/(2 ln 2).

3) DE:一種優(yōu)秀的自然計(jì)算算法[21].參數(shù)設(shè)置為：F=0.5,CR=0.9.

4) ABC：在ABC中，食物源個(gè)數(shù)SN設(shè)置為100，limit是與食物源相關(guān)的另一個(gè)參數(shù).當(dāng)收集到的食物源數(shù)量超過limit的值時(shí)，它們就會(huì)被丟棄[4].

5) CMA-ES:在CMA-ES中，新的候選解根據(jù)多元正態(tài)分布的參數(shù)進(jìn)行采樣[10].

6) BBFWA:一種具有競爭力的群體智能算法，已經(jīng)得到廣泛應(yīng)用[22].

在維度等于60的條件下，對這些算法進(jìn)行測試，實(shí)驗(yàn)結(jié)果如表6所示.為了直觀分析表6數(shù)據(jù)，圖1展示了幾個(gè)算法平均值優(yōu)于其他算法的次數(shù).從圖中可以看出，HI-MQHOA的優(yōu)化結(jié)果優(yōu)于除f1,f2,f4,f5和f13以外的其他算法，取得最好的平均排名；其次是DE和CMA-ES，表明HI-MQHOA具有解決復(fù)雜函數(shù)問題的能力.由于ABC和BBFWA沒有一次超越其他算法，因此沒有在圖1中顯示.

為了驗(yàn)證算法間性能差異是否明顯，HI-MQHOA與其他算法之間還進(jìn)行了Wilcoxon符號秩檢驗(yàn).圖2展示了HI-MQHOA顯著優(yōu)于其他算法的次數(shù).在該實(shí)驗(yàn)中，將測試函數(shù)分為5個(gè)單模和9個(gè)多模進(jìn)行對比.從圖中可以看出，在單模函數(shù)方面，HI-MQHOA優(yōu)于ABC和BBFWA算法5次，而優(yōu)于QPSO算法4次，優(yōu)于CMA-ES算法2次；在多模函數(shù)上，HI-MQHOA優(yōu)于ABC，BBFWA和QPSO算法7次，優(yōu)于DE算法5次，優(yōu)于CMA-ES算法3次.HI-MQHOA在單模函數(shù)上性能不及CMA-ES和DE算法；在多模函數(shù)方面，HI-MQHOA的結(jié)果明顯優(yōu)于ABC，BBFWA和QPSO算法.

由表6、圖1及圖2的分析看出，對于多模函數(shù)，HI-MQHOA能夠較為精確地找到最優(yōu)解，因?yàn)镠I-MQHOA能夠較好地平衡探索和開發(fā).而對于單模問題，HI-MQHOA優(yōu)勢不夠明顯，原因在于算法提出的動(dòng)態(tài)尺度在面對復(fù)雜多模問題時(shí)具備優(yōu)勢，而對于單模問題不具備優(yōu)勢，因?yàn)閱文栴}要求算法能夠快速定位解的位置，從而更好地開發(fā)以獲得高精度的解.QPSO和CMA-ES在單模函數(shù)f1,f2上表現(xiàn)優(yōu)于HI-MQHOA，但是它在多模問題上面臨早熟的問題.這也再次證明了對于優(yōu)化問題不存在一成不變的最優(yōu)解決方法[23].

表6 60維函數(shù)下HI-MQHOA與其他算法的性能對比

圖1 不同算法在測試中平均值優(yōu)于其他算法的次數(shù)

圖2 不同算法的性能對比

4.3 HI-MQHOA解決高維優(yōu)化問題

在工程應(yīng)用場景中，許多優(yōu)化問題涉及大量的變量.因此，在設(shè)計(jì)算法時(shí)應(yīng)考慮到可伸縮性.上述維度為60的實(shí)驗(yàn)證實(shí)，HI-MQHOA，CMA-ES和DE這三種算法整體性能最好.本節(jié)討論HI-MQHOA在高維(d=200)優(yōu)化問題中的應(yīng)用.

實(shí)驗(yàn)的均值排名結(jié)果如表7和圖3所示.表7所示，除f13和f14外，HI-MQHOA的標(biāo)準(zhǔn)差性能優(yōu)于CMA-ES和DE，表明HI-MQHOA具有很好的穩(wěn)定性；從尋優(yōu)準(zhǔn)確率上看，只要HI-MQHOA能夠找到最優(yōu)解，準(zhǔn)確率均為100%，表現(xiàn)出良好的尋優(yōu)性能.圖3中橫坐標(biāo)為14個(gè)測試函數(shù)，縱坐標(biāo)為排名情況.除f7,f13和f14外，HI-MQHOA優(yōu)化結(jié)果的平均值優(yōu)于CMA-ES和DE，體現(xiàn)了HI-MQHOA的優(yōu)勢.以上分析證實(shí)了HI-MQHOA具有解決高維優(yōu)化問題的潛力.

表7 高維函數(shù)測試結(jié)果

圖3 高維函數(shù)均值排名的可視化

5 結(jié) 語

本文提出HI-MQHOA，解決了MQHOA歷史信息利用率低的問題.首先，通過選擇最優(yōu)部分解的質(zhì)心來獲取指導(dǎo)信息，充分利用了算法中的歷史數(shù)據(jù)；其次，通過兩代最優(yōu)部分解的質(zhì)心之間距離，自適應(yīng)調(diào)整算法的尺度.這兩部分的改進(jìn)，使算法能夠在搜索空間中更加合理地進(jìn)行探索和開發(fā).同時(shí)，不僅與MQHOA及IS-MQHOA的對比實(shí)驗(yàn)，驗(yàn)證了歷史數(shù)據(jù)驅(qū)動(dòng)機(jī)制的有效性，而且與其他主流算法的對比實(shí)驗(yàn)，也驗(yàn)證了算法在最優(yōu)化領(lǐng)域的潛力.另外，HI-MQHOA可以有效解決高維全局優(yōu)化問題，說明算法具有良好的延展性.總之，利用歷史數(shù)據(jù)驅(qū)動(dòng)機(jī)制來改進(jìn)自然計(jì)算的原理簡單有效，對其他算法的設(shè)計(jì)具有一定的指導(dǎo)意義.