×

zbMATH — the first resource for mathematics

Evolutionary multiobjective optimization in noisy problem environments. (English) Zbl 1180.90287
Summary: This paper presents a multiobjective evolutionary algorithm (MOEA) capable of handling stochastic objective functions. We extend a previously developed approach to solve multiple objective optimization problems in deterministic environments by incorporating a stochastic nondomination-based solution ranking procedure. In this study, concepts of stochastic dominance and significant dominance are introduced in order to better discriminate among competing solutions. The MOEA is applied to a number of published test problems to assess its robustness and to evaluate its performance relative to NSGA-II. Moreover, a new stopping criterion is proposed, which is based on the convergence velocity of any MOEA to the true Pareto optimal front, even if the exact location of the true front is unknown. This stopping criterion is especially useful in real-world problems, where finding an appropriate point to terminate the search is crucial.

MSC:
90C29 Multi-objective and goal programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Babbar, M., Lakshmikantha, A., Goldberg, D.E.: A modified NSGA-II to solve noisy multiobjective problems. In: 2003 Genetic and Evolutionary Computation Conference. Late-Breaking Papers, pp. 21–27. AAAI, Chicago (2003)
[2] Basseur, M., Zitzler, E.: Handling uncertainty in indicator-based multiobjective optimization. Int. J. Comput. Intell. Res. 2(3), 255–272 (2006)
[3] Beyer, H.G.: Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practice. Comput. Methods Appl. Mech. Eng. 186, 239–267 (2000) · Zbl 1064.90574 · doi:10.1016/S0045-7825(99)00386-2
[4] Borjesson, P.O., Sundberg, C.E.W.: Simple approximation of the error function Q(x) for communications applications. IEEE Trans. Commun. 27(3), 639–643 (1979) · doi:10.1109/TCOM.1979.1094433
[5] Buche, D., Stoll, P., Dornberger, R., Koumoutsakos, P.: Multiobjective evolutionary algorithm for the optimization of noisy combustion processes. IEEE Trans. Syst. Man Cybern. Part C: Appl. Rev. 32(4), 460–473 (2002) · doi:10.1109/TSMCB.2002.804372
[6] Bui, L., Abbass, H., Essam, D., Green, D.: Performance analysis of evolutionary multi-objective optimization methods in noisy environments. In: Proceedings of the 8th Asia Pacific Symposium on Intelligent and Evolutionary Systems, pp. 29–39 (2004)
[7] Bui, L.T., Hussein, A.A., Essam, D.: Fitness inheritance for noisy evolutionary multi-objective optimization. In: Beyer, H.-G. (ed.) Proceedings of the 2005 Genetic and Evolutionary Computation Conference, vol. 1, pp. 779–785. ACM, New York (2005)
[8] Coello, C.A.C., Veldhuizen, D.A., Lamont, G.B.: Evolutionary Algorithms for Solving Multi-Objective Problems, 1st edn. Kluwer Academic, New York (2002) · Zbl 1130.90002
[9] Corne, D., Deb, K., Fleming, P., Knowles, J.: The good of the many outweighs the good of the one: evolutionary multiobjective optimization. coNNectionS 1(1), 9–13 (2003)
[10] Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms, 1st edn. Wiley, Chichester (2001) · Zbl 0970.90091
[11] Deb, K., Pratap, A., Agarval, S., Meyarivan, T.A.: Fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2002) · Zbl 05451853 · doi:10.1109/4235.996017
[12] 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) · Zbl 05412959 · doi:10.1162/106365605774666895
[13] Erbas, C., Cerav-Erbas, S., Pimentel, A.D.: Multiobjective optimization and evolutionary algorithms for the application mapping problem in multiprocessor system-on-chip design. IEEE Trans. Evol. Comput. 10(3), 358–374 (2006) · Zbl 05451880 · doi:10.1109/TEVC.2005.860766
[14] Eskandari, H., Geiger, C.D.: A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems. J. Heuristics 14(3), 203–241 (2008) · Zbl 1211.90207 · doi:10.1007/s10732-007-9037-z
[15] Fieldsend, J.E., Everson, R.M.: Multi-objective optimization in the presence of uncertainty. In: 2005 IEEE Congress on Evolutionary Computation (CEC’2005), vol. 1, pp. 243–250. IEEE Service Center, Edinburgh (2005)
[16] Fonseca, C.M., Flemming, P.J.: Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. In: Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, CA, pp. 416–423 (1993)
[17] Goh, C.K., Tan, K.C.: An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 11(3), 354–381 (2007) · Zbl 05516216 · doi:10.1109/TEVC.2006.882428
[18] Goldberg, D.E., Deb, K., Clark, J.H.: Genetic algorithms, noise, and the sizing of populations. Complex Syst. 6, 333–362 (1992) · Zbl 0800.68600
[19] Hughes, E.J.: Evolutionary multi-objective ranking with uncertainty and noise. In: First International Conference on Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer, Berlin (2001)
[20] Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments–a survey. IEEE Trans. Evol. Comput. 9(3), 303–318 (2005) · Zbl 05452035 · doi:10.1109/TEVC.2005.846356
[21] Joines, J., Gupta, D., Gokce, M.A., King, R.E., Kay, M.G.: Supply chain multi-objective simulation optimization. In: Proceedings of the 2002 Winter Simulation Conference, pp. 1306–1313. Institute of Electrical and Electronics Engineers, Piscataway (2002)
[22] Knowles, J.: ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans. Evol. Comput. 10(1), 50–66 (2006) · Zbl 05452069 · doi:10.1109/TEVC.2005.851274
[23] Knowles, J., Corne, D.: The Pareto archived evolution strategy: a new baseline algorithm for multiobjective optimization. In: Proceedings of the 1999 Congress on Evolutionary Computation (CEC 1999), pp. 98–105. IEEE Service Center, Washington (1999)
[24] Knowles, J.D., Corne, D.W.: On metrics for comparing nondominated sets. In: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 1, pp. 711–716 (2002)
[25] Liefooghe, A., Basseur, M., Jourdan, L., Talbi, E.: Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem. In: EMO 2006, pp. 457–471 (2007)
[26] Lim, D., Ong, Y.S., Jin, Y., Sendhoff, B., Lee, B.S.: Inverse multi-objective robust evolutionary design. Gen. Program. Evol. Mach. 7(4), 383–404 (2005) · Zbl 05146473 · doi:10.1007/s10710-006-9013-7
[27] Miller, B.L.: Noise, sampling, and efficient genetic algorithms. IlliGAL Report No. 97001, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL (1997)
[28] Poles, S., Rigoni, E., Robic, T.: MOGA-II performance on noisy optimization problems. In: Proceedings of the International Conference on Bioinspired Optimization Methods and their Applications, pp. 51–62. Jozef Stefan Institute, Ljubljana (2004)
[29] Safe, M., Carballido, J.A., Ponzoni, I., Brignole, N.B.: On stopping criteria for genetic algorithms. In: Advances in Artificial Intelligence, SBIA 2004, pp. 405–413 (2004) · Zbl 1105.68428
[30] Singh, A.: Uncertainty based multi-objective optimization of groundwater remediation design. Master’s Thesis, University of Illinois at Urbana-Champaign (2003)
[31] Singh, A., Minsker, B.S.: Uncertainty based multi-objective optimization of groundwater remediation at the umatilla chemical depot. In: American Society of Civil Engineers (ASCE) Environmental & Water Resources Institute (EWRI) World Water & Environmental Resources Congress 2004 & Related Symposia, Salt Lake City, UT (2004)
[32] Srinivas, N., Deb, K.: Multiobjective optimization using nondominated sorting in genetic algorithms. Int. J. Evol. Comput. 2(3), 221–248 (1994) · Zbl 05412883 · doi:10.1162/evco.1994.2.3.221
[33] Teich, J.: Pareto-front exploration with uncertain objectives. In: Proceedings of the First Conference on Evolutionary Multi-Criterion Optimization (2001)
[34] Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173–195 (2000) · Zbl 05412936 · doi:10.1162/106365600568202
[35] Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative study and strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999) · Zbl 05452215 · doi:10.1109/4235.797969
[36] Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength Pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland (2001)
[37] 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) · Zbl 05452216 · doi:10.1109/TEVC.2003.810758
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.