協作限制處理機制結合演化式演算法解決限制多目標最佳化問題

Abstract

限制多目標最佳化問題是一種在現實中常常能夠見到的問題，例如排程問題與工程上的設計問題。面對這樣子的問題，我們往往需要同時解決多個互相衝突的目標並且求出來的解必須要滿足多種不同的限制。為此，我們提出結合協作限制處理機制結合多目標演算法來解決限制多目標的問題。協作限制處理機制結合了ε-比較(ε-comparison)法,懲罰(penalty)法,以及一個外部檔案紀錄(external archive)。不同於傳統的ε-比較法，我們給予每個限制一個獨立的ε值並且根據限制違反程度來控制它。懲罰法則用來處理限制違反程度超過ε值的區域，使搜尋能朝向ε-合理(feasible)區前進。外部檔案紀錄(external archive)用以維持搜尋過程中的有用個體(individual)。我們提出的演算法將建構在一個知名的多目標演化式演算法架構上，MOEA/D-DRA，並且調整繁殖運算子(reproduction operator)以接受來自於外部檔案紀錄(external archive)的有用資訊。實驗上，我們把所提出的演算法與NSGA-II以及一個利用自適性懲罰函數改進的版本在二十五個公開的限制多目標最佳化問題上作比較。

In this thesis, a constrained multiobjective optimization problem is addressed. A constrained multiobjective optimization problem involves many conflicting objectives to be optimized simultaneously and many constraints to be satisfied. A constrained multiobjective algorithm which incorporates a collaborative constraint handling mechanism is proposed to solve these problems. The collaborative constraint handling mechanism combines the ε-comparison method, penalty method, and an external archive. Unlike original ε-comparison method, we set an individual ε-value to each constraint and control it by the amount of violation. The penalty method deals with the region where constraint violation exceeds the ε-value and guides the search toward the ε-feasible region. The external archive maintains the useful individuals during the search. The proposed algorithm is based on a well-known framework of multiobjective evolutionary algorithms, MOEA/D-DRA, and the reproduction operator is modified to incorporate the useful information from the external archive. Performance of the proposed algorithm is compared with NSGA-II and an improved version with a adaptive penalty function on twenty-five public constrained multiobjective optimization problem instances.