多目标優化

MOEA-D

A multi-objective evolutionary algorithm based on decomposition

基于分解的多目标進化算法

将多目标優化問題分解成單目标優化問題

1. 權重和： g ( x ∣ λ ) = ∑ i = 1 m λ i f i ( x ) g(x|\lambda)=\sum_{i=1}^m\lambda_if_i(x) g(x∣λ)=∑i=1m​λi​fi​(x)，取不同的 λ \lambda λ可以得到不同的Pareto解
2. 切比雪夫方法： g ( x ∣ λ , z ∗ ) = m a x 1 ≤ i ≤ m { λ i ∣ f i ( x ) − z i ∗ ∣ } g(x|\lambda,z^*)=max_{1\leq i\leq m}\{\lambda_i|f_i(x)-z_i^*|\} g(x∣λ,z∗)=max1≤i≤m​{λi​∣fi​(x)−zi∗​∣}，其中 z ∗ z^* z∗是參考點， z i ∗ = m a x { f i ( x ) ∣ x ∈ Ω } z_i^*=max\{f_i(x)|x\in \Omega\} zi∗​=max{fi​(x)∣x∈Ω}，調整權重矢量 λ \lambda λ得到不同的Pareto解
3. 交叉邊界法

過程

1. 計算兩兩權重向量的歐式距離，找到距離每一個權重向量最近的 T T T個權重向量。對每一個 i = 1 , 2 , … , N i=1,2,\dots,N i=1,2,…,N，使 B ( i ) = { i 1 , i 2 , … , i T } B(i)=\{i_1,i_2,\dots,i_T\} B(i)={i1​,i2​,…,iT​}，其中 λ 1 i , λ 2 i , … , λ T i \lambda^i_1,\lambda^i_2,\dots,\lambda^i_T λ1i​,λ2i​,…,λTi​是距離 λ i \lambda^i λi最近的 T T T個向量。
2. 随機生成初始種群
3. 計算 z = ( z 1 , z 2 , … , z m ) z=(z_1,z_2,\dots,z_m) z=(z1​,z2​,…,zm​)
4. 在 B ( i ) B(i) B(i)中執行選擇交叉變異算子生成一個新個體
5. 計算新個體的适應度值 y ′ y' y′
6. 更新 z z z，對于每一個 j = 1 , 2 , … , m j=1,2,\dots,m j=1,2,…,m，如果 z j < f j ( y ′ ) z_j<f_j(y') zj​<fj​(y′)，那麼使 z j = f j ( y ′ ) z_j=f_j(y') zj​=fj​(y′)
7. 更新鄰域
8. 更新EP

NSGA-II

A Fast and Elitist Multi-objective Genetic Algorithm

基本概念

1. 快速非支配等級排序：如果目前集合中沒有其他個體支配個體 i i i，則個體 i i i處于目前集合的最高非支配等級。
2. 擁擠度評估：對同一非支配等級的解，進行擁擠度評估，即計算目标空間中以距離目前解最近的解為頂點組成的超立方體的周長。 I [ i ] d i s t a n c e = ( I [ i + 1 ] . m − I [ i − 1 ] . m ) / ( f m m a x − f m m i n ) I[i]_{distance}=(I[i+1].m-I[i-1].m)/(f_m^{max}-f_m^{min}) I[i]distance​=(I[i+1].m−I[i−1].m)/(fmmax​−fmmin​)規定處于邊界的個體的擁擠度為無窮大。
3. 比較算子 ≺ n \prec_n ≺n​：定義 i ≺ n j i\prec_nj i≺n​j當且僅當 i r a n k < j r a n k i_{rank}<j_{rank} irank​<jrank​或者 i r a n k = j r a n k i_{rank}=j_{rank} irank​=jrank​并且 i d i s t a n c e > j d i s t a n c e i_{distance}>j_{distance} idistance​>jdistance​
4. 排序時不需要全排，隻要排夠前 N N N個即可。

過程

1. 随機初始化種群
2. 非支配等級和擁擠度距離排序
3. 執行選擇交叉變異算子生成新個體，回到第2步

PESA

The Pareto Envelop-based Selection Algorithm for Multi-Objective Optimization

基本概念

1. 壓縮因子：在目标空間中維持一個網格，壓縮因子表示在同一網格中非支配個體的數目。
2. 選擇算子：從外部種群中采用錦标賽法選擇個體，因外部種群中存儲的是非支配個體，是以個體的适應度值由壓縮因子決定，壓縮因子越小，适應度值越好。
3. 存檔更新算子：當内部種群和外部種群組成的混合種群中非支配個體的數目超過預定義的外部種群數目時，需要從外部種群中移除多餘的個體。首先移除壓縮因子最大的個體，如果多個個體的壓縮因子相等且都為最大時，則随機選擇一個移除（注意：一次移除一個）。

過程

1. 随機初始化内部種群，外部種群置空
2. 将内部種群和外部種群合并成一個臨時種群，并用臨時種群中的非支配個體重新初始化外部種群。
3. 執行存檔更新算子
4. 清空内部種群，如果 0 < r < P c 0<r<P_c 0<r<Pc​則從外部種群中利用選擇算子選擇兩個個體執行交叉變異操作生成子代個體；如果 P c < r < 1 P_c<r<1 Pc​<r<1，則從外部種群中選擇一個個體執行變異操作生成子代個體，直到填滿内部種群

SPEA2

Improving the Strength Pareto Evolutionary Algorithm

基本概念

1. 計算強度值 S ( i ) = ∣ { j ∣ j ∈ P t + P t ˉ ⋂ i ≺ j } ∣ S(i)=|\{j|j\in P_t+\bar{P_t}\bigcap i\prec j\}| S(i)=∣{j∣j∈Pt​+Pt​ˉ​⋂i≺j}∣，個體 i i i的強度值等于被個體 i i i支配個體的數目
2. 計算适應度值 R ( i ) = ∑ j ∈ P t + P t ˉ , j ≺ i S ( j ) R(i)=\sum_{j\in P_t+\bar{P_t},j\prec i}S(j) R(i)=∑j∈Pt​+Pt​ˉ​,j≺i​S(j)，個體 i i i的适應度值表示所有支配 i i i的個體的強度之和

3. 當個體兩兩互不支配時，适應度值相同，是以加入密度資訊。 D ( i ) = 1 σ i k + ϵ D(i)=\frac{1}{\sigma_i^k+\epsilon} D(i)=σik​+ϵ1​，其中 σ i k \sigma_i^k σik​表示與個體 i i i距離最近的第 k k k個個體的距離，通常 k = N p + N p ˉ k=\sqrt{N_p+\bar{N_p}} k=Np​+Np​ˉ​

   ​

4. 總适應度值 F ( i ) = R ( i ) + D ( i ) F(i)=R(i)+D(i) F(i)=R(i)+D(i)
5. 存檔與截斷：将所有的非支配個體放入存檔，如果正好填滿，則複制過程結束；如果不夠，則從剩餘的支配個體中選擇最好的填滿存檔；如果過多，則一次移除一個個體，移除标準是：如果個體 i i i與其他個體在目标空間的第一最近鄰距離最小，則移除個體 i i i；如果同時有幾個個體與其他個體在目标空間的第一最近鄰距離最小，則判斷它們的第二最近鄰距離，以此類推。

過程

1. 随機初始化種群，存檔置零
2. 計算所有個體的适應度值，執行存檔與截斷
3. 在存檔中選擇個體，填充交配池，執行交叉變異算子生成新個體

參考文獻

待補充（每個大标題下面）