前言
本篇部落格出于學習交流目的，主要是用來記錄自己學習多目标優化中遇到的問題和心路曆程，友善之後回顧。過程中可能引用其他大牛的部落格，文末會給出相應連結，侵删！
REMARK：本人純小白一枚，如有了解錯誤還望大家能夠指出，互相交流。也是第一次以部落格的形式記錄，文筆爛到自己都看不下去，哈哈哈
筆記（二）記錄基于Pareto支配的優化算法，在筆記（三）中記錄在學習MOEA/D算法（包括對Tchebycheff聚合方法的了解，比較詳細），MOEA/D也是我的直接目标，以為參考的那篇論文用到了這個論文的思想，因為對這個領域一點不了解，就有了前面兩個筆記。（一些在第一篇提到的概念這篇就不再重複了）
正文
基于分解的多目标進化算法（MOEA/D）2007年由Qingfu Zhang等人提出。該算法将傳統多目标問題轉化成為多個單目标問題，對它們同時優化，該算法需要具備一定Pareto基礎知識，可回顧多目标優化_學習筆記（一）。
MOEA/D特性：
- 引入分解的概念，簡單但是有效；
- 由于算法将MOP問題分解成子問題（單次元）進行計算，适配度配置設定和多樣性控制的難度都有所降低；
- 相較NSGA-II和MOGLS算法MOEA/D具有更低的計算複雜度，但在許多場景下解得表現上更為出色；
- 彌補傳統不是基于分解的算法難以找到一個簡單方法來利用标量（單次元）優化算法的缺點；
三種分解算法
一般将MOP多目标轉換到一組标量優化問題常用的分解方法有權重求和法；切比雪夫聚合方法；邊界交叉聚合方法。下面會一一解釋這些方法，MOEA/D采用切比雪夫聚合方法，也可以隻看這一部分。
A、權重求和法（Weighted Sum Approach ）
常用的權重求和公式為（最小化）：
m i n g w s ( x ∣ λ ⃗ ) = ∑ i = 1 m λ i f i ( x ) min \; g^{ws}(x|\vec{\lambda })=\sum_{i=1}^m\lambda_if_i(x) mingws(x∣λ
)=i=1∑mλifi(x) s . t . x ∈ Ω s.t. \; x\in \Omega s.t.x∈Ω 其中，待優化的目标分量有 m m m個， λ ⃗ = ( λ 1 ， λ 2 ， ⋯ ， λ m ) \vec{\lambda }=\left ( \lambda_{1}，\lambda_{2}，\cdots ，\lambda_{m} \right ) λ
=(λ1，λ2，⋯，λm)是的權值向量，每個權值分量 λ i \lambda_{i} λi分别對應第 i i i個目标分量；限制條件 λ i ≥ 0 \lambda_{i}\geq 0 λi≥0 && ∑ i = 1 m λ i = 1 \sum_{i=1}^m\lambda_{i}=1 ∑i=1mλi=1 （如二維坐标，保證等高線斜率為 [ − 0 ， − ∞ ] \left [-0 ，-\infty \right ] [−0，−∞] ）。文章給出了利用線性權重法求Pareto解得圖例，可以看下連結中的圖例，有助于了解等高線（等值線）概念。 利用這個方法可将多目标問題轉換成單個數值目标函數，但在尋找非凸解得問題上難度大。
B、切比雪夫聚合方法（Tchebycheff Approach） m i n g t e ( x ∣ λ , z ∗ ) = m a x { λ i ( f i ( x ) − z i ∗ ) } min\; g^{te}(x|\lambda,z^*)=max\; \{\lambda_i (f_i(x) - z_i^*)\} mingte(x∣λ,z∗)=max{λi(fi(x)−zi∗)} s . t . x ∈ Ω s.t. \; x\in \Omega s.t.x∈Ω
其中， z ∗ = ( z 1 ∗ ， ⋯ ， z i ∗ ) z^*=\left (z_1^*，\cdots ，z_i^* \right ) z∗=(z1∗，⋯，zi∗) T ^T T，對于每一個目标分量 i i i， z i ∗ = m i n { f i ( x ) ∣ x ∈ Ω } z_i^*=min \left \{f_i(x) | x\in \Omega \right \} zi∗=min{fi(x)∣x∈Ω}，即每個目标分量最小值組成的坐标。
下面給出圖例用于了解這個公式，首先感謝兩篇部落格，通過他們的分享給了我很大的啟發，但是由于有些了解上的不同，下面給出我自己的了解，如有錯誤還請大家指正。
Chithonhttp://blog.csdn.net/qithon/article/details/72885053#comments
jinTesterhttp://blog.csdn.net/jinjiahao5299/article/details/76045936
針對我的了解和前人給出的圖例我重新畫了一個圖，幫助了解。
以二目标最小優化問題為例，我們令 f i ′ ( x ) = f i ( x ) − z i ∗ f^{'}_i(x)=f_i(x) - z_i^* fi′(x)=fi(x)−zi∗，如圖所示坐标系從 f i f_i fi變換到 f i ′ f^{'}_i fi′，這個過程對應定義很容易了解，之後的操作都針對這個變換後的坐标系;那麼公式變為 m i n g t e ( x ∣ λ ) = m a x { λ i f i ′ ( x ) } min\; g^{te}(x|\lambda)=max\; \{\lambda_i f^{'}_i(x)\} mingte(x∣λ)=max{λifi′(x)}，可以看出這個公式和線性權重的很像，隻是線性權重是求和，而切比雪夫方法是比較最大值。
現在我們給定一個 λ ⃗ \vec{\lambda } λ
，如圖紫線所示；我們的目标是要找到Pareto前沿面PF（紅線）上的個體（點），給定 λ ⃗ \vec{\lambda } λ
之後，對位于 λ ⃗ \vec{\lambda } λ
上方的個體衡有 f 1 ′ λ 1 > f 2 ′ λ 2 f^{'}_1\lambda _{1}> f^{'}_2\lambda _{2} f1′λ1>f2′λ2，即 m i n g t e ( x ∣ λ , z ∗ ) = f 1 ′ λ 1 min\; g^{te}(x|\lambda,z^*)=f^{'}_1\lambda _{1} mingte(x∣λ,z∗)=f1′λ1，無論$ f{’}_2$取值如何變化，隻要$f{’}_1 不 變 ， 結 果 大 小 都 一 樣 ， 所 以 等 高 線 是 平 行 于 不變，結果大小都一樣，是以等高線是平行于 不變，結果大小都一樣，是以等高線是平行于 f^{’}_2 的 一 條 直 線 ， 同 理 可 推 位 的一條直線，同理可推位 的一條直線，同理可推位\vec{\lambda } 下 方 等 高 線 是 平 行 于 下方等高線是平行于 下方等高線是平行于 f^{’}_1 的 一 條 直 線 ， 兩 條 直 線 組 合 成 為 等 高 線 （ 橙 色 ） ， 且 等 高 線 上 的 個 體 評 估 值 與 等 高 線 交 于 的一條直線，兩條直線組合成為等高線（橙色），且等高線上的個體評估值與等高線交于 的一條直線，兩條直線組合成為等高線（橙色），且等高線上的個體評估值與等高線交于\vec{\lambda }$的點取值相同。
下面是收斂過程，上面已經講解了等高線為什麼是由兩條垂直的線組成，同樣可以用來說明收斂過程，在位于 λ ⃗ \vec{\lambda } λ
上方的個體，如果出現新的個體$ f^{’}_1 小 于 等 高 線 值 ， 則 等 高 線 向 下 移 動 （ 注 意 兩 條 線 同 時 移 動 ） ； 同 理 ， 位 于 小于等高線值，則等高線向下移動（注意兩條線同時移動）；同理，位于 小于等高線值，則等高線向下移動（注意兩條線同時移動）；同理，位于\vec{\lambda } 下 方 的 個 體 ， 如 果 出 現 新 的 個 體 下方的個體，如果出現新的個體 下方的個體，如果出現新的個體 f^{’}_2$小于等高線值，則等高線向左移動（注意兩條線同時移動），直到搜尋到Pareto前沿。
當我們對 λ ⃗ \vec{\lambda } λ
取不同值（如 λ ′ ⃗ \vec{\lambda^{ '} } λ′
），就可以得到其他Pareto解。
文中還提到了一個權重切比雪夫聚合方法，就是結合兩種方法并加了個參數 ρ \rho ρ 控制兩種方法的比例。思想比較簡單直接給公式：
m i n g t e ( x ∣ λ , z ∗ ) = m a x { λ i ( f i ( x ) − z i ∗ ) } + ρ ∑ j = 1 m ( f j ( x ) − z j ∗ ) min\; g^{te}(x|\lambda,z^*)=max\; \{\lambda_i (f_i(x) - z_i^*)\}+\rho \sum_{j=1}^m(f_j(x) - z_j^*) mingte(x∣λ,z∗)=max{λi(fi(x)−zi∗)}+ρj=1∑m(fj(x)−zj∗) s . t . x ∈ Ω s.t. \; x\in \Omega s.t.x∈Ω
Chithon的部落格中提到标準Tchebycheff Approach得到的解不均勻，Yutao Qi等人于2014年提出一種解決方法(MOEA/D with Adaptive Weight Adjustment)， λ ∗ = ( 1 λ 1 ∑ i = 1 m 1 λ i , . . . . , 1 λ m ∑ i = 1 m 1 λ i ) \lambda^* =(\frac{\frac{1}{\lambda_1}}{\sum_{i=1}^m\frac{1}{\lambda_i}},....,\frac{\frac{1}{\lambda_m}}{\sum_{i=1}^m\frac{1}{\lambda_i}}) λ∗=(∑i=1mλi1λ11,....,∑i=1mλi1λm1)通過這個參照向量的轉換即可得到分布均勻的解。
C、邊界交叉聚合方法（penalty-based boundary intersection (PBI) approach）
最初的邊界交叉方法給出公式如下：
m i n g b i ( x ∣ λ , z ∗ ) = d min\; g^{bi}(x|\lambda,z^*)=d mingbi(x∣λ,z∗)=d s . t . x ∈ Ω s.t. \; x\in \Omega s.t.x∈Ω z ∗ − F ( x ) = d λ z^*- F\left ( x \right )=d\lambda z∗−F(x)=dλ
給個文中的圖例，其中， λ , z ∗ \lambda,z^* λ,z∗和上個方法切比雪夫中的定義一緻（最大優化問題，隻是的 z ∗ z^* z∗最大最小變了一下），限制條件$z^*- F\left ( x \right )=d\lambda ， 需 要 保 證 ，需要保證 ，需要保證F\left ( x \right ) 與 與 與\lambda 在 同 一 直 線 上 ， 這 個 限 制 條 件 不 太 現 實 ， 所 以 做 出 來 改 進 。 其 中 ， 在同一直線上，這個限制條件不太現實，是以做出來改進。其中， 在同一直線上，這個限制條件不太現實，是以做出來改進。其中，d 為 标 量 ， 表 示 為标量，表示 為标量，表示F\left ( x \right ) 在 在 在\lambda$方向上的距離，越小表示越優。
>>> penalty-basedboundary intersection approach
基于懲罰的邊界交叉方法：
m i n g b i p ( x ∣ λ , z ∗ ) = d 1 + θ d 2 min\; g^{bip}(x|\lambda,z^*)=d_{1}+\theta d_{2} mingbip(x∣λ,z∗)=d1+θd2 s . t . x ∈ Ω s.t. \; x\in \Omega s.t.x∈Ω d 1 = ∣ ( z ∗ − F ( x ) ) T λ ∣ ∣ λ ∣ d_{1}=\frac{\left |\left ( z^{*}-F\left ( x\right ) \right )^T\lambda \right |}{\left | \lambda \right |} d1=∣λ∣∣∣∣(z∗−F(x))Tλ∣∣∣ d 2 = ∣ F ( x ) − ( z ∗ − d 1 λ ) ∣ d_{2}=\left | F\left ( x \right )-\left ( z^{*} -d_{1}\lambda \right ) \right | d2=∣F(x)−(z∗−d1λ)∣
作為對上一個算法的改進，改為添加懲罰函數進行處理限制。 θ > 0 \theta>0 θ>0 是一個預設參數，通常取0.5。 d 1 d_{1} d1為标量，表示 F ( x ) F\left ( x \right ) F(x)在 λ \lambda λ方向上投影的距離； d 2 d_{2} d2為懲罰值（标量），表示 F ( x ) F\left ( x \right ) F(x)在 λ \lambda λ方向上垂直投影的距離，偏離 λ \lambda λ越遠，懲罰值越大。
在超過兩個目标時，PBI方法比切比雪夫聚合方法能夠獲得的最優解分布更加均勻，尤其是在目标較少的情況下，這種現象更加明顯。
整體架構
下面是中午原文中的算法流程圖，我們按這個思路了解。
算法主要思想在于，若 λ j \lambda^{j} λj與$\lambda^{j} 相 鄰 ， 那 麼 相鄰，那麼 相鄰，那麼g^{te}\left ( x\mid \lambda {j},z{*} \right )$ 與 g t e ( x ∣ λ j , z ∗ ) g^{te}\left ( x\mid \lambda ^{j},z^{*} \right ) gte(x∣λj,z∗)也應該非常相近。
算法細節上的了解
輸入輸出很好了解，我們直接看算法步驟 ↓
Step1：初始化
1)計算權重向量之間的歐式距離，對于每個權重向量 λ i \lambda ^{i} λi得到離它最近的T個權重向量存在 B ( i ) B\left ( i \right ) B(i)（相鄰集合）中，畫了一個簡要圖，便于了解，注意 λ i \lambda ^{i} λi的取值範圍 ∑ i = 1 m λ i = 1 \sum_{i=1}^m\lambda_{i}=1 ∑i=1mλi=1(這裡 m = 2 m=2 m=2)，是以向量終端一定在橙線（ y = − x + 1 y=-x+1 y=−x+1）上，是以歐式距離越小，表示越相鄰；
2)随機生成初始種群 x 1 , ⋯ , x N x^{1},\cdots ,x^{N} x1,⋯,xN；
3)初始化 z ∗ ⃗ = ( z 1 , ⋯ , z m ) T \vec{z^{*}}= \left ( z_{1},\cdots ,z_{m}\right )^{T} z∗
=(z1,⋯,zm)T， z i = m i n { f i ( x 1 ) , f i ( x 2 ) , ⋯ f i ( x N ) } z_{i}=min\left \{ f_{i}\left ( x^{1} \right ),f_{i}\left ( x^{2} \right ) ,\cdots f_{i}\left ( x^{N} \right )\right \} zi=min{fi(x1),fi(x2),⋯fi(xN)},即每個目标分量上的最大值或最小值（視優化問題而定，這裡是最小化優化）；
4)建立一個外部種群（EP）用于存儲過程優秀個體，初始為空。
Step2：種群更新
對于每個 i i i都做以下操作:
1)從鄰集 B ( i ) B\left ( i \right ) B(i)中随機取兩個序号 k , l k,l k,l利用基因重組遺傳算子讓 x k x^{k} xk和 x l x^{l} xl産生新解 y y y；
2)對 y y y 運用基于測試你問題的修複和改進啟發産生 y , y^{,} y, ;
對0/1背包問題
在随機生成解得同時，我們有可能獲得一個沒有完全符合解限制的解，這時候需要進行修複
k = a r g m i n j ∈ J g ( y ) − g ( y j − ) ∑ i ∈ I w i j k= arg min_{j\in J}\frac{g\left ( y \right )-g\left ( y^{j-} \right )}{\sum_{i\in I}^{ }w_{ij}} k=argminj∈J∑i∈Iwijg(y)−g(yj−)
可利用上式修複， g g g為目标函數，如果分母影響最大同時又對分子影響最小的y存在，那麼我們将這個y從解中去掉，反複循環，可知目前解符合要求。
3)更新 z ∗ ⃗ \vec{z^{*}} z∗
，判斷 y , y^{,} y,是否可能替換原有極值；
4)更新領域解 B ( i ) B\left ( i \right ) B(i)，對于領域中每個權值向量 λ j \lambda ^{j} λj，如果得到優化，則更新；
5)更新外部種群EP，從EP中移除所有被 F ( y , ) F\left ( y^{,} \right ) F(y,)支配的解，如果不存在這的解，則将 F ( y , ) F\left ( y^{,} \right ) F(y,)加入EP中。
Step3：條件終止
根據停止條件停止，停止并輸出EP，否則重複步驟2。
結論
MOEA/D相比于NSGA-II和MOGLS有較低的計算複雜度，同時解得品質又很高；可以解決不連續優化問題；對T參數不敏感，且計算成本是線性增長。——中文原文
最後任然要感謝以下部落格對我的幫助
多目标優化系列（三）MOEA/D
多目标優化算法的了解：線性權重法
多目标進化算法(MOEA)概述
多目标優化問題中常見分解方法的了解
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition
中文連結：https://wenku.baidu.com/view/d163a04d915f804d2a16c102.html