Space partitioning with adaptive ε-ranking and substitute distance assignments: a comparative study on many-objective mnk-landscapes

ABSTRACT

This work compares the performance among objective space partitioning with adaptive ε-ranking, subvector dominance assignment, and epsilon dominance assignment methods that have been recently proposed for many-objective optimization. These three methods enhance selection using different strategies to recalculate the primary or secondary ranking of solutions and have been implemented using the framework of NSGA-II. The first method focuses on the primary ranking of solutions by partitioning the objective space into lower dimensional subspaces and re-ranking solutions within each subspace using an adaptive epsilon-ranking procedure. On the other hand, the latter two methods focus on the secondary ranking of solutions, replacing crowding distance with a substitute assignment distance. As test problems, we use scalable MNK-Landscapes with 4 ‹ M ‹ 10 objectives, N=100 bits, varying the number of epistatic interactions per bit K in the range 0 ‹ K ‹ 50.

REFERENCES

• 1: E. J. Hughes, "Evolutionary Many-Objective Optimisation: Many Once or One Many?", Proc. 2005 IEEE Congress on Evolutionary Computation, IEEE Service Center, Vol.1, pp.222--227, September 2005.
• 2: Marco Laumanns , Lothar Thiele , Kalyanmoy Deb , Eckart Zitzler, Combining convergence and diversity in evolutionary multiobjective optimization, Evolutionary Computation, v.10 n.3, p.263-282, Fall 2002 [doi>10.1162/106365602760234108]
• 3: E. Zitzler and S. Kunzli, "Indicator-based Selection in Multiobjective SearchAh, Proc. 8th Intl. Conf. on Parallel Problem Solving from Nature, Springer, LNCS, vol.3242, pp. 832--842, 2004.
• 4: A. Sulflow, N. Drechsler, R. Drechsler, "Robust Multi-Objective Optimization in High Dimensional Spaces", Proc. 4th Int'l Conf. on Evolutionary Multi-Criterion Optimzation, LNCS (Springer), Vol.4403, pp,715--726, 2007.
• 5: M. Koppen and K. Yoshida, "Substitute Distance Assignments in NSGA-II for Handling Many-Objective Optimization Problems", Proc. 4th Intl. Conf. on Evolutionary Multi--Criterion Optimization, Springer, LNCS, vol.4403, pp,727--741, 2007.
• 6: T. Wagner, N. Beume, and B. Naujoks, "Pareto-, Aggregation, and Indicator-Based Methods in Many-Objective Optimization", Proc. 4th Intl. Conf. on Evolutionary Multi-Criterion Optimzation, Springer, LNCS, vol.4403, pp.742--756, 2007.
• 7: Hemant K. Singh , Amitay Isaacs , Tapabrata Ray , Warren Smith, A Study on the Performance of Substitute Distance Based Approaches for Evolutionary Many Objective Optimization, Proceedings of the 7th International Conference on Simulated Evolution and Learning, December 07-10, 2008, Melbourne, Australia [doi>10.1007/978-3-540-89694-4_41]
• 8: Hernán Aguirre , Kiyoshi Tanaka, Robust Optimization by ε-Ranking on High Dimensional Objective Spaces, Proceedings of the 7th International Conference on Simulated Evolution and Learning, December 07-10, 2008, Melbourne, Australia [doi>10.1007/978-3-540-89694-4_43]
• 9: Hernán Aguirre , Kiyoshi Tanaka, Many-Objective Optimization by Space Partitioning and Adaptive ε-Ranking on MNK-Landscapes, Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization, April 07-10, 2009, Nantes, France [doi>10.1007/978-3-642-01020-0_33]
• 10: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 11: Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 12: K. Deb, S. Agrawal, A. Pratap and T. Meyarivan, "A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II", KanGAL report 200001, 2000.
• 13: H. Aguirre and K. Tanaka, "Insights on Properties of Multiobjective MNK-Landscapes", Proc. 2004 IEEE Congress on Evolutionary Computation, IEEE Service Center, pp.196--203, 2004.
• 14: H. Aguirre and K. Tanaka, "Working Principles, Behavior, and Performance of MOEAs on MNK-Landscapes", European Journal of Operational Research, Elsevier, vol. 181(3), pp. 1670--1690, September 2007.
• 15: S. A. Kauffman, The Origins of Order: Self-Organization and Selection in Evolution, Oxford University Press, 1993.
• 16: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, "Scalable Multi-Objective Optimization Test Problems". Proc. 2002 Congress on Evolutionary Computation, IEEE Service Center, pp.825--830, 2002.
• 17: E. Zitzler, Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications, PhD thesis, Swiss Federal Institute of Technology, Zurich, 1999.
• 18: C. Fonseca, L. Paquete, and M. Lopez-Ibanez, "An Improved Dimension-sweep Algorithm for the Hypervolume Indicator", Proc. 2006 IEEE Congress on Evolutionary Computation, IEEE Service Center, pp.1157--1163, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
combinatorial problems, epistasis, evolutionary many-objective optimazation, non-linear fitness functions