###### tags: `paper_reading`

# Coevolutionary Particle Swarm Optimization With Bottleneck Objective Learning Strategy for Many-Objective Optimization

## Abstract
**多目標進化算法在多目標優化問題中的應用經常面臨多樣性和收斂性方面的挑戰:**

> 1. 種群規模有限，算法很難在大的目標空間中覆蓋整個帕累托前沿（PF）的不同部分。
> 2. 隨著目標數量的增加，易在某些目標上有較差的值，可被視為限制解決方案收斂於 PF 瓶頸目標。

**研究結合:**

> 1. 瓶頸目標學習(BOL)策略的協同進化粒子群優化: 多個群體以分佈式方式共同進化以保持多樣性以逼近整個 PF 的不同部分，並開發了一種新穎的 BOL 策略以提高所有目標的收斂性。
> 2. 精英學習策略(ELS): 幫助算法跳出局部 PF。
> 3. 關鍵學習策略(JLS): 幫助到達 PF 的缺失區域。

## Introduction
**處理涉及三個以上目標的多目標優化問題(MaOPs)時，MaOPs 中的“維數災難”給傳統多目標進化算法(MOEA)帶來了多樣性和收斂性的挑戰。**

**多樣性挑戰:**
> *隨著 MaOPs 目標空間的擴大，難以保持結果多樣性來找到沿整個帕累托前沿(PF)分佈良好的解決方案，局限於 PF 的有限部分*
> 1. 目標空間維數的增加，逼近整個 PF 所需的解數呈指數增長
> 2. 高維目標空間中距離評估困難 (ex: NSGA2密度評估)

**收斂性挑戰:**
> 目標數量的增加，算法越來越難以對所有目標給予同樣的關注，不同目標的演化可能是不平衡的，導致一些目標表現良好，而另一些目標表現不佳。帕累托支配無法區分這些解決方案，大多數這些解決方案往往是相互非支配而保留的，缺乏對表現不佳的目標的引導，導致演化中的不平衡。

**MaOPs 研究方向:**
> 1. NSGA-III & MOEA/D : 單一種群考慮所有目標，難保持探索所有解決方法的多樣性。
> 2. MPMO + PSO : 協同進化，將每個目標視為一個子問題，並採用多目標多群體（MPMO）框架來對不同種群進行目標優化，有助於定位 PF 的不同部分，避免忽略某些目標。這邊透過 PSO 對個別種群優化。

**本研究說明:**
> 1. 每個種群都專注於 MPMO 框架中的一個目標(PO)，透過檔案匯總所有粒子群的非支配解決方案以供信息共享。
> 2. 解決方案（即粒子）在某些目標上可能具有非常差的值。即限制粒子向 PF 收斂速度的瓶頸目標(BO)。
> 3. 瓶頸目標學習 (BOL) 策略: 粒子首先確定自己的 BO，然後通過學習根據兩個目標（即該粒子的 PO 和 BO）上的優勢關係從存檔中選擇的解來更新自身，從而使粒子能夠更好地收斂到 PF。
> 4. MPMO + BOL 開發 coevolutionary PSO (CPSO)，使粒子群更好的分配到 PF 各個部份且增加所有目標的解決方案收斂性。
> 5. 精英學習策略（ELS）和接合點學習策略（JLS），有助於跳出本地 PF，並到達 PF 中容易被粒子群遺漏的區域。

## Background

