以調變式記憶規劃改善拆解式多目標演化演算法

Adaptive Memory Programming for Improving MOEA/D

陳柏諭(Bo-Yu Chen)

指導教授 ： 尹邦嚴

國立暨南國際大學/管理學院/資訊管理學系/碩士(2012年)

https://doi.org/10.6837/NCNU.2012.00254

摘要

MOEA/D演算法是一種新興的多目標演化式演算法(MOEA)，它利用目標空間拆解(decomposition)的觀念，將多目標問題拆解成數個單一目標子問題。MOEA/D是利用一組均勻間隔的權重向量來定義拆解後的數個單一目標子問題，再分別對個別的子問題進行演化一群特定候選解，以同時達到良好的收斂率(convergence)及分散率(diversity)。本研究提出兩個不同於傳統MOEA/D的演算法，其中slop reference update演算法利用斜率參考區間概念來判斷更適合的更新候選解對象。projection reference update演算法則加入ε-constraint programming的概念，求解某單一目標維度的最佳解，其他目標維度則限制在很小的ε可接受的範圍內。另外，我們使用了路徑重劃(Path-relinking)來改進候選解彼此分佈不均勻的情況，進行跨區間的搜尋。實驗結果顯示，我們所提出的方法在7個標竿測試問題的表現上皆較傳統的MOEA/D有更佳的表現。

關鍵字

拆解 ； 多目標演化式演算法 ； 斜率 ； ε-constraint programming ； 路徑重劃

並列摘要

MOEA/D is an emerging method for tackling multi-objective optimization problem (MOOP). Using the concept of decomposition, MOEA/D improves the multi-objective evolutionary algorithm (MOEA) by decomposing an MOOP into a number of single-objective sub-problems. MOEA/D develops a group of candidate solutions by using a set of weight vectors uniformly spread in the objective space. Then, MOEA/D optimizes each sub-problem by reference to corresponding candidate solutions. In this paper we propose adaptive memory programming strategies based on the concept of slop reference and projection reference. On the one hand, slop reference update uses the line connecting the origin and reference points in object space to instruct the direction of evolution. On the other hand, projection reference update implements the decomposition using the ɛ-constraint programming technique which optimizes the objective function in a single object while the remaining objects are constrained by a small ɛ value. Furthermore, we employed the Path-relinking strategy to improve the diversity of the solution front. Experimental results show that our methods perform better than the traditional MOEA/D on seven benchmark functions widely used in the MOOP literature.

並列關鍵字

decomposition ； multi-objective evolutionary algorithm ； slop ； ε-constraint programming ； path relinking

參考文獻

蔣雅慈 (2009). 利用擴散式粒子群最佳化進行多目標護士排程. 國立暨南國際大學資訊管理研究所碩士論文. 南投縣.

Chen, C.-M., Chen, Y.-p., and Zhang, Q. Enhancing MOEA/D with Guided Mutation and Priority Update for Multi-objective Optimization.

Chen, C.-M., Chen, Y.-p., & Zhang, Q. (2009). Enhancing MOEA/D with guided mutation and priority update for multi-objective optimization. In Proceedings of 2009 IEEE Congress on Evolutionary Computation, 209–216.

Chiang, T.-C., and Lai, Y.-P. (2011). MOEA/D-AMS: Improving MOEA/D by an Adaptive Mating Selection Mechanism. in: IEEE.

Coello, Pulido, and Lechuga. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transaction on Evolutionary Computation ( 8), 256-279.