Effects of MOEA Temporally Switching Pareto Partial Dominance on Many-objective 0/1 Knapsack Problems

• Sato Hiroyuki

  Faculty of Electro-Communications, The University of Electro-Communications

• Aguirre Hernán E.

  International Young Researcher Empowerment Center, Shinshu University

• Kiyoshi Tanaka

  Faculty of Engineering, Shinshu University

Bibliographic Information

Other Title

• 多数目的０／１ナップザック問題における部分支配を時間的に切り替えるＭＯＥＡの効果

Abstract

In this work, we propose a novel multi-objective evolutionary algorithm (MOEA) which improves search performance of MOEA especially for many-objective combinatorial optimization problems. Pareto dominance based MOEAs such as NSGA-II and SPEA2 meet difficulty to rank solutions in the population noticeably deteriorating search performance as we increase the number of objectives. In the proposed method, we rank solutions by calculating Pareto partial dominance between solutions using r objective functions selected from m objective functions to induce appropriate selection pressure in many-objective optimization by Pareto-based MOEA. Also, we temporally switch r objective functions among _mC_r combinations in every interval generations I_g to optimize all of the objective functions throughout the entire evolution process. In this work, we use many-objective 0/1 knapsack problems to show the search performance of the proposed method and analyze its evolution behavior. Simulation results show that there is an optimum value for the number of objective functions r to be considered for the calculation of Pareto partial dominance and the interval (generation numbers) I_g to maximize the entire search performance. Also, the search performance of the proposed method is superior to recent state-of-the-art MOEAs, i.e., IBEA, CDAS and MSOPS. Furthermore, we show that the computational time of the proposed method is much less than IBEA, CDAS and MSOPS, and comparative or sometimes less than NSGA-II.

Journal

• Transactions of the Japanese Society for Artificial Intelligence

  Transactions of the Japanese Society for Artificial Intelligence 25 (2), 320-331, 2010

  The Japanese Society for Artificial Intelligence

Keywords

• multi-objective evolutionary algorithm
• many-objective optimizaion
• Pareto partial dominance
• many-objective 0/1 knapsack problem

Details

• CRID: 1390282680085779968
• NII Article ID: 130000259124
• DOI: 10.1527/tjsai.25.320
• ISSN: 13468030
• ISSN: 13460714
• Web Site: http://www.jstage.jst.go.jp/article/tjsai/25/2/25_2_320/_pdf
• Text Lang: ja
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed