一種多目標(biāo)量子算術(shù)優(yōu)化算法探究

陳 超，趙海濤，王 臻

(國網(wǎng)浙江省電力有限公司信息通信分公司，浙江 杭州 310000)

0 引言

元啟發(fā)式方法是一組利用不同啟發(fā)式算法探索搜索空間的高級策略，在解決復(fù)雜的現(xiàn)實世界問題中非常有效。目前，眾多基于自然過程、集體行為或科學(xué)規(guī)則的元啟發(fā)式方法被提出并廣泛應(yīng)用于解決各種工程問題[1-5]，如差分進(jìn)化算法[6]、蟻群算法[7]、粒子群算法[8]、爬蟲搜索算法[9]等。應(yīng)用實踐表明，元啟發(fā)式算法在解決復(fù)雜的優(yōu)化問題時能夠以較高的精度和合理的時間來解決相關(guān)問題，同時具有易于實現(xiàn)、結(jié)構(gòu)簡單、精度好、執(zhí)行時間適當(dāng)?shù)葍?yōu)勢。在實踐中，解決單目標(biāo)優(yōu)化問題相對容易，但實際工程問題大都屬于多目標(biāo)優(yōu)化問題，目標(biāo)函數(shù)相互競爭，沒有標(biāo)準(zhǔn)方法可以同時對所有目標(biāo)函數(shù)進(jìn)行優(yōu)化。因此，決策者需要尋找可接受的替代方案而不是最佳方案，問題的帕累托解則是一種可接受的解決方案之一。在多目標(biāo)優(yōu)化問題中，最優(yōu)性是可通過帕累托最優(yōu)化方法進(jìn)行更新的；而多目標(biāo)優(yōu)化算法則通過尋找帕累托最優(yōu)解集獲得問題的可接受解[10]。

近年來，研究學(xué)者已經(jīng)提出了一系列優(yōu)秀的多目標(biāo)優(yōu)化算法，如多目標(biāo)粒子群優(yōu)化算法(multiobjective particle swarm optimization，MOPSO)、快速非支配排序遺傳算法(non-dominated sorting genetic algorithm II，NSGA2)、改進(jìn)強(qiáng)度帕累托進(jìn)化算法(improving the strength pareto evolutionary algorithm，SPEA2)、基于分解的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm based on decomposition，MOEA/D)以及多目標(biāo)灰狼優(yōu)化算法(multi-objective grey wolf optimizer，MOGWO)等[11-15]。著名的“沒有免費(fèi)的午餐”(no-free-lunch)定理[16]顯示沒有一種最佳方法可以解決所有的優(yōu)化問題，這意味著可通過改進(jìn)現(xiàn)有的算法或提出新的算法來幫助解決特定的問題。然而，目前提出的新算法更適合于解決無約束問題，若不使用特定的算子，就無法處理各種約束。因此，提出算術(shù)優(yōu)化算法(arithmetic optimization algorithm，AOA)[17]與量子進(jìn)化算法(quantum evolutionary algorithm，QEA)[18]相結(jié)合的多目標(biāo)量子算術(shù)優(yōu)化算法(MQAOA)，以解決實際應(yīng)用問題。

1 多目標(biāo)優(yōu)化理論背景

在多目標(biāo)優(yōu)化問題中，一般均包含多個相互沖突的目標(biāo)函數(shù)，在某個目標(biāo)上表現(xiàn)較好的個體，在其他目標(biāo)上可能表現(xiàn)較差。公式(1)表示了一個通用的多目標(biāo)優(yōu)化問題實例[19]。

其中，Ω表示可行解的集合，x∈Rk為決策變量，k是決策分量的數(shù)量，F(xiàn):Ω→Rm是一個多維的目標(biāo)映射函數(shù)，Rm代表目標(biāo)空間，ΩRk代表決策空間。

圖1為雙目標(biāo)最小化問題的帕累托最優(yōu)概念的示意，由此可推知帕累托最優(yōu)相關(guān)概念與定義[20-21]。

圖1 雙目標(biāo)最小化問題的帕累托最優(yōu)概念示意

1.1 帕累托支配

在多目標(biāo)問題中，對于給定的一組解，如=(x1，x2，，xk)和=(y1，y2，，yk)，當(dāng)且僅當(dāng)中所有的分量都不大于y→中的對應(yīng)值且存在至少一個分量小于中的對應(yīng)值時，認(rèn)為支配了(記為)。因此，在圖1中的解C支配了解D，具體定義如下。

1.2 帕累托最優(yōu)解

