Alternative Fitness Assignment Methods For Many Objective Optimization Problems

This paper presents a meta-objective optimization approach, called Bi-Goal Evolution (BiGE), to deal with multi-objective optimization problems with many objectives. In multi-objective optimization, it is generally observed that 1) the conflict between the proximity and diversity requirements is aggravated with the increase of the number of objectives and 2) the Pareto dominance loses its effectiveness for a high-dimensional space but works well on a low-dimensional space. Inspired by these two observations, BiGE converts a given multi-objective optimization problem into a bi-goal (objective) optimization problem regarding proximity and diversity, and then handles it using the Pareto dominance relation in this bi-goal domain. Implemented with estimation methods of individuals' performance and the classic Pareto nondominated sorting procedure, BiGE divides individuals into different nondominated layers and attempts to put well-converged and well-distributed individuals into the first few layers. From a series of extensive experiments on four groups of well-defined continuous and combinatorial optimization problems with 5, 10 and 15 objectives, BiGE has been found to be very competitive against five state-of-the-art algorithms in balancing proximity and diversity. The proposed approach is the first step towards a new way of addressing many-objective problems as well as indicating several important issues for future development of this type of algorithms.

  • 1.

    Bentley, P.J., Wakefield, J.P.: Finding Acceptable Solutions in the Pareto-Optimal Range using Multiobjective Genetic Algorithms. In: Chawdhry, P.K., Roy, R., Pant, R.K. (eds.) Soft Computing in Engineering Design and Manufacturing, Part 5, London, June 1997, pp. 231–240. Springer Verlag London Limited, Heidelberg (1997) (Presented at the 2nd On-line World Conference on Soft Computing in Design and Manufacturing (WSC2))Google Scholar

  • 2.

    Deb, K., Agrawal, S., Pratab, A., Meyarivan, T.: A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. KanGAL report 200001, Indian Institute of Technology, Kanpur, India (2000)Google Scholar

  • 3.

    Deb, K., Mohan, R.S., Mishra, S.K.: Towards a quick computation of well-spread pareto-optimal solutions. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 222–236. Springer, Heidelberg (2003)CrossRefGoogle Scholar

  • 4.

    Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable Test Problems for Evolutionary Multiobjective Optimization. In: Abraham, A., Jain, L., Goldberg, R. (eds.) Evolutionary Multiobjective Optimization. Theoretical Advances and Applications, pp. 105–145. Springer, USA (2005)CrossRefGoogle Scholar

  • 5.

    di Pierro, F., Khu, S.-T., Savić, D.A.: An Investigation on Preference Order Ranking Scheme for Multiobjective Evolutionary Optimization. IEEE Transactions on Evolutionary Computation 11(1), 17–45 (2007)CrossRefGoogle Scholar

  • 6.

    Drechsler, N., Drechsler, R., Becker, B.: Multi-objective optimisation based on relation favour. In: Zitzler, E., Deb, K., Thiele, L., Coello Coello, C.A., Corne, D.W. (eds.) EMO 2001. LNCS, vol. 1993, pp. 154–166. Springer, Heidelberg (2001)CrossRefGoogle Scholar

  • 7.

    Farina, M., Amato, P.: On the Optimal Solution Definition for Many-criteria Optimization Problems. In: Proceedings of the NAFIPS-FLINT International Conference 2002, Piscataway, New Jersey, June 2002, pp. 233–238. IEEE Service Center, Los Alamitos (2002)Google Scholar

  • 8.

    Farina, M., Amato, P.: A fuzzy definition of “optimality” for many-criteria optimization problems. IEEE Transactions on Systems, Man, and Cybernetics Part A—Systems and Humans 34(3), 315–326 (2004)CrossRefGoogle Scholar

  • 9.

    Fonseca, C.M., Fleming, P.J.: Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization. In: Forrest, S. (ed.) Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, pp. 416–423. University of Illinois at Urbana-Champaign, Morgan Kauffman Publishers (1993)Google Scholar

  • 10.

    Hughes, E.J.: Evolutionary Many-Objective Optimisation: Many Once or One Many? In: 2005 IEEE Congress on Evolutionary Computation (CEC’2005), Edinburgh, Scotland, September 2005, vol. 1, pp. 222–227. IEEE Service Center, Los Alamitos (2005)CrossRefGoogle Scholar

  • 11.

    Hughes, E.J.: Fitness Assignment Methods for Many-Objective Problems. In: Knowles, J., Corne, D., Deb, K. (eds.) Multi-Objective Problem Solving from Nature: From Concepts to Applications, pp. 307–329. Springer, Berlin (2008)CrossRefGoogle Scholar

  • 12.

    Khare, V.R., Yao, X., Deb, K.: Performance scaling of multi-objective evolutionary algorithms. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 376–390. Springer, Heidelberg (2003)CrossRefGoogle Scholar

  • 13.

    Knowles, J.D., Corne, D.W.: Quantifying the effects of objective space dimension in evolutionary multiobjective optimization. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 757–771. Springer, Heidelberg (2007)CrossRefGoogle Scholar

  • 14.

    Kokolo, I., Hajime, K., Shigenobu, K.: Failure of Pareto-based MOEAs: Does Non-dominated Really Mean Near to Optimal? In: Proceedings of the Congress on Evolutionary Computation 2001 (CEC 2001), Piscataway, New Jersey, May 2001, vol. 2, pp. 957–962. IEEE Service Center, Los Alamitos (2001)Google Scholar

  • 15.

    Le, K., Landa-Silva, D.: Obtaining Better Non-Dominated Sets Using Volume Dominance. In: 2007 IEEE Congress on Evolutionary Computation (CEC’2007), Singapore, September 2007, pp. 3119–3126. IEEE Press, Los Alamitos (2007)Google Scholar

  • 16.

    Pareto, V.: Cours d’Economie Politique. Droz, Genève (1896)Google Scholar

  • 17.

    Purshouse, R.C., Fleming, P.J.: Evolutionary Multi-Objective Optimisation: An Exploratory Analysis. In: Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003), Canberra, Australia, December 2003, vol. 3, pp. 2066–2073. IEEE Press, Los Alamitos (2003)CrossRefGoogle Scholar

  • 18.

    Sato, H., Aguirre, H.E., Tanaka, K.: Controlling dominance area of solutions and its impact on the performance of mOEAs. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 5–20. Springer, Heidelberg (2007)CrossRefGoogle Scholar

  • 19.

    Wagner, T., Beume, N., Naujoks, B.: Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 742–756. Springer, Heidelberg (2007)CrossRefGoogle Scholar

  • 20.

    Zou, X., Chen, Y., Liu, M., Kang, L.: A New Evolutionary Algorithm for Solving Many-Objective Optimization Problems. IEEE Transactions on Systems, Man, and Cybernetics–Part B: Cybernetics 38(5), 1402–1412 (2008)CrossRefGoogle Scholar

  • Comments

    Leave a Reply

    Your email address will not be published. Required fields are marked *