如何將多目標優化問題轉化成單目標優化？

01-06

假如問題是根據兩個變數x與y進行決策，兩個變數的單位不一樣，x的單位為m，而y的單位為s，最優情況是兩個變數同時取最小值，但現實是兩個變數不可能同時取最小，並且變數y對目標的影響相比x更大，即y的微小增大可能會導致目標值較大的增長。所以我直接用下面的函數作為目標函數：
　　f(x,y)=(1-a)*x + a*(exp(y))
　　請問可以這樣做嗎？

　　我在網上看了一些多目標轉化為單目標的資料，但是這種線性加權的要先消除量綱，那麼對於上述情況，應該怎麼處理呢？
改：剛剛想了想，是否可以用乘除法：
　　f(x,y)=(x+1)*exp(a*y)
　　上面用x+1是為了當x=0時，可以選擇出使得exp(a*y)最小的情況，而a是為了調節exp(a*y)對目標影響的大小。

　　對於這些知識不是很明白，希望大神幫幫忙~

一般採用兩個目標函數加權相加的形式。加權可以解決兩個目標函數量綱不一致，或者變化劇烈程度不一致的問題，不過權重本身需要人為選取。

一般不使用乘法來組合目標函數，因為這樣會使得導數的形式變得複雜。

謝個邀

1. 能做的一件事情是，畫出帕累托曲線，就是說每次固定x，看看y的最優值是什麼。然後連續變化x找到所有最優的y，這條曲線刻畫出能達到的所有最好狀態。

2. 剩下的一步就不是數學問題了，是你對原問題的理解：什麼才是最好？！因為涉及到x和y取值的取捨。舉個例子，我們看客服的兩個指標，一個是客人等電話的時間，這個越短越好，另一個是客服數量，也是越小越好。但是一般情況下，客人總數一樣，客戶數量多，客人等電話的時間才短，但是公司總要有取捨，該怎麼挑呢？一個方法是看市場劃分，看競爭對手都是怎麼做的，假如市面上的客服都希望最小化客人等電話的時間，那這家公司為了避免紅海，也許可以考慮最小化客服數量來提高效率。

我的觀點是，這種優化問題都是因問題而異的，通解都是騙人的，這就是學院派的缺點，所謂沒有實事求是。

關於將多目標轉化為單目標優化的方法，可以搜這篇文章：

Srinivas N, Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, 2(3):221-248.

這是NSGA演算法第一次被提出，文章中Deb在提出NSGA演算法之前，詳細講了業界應用最廣的三個將多目標優化問題轉化為單目標優化的經典方法，但這些classical的方法的缺點顯而易見，就是參數很難確定。

在單目標優化問題中，通常得到的最優解都是全局最大或最小解，而在典型的多目標優化問題中，在考慮所有的目標函數取值情況時，會有很多的解在一部分目標函數上的表現優於其他的解，但是在另一部分目標函數上的表現遜於其他的解。在上述解中，沒有一個解是完全優於其他的解。究竟選擇哪一個解，取決於對問題的理解認知和研究人員的偏好。

因此，多目標問題通常存在一個解的集合，它們之間不能簡單的進行比較好壞。對這種解來說，不可能進一步優化某一個或幾個目標而不損壞其他目標，這種解稱作非劣最優解集，也就是所謂的Pareto最優解集。

基於這種考慮，就有了帶精英策略的非支配快速排序遺傳演算法，也就是上述答主說的NSGA-Ⅱ演算法。

關於NSGA-Ⅱ可以參看這篇論文：

Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.

這是詳細講解演算法過程，網上也有很多源代碼，比如由Aravind Seshadri所寫的：

NSGA - II: A multi-objective optimization algorithm - File Exchange - MATLAB Central

還配套有演算法的notes。

對於解決多目標問題，如果人為的定義權重，是需要先驗知識的。通常做法是用多目標優化演算法，算出一組帕累托解，然後做一個decision making，選取幾個典型解。decision making的時候，加入主觀因素進行選擇，是比較合適的。

衝突的目標加權方法不行，如果pareto front是convex的話只能求得extreme point。如果concave的話求的一組分布不均的non-dominated得解。如果想換成單目標就用moea/d。不過你就2個目標，nsga-ii就可以了。不用轉單目標

這讓我想到了MOEA/D

他的思想是基於分解的方法，把一個多目標優化問題轉成一組單目標的問題，然後同時求解這一組問題，從而得出一組解。當然他這個方法還有一部分是關於結合進化演算法的，這裡不展開，只提他的分解的思想。

具體的方法是把多目標每一個子目標歸一化，然後給每個目標賦予一個權值，然後通過不斷調整這些權值，從而獲得一組不同權值的單目標問題，然後再去同時解決這一組問題。

比如只考慮2個目標，那麼可以劃分成（1,0），（0.9,0.1），。。。，（0,1）這樣一組問題，然後依次往後求解。

總結：既然不知道什麼樣的權重合適，就乾脆窮舉。

論文原文

Zhang Q, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on evolutionary computation, 2007, 11(6): 712-731.