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

陳 超，趙海濤，王 臻

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

0 引言

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

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

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

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

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

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

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

1.1 帕累托支配

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

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

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

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

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

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

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

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

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

算術(shù)優(yōu)化算法是一種根據(jù)數(shù)學(xué)運算符算子(加、減、乘、除)的分布特性實現(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]的隨機數(shù)r1，用來選擇算法的優(yōu)化策略。當(dāng)r1＞AMOA時，算法進行全局探索(exploration)，采用乘法算子與除法算子提高解的分散性，增強算法的全局尋優(yōu)與克服早熟收斂能力，實現(xiàn)全局搜索尋優(yōu)；當(dāng)(r1≤AMOA)時，算法進行局部開發(fā)(exploitation)，利用加法算子與減法算子降低解的分散性，有利于種群在當(dāng)前解局部鄰域范圍內(nèi)充分開發(fā)，加強算法的局部尋優(yōu)能力。

2) 在全局探索過程中，算法產(chǎn)生一個[0,1]的隨機數(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]的隨機數(shù)r3。當(dāng)r3＞0.5時，算法執(zhí)行加法算子；當(dāng)r3≤0.5時，算法執(zhí)行減法算子。解的位置求解更新如下。

2.2 改進的多目標量子算術(shù)優(yōu)化算法

為將算術(shù)優(yōu)化算法用于處理多目標優(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)隨機剔除一個非支配解。

在傳統(tǒng)的AOA算法中，執(zhí)行加法或減法、乘法或除法的判斷參數(shù)p、q一般取固定值0.5。MQAOA算法使用量子旋轉(zhuǎn)門[18]根據(jù)算法選擇算子的情況和執(zhí)行算子的優(yōu)化結(jié)果對p、q進行量子更新，使選擇加法(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)門將增強當(dāng)前所選算子的活躍程度，增加選中該算子的概率，計算公式如下。

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

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

3 算法性能驗證

3.1 試驗平臺與測試集

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

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

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

3.2 性能評價指標

3.2.1 世代距離

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

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

3.2.2 反向世代距離

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

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

3.2.3 最大散布指標

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

3.2.4 間距指標

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

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

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

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

表2 各算法GD指標的平均值和標準差

表2顯示了各算法在ZDT和DTLZ函數(shù)上的GD指標統(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é)多目標優(yōu)化問題的能力得到驗證，在大多數(shù)測試的問題中獲得了較好的結(jié)果，且標準差值較低。

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

表3 各算法IGD指標的平均值和標準差

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

表4 各算法MS指標的平均值和標準差

表5中各算法S指標的統(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ù)雜的多目標優(yōu)化問題，并實現(xiàn)良好的分布性。除ZDT1、DTLZ2和DTLZ4之外，MQAOA在大多數(shù)低標準差值的測試問題中產(chǎn)生了最佳結(jié)果。而MOPSO在S指標方面沒有獲得任何最佳結(jié)果。

表5 各算法S指標的平均值和標準差

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

4 結(jié)論

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