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

A Collaborative Constraint Handling Mechanism with Evolutionary Algorithm for Constrained Multiobjective Optimization

謝旻男(Min-Nan Hsieh)

指導教授 ： 傅立成

共同指導教授 ： 蔣宗哲

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.01984

摘要

限制多目標最佳化問題是一種在現實中常常能夠見到的問題，例如排程問題與工程上的設計問題。面對這樣子的問題，我們往往需要同時解決多個互相衝突的目標並且求出來的解必須要滿足多種不同的限制。為此，我們提出結合協作限制處理機制結合多目標演算法來解決限制多目標的問題。協作限制處理機制結合了ε-比較(ε-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.

並列關鍵字

Multiobjective Evolutionary Algorithm ； Constraint Handling ； Differential Evolution ； Constrained Multiobjective Optimization ； Constrained Optimization ； Multiobjective Optimization

參考文獻

[2] K. Deb, Multiobjective Optimization Using Evolutionary Algorithms. Chichester, U.K.: Wiley, 2001.

[3] Y. G. Woldesenbet, G. G. Yen, and B. G. Tessema, “Constraint handling in multiobjective evolutionary optimization,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 3, pp. 514-525, 2009.

[5] Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, 2007.

[6] H. Li and Q. Zhang, "Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II," IEEE Transactions on Evolutionary Computation, vol. 13, pp. 284-302, 2009.

[7] Q. Zhang, W. Liu, and H. Li, "The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances," in Proceedings of IEEE Congress on Evolutionary Computation, pp. 203-208, 2009.