多目标優化問題中常見分解方法的了解

作為剛上研一提前來給老師當苦力的小菜鳥，第一次學習MOEAD算法的時候，對其中介紹的分解方法一臉懵*，上網查了不少資料，很難查到詳細的解釋（好吧，可能我查的姿勢不對），完全不了解這些分割方法所給出的表達式的意義，索性擱置了小半個月。

這裡必須要感謝一下Chithon的http://blog.csdn.net/qithon/article/details/72885053#comments這篇部落格，其中的兩幅配圖讓我豁然開朗，當然，大神完全沒有必要閱讀這篇部落格了，我隻是說一下自己從向量和幾何的角度是如何了解這些方法的。

Weighted Sum Approach

        該方法給出的表達式為：

        首先，λ被稱之為權重向量，觀察和式，這完全就是m維向量的點乘公式嘛。具體的說，在目标空間中，把算法求出的一個目标點和原點相連構造成一個向量，此時，該方法的做法是将該向量與對應權重向量點乘，由向量點乘的幾何意義可知，所得的數為該向量在權重向量方向上的投影長度，因為權重向量不變，最大/小化該長度值其實就是在優化該向量。可知若要增大該向量在權重向量上投影的長度，一方面可以增大/減小與權重向量的夾角，另一方面可以增大/減小該向量的長度。樣例圖如下：

        上圖中：考慮紅色權重向量，因為是最小化問題，是以減小長度，增大夾角都是可行的方案，綠色為等高線，垂直于權重向量。

TchebycheffApproach

        該方法給出的表達式為：

        注意該方法中不再含有Σ符号，故不能再從向量點乘的角度了解。該方法大緻思想是減少最大差距進而将個體逼近PF。等高線示意圖如下：

        首先解釋等高線為什麼是這樣的。單看f1函數，即隻考慮縱坐标，若兩點等值，必然是 式中f1的函數值相等（因為另外兩個量是不變的），即縱坐标相等，是以f1函數的等高線是一組平行于橫軸的直線。f2類似，為一組平行于縱軸的直線。

        那麼，圖中的等高線是橫豎相交且剛好交在權重向量的方向上的，這是巧合嗎？可以稍微來證明一下，可知，對于任何一個可行的切比雪夫值（自己叫的），我們從f1的角度上可以得到一個f1的值y，從f2的角度上可以得到一個f2的值x，他們的切比雪夫值是相等的，自然想到，點(x,y)（圖中紫色點）為該切比雪夫值得橫縱兩條等值線的交點，那麼有：λ1*(y-z1)= λ2*(x-z2)，化簡的(y-z1)/(x-z2)= λ2/λ1，可知該交點位于權重向量的方向上。

        需要注意一點，這裡的權重向量起點是Z*，不再是原點。

        此時可知，若某個個體位于其權重向量方向的上部，則max得到的一定是其f1部分，故優化也需要減小其f1的值，即個體向下移動，相反，若在權重向量方向的下部，則應像左移動。以此來保證個體目标值落在黃點附近。

一種可能的個體運動路線如下圖橘黃色所示：

Boundary IntersectionApproach

        該方法給出的表達式為：

        式中個參數含義如下圖所示：

        式子中等式限制其目的是為了保證F(x)位于權重向量λ的方向上，通過減小d來使算法求出的解逼近PF。但該條件不太容易實作，故将其改進為下邊這種方法。

penalty-basedboundary intersection approach

改進後的式子為：

        各個參數的含義如下圖：

        可知算法放寬了對算法求出的解得要求，但加入了一個懲罰措施，說白了，就是你可以不把解生成在權重向量的方向上，但如果不在權重向量方向上，你就必須要接收懲罰，你距離權重向量越遠，受的懲罰越厲害，以此來限制算法向權重向量的方向生成解。

接下來是關于d1和d2兩個參數的計算表達式的含義說明，我依然是從幾何角度了解的。

        d1——觀察d1的計算表達式，Z*-F(x)可以看做原點到Z*點的向量減去原點到F(x)的向量，得到的是從F(x)出發指向Z*的一個向量，暫且命名為μ，之後μ與λ相乘得到μ在λ方向上的投影，這個長度值與λ的長度值之比為d1。

        d2——其表達式的含義其實也無非就是利用向量運算構造出d2所表示的向量，取模即可得到d2.構造過程如下：

        Z*表紅色向量，d1*λ表藍色向量（因為減法，是以方向取反），紅色減藍色得紫色向量，F(x)表綠色向量，綠色減紫色得黃色向量，即d2表黃色向量的長度。