1.3 帕累托最優(yōu)解集

帕累托最優(yōu)解集(也稱為非支配解集)是所有帕累托最優(yōu)解的集合，計算公式如下。

1.4 帕累托最優(yōu)前沿

所有帕累托最優(yōu)解在目標(biāo)空間所構(gòu)建的圖像被稱為帕累托最優(yōu)前沿，計算公式如下。

解決多目標(biāo)問題，就需要確定帕累托最優(yōu)解集，即代表多目標(biāo)問題各目標(biāo)間最佳均衡的解決方案的集合。

2 多目標(biāo)量子算術(shù)優(yōu)化算法

2.1 算術(shù)優(yōu)化算法

算術(shù)優(yōu)化算法是一種根據(jù)數(shù)學(xué)運(yùn)算符算子(加、減、乘、除)的分布特性實現(xiàn)全局尋優(yōu)的元啟發(fā)式優(yōu)化算法[17]，主要步驟分為三步。

1) 首先算法使用數(shù)學(xué)加速算子(math optimizer accelerated，MOA)選擇搜索階段。

其中：t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)，Amax和Amin為加速算子的最大值與最小值，取值分別為1和0.2。

引入數(shù)學(xué)算子概率系數(shù)(math optimizer probability，MOP)，計算如下。

其中：α為控制參數(shù)，取值為5。

在更新獲得AMOA與PMOP后，算法產(chǎn)生一個[0,1]的隨機(jī)數(shù)r1，用來選擇算法的優(yōu)化策略。當(dāng)r1＞AMOA時，算法進(jìn)行全局探索(exploration)，采用乘法算子與除法算子提高解的分散性，增強(qiáng)算法的全局尋優(yōu)與克服早熟收斂能力，實現(xiàn)全局搜索尋優(yōu)；當(dāng)(r1≤AMOA)時，算法進(jìn)行局部開發(fā)(exploitation)，利用加法算子與減法算子降低解的分散性，有利于種群在當(dāng)前解局部鄰域范圍內(nèi)充分開發(fā)，加強(qiáng)算法的局部尋優(yōu)能力。

2) 在全局探索過程中，算法產(chǎn)生一個[0,1]的隨機(jī)數(shù)r2。當(dāng)r2＞0.5時，執(zhí)行除法算子；當(dāng)r2≤0.5時，執(zhí)行乘法算子。解的位置求解更新如下。

其中：μ是調(diào)整搜索過程的控制參數(shù)，取值為0.499；ε為極小值；B(xj)為目前所獲得的最優(yōu)的第j個分量取值；UBj和LBj為問題取值的上下界。

3) 在局部開發(fā)過程中，算法產(chǎn)生一個[0,1]的隨機(jī)數(shù)r3。當(dāng)r3＞0.5時，算法執(zhí)行加法算子；當(dāng)r3≤0.5時，算法執(zhí)行減法算子。解的位置求解更新如下。

2.2 改進(jìn)的多目標(biāo)量子算術(shù)優(yōu)化算法

為將算術(shù)優(yōu)化算法用于處理多目標(biāo)優(yōu)化問題，需要解決存儲搜索到的非支配解以及選擇存儲解的領(lǐng)導(dǎo)解兩個問題。

MQAOA算法采用外部檔案集存儲搜索到的非支配解，并執(zhí)行類似于NSGA2的領(lǐng)導(dǎo)解選取方式，主要分為三種情況。

1) 產(chǎn)生的新解被檔案中的解支配，則舍棄產(chǎn)生的新解。

2) 產(chǎn)生的新解支配檔案中的解，則剔除被支配的解，同時將新解加入檔案。

3) 產(chǎn)生的新解與檔案中所有的解互不支配，則將新解加入檔案。

當(dāng)外部檔案集被填滿時，則找到解的分布空間中最擁擠的超立方體，在該網(wǎng)格內(nèi)隨機(jī)剔除一個非支配解。

在傳統(tǒng)的AOA算法中，執(zhí)行加法或減法、乘法或除法的判斷參數(shù)p、q一般取固定值0.5。MQAOA算法使用量子旋轉(zhuǎn)門[18]根據(jù)算法選擇算子的情況和執(zhí)行算子的優(yōu)化結(jié)果對p、q進(jìn)行量子更新，使選擇加法(A)、減法(S)、乘法(M)、除法(D)算子的量子概率幅值(αA、αS、αM、αD)滿足αA2+α2B=1、αM2+αD2=1且p=αA2、q=αD2。在初始化過程中，四種算子的概率幅值均初始化為2/2。當(dāng)某種算子被選中且執(zhí)行算子后產(chǎn)生新的非支配解時，量子旋轉(zhuǎn)門將增強(qiáng)當(dāng)前所選算子的活躍程度，增加選中該算子的概率，計算公式如下。