[**PSO (粒子群演算法)**](https://medium.com/qiubingcheng/%E4%BB%A5python%E5%AF%A6%E4%BD%9C%E7%B2%92%E5%AD%90%E7%BE%A4%E6%BC%94%E7%AE%97%E6%B3%95-particle-swarm-optimization-pso-f0d0404c443b)

[**MaOPs (多目標優化問題)**](https://zhuanlan.zhihu.com/p/158705342)

[**MaOPs 常用方法**](https://zhuanlan.zhihu.com/p/158705342)
> 1. Pareto-based (基於帕累託)
> 2. Indicator-based (基於指標)
> 3. Preference-based (基於偏好)
> 4. decomposition-based (基於分解)

**MPMO (多目標協同進化)**
> 對於 M 目標問題，創建 M 個種群，每個種群同時優化一個不同的目標。每個種群都可以採用任何"單"目標優化算法根據目標來競爭生存。

## CPSO for MaOPs
*介紹作者提出的方法 CPSO，算法框架、各群的搜索過程、CPSO的檔案更新過程。*

**Algorithm Framework (算法框架)**


> 採用 MPMO 技術並使用多個群體向 PF 共同進化:
> 1. M 個目標由 CPSO 中 M 個群體優化，表示為 PO。
> 2. M 群採用 PSO 和 BOL 策略同時優化它們的 PO。
> 3. 透過固定大小的檔案(Archive)儲存所有群體的非支配方案。
> 4. 透過 SR (solution reproduction: ELS + JLS) 組件提高存檔解決方案的質量。
> 5. 透過 SP (solution preservation) 組件使用"複製的解決方案"、"存檔中的解決方案"、"所有群體中粒子的所有位置"、 "pBests" 來更新存檔

**Search Process of Each Swarm**
> BOL Strategy：
> 1. BO 是一組具有較差值的"目標"
> 2. 定義一個優化度 (optimization degree, OD) 來表示粒子中每個目標的性能
> 
> *a. 假設粒子由 i 索引，其位置 Xi 的目標向量為 F(Xi) = (fi1, ..., fiM)。*
> *b. f_best_l 和 f_worst_l 為目標 l 上一代所有非支配解中的 fitness 最佳和最差值。*
> *c. 透過 f_best_l 和 f_worst_l 將目標 l 在 particle 中各個 objective 的 fitness 正規化，使得不同目標可以互相比較。*
> 3. 選擇具有最差（最大, 更新幅度最小） OD 值的目標作為粒子 i 的 BO bi (bottleneck object) => BO 為 object 非 OD 值
> 
> 4. 粒子 i 通過從 pBest_i(particle 歷史最佳解) 和 Archive Solution 來更新速度 => 原 PSO 為 pBest_i & gBest_i，這邊改為 archive 可以納入不同 BO object 來調整
> 
> 5. 上述 V 更新公式中的 Archive Solution 是根據 PO(j) 和 BO(bi) 的支配關係從所有 Archive 中選擇
> 
> a. 初始，Archive Solution 被設置為 A 中的第一個解。
> b. 透過 Archive Solution 在 PO 和 BO 上互相的支配關係，將 A 中倍 Pareto 支配的解替代。
> c. 如果兩個解不相互支配，保留具有更小或相同的收斂性能 (CP值: 計算 Archive 所有目標的 OD 之和) 的 Archive。
> 
> 6. Example:
> setting:
> a. 3-objective problem (3 個 swarm)
> b. swarm 1 裡有一個 particle 的 3-objective fitness (f1,f2,f3) 為 **X(2,3,4)**，且該 particle 的 pBest 為 **pBest(1,4,5)**
> c. Archive 裡的解為 {**A1(3,5,1)**, **A2(3,1,5)**, **A3(5,3,1)**, **A4(1,2,3)**}
> --
> solution:
> a. 可得知 PO 為 f1(swarm 1 對應的 object)，BO 為 f3(OD 最高)
> 
> b. 取 f1, f3 來做 pareto dominate
> c. 找到非支配的解 A1 及 A4
> d. 比較 CP 值，得到最終解 A4
> 
> 

**Archive Update**
*- 在每一代結束時，檔案都會更新*
*- 初始化: 新集合 P 由 pBests + swarm 裡所有 particles*
*- 更新: ELS + JLS*

> Solution Reproduction(SR):
> 1. Elitist Learning Strategy (ELS):
> a. 制定一個擾動策略(類似基因算法的突變)來嘗試得到更好的 Xid，參考文獻: [Adaptive Particle Swarm Optimization - ELS 方法](https://ithelp.ithome.com.tw/articles/10231753)
> b. ELS 對 前 0.9n 個 Archive 執行
> 
> c. Xmin,d 和 Xmax,d 分別是第 d 維的下限和上限
> d. fes: 已計算解數量；FES: fitness 最大需計算解數量；
> e. Gaussian(0, σ2) 是均值為0的高斯分佈，其標準差σ隨著fes的增加從 0.5 減小到 0.1
> f. 新的解被加到 P 集合中
> 2. Juncture Learning Strategy (JLS):
> a. 由於不同 swarm 專注於不同的目標，它們會向不同的區域移動，尤其是 PF 的邊緣。因此，所有 swarm 的近似前沿可能會失去它們的接合區域，如 PF 的中心。
> b. 通過從不同的檔案中隨機選擇兩個 Archive，進行模擬二元交叉（SBX）和多項式變異（PM），在接合區域生成新的解決方案。
> c. 在每一代中，執行 JLS 以生成 0.1n 個新解決方案，然後將這些新解決方案添加到集合 P。

> Solution Preservation(SP):
> 1. 從 P 中刪除所有支配解
> 2. 非支配解決方案中每個目標的最佳和最差值表示為 fbest_j 和 fworst _j
> 3. 清空 Archive，將 Archive n(NA) 的大小設置為 0:
> a. 如果 P ≤ NA 的大小，則 P 中的解存儲在 Archive 中，n 更新為 𝑃 的大小
> b. 如果 P > NA 的大小，只有 "**最大化非支配解的多樣性**" 的 NA 解才會被選擇存儲在 A 中

**Computational Complexity of One Generation of CPSO**


## EXPERIMENTS AND COMPARISONS
*Benchmark problem: DTLZ1-DTLZ7, WFG1-WFG9*
*Performance metric: **IGD**(Inverted generational distance), **HV***
*All reported are obtained **30 independents runs**, **100,000 function evaluation***

**解決多目標問題的方法**

**實驗結果**

> "不同數據集"&"不同多目標解決方法"比較:
> 1. 比較標準為 ["IGD 指標"](https://juejin.cn/post/7104289806338752520)
> 
> 2. CPSO 有較優表現
> 

> 不同演算法比較結果:
> 1. 不同線為不同初始值收斂結果
> 2. X: 不同 object, Y: fitness value
> 

> 不同目標數量收斂結果:
> 1. IGD 收斂曲線
> 2. 小圖為針對 30000-90000 世代收斂放大呈現
> 

> 根據 iteration 收斂結果:
> 1. 以 100 代為單位看各目標 fitness 結果
> 

> CPSO 消融實驗:
> 1. CPSO vs 三個元件消融(MPMO、SR、SP)
> 
> 2. CPSO vs BOL 方法消融
> 
> 3. CPSO vs SR 方法消融(JLS、ELS)
>