基于決策空間劃分的雙模型協同搜索多目標優化方法

一、前言

復雜多目標優化問題廣泛存在于實際應用中（如車輛路徑規劃1、無人機調度問題[2]等）。這些問題通常需要同時優化多個指標，沒有明確的解析表達式，目標梯度不可用。在求解時，函數評估往往基于昂貴的物理實驗或耗時的模型擬合，稱為昂貴多目標優化問題。為了減少真實的目標函數評估次數，學者們提出多種代理模型輔助的進化算法（Surrogate-assistedEvolutionaryAlgorithm，SAEA）[3用于解決昂貴多目標優化問題。在SAEA算法中，通過歷史數據集訓練代理模型替代真實的函數評估，使算法在有限精確評估次數下，快速找到最優帕累托解集。

首先，在多模態優化問題中，適應度景觀中有許多局部最優點。因此SAEA算法很容易陷入局部最優。其次，在沒有先驗知識的情況下，算法很難選擇合適的模型及訓練集。再次，設置填充準則的好壞直接影響算法搜索效率。基于以上分析，本文提出了一種基于決策，該策略將決策空間劃分為若干區域，然后構建的全局代理模型同時搜索這些區域，來實現在決策空間中實現良好的探索能力，降低陷入局部最優的概率。本文提出一種混合估值策略，旨在為每個優化目標建立局部模型，實現全局和局部模型協同搜索種群進化。最后，使用填充準則選擇真實評價個體，從而更新數據集，輸出最優解集。

二、基于決策空間劃分的雙模型協同搜索多目標優化方法

（一）算法框架

本文提出基于決策空間劃分的雙模型協同搜索多目標優化方法。首先使用拉丁超立方采樣生成初始樣本點，并進行真實評價存入數據集。其次基于決策空間將數據集劃分為k個簇，進行全局模型搜索得到種群P1。同時基于目標空間構建全局和局部雙模型，使用RVEA[4算法進行混合模型協同搜索得到有潛力的個體。最后基于本文提出的填充準則選擇個體進行真實評估，更新數據集，詳細算法步驟見表1。

（二）雙模型協同種群進化搜索

在昂貴的優化問題中存在多種多模態優化問題，這些問題可能包含大量局部極值點。因此，SAEA算法在搜索中很容易陷人局部最優解。通過提高進化優化算法的探索和開采能力，可以降低陷人局部最優解的概率。DSP-SAEA算法提出一種基于決策空間劃分的全局和局部雙模型搜索策略，詳見表2。

表1算法主要框架

表2雙模型協同種群進化搜索步驟

該策略的主要思想是使用K-Medoids聚類，將Arch中的數據集在決策空間劃分為n個簇。給定第i個簇，如果分布在該區域內數據點的數量大于5D，則該區域內的所有數據點都作為模型訓練點存入DS中。否則，選擇距離該區域最近的數據點補齊存入DS中，詳見表3。然后，在每個區域分別選取K個點，共 n^*k 點作為初始父代種群 P（t） 。分別為每個建立全局RBF模型和鄰域估值的局部模型，協同搜索，得到后代種群P（t+1） 。算法通過全局RBF模型捕捉整體趨勢，局部模型精準刻畫局部特征，有效平衡探索與開采。迭代過程中，動態調整模型參數，確保種群多樣性，逐步逼近全局最優解。將數據集DS作為訓練集去構建全局RBF模型。基于在每個區域分別選取K個點，共n×k 點作為初始父代種群P（t）。分別為每個建立全局RBF模型和鄰域估值的局部模型，協同搜索，得到后代種群 P（Ω_t+1） 。

（三）鄰域估值的局部模型策略

本文提出一種基于個體鄰域內適應值估模型，該模型基于決策空間中個體間的位置關系構建。在種群P0 ）代中個體 X_k 的適應值估計方法為：在決策空間中，計算個體 X_k 與數據集Arch中所有數據點之間的歐氏距離和角度值分別得到 d_k 和 cosθ_k ，再通過公式（1）求得權重系數 w 。此時，個體 X_k 與Arch中 ρ_m 個解使用式（1）計算出 Σ_m 個 Δ_W 值，將 m 個 w 值從大到小排序，取前j個解的目標函值，通過式（2）計算 ΔX_k 的估值。

表3全局模型訓練集DS的選擇

表4RVEA、K-RVEA、CSEA、DSP-SAEA算法在DTLZ1中測試結果對比

鄰域估值的局部模型估值過程如下。

m 為 Arch 中解的數量大小。

f_j=f_j¹，f_j²，…，f_j^m ， m 為目標數。

（四）填充準則

在SAEA算法中，填充準則作為策略，在種群進化過程中用來選擇真實計算的個體，從而加入訓練集中，動態更新模型。然而不同選擇策略可以對模型帶來不同的性能改進。

基于收斂性和多樣性選擇真實計算個體有助于提高種群在收斂和多樣性方面的性能，而不確定度選擇策略有利于提高代理模型的全局近似精度。

由于本文研究的多目標優化問題成本高昂，需要在有限的函數真實評估次數下，充分利用填充準則策略。因此，本文考慮算法的收斂性和模型估值的不確定性，通過求個體的全局模型估值和鄰域局部模型估值的均方差作為不確定度，然后將個體的不確定值的負值和APD值作為兩個目標進行非支配排序；隨機選擇第一層的2個個體進行真實計算。將真實計算的個體加入Arch中，從而更新最優解集PS。

三、實驗設計及結果分析

為了驗證本文提出的DSP-SAEA算法的性能，在DTLZ1- -7^[5] 基準測試問題上，與近年來性能好的3個SAEA多目標算法進行了實驗結果對比。本文設置測試問題維度為30維，優化目標分別為3和5，最大評價次數max_EFs為 300 。文中所有算法都使用Wilcoxon秩和（WRS）檢驗，來比較30次獨立運行中顯著性水平為0.05的結果。本文采用反世代距離IGD作為評價指標，IGD值越小，算法性能越好。

本文將DSP-SAEA算法與K-RVEA算法、CSEA算法、RVEA算法在DTLZ基準問題上進行了測試，表3給出了對比結果。表中符號“ + ，-， Φ=Φ^′′ 分別表示對比算法比DSP-SAEA性能好、性能差以及無明顯差異。

表3中對比結果來看，在DTLZ6中，DSP-SAEA展現了其有效的收斂速度，其他三種算法仍然無法收斂。相反在DTLZ5上，同行算法的性能穩定，幾乎能夠找到所需的 PF 而在多模態問題DTLZ7中，DSP-SAEA算法可以在收斂性和多樣性之間尋求平衡，從而獲得最穩健的性能。在DTLZ2和DTLZ3上，直觀來看，DSP-SAEA的IGD值是算法中最小的，表明其具有更優的搜索能力。

在DTLZ1和DTLZ4測試問題上，DSP-SAEA算法的多樣性有所下降，原因可能是，在多目標空間中參考向量較為稀疏。因此，多樣性階段未能完善性能。為了解決這一挑戰，需要增加參考向量的數量，以更密集地劃分目標空間。

四、結語

本文提出了一種針對昂貴多目標優化問題的基于決策空間劃分的雙代理協同搜索的優化算法DSP-SAEA，該算法使用聚類算法將數據集的決策空間進行劃分，在簇中選擇數據點構造訓練集訓練全局模型，同時基于個體鄰域內適應值估計構造局部模型。然后使用局部和全局雙代理模型去搜索種群中有潛力的個體，最后使用基于估值不確定度和APD值的非支配排序的填充準則策略從有潛力的個體中選擇真實計算的解。

與現有的先進算法相比，DSP-SAEA在高維多目標情況下，具有良好的性能。無論問題的類型、PF特性以及目標或維度的數量如何，DSP-SAEA算法都具有極快的收斂速度。對于可能收斂的問題，DSP-SAEA可以找到更多的非支配解，這意味著它可以為昂貴的優化問題提供更多的方案。

但本文仍需改進多峰多目標優化問題的模型采樣方法，這樣算法使用近似不確定度來搜索更好的解時，可以減少模型訓練時間。從而可以將DSP-SAEA算法更好地用于實際的工程優化問題中。

參考文獻

[1]李堅強，蔡俊創，孫濤，等.面向復雜物流配送場景的車輛路徑規劃多任務輔助進化算法[J].自動化學報，2024，50（03）：544-559.

[2]Z.H.Sun，X.Luo.Monitoring Scheduling of Drones for Emission Control Areas：An Ant Colony-Based Approach[J].IEEE Transactions on Intelligent Transportation Systems，2022，23（08）：11699-11709.

[3]劉曉彤，孫超利，王浩，等.兩階段模型協同搜索的昂貴多目標進化優化[J].控制理論與應用，2024，41（09）：1676-1684.

[4]K.Deb，H.Jain.An Surrogate-Assisted Reference Vector Guided Evolutionary Algorithm for Computationally Expensive Many-Objective Optimization[J].IEEE Transactions on Evolutionary Computation，2016，22（01）：129-142.

[5]K.DEB，L.HIELE L，M.LAUMANNS.Scalable test problemsfor evolutionary multiobjective optimization.International Conference onEvolutionary Multi-Criterion Optimization[C].London，UK：Spring er，2005：105-145.

基金項目：山西省高等學校科技創新項目“代理模型輔助的進化算法在昂貴多目標優化問題中的研究”（項目編號：2023L451）

作者單位：山西電子科技學院■責任編輯：張津平尚丹