Inverted PBI in MOEA/D and its impact on the search performance on multi and many-objective optimization

ABSTRACT

MOEA/D decomposes a multi-objective optimization problem into a number of single objective optimization problems. Each single objective optimization problem is defined by a scalarizing function using a weight vector. In MOEA/D, there are several scalarizing approaches such as the weighted Tchebycheff, the weighted sum, and the PBI (penalty-based boundary intersection). However, these conventional scalarizing approaches face a difficulty to approximate a widely spread Pareto front in some problems. To enhance the spread of Pareto optimal solutions in the objective space and improve the search performance of MOEA/D especially in many-objective optimization problems, in this work we propose the inverted PBI scalarizing approach which is an extension of the conventional PBI. We use many-objective knapsack problems and WFG4 problems with 2-8 objectives, and compare the search performance of NSGA-III and four MOEA/Ds using the weighted Tchebycheff, the weighted sum, the PBI and the inverted PBI. As results, we show that MOEA/D using the inverted PBI achieves higher search performance than other algorithms in problems with many-objectives and the difficulty to obtain a widely spread Pareto front in the objective space.

References

1. . Zhang and H. Li, "MOEA/D: A Multi-objective Evolutionary Algorithm Based on Decomposition," IEEE Trans. on Evolutionary Computation, Vol.11, No. 6, pp.712--731, 2007.
2. . Zhang, W. Liu and Hui Li, "The Performance of a New Version of MOEA/D on CEC09 Unconstrained MOP Test Instances," Proc. of 2009 IEEE Congress on Evolutionary Computation (CEC'2009), pp. 203--208, 2009.
3. . Zhang, W. Liu, E. Tsang and B. Virginas, "Expensive Multiobjective Optimization by MOEA/D with Gaussian Process Model," IEEE Transactions on Evolutionary Computation, Vol. 14, No. 3, pp. 456--474, 2010.
4. . Ishibuchi, Y. Sakane, N. Tsukamoto and Y. Nojima, "Simultaneous Use of Different Scalarizing Functions in MOEA/D," Proc. of the 12th annual conference on Genetic and Evolutionary Computation (GECCO'2010), pp. 519--526, ACM Press, 2010.
5. . Z. Martinez and C. A. C. Coello, "A Hybridization of MOEA/D with the Nonlinear Simplex Search Algorithm," Proc. of the 2013 IEEE Symposium on Computational Intelligence in Multicriteria Decision Making (MCDM'2013), pp. 48--55, IEEE Press, 2013.
6. . Deb, A. Pratap, S. Agarwal, T. Meyarivan, "A Fast Elitist Multi-Objective Genetic Algorithm: NSGA-II," IEEE Trans. on Evolutionary Computation, Vol.6, pp.182--197, 2002.
7. . Zitzler, M. Laumanns and L. Thiele, "SPEA2: Improving the Strength Pareto Evolutionary Algorithm," shape TIK-Report, No.103, 2001.
8. . Ishibuchi, N. Tsukamoto, and Y. Nojima, "Evolutionary many-objective optimization: A short review," Proc. of 2008 IEEE Congress on Evolutionary Computation (CEC2008), pp. 2424--2431, 2008.
9. . Deb and H. Jain, "An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach, Part I: Solving Problems with Box Constraints," IEEE Transactions on Evolutionary Computation, Volume:PP, Issue:99, pp.1--23, 2013.
10. . Ishibuchi, N. Akedo, and Y. Nojima, "A Study on the Specification of a Scalarizing Function in MOEA/D for Many-Objective Knapsack Problems," Proc. of Learning and Intelligent Optimization 7 (LION 7), LNCS 7997, pp. 231--246, 2013.
11. . Zitzler and L. Thiele, "Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach," IEEE Trans. on Evolutionary Computation, Vol.3 (4), pp. 257--271, 1999.
12. . Huband, P. Hingston, L. Barone, and L. While, "A Review of Multi-objective Test Problems and a Scalable Test Problem Toolkit," IEEE Transactions on Evolutionary Computation, Vol. 10, No 5, pp. 477--506, 2006.
13. . Miettinen, Nonlinear Multiobjective Optimization, Norwell, MA:Kluwer, 1999.
14. .Zitzler, Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications, PhD thesis, Swiss Federal Institute of Technology, Zurich, 1999.
15. . Sato, H. Aguirre and K. Tanaka, "Effects of δ-Similar Elimination and Controlled Elitism in the NSGA-II Multiobjective Evolutionary Algorithm," Proc. of 2006 IEEE Congress on Evolutionary Computation (CEC2006), pp. 1164--1171, 2006.
16. http://www.tik.ee.ethz.ch/sop/download/supplementary/testProblemSuite/

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization