×

Optimal averaged Hausdorff archives for bi-objective problems: theoretical and numerical results. (English) Zbl 1369.90162

Summary: One main task in evolutionary multiobjective optimization (EMO) is to obtain a suitable finite size approximation of the Pareto front which is the image of the solution set, termed the Pareto set, of a given multiobjective optimization problem. In the technical literature, the characteristic of the desired approximation is commonly expressed by closeness to the Pareto front and a sufficient spread of the solutions obtained. In this paper, we first make an effort to show by theoretical and empirical findings that the recently proposed Averaged Hausdorff (or \(\Delta_p\)-) indicator indeed aims at fulfilling both performance criteria for bi-objective optimization problems. In the second part of this paper, standard EMO algorithms combined with a specialized archiver and a postprocessing step based on the \(\Delta_p\) indicator are introduced which sufficiently approximate the \(\Delta_p\)-optimal archives and generate solutions evenly spread along the Pareto front.

MSC:

90C29 Multi-objective and goal programming

Software:

MOEA/D; jMetal; SMS-EMOA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Auger, A., Bader, J., Brockhoff, D., Zitzler, E.: Theory of the hypervolume indicator: optimal \(μ \)-distributions and the choice of the reference point. In: Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA), pp. 87-102. ACM Press (2009) · Zbl 1369.68293
[2] Beume, N; Naujoks, B; Emmerich, M, SMS-EMOA: multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 1653-1669, (2007) · Zbl 1123.90064 · doi:10.1016/j.ejor.2006.08.008
[3] Coello Coello, CA; Cruz Cortés, N, Solving multiobjective optimization problems using an artificial immune system, Genet. Program. Evolvable Mach., 6, 163-190, (2005) · doi:10.1007/s10710-005-6164-x
[4] Coello Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-objective Problems, 2nd edn. Springer, New York (2007) · Zbl 1142.90029
[5] Deb, K.: Multi-objective Optimization Using Evolutionary Algorithms. Wiley, New York (2001) · Zbl 0970.90091
[6] Deb, K; Pratap, A; Agarwal, S; Meyarivan, T, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 182-197, (2002) · doi:10.1109/4235.996017
[7] Dominguez-Medina, C., Rudolph, G., Schütze, O., Trautmann, H.: Evenly spaced Pareto fronts of quad-objective problems using PSA partitioning technique. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2013), pp. 3190-3197. IEEE Press, Piscataway, NJ (2013)
[8] Durillo, JJ; Nebro, AJ, Jmetal: a Java framework for multi-objective optimization, Adv. Eng. Softw., 42, 760-771, (2011) · doi:10.1016/j.advengsoft.2011.05.014
[9] Emmerich, M., Deutz, A., Kruisselbrink, J., Shukla, P.: Cone-based hypervolume indicators: construction, properties, and efficient computation. In: Purshouse, R., Fleming, P., Fonseca, C., Greco, S., Shaw, J. (eds.) Proceedings of Evolutionary Multi-Criterion Optimization (EMO 2013), pp. 111-127. Springer, Berlin (2013)
[10] Emmerich, M.T., Deutz, A.H., Kruisselbrink, J.W.: On quality indicators for black-box level set approximation. In: EVOLVE-A Bridge Between Probability, Set Oriented Numerics and Evolutionary Computation, pp. 157-185. Springer, Berlin (2013) · Zbl 1251.68201
[11] Gerstl, K., Rudolph, G., Schütze, O., Trautmann, H.: Finding evenly spaced fronts for multiobjective control via averaging Hausdorff-measure. In: Proceedings of 8th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE), pp. 1-6. IEEE Press (2011). doi:10.1109/ICEEE.2011.6106656
[12] Hansen, M.P., Jaszkiewicz, A.: Evaluating the quality of approximations of the non-dominated set. IMM Technical Report IMM-REP-1998-7, Institute of Mathematical Modeling, Technical University of Denmark, Lyngby (1998)
[13] Hillermeier, C.: Nonlinear Multiobjective Optimization—A Generalized Homotopy Approach. Birkhäuser, Basel (2001) · Zbl 0966.90069 · doi:10.1007/978-3-0348-8280-4
[14] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[15] Huang, V., Qin, A., K.Deb, Zitzler, E., Suganthan, P., Liang, J., Preuss, M., Huband, S.: Problem definitions for performance assessment of multi-objective optimization algorithms. Technical Report TR-13, Nanyang Technological University, Singapore (2007). http://www3.ntu.edu.sg/home/epnsugan/index_files/CEC-07/CEC07.htm
[16] Huband, S; Hingston, P; Barone, L; While, L, A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evol. Comput., 10, 477-506, (2006) · Zbl 1109.68603 · doi:10.1109/TEVC.2005.861417
[17] Knowles, J., Corne, D.: On metrics for comparing nondominated sets. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2002), vol. 1, pp. 711-716. IEEE Press, Piscataway, NJ (2002)
[18] Knowles, J.D., Corne, D.W., Fleischer, M.: Bounded archiving using the Lebesgue measure. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2003), vol. 4, pp. 2490-2497. IEEE Press, Piscatawa, NJ (2003)
[19] Kukkonen, S., Deb, K.: Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2006), pp. 1179-1186. IEEE Press, Piscataway, NJ (2006)
[20] Mehnen, J., Wagner, T., Rudolph, G.: Evolutionary optimization of dynamic multi-objective test functions. In: Proceedings of the Second Italian Workshop on Evolutionary Computation (GSICE2). ACM Press (2006). CD-ROM; http://ls11-www.cs.uni-dortmund.de/people/rudolph/publications/papers/MWR06.pdf
[21] Pareto, V.: Manual of Political Economy. The MacMillan Press, London (1971)
[22] Pottharst, A., Baptist, K., Schütze, O., Böcker, J., Fröhlecke, N., Dellnitz, M.: Operating point assignment of a linear motor driven vehicle using multiobjective optimization methods (2004). In: Proceedings of the 11th International Conference EPE-PEMC 2004. Riga, Latvia
[23] Powell, MJD, On search directions for minimization algorithms, Math. Program., 4, 193-201, (1973) · Zbl 0258.90043 · doi:10.1007/BF01584660
[24] Rudolph, G; Trautmann, H; Schütze, O, Homogene approximation der paretofront bei mehrkriteriellen kontrollproblemen, Automatisierungstechnik (at), 60, 612-621, (2012) · doi:10.1524/auto.2012.1033
[25] Rudolph, G., Trautmann, H., Sengupta, S., Schütze, O.: Evenly spaced Pareto front approximations for tricriteria problems based on triangulation. In: Proceedings of 7th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2013), pp. 443-458. Springer, Berlin (2013) · Zbl 0258.90043
[26] Salomon, S., Avigad, G., Goldvard, A., Schütze, O.: PSA—a new scalable space partition based selection algorithm for MOEAs. In: Schütze, O., et al. (eds.) EVOLVE—A Bridge Between Probability, Set Oriented Numerics, and Evolutionary Computation II (Proceedings), vol. 175, pp. 137-151. Springer, Berlin (2013)
[27] Schütze, O; Esquivel, X; Lara, A; Coello Coello, CA, Using the averaged Hausdorff distance as a performance measure in evolutionary multiobjective optimization, IEEE Trans. Evol. Comput., 16, 504-522, (2012) · doi:10.1109/TEVC.2011.2161872
[28] Trautmann, H., Rudolph, G., Dominguez-Medina, C., Schütze, O.: Finding evenly spaced Pareto fronts for three-objective optimization problems. In: Schütze, O., et al. (eds.) EVOLVE—A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II (Proceedings), pp. 89-105. Springer, Berlin (2013)
[29] Veldhuizen, D.A.V.: Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. Ph.D. thesis, Department of Electrical and Computer Engineering. Graduate School of Engineering. Air Force Institute of Technology, Wright-Patterson AFB, Ohio (1999)
[30] Witting, K.: Numerical Algorithms for the Treatment of Parametric Optimization Problems and Applications. PhD thesis, University of Paderborn (2012)
[31] Witting, K; Schulz, B; Dellnitz, M; Böcker, J; Fröhleke, N, A new approach for online multiobjective optimization of mechatronic systems, Int. J. Softw. Tools Technol. Transf., 10, 223-231, (2008) · doi:10.1007/s10009-008-0066-1
[32] Zhang, Q; Li, H, MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 712-731, (2007) · doi:10.1109/TEVC.2007.892759
[33] Zitzler, E; Deb, K; Thiele, L, Comparison of multiobjective evolutionary algorithms: empirical results, Evol. Comput., 8, 173-195, (2000) · doi:10.1162/106365600568202
[34] Zitzler, E; Thiele, L, Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3, 257-271, (1999) · doi:10.1109/4235.797969
[35] Zitzler, E; Thiele, L; Laumanns, M; Fonseca, CM; Fonseca, VG, Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput., 7, 117-132, (2003) · 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. 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.