Two New EAs for MOPs

Two New Evolutionary Algorithms for Multi-objective Optimization



　　　　　　　　－ RM-MEDA & MOEA/D





　　此場演講，請到專門研究進化式演算法(Evolutionary Algorithms, EAs)

的張教授蒞臨系上，為我們介紹近年來其個人的研究成果。對於以EA求解多目

標最佳化問題(Multi-objective Optimization Problems, MOPs)的時候，一般

常見的幾個困難點，分別為：1. 建模(framework)；2. 選擇具代表性的解

(selection)；3. 反覆演算(reproduction)；4. 區域搜尋(local search)；5. 問題

特性(problem specific)。

　　對於演算過程所遇到的這些決策困難之處，張教授則提出RM-MEDA和

MOEA/D兩種改良式的EA，以數學觀點來解決上述問題。目前所達成的具體貢

獻，可將搜尋出來的最佳解集合盡可能提高其「稀疏性」，同時改善運算效率。

　　MOPs也常存在於現實問題之中。例如：在一家公司的製造線中，往往既

要求產量盡可能提高，同時又要求盡可能減少資源消耗，但這兩項指標是相互

矛盾的。因此，在這類問題上首先遇到的是「最佳化」概念如何定義。很顯然

它不像單目標問題那樣，只有唯一一組確定的最佳解。它牽涉到一個所謂「偏

序」問題，即對可供選擇的方案及各方案屬性間，該如何定義和比較其「優劣

次序」？換言之，也就是如何描述目標函數對於可供選擇的方案的依賴關係。

　　然而，決定多目標的偏序並不容易，因為績效指標不單只有一個。好比說

在某指標衡量下，A方案比B方案好；但對於另一個指標而言，A方案未必比B方

案好。假如對於所有指標，A方案都比B方案好，決策自然是容易，但只要存在

一個反例，A和B會變得難以比較好壞，此時偏序問題也就突顯出來。一般而言

，MOPs不但是數學問題，也牽涉到如何從外部環境(專家或決策者)得到一些資

訊，藉以有效地做好「偏序」處理。

　　在數理規劃的應用中，有些問題所牽涉的輸入資訊，常隨時間而作微幅變

動。而這些變動有時可能影響目標函數發生巨大的變動。基於這種現象，而產

生一個新的參數分解規劃。它既期望處理當參數出現於目標函數或限制條件時

的區域搜尋，同時也必須處理解本身的性質對於整體環境的代表性。

　　以EA求解MOPs，搜尋到最後得到的最佳解往往有無限多組，但有限的時

間內，亟欲從這一大群解中挑選幾個代表性方案來考量，在現實中是很不合實

際的。決策者所在乎的結果，通常只希望從數個方案中，擇其一而執行。故要

如何從無限多組解中，取有限組具有決定性影響力的解，進行最終決策，又是

另一個所謂selection的問題。

　　關於從解集合(or解空間)裡，選擇具代表性的解，張教授引用Deb's

selection所提出的法則。此法的基本原理是利用鄰近解(neighbor)的概念，首

先將多維的最佳解空間映射到二維平面，得到一個曲線(or線性)解集合。對於

任一組解，分別計算它跟兩邊鄰近解之距離，然後將此距離值最大化，避免

一再挑選到相似程度高的局部解。盡可能讓各個解呈均勻分布後，每個解的

代表性也相對提高。

　　最後，張教授跟我們分享一些評審經驗，以及口試的應答要訣，可能因完

全沒有過任何經驗，還抓不到所謂的臨場感，就算想請教也不知該從哪邊問起

。此外，目前為止，英文paper對我而言仍是一項不小的障礙，很多觀念上的釐

清，因為英文敘述的緣故而被搞得一知半解，沒辦法我向來對滿滿一整篇豆芽

菜真的會眼花，而且難以消化，看樣子我的英文能力還有很大的空間需要努力。





2008/04/04