一種多目標量子算術優化算法探究

陳 超，趙海濤，王 臻

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

0 引言

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

近年來，研究學者已經提出了一系列優秀的多目標優化算法，如多目標粒子群優化算法(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)以及多目標灰狼優化算法(multi-objective grey wolf optimizer，MOGWO)等[11-15]。著名的“沒有免費的午餐”(no-free-lunch)定理[16]顯示沒有一種最佳方法可以解決所有的優化問題，這意味著可通過改進現有的算法或提出新的算法來幫助解決特定的問題。然而，目前提出的新算法更適合于解決無約束問題，若不使用特定的算子，就無法處理各種約束。因此，提出算術優化算法(arithmetic optimization algorithm，AOA)[17]與量子進化算法(quantum evolutionary algorithm，QEA)[18]相結合的多目標量子算術優化算法(MQAOA)，以解決實際應用問題。

1 多目標優化理論背景

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

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

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

圖1 雙目標最小化問題的帕累托最優概念示意

1.1 帕累托支配

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

1.2 帕累托最優解

1.3 帕累托最優解集

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

1.4 帕累托最優前沿

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

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

2 多目標量子算術優化算法

2.1 算術優化算法

算術優化算法是一種根據數學運算符算子(加、減、乘、除)的分布特性實現全局尋優的元啟發式優化算法[17]，主要步驟分為三步。

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

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

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

其中：α為控制參數，取值為5。

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

2) 在全局探索過程中，算法產生一個[0,1]的隨機數r2。當r2＞0.5時，執行除法算子；當r2≤0.5時，執行乘法算子。解的位置求解更新如下。

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

3) 在局部開發過程中，算法產生一個[0,1]的隨機數r3。當r3＞0.5時，算法執行加法算子；當r3≤0.5時，算法執行減法算子。解的位置求解更新如下。

2.2 改進的多目標量子算術優化算法

為將算術優化算法用于處理多目標優化問題，需要解決存儲搜索到的非支配解以及選擇存儲解的領導解兩個問題。

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

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

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

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

當外部檔案集被填滿時，則找到解的分布空間中最擁擠的超立方體，在該網格內隨機剔除一個非支配解。

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

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

關于MQAOA算法的計算復雜性，當n是群體的個體總數，m是目標總數時，MQAOA算法的計算復雜性可通過O(mn2)表示。該計算復雜性優于具有O(mn3)復雜性的算法。

3 算法性能驗證

3.1 試驗平臺與測試集

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

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

表1 算法參數設置

3.2 性能評價指標

3.2.1 世代距離

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

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

3.2.2 反向世代距離

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

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

3.2.3 最大散布指標

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

3.2.4 間距指標

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

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

3.3 驗證結果與分析

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

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

表2顯示了各算法在ZDT和DTLZ函數上的GD指標統計結果。可由數據得出：與其他比較方法（MOPSO、NSGA2、MOGWO）相比，MQAOA取得了更好的結果，在七個測試函數中的四個（ZDT1、ZDT2、ZDT4與ZDT6）獲得了最優秀的結果，其次是MOPSO，其在七個測試函數中的三個（ZDT3、DTLZ2與DTLZ4）帶來了最佳結果。MQAOA解決復雜的數學多目標優化問題的能力得到驗證，在大多數測試的問題中獲得了較好的結果，且標準差值較低。

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

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

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

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

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

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

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

4 結論

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