其中：Δθ為旋轉(zhuǎn)角，相當(dāng)于決定了向當(dāng)前最優(yōu)解收斂速度的步長。如果選中該算子后未能產(chǎn)生新的非支配解，則對應(yīng)的概率幅值將被重新初始化，以保持算法的多樣性。

關(guān)于MQAOA算法的計算復(fù)雜性，當(dāng)n是群體的個體總數(shù)，m是目標(biāo)總數(shù)時，MQAOA算法的計算復(fù)雜性可通過O(mn2)表示。該計算復(fù)雜性優(yōu)于具有O(mn3)復(fù)雜性的算法。

3 算法性能驗證

3.1 試驗平臺與測試集

測試中使用七個標(biāo)準(zhǔn)測試問題對算法進(jìn)行對比試驗。所有的測試集均為最小化問題，具體包含ZDT系列測試問題和DTLZ系列測試問題。所有試驗均在Matlab 2020b與進(jìn)化多目標(biāo)優(yōu)化問題平臺PlatEMO v3.4上進(jìn)行。平臺配置如下：Core (TM) i9-10900k處理器、64GB RAM以及Windows 10系統(tǒng)。

種群數(shù)量設(shè)定為100，外部檔案集的最大容量設(shè)為100，最大迭代次數(shù)為1 000，各算法參數(shù)設(shè)置如表1所示；每個算法進(jìn)行30次獨(dú)立運(yùn)行，分別給出平均值和標(biāo)準(zhǔn)差并進(jìn)行相互比較；同時對每個問題都進(jìn)行威爾科克松符號秩檢驗[22]，顯著性水平設(shè)置為0.05。

表1 算法參數(shù)設(shè)置

3.2 性能評價指標(biāo)

3.2.1 世代距離

世代距離(generational distance，GD)指標(biāo)的計算基于算法所獲得的非支配前沿與真實帕累托最優(yōu)前沿之間的平均歐式距離。該指標(biāo)衡量了所獲得的非支配解的收斂性，定義如下。

其中:P*為真實帕累托最優(yōu)前沿的一組采樣值，R為檔案集中的解在目標(biāo)空間的投影，dis(R，Pi*)為R中的點(diǎn)到其在P*中距離最近的解在目標(biāo)空間的歐氏距離，k為P*中采樣點(diǎn)個數(shù)。

3.2.2 反向世代距離

反向世代距離(inverted generational distance，IGD)指標(biāo)的計算基于真實帕累托最優(yōu)前沿與算法所獲得的非支配前沿之間的平均歐式距離。該指標(biāo)同時衡量了所獲得的非支配解的多樣性與收斂性。與世代距離的區(qū)別在于反向世代距離是從真實帕累托前沿上的參考點(diǎn)射向算法得到的解，定義如下。

其中:P*為真實帕累托最優(yōu)前沿的一組采樣值，R為檔案集中的解在目標(biāo)空間的投影， 表示P*中的點(diǎn)到其在R中距離最近的解在目標(biāo)空間的歐氏距離，k表示P*中采樣點(diǎn)個數(shù)。

3.2.3 最大散布指標(biāo)

最大散布指標(biāo)(maximum spread，MS)指標(biāo)通過考慮各種最優(yōu)解，描述了候選解在其他獲得的集合中的分布，定義如下。

3.2.4 間距指標(biāo)

間距指標(biāo)(spacing，S)指標(biāo)的計算基于算法所獲得的非支配解之間的距離。該指標(biāo)主要衡量所獲得的非支配解的分布性，定義如下。

其中：di=minj(|f1(xi)-f1(xj)|+|f2(xi)-f2(xj)|)，表示兩個解間的最短距離，i，j=1，2，…，n，而表示所有di的平均值，n為帕累托最優(yōu)解的個數(shù)。

3.3 驗證結(jié)果與分析

MQAOA算法與三種多目標(biāo)優(yōu)化算法(MOPSO、NSGA2、MOGWO)在測試函數(shù)上的試驗結(jié)果如表2～5所示。符號+表示比較算法明顯優(yōu)于MQAOA，符號-表示比較算法明顯比MQAOA差，符號=表示兩者沒有顯著差異。

