SRA:基于多名額的多目标優化随機排序算法
參考文獻
《Bingdong Li, Student Member , IEEE, Ke Tang, Senior Member , IEEE, Jinlong Li, Member , IEEE, and Xin Yao , Fellow, IEEE：Stochastic Ranking Algorithm for Many-Objective Optimization Based on Multiple Indicators》
要點
單一名額可能會有偏差，導緻種群向帕累托前沿的一個次優區域彙聚。本文針對多目标優化問題，提出了一種基于多名額的算法。該算法采用随機排序技術來平衡不同名額的搜尋偏差，即基于随機排序的多名額算法。
實證研究表明，與最先進的算法相比，SRA在反向世代距離和超體積名額方面表現良好。在一個問題需要算法具有很強的收斂能力的情況下，SRA的性能可以通過基于導向的檔案來存儲收斂良好的解和保持多樣性來進一步提高。
一、介紹
随着多目标問題中目标數量的增加，非支配解的比例相當大，傳統的帕累托支配失去了将種群推向最優解的效率。當基于支配的(主要)選擇标準不能區分非支配解時，基于多樣性的(次要)标準在環境選擇中起着至關重要的作用。是以，最終的群體可能遍布整個目标空間，但無法收斂到PF。
為了克服這一障礙，研究者提出了各種多目标進化算法。根據所使用的關鍵思想，這些方法可以分為六類。
1）基于松弛支配的算法試圖通過擴大解的支配區域來緩解支配的低效性。已經提出了一系列方法，例如ε-支配，控制解的支配面積，和L-支配。在這些松弛的定義下，一個解被其他解支配的機會更大，對PF的選擇壓力增加。一種代表性的基于支配的松弛算法是GrEA，它使用基于網格的收斂和多樣性測量來比較非支配解。這些方法的一個難題在于确定不同問題的新支配定義的松弛程度，并且已經研究了動态調整方法。
2）基于多樣性的方法試圖通過更先進的多樣性保持政策來提高性能。一般來說，這些方法通過考慮收斂到一定程度，減少多樣性維護對選擇壓力的不利影響。
3）基于聚集的方法使用一系列的标量化函數來将多目标規劃分解成一組單目标子問題。
4）基于名額的方法在優化MaOP時利用名額值來指導搜尋過程。最終的解集主要取決于所包含的名額特征。然而，與其他算法相比，基于超體積的算法通常更耗時。評估GD和IGD值需要一個參考集作為PF。因為真正的PF通常是未知的，是以維護參考集也是一項非常重要的任務。
5）基于偏好的算法根據使用者的偏好資訊關注感興趣的區域。為了選擇解，文獻中研究了一系列偏好模型，如目标指定、偏好多面體、目标權重等，然而如何選擇合适的偏好模型可能是一個依賴于問題的任務。一種有趣的算法，即偏好啟發的協同進化算法，将偏好資訊模組化為一組與種群共同進化的解。
6）最近，還提出了将兩種或多種上述技術相結合的混合MaOEAs。兩個有代表性的算法是NSGA-ⅲ和Two_Arch2。
本文采用随機排序技術，該技術最初是為了平衡限制優化中的适應度和限制違反而設計的。引入了一種新的技術來平衡多目标優化算法中不同名額的影響。這種平衡是通過基于随機冒泡排序過程來實作的。通過可調參數，使算法設計者能夠在不同的名額之間進行适當的權衡。為了處理要求算法具有強收斂能力的問題，基于導向的檔案（DBA）被結合到SRA中，以存儲良好收斂的解并保持多樣性。
二、拟議的SRA
A、概述
算法1描述了SRA的架構
B、名額
在計算上，算法1可以适應任何可計算的名額。然而，我們期望通過涉及兩個名額來獲得額外的好處，直覺地說，它們應該顯示不同的偏差，例如，一個傾向于趨同，另一個傾向于多元化。于是，名額Iε+和ISDE被用于SRA，因為這兩個名額已被證明在趨同或多樣性方面是有效的，它們不涉及設定适當的參考集/點這一重要任務。
加性名額Iε+和相應的I1(x)定義為
名額ISDE和相應的I2(x)定義為
其中
C、基于随機排序的環境選擇
在多個名額的情況下，排序變得複雜得多，因為不同的名額可能會給同一個個體配置設定不同的等級。特别是當名額支援多目标優化的不同方面，即收斂性和多樣性，這很可能發生。這種情況下的排序結果應該代表對同一種群産生不一緻排序的兩個名額之間的良好平衡。這種情況類似于限制(單目标)優化中通常遇到的情況，在這種情況下，通過根據适應度和限制違反對種群進行排序，可能會得到不同的結果。是以，SRA利用随機排序技術，一種已被證明對限制優化中的排序問題有效的方法，來解決多名額多目标優化中的排序問題。
具體來說，一旦獲得所有個體的名額值，就應用随機排序。如算法2所示，随機排序是一種随機冒泡排序算法。
三、帶存檔的SRA
通過在SRA加入基于導向的檔案DBA，産生了SRA的一種變體，即帶檔案的SRA(SRA2)。這裡，搜尋方向由一組權重向量定義，權重向量根據《K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 577–601, Aug. 2014.》中的方法設定。給定一組權重向量，SRA2首先生成2N個個體，其中N個被随機配置設定給每個權重向量，并被視為初始檔案。其餘N個個體作為初始種群。在每一代中，檔案中的每個成員都與從目前群體中随機選擇的一個個體進行重組，以産生後代。然後，在環境選擇步驟之後，使用新的群體更新檔案。
算法3中顯示了檔案更新過程的僞代碼。對基于權重向量的方法，兩個關鍵步驟是是關聯和替換。在SRA2中，根據《K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 577–601, Aug. 2014.》和《Y . Yuan, H. Xu, B. Wang, B. Zhang, and X. Y ao, “Balancing convergence and diversity in decomposition-based many-objective optimizers,” IEEE Trans. Evol. Comput., vol. 20, no. 2, pp. 180–198, Apr. 2016.》，個體與具有最小垂直距離的權重向量相關聯。下圖示出了關聯步驟的圖示。此後，個體最多可以替換對應于關聯權重向量的鄰域的nr個檔案成員，隻要其獲得比沿着方向的檔案成員更好的适應度值。基于懲罰的邊界相交(PBI)适應度函數，定義為垂直距離和投影長度的權重和，在SRA2中用于比較個體和檔案成員。