×

zbMATH — the first resource for mathematics

Generalized decomposition and cross entropy methods for many-objective optimization. (English) Zbl 1355.90091
Summary: Decomposition-based algorithms for multi-objective optimization problems have increased in popularity in the past decade. Although convergence to the Pareto optimal front (PF) for such algorithms can often be superior to that of Pareto-based alternatives, the problem of effectively distributing Pareto optimal solutions in a high-dimensional space has not been solved. In this work, we introduce a novel concept which we call generalized decomposition. Generalized decomposition provides a framework with which the decision maker (DM) can guide the underlying search algorithm toward specific regions of interest, or the entire Pareto front, with the desired distribution of Pareto optimal solutions. The method simplifies many-objective problems by unifying the three performance objectives of an a posteriori multi-objective optimizer – convergence to the PF, evenly distributed Pareto optimal solutions and coverage of the entire front – to only one, that of convergence. A framework, established on generalized decomposition, and an estimation of distribution algorithm (EDA) based on low-order statistics, namely the cross-entropy method, is created to illustrate the benefits of the proposed concept for many-objective problems. The algorithm – MACE-gD – is shown to be highly competitive with the existing best-in-class decomposition-based algorithm (MOEA/D) and a more elaborate EDA method (RM-MEDA).

MSC:
90C29 Multi-objective and goal programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fleming, P.; Purshouse, R., Evolutionary algorithms in control systems engineering: a survey, Control Eng. Pract., 10, 11, 1223-1241, (2002)
[2] M. Tapia, C. Coello, Applications of multi-objective evolutionary algorithms in economics and finance: a survey, in: IEEE Congress on Evolutionary Computation, 2007, pp. 532-539.
[3] N. Krasnogor, W. Hart, J. Smith, D. Pelta, Protein structure prediction with evolutionary algorithms, in: Proceedings of the Genetic and Evolutionary Computation Conference, vol. 2, 1999, pp. 1596-1601.
[4] Miettinen, K., Nonlinear Multiobjective Optimization, vol. 12, (1999), Springer · Zbl 0949.90082
[5] E. Zitzler, M. Laumanns, L. Thiele, et al., SPEA2: improving the strength Pareto evolutionary algorithm, in: EUROGEN, no. 103, 2001, pp. 1-21.
[6] Purshouse, R.; Fleming, P., Evolutionary many-objective optimisation: an exploratory analysis, (IEEE Congress on Evolutionary Computation, vol. 3, (2003), IEEE), 2066-2073
[7] Goldberg, D.; Holland, J., Genetic algorithms and machine learning, Mach. Learn., 3, 2, 95-99, (1988)
[8] Giagkiozis, I.; Purshouse, R. C.; Fleming, P. J., An overview of population-based algorithms for multi-objective optimisation, Int. J. Syst. Sci., 0, 0, 1-28, (2013)
[9] C. Fonseca, P. Fleming, Genetic algorithms for multiobjective optimization: formulation, discussion and generalization, in: Conference on Genetic Algorithms, vol. 423, 1993, pp. 416-423.
[10] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731, (2007)
[11] F. Edgeworth, Mathematical Psychics: An Essay on the Application of Mathematics to the Moral Sciences, no. 10, CK Paul, 1881. · Zbl 0005.17402
[12] V. Pareto, Cours d’économie politique, Librairie Droz, 1896.
[13] H. Ishibuchi, N. Tsukamoto, Y. Nojima, Evolutionary many-objective optimization: a short review, in: IEEE Congress on Evolutionary Computation, 2008, pp. 2419-2426.
[14] Takahashi, R.; Saldanha, R.; Dias-Filho, W.; Ramírez, J., A new constrained ellipsoidal algorithm for nonlinear optimization with equality constraints, IEEE Trans. Magn., 39, 3, 1289-1292, (2003)
[15] Jaszkiewicz, A., On the performance of multiple-objective genetic local search on the 0/1 knapsack problem - a comparative experiment, IEEE Trans. Evol. Comput., 6, 4, 402-412, (2002)
[16] Hughes, E., Multiple single objective Pareto sampling, (Congress on Evolutionary Computation, vol. 4, (2003), IEEE), 2678-2684
[17] E. Hughes, MSOPS-II: a general-purpose many-objective optimiser, in: IEEE Congress on Evolutionary Computation, 2007, pp. 3944-3951.
[18] Giagkiozis, I.; Purshouse, R. C.; Fleming, P. J., Generalized decomposition, (Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, vol. 7811, (2013), Springer Berlin, Heidelberg), 428-442
[19] S. Jiang, Z. Cai, J. Zhang, Y.-S. Ong, Multiobjective optimization by decomposition with Pareto-adaptive weight vectors, in: International Conference on Natural Computation, vol. 3, 2011, pp. 1260-1264.
[20] Jiang, S.; Zhang, J.; Ong, Y., Asymmetric Pareto-adaptive scheme for multiobjective optimization, (Advances in Artificial Intelligence, Lecture Notes in Computer Science, vol. 7106, (2011), Springer Berlin, Heidelberg), 351-360
[21] 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)
[22] While, L.; Hingston, P.; Barone, L.; Huband, S., A faster algorithm for calculating hypervolume, IEEE Trans. Evol. Comput., 10, 1, 29-38, (2006)
[23] C. Fonseca, L. Paquete, M. Lopez-Ibanez, An improved dimension-sweep algorithm for the hypervolume indicator, in: IEEE Congress on Evolutionary Computation, 2006, pp. 1157-1163.
[24] Gu, F.; Liu, H.; Tan, K., A multiobjective evolutionary algorithm using dynamic weight method, Int. J. Innov. Comput. Inform. Control, 8, 5B, 3677-3688, (2012)
[25] I. Giagkiozis, R. Purshouse, P. Fleming, Towards understanding the cost of adaptation in decomposition-based optimization algorithms, in: IEEE International Conference on Systems, Man and Cybernetics, 2013, pp. 615-620.
[26] 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, 5, 477-506, (2006)
[27] K. Deb, L. Thiele, M. Laumanns, E. Zitzler, Scalable multi-objective optimization test problems, in: Congress on Evolutionary Computation, vol. 1, 2002, pp. 825-830.
[28] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evol. Comput., 8, 2, 173-195, (2000)
[29] Mühlenbein, H.; Paass, G., From recombination of genes to the estimation of distributions I. binary parameters, Parall. Probl. Solving Nat., 178-187, (1996)
[30] He, J.; Yao, X., Drift analysis and average time complexity of evolutionary algorithms, Artif. Intell., 127, 1, 57-85, (2001) · Zbl 0971.68129
[31] Chen, T.; Tang, K.; Chen, G.; Yao, X., Analysis of computational time of simple estimation of distribution algorithms, IEEE Trans. Evol. Comput., 14, 1, 1-22, (2010)
[32] M. Hauschild, M. Pelikan, A Survey of Estimation of Distribution Algorithms, Tech. Rep., University of Missouri - St. Louis, 2011.
[33] Pelikan, M., Bayesian optimization algorithm, Hierarchical Bayesian Optim. Algor., 31-48, (2005)
[34] Emmendorfer, L.; Pozo, A., Effective linkage learning using low-order statistics and clustering, IEEE Trans. Evol. Comput., 13, 6, 1233-1246, (2009)
[35] Echegoyen, C.; Zhang, Q.; Mendiburu, A.; Santana, R.; Lozano, J., On the limits of effectiveness in estimation of distribution algorithms, (IEEE Congress on Evolutionary Computation, (2011), IEEE), 1573-1580
[36] Rubinstein, R., The cross-entropy method for combinatorial and continuous optimization, Methodol. Comput. Appl. Probabi., 1, 2, 127-190, (1999) · Zbl 0941.65061
[37] Damelin, S. B.; Grabner, P. J., Energy functionals, numerical integration and asymptotic equidistribution on the sphere, J. Complex., 19, 3, 231-246, (2003) · Zbl 1043.65049
[38] Miettinen, K.; Mäkelä, M., On scalarizing functions in multiobjective optimization, OR Spectrum, 24, 2, 193-213, (2002) · Zbl 1040.90037
[39] I. Giagkiozis, P. Fleming, Methods for Many-Objective Optimization: An Analysis, Research Report No. 1030, November 2012. · Zbl 1355.90090
[40] Grant, M.; Boyd, S.; Ye, Y., (Disciplined Convex Programming, Nonconvex Optimization and its Applications, vol. 84, (2006), Springer), 155-210 · Zbl 1130.90382
[41] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge University Press · Zbl 1058.90049
[42] M. Grant, S. Boyd, CVX: Matlab Software for Disciplined Convex Programming. <http://cvxr.com/cvx/>.
[43] Saff, E.; Kuijlaars, A., Distributing many points on a sphere, Math. Intell., 19, 1, 5-11, (1997) · Zbl 0901.11028
[44] Hardin, D.; Saff, E., Discretizing manifolds via minimum energy points, Notices AMS, 51, 10, 1186-1194, (2004) · Zbl 1095.49031
[45] Li, H.; Zhang, Q., Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II, IEEE Trans. Evol. Comput., 13, 2, 284-302, (2009)
[46] Thompson, H.; Chipperfield, A.; Fleming, P.; Legge, C., Distributed aero-engine control systems architecture selection using multi-objective optimisation, Control Eng. Pract., 7, 5, 655-664, (1999)
[47] Tavakkoli-Moghaddam, R.; Rahimi-Vahed, A.; Mirzaei, A., A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness, Inform. Sci., 177, 22, 5072-5090, (2007) · Zbl 1121.90340
[48] Zhang, G.; Shao, X.; Li, P.; Gao, L., An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Comput. Ind. Eng., 56, 4, 1309-1318, (2009)
[49] Katanforoush, A.; Shahshahani, M., Distributing points on the sphere, I, Exp. Math., 12, 2, 199-210, (2003)
[50] P. Leopardi, Distributing Points on the Sphere: Partitions, Separation, Quadrature and Energy, Ph.D. Thesis, University of New South Wales, 2007.
[51] Wolpert, D., Information theory - the bridge connecting bounded rational game theory and statistical physics, Complex Eng. Syst., 262-290, (2006)
[52] Rubinstein, R., A stochastic minimum cross-entropy method for combinatorial optimization and rare-event estimation, Methodol. Comput. Appl. Probabi., 7, 1, 5-50, (2005) · Zbl 1073.65052
[53] Botev, Z.; Kroese, D.; Taimre, T., Generalized cross-entropy methods with applications to rare-event simulation and optimization, Simulation, 83, 11, 785, (2007)
[54] De Boer, P.; Kroese, D.; Mannor, S.; Rubinstein, R., A tutorial on the cross-entropy method, Ann. Oper. Res., 134, 1, 19-67, (2005) · Zbl 1075.90066
[55] Morris, C. N., Natural exponential families with quadratic variance functions, Ann. Stat., 10, 65-80, (1982) · Zbl 0498.62015
[56] Zhang, Q.; Zhou, A.; Jin, Y., RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm, IEEE Trans. Evol. Comput., 12, 1, 41-63, (2008)
[57] I. Das, J. Dennis, Normal-Boundary Intersection: An Alternate Method for Generating Pareto Optimal Points in Multicriteria Optimization Problems, Tech. Rep., DTIC Document, 1996.
[58] Deb, K.; Sinha, A.; Kukkonen, S., Multi-objective test problems, linkages, and evolutionary methodologies, (Conference on Genetic and Evolutionary Computation, (2006), ACM), 1141-1148
[59] Kukkonen, S.; Lampinen, J., GDE3: the third evolution step of generalized differential evolution, (IEEE Congress on Evolutionary Computation, vol. 1, (2005), IEEE), 443-450
[60] Bosman, P.; Thierens, D., The naive MIDEA: a baseline multi-objective EA, (Evolutionary Multi-Criterion Optimization, (2005), Springer), 428-442 · Zbl 1109.68587
[61] Wolpert, D.; Macready, W., No free lunch theorems for optimization, IEEE Trans. Evol. Comput., 1, 1, 67-82, (1997)
[62] D. Van Veldhuizen, Multiobjective evolutionary algorithms: classifications, analyses, and new innovations, in: Evolutionary Computation, 1999.
[63] Purshouse, R.; Fleming, P., On the evolutionary optimization of many conflicting objectives, IEEE Trans. Evol. Comput., 11, 6, 770-784, (2007)
[64] Hadka, D.; Reed, P., Diagnostic assessment of search controls and failure modes in many - objective evolutionary optimization, Evol. Comput., 20, 3, 423-452, (2012)
[65] Rockafellar, R., Convex Analysis, vol. 28, (1970), Princeton University Press · Zbl 0193.18401
[66] Mattingley, J.; Boyd, S., CVXGEN: a code generator for embedded convex optimization, Optimiz. Eng., 1-27, (2012) · Zbl 1293.65095
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.