表2 各算法GD指標(biāo)的平均值和標(biāo)準(zhǔn)差

表2顯示了各算法在ZDT和DTLZ函數(shù)上的GD指標(biāo)統(tǒng)計結(jié)果?？捎蓴?shù)據(jù)得出：與其他比較方法（MOPSO、NSGA2、MOGWO）相比，MQAOA取得了更好的結(jié)果，在七個測試函數(shù)中的四個（ZDT1、ZDT2、ZDT4與ZDT6）獲得了最優(yōu)秀的結(jié)果，其次是MOPSO，其在七個測試函數(shù)中的三個（ZDT3、DTLZ2與DTLZ4）帶來了最佳結(jié)果。MQAOA解決復(fù)雜的數(shù)學(xué)多目標(biāo)優(yōu)化問題的能力得到驗證，在大多數(shù)測試的問題中獲得了較好的結(jié)果，且標(biāo)準(zhǔn)差值較低。

表3中各算法IGD指標(biāo)的統(tǒng)計表明了MQAOA比其他比較方法（MOPSO、NSGA2、MOGWO）獲得了更好的結(jié)果。MQAOA在七個測試函數(shù)中的五個獲得了最優(yōu)秀的結(jié)果，其次是MOPSO，其在七個測試函數(shù)中的兩個帶來了最好的結(jié)果。MQAOA在解決復(fù)雜的多目標(biāo)優(yōu)化問題上的能力較為突出，在大多數(shù)測試的問題中產(chǎn)生了最好的結(jié)果，且標(biāo)準(zhǔn)差很低，而NSGA2、MOGWO在IGD性能指標(biāo)方面沒有獲得任何最佳結(jié)果。

表3 各算法IGD指標(biāo)的平均值和標(biāo)準(zhǔn)差

表4中各算法MS指標(biāo)的統(tǒng)計表明MQAOA在幾乎所有的測試函數(shù)中都比其他比較方法(MOPSO、NSGA2、MOGWO)有更好的結(jié)果。MQAOA在七個測試函數(shù)中都獲得了最優(yōu)秀的結(jié)果，除ZDT3和DTLZ2函數(shù)外，MQAOA的標(biāo)準(zhǔn)差值也是最好的，而MOPSO、NSGA2、MOGWO在MS指標(biāo)方面沒有獲得任何最佳結(jié)果。

表4 各算法MS指標(biāo)的平均值和標(biāo)準(zhǔn)差

表5中各算法S指標(biāo)的統(tǒng)計表明MQAOA比其他算法(MOPSO、NSGA2、MOGWO)有更好的結(jié)果。MQAOA在七個測試函數(shù)中的三個(ZDT2、ZDT3、ZDT6)獲得了最優(yōu)秀的結(jié)果，其次是NSGA2，其在七個測試函數(shù)中的三個(ZDT4、DTLZ2、DTLZ4)獲得了最優(yōu)秀的結(jié)果，而MOGWO在七個測試函數(shù)中的一個(ZDT1)獲得了最優(yōu)秀的結(jié)果。MQAOA有能力解決復(fù)雜的多目標(biāo)優(yōu)化問題，并實現(xiàn)良好的分布性。除ZDT1、DTLZ2和DTLZ4之外，MQAOA在大多數(shù)低標(biāo)準(zhǔn)差值的測試問題中產(chǎn)生了最佳結(jié)果。而MOPSO在S指標(biāo)方面沒有獲得任何最佳結(jié)果。

表5 各算法S指標(biāo)的平均值和標(biāo)準(zhǔn)差

通過試驗對比可知：相對于其他三種對比算法，MQAOA可在真正的帕累托前沿附近產(chǎn)生更多的兼具收斂性和廣泛分布性的帕累托最優(yōu)解，根據(jù)各算法IGD、MS、S指標(biāo)的數(shù)據(jù)對比，MQAOA更加有效。

4 結(jié)論

多目標(biāo)優(yōu)化算法可以為各種具有許多相互矛盾目標(biāo)的復(fù)雜問題向決策者提供解決方案?；跈n案的多目標(biāo)量子算術(shù)優(yōu)化算法利用量子選擇算子對算法采用的數(shù)學(xué)運(yùn)算符算子進(jìn)行選擇與搜索，采用檔案集進(jìn)行存儲與更新非支配的帕累托最優(yōu)解。算法性能測試表明：與其他常用算法相比，MQAOA算法性能優(yōu)越，收斂速率快，解的分布性更好，為解決實際工程問題提供了一種較優(yōu)秀的方法。