A fast steady-state \(\varepsilon \)-dominance multi-objective evolutionary algorithm. (English) Zbl 1209.90314
Summary: Multi-objective evolutionary algorithms (MOEAs) have become an increasingly popular tool for design and optimization tasks in real-world applications. Most of the popular baseline algorithms are pivoted on the use of Pareto-ranking (that is empirically inefficient) to improve the convergence to the Pareto front of a multi-objective optimization problem. This paper proposes a new \(\varepsilon \)-dominance MOEA (EDMOEA) which adopts pair-comparison selection and steady-state replacement instead of the Pareto-ranking. The proposed algorithm is an elitist algorithm with a new preservation technique of population diversity based on the \(\varepsilon\)-dominance relation. It is demonstrated that superior results could be obtained by the EDMOEA compared with other algorithms: NSGA-II, SPEA2, IBEA, \(\varepsilon \)-MOEA, PESA and PESA-II on test problems. The EDMOEA is able to converge to the Pareto optimal set much faster especially on the ZDT test functions with a large number of decision variables.
MSC:
| 90C29 | Multi-objective and goal programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
multi-objective optimization; \(\varepsilon \)-dominance; steady-state EAs; diversity preservationReferences:
| [1] | Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002) · doi:10.1109/4235.996017 |
| [2] | Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, Athens, Greece (2001) |
| [3] | Zitzler, E., Künzli, S.: Indicator-based selection in multiobjective search. In: Parallel Problem Solving from Nature, PPSN VIII. Lecture Notes in Computer Science, vol. 3242, pp. 832–842. Springer, Berlin (2004) |
| [4] | Knowles, J., Corne, D.: The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation. In: Proceedings of the Congress on Evolutionary Computation, Washington, DC (1999) |
| [5] | Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading (1989) · Zbl 0721.68056 |
| [6] | Srinivasan, D., Rachmawati, L.: An efficient multi-objective evolutionary algorithm with steady-state replacement model. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Seattle, Washington (2006) |
| [7] | Valenzuela, C.L.: A simple evolutionary algorithm for multi-objective optimization (SEAMO). In: Proceedings of the 2002 Congress on Evolutionary Computation, Honolulu, HI (2002) |
| [8] | Rajeev, K., Peter, R.: Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm. Evol. Comput. 10(3), 283–314 (2002) · doi:10.1162/106365602760234117 |
| [9] | Laumanns, M., Thiele, L., Deb, K., Zitzler, E.: Combining convergence and diversity in evolutionary multiobjective optimization. Evol. Comput. 10(3), 263–282 (2002) · doi:10.1162/106365602760234108 |
| [10] | Deb, K., Mohan, M., Mishra, S.: Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evol. Comput. 13(4), 501–525 (2005) · doi:10.1162/106365605774666895 |
| [11] | Chinchuluun, A., Pardalos, P.: A survey of recent developments in multiobjective optimization. Ann. Oper. Res. 154(1), 29–50 (2007) · Zbl 1146.90060 · doi:10.1007/s10479-007-0186-0 |
| [12] | Coello Coello, C.A.: Evolutionary multi-objective optimization: a historical view of the field. IEEE Comput. Intell. Mag. 1(1), 28–36 (2006) · doi:10.1109/MCI.2006.1597059 |
| [13] | Coello Coello, C.A., Van Veldhuizen, D.A., Lamont, G.B.: Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic, Dordrecht (2002) · Zbl 1130.90002 |
| [14] | Ikeda, K., Kita, H., Kobayashi, S.: Failure of Pareto-based MOEAs: does non-dominated really mean near to optimal? In: Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, South Korea (2001) |
| [15] | Zitzler, E., Laumanns, M., Bleuler, S.: A tutorial on evolutionary multiobjective optimization. In: Workshop on Multiple Objective Metaheuristics (MOMH 2002), Berlin, Germany (2004) · Zbl 1134.90491 |
| [16] | Deb, K.: Multi-Objective Optimization using Evolutionary Algorithm. Wiley, New York (2001) · Zbl 0970.90091 |
| [17] | Fonseca, C.M., Fleming, P.J.: An overview of evolutionary algorithms in multiobjective optimization. Evol. Comput. 3(1), 1–16 (1995) · doi:10.1162/evco.1995.3.1.1 |
| [18] | Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999) · doi:10.1109/4235.797969 |
| [19] | Kukkonen, S., Deb, K.: Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. In: IEEE Congress on Evolutionary Computation, Canada (2006) |
| [20] | Corne, D.W., Jerram, N.R., Knowles, J.D., Oates, M.J.: PESA-II: Region-based selection in evolutionary multiobjective optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) (2001) |
| [21] | Jensen, M.T.: Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms. IEEE Trans. Evol. Comput. 7(5), 503–515 (2003) · doi:10.1109/TEVC.2003.817234 |
| [22] | Liu, L., Li, M., Lin, D.: A novel epsilon-dominance multi-objective evolutionary algorithms for solving DRS multi-objective optimization problems. In: Third International Conference on Natural Computation, Haikou, HaiNan (2007) |
| [23] | Schütze, O., Laumanns, M., Tantar, E., Coello, C.A.C., Talbi, E.: Convergence of stochastic search algorithms to gap-free Pareto front approximations. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, London, England (2007) |
| [24] | Parks, G.T., Miller, I.: Selective breeding in a multiobjective genetic algorithm. In: Parallel Problem Solving from Nature, PPSN V. Lecture Notes in Computer Science, vol. 1498, pp. 250–259. Springer, Berlin (1998) |
| [25] | Deb, K., Goel, T.: Controlled elitist non-dominated sorting genetic algorithms for better convergence. In: First International Conference on Evolutionary Multi-Criterion Optimization, Zurich (2001) |
| [26] | Hu, J., Seo, K., Fan, Z., Rosenberg, R.C., Goodman, E.D.: Hemo: A sustainable multi-objective evolutionary optimization framework. In: Genetic and Evolutionary Computation Conference, Washington, DC (2003) · Zbl 1028.68776 |
| [27] | Sierra, M.R., Coello, C.A.C.: Improving PSO-based multi-objective optimization using crowding, mutation and e-dominance. In: Evolutionary Multi-Criterion Optimization, vol. 3410, pp. 505–519 (2005) · Zbl 1109.68631 |
| [28] | Wu, J., Azarm, S.: Metrics for quality assessment of a multiobjective design optimization solution set. J. Mech. Des. 123(1), 18–25 (2001) · doi:10.1115/1.1329875 |
| [29] | Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173–195 (2000) · doi:10.1162/106365600568202 |
| [30] | Deb, K., Agrawal, R.B.: Simulated binary crossover for continuous search space. Complex Syst. 9(1), 115–148 (1995) · Zbl 0843.68023 |
| [31] | Deb, K., Goyal, M.: A combined genetic adaptive search GeneAS for engineering design. Comput. Sci. Inform. 26(4), 30–45 (1996) |
| [32] | Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003) · doi:10.1109/TEVC.2003.810758 |
| [33] | Knowles, J., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastic multiobjective optimizers. Technical Report, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland (2006) |
| [34] | Conover, W.J.: Practical Nonparametric Statistics, 3rd edn. Wiley, New York (1999) |
| [35] | Rosner, B.: Fundamentals of Biostatistics, 4th edn. Duxbury, Boston (1995) |
| [36] | Fonseca, C.M., Fleming, P.J.: On the performance assessment and comparison of stochastic multiobjective optimizers. In: Proceedings of the 4th International Conference on Parallel Problem Solving from Nature (1996) |
| [37] | Laumanns, M., Zitzler, E., Thiele, L.: A unified model for multi-objective evolutionary algorithms with elitism. In: Proceedings of the 2000 Congress on Evolutionary Computation, California (2000) |
| [38] | Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable test problems for evolutionary multi-objective optimization. Technical Report, Computer Engineering and Networks Laboratory, ETH Zurich (2001) · Zbl 1078.90567 |
| [39] | Wagner, T., Beume, N., Naujoks, B.: Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Evolutionary Multi-Criterion Optimization, vol. 742–756 (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
