×

zbMATH — the first resource for mathematics

Multi-objective optimization with an adaptive resonance theory-based estimation of distribution algorithm. (English) Zbl 1292.65071
Summary: The introduction of learning to the search mechanisms of optimization algorithms has been nominated as one of the viable approaches when dealing with complex optimization problems, in particular with multi-objective ones. One of the forms of carrying out this hybridization process is by using multi-objective optimization estimation of distribution algorithms (MOEDAs). However, it has been pointed out that current MOEDAs have an intrinsic shortcoming in their model-building algorithms that hamper their performance. In this work, we put forward the argument that error-based learning, the class of learning most commonly used in MOEDAs is responsible for current MOEDA underachievement. We present adaptive resonance theory (ART) as a suitable learning paradigm alternative and present a novel algorithm called multi-objective ART-based EDA (MARTEDA) that uses a Gaussian ART neural network for model-building and a hypervolume-based selector as described for the HypE algorithm. In order to assert the improvement obtained by combining two cutting-edge approaches to optimization an extensive set of experiments are carried out. These experiments also test the scalability of MARTEDA as the number of objective functions increases.

MSC:
65K10 Numerical optimization and variational techniques
90C29 Multi-objective and goal programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahn, C.W.: Advances in Evolutionary Algorithms. Theory, Design and Practice. Springer (2006). ISBN 3-540-31758-9 · Zbl 1103.68105
[2] Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York (1996) · Zbl 0877.68060
[3] Bader, J.: Hypervolume-based search for multiobjective optimization: theory and methods. Ph.D. thesis, ETH Zurich, Switzerland (2010)
[4] Bader, J; Deb, K; Zitzler, E; Beckmann, M (ed.); Künzi, HP (ed.); Fandel, G (ed.); Trockel, W (ed.); Basile, A (ed.); Drexl, A (ed.); Dawid, H (ed.); Inderfurth, K (ed.); Kürsten, W (ed.); Schittko, U (ed.); Ehrgott, M (ed.); Naujoks, B (ed.); Stewart, TJ (ed.); Wallenius, J (ed.), Faster hypervolume-based search using Monte Carlo sampling, No. 634, 313-326, (2010), Berlin · Zbl 1184.90147
[5] Bader, J; Zitzler, E, Hype: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 45-76, (2011)
[6] Bellman, R.E.: Adaptive Control Processes. Princeton University Press, Princeton (1961) · Zbl 0103.12901
[7] Beume, N, S-metric calculation by considering dominated hypervolume as klee’s measure problem, Evol. Comput., 17, 477-492, (2009)
[8] 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
[9] Beume, N., Rudolph, G.: Faster S-metric calculation by considering dominated hypervolume as Klee’s measure problem. In: Kovalerchuk, B. (ed.) Proceedings of the Second IASTED International Conference on Computational Intelligence, pp. 233-238. IASTED/ACTA Press (2006)
[10] Bosman, P.A.N.: Design and application of iterated density-estimation evolutionary algorithms. Ph.D. thesis, Institute of Information and Computing Sciences, Universiteit Utrecht, Utrecht, The Netherlands (2003)
[11] Bosman, P.A.N., Thierens, D.: The naïve MIDEA: A baseline multi-objective EA. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) Evolutionary Multi-Criterion Optimization. Third International Conference, EMO 2005. Springer. Lecture Notes in Computer Science, vol. 3410, pp. 428-442. Guanajuato, México (2005) · Zbl 1109.68587
[12] Box, GEP; Muller, ME, A note on the generation of random normal deviates, Ann. Math. Stat., 29, 610-611, (1958) · Zbl 0085.13720
[13] Branke, J., Lode, C., Shapiro, J.L.: Addressing sampling errors and diversity loss in umda. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation—GECCO ’07, pp. 508-515. ACM Press (2007). doi:10.1145/1276958.1277068, URL: http://portal.acm.org/citation.cfm?doid=1276958.1277068
[14] Branke, J., Miettinen, K., Deb, K., Słowiǹski, R. (eds.): Multiobjective Optimization. Lecture Notes in Computer Science, vol. 5252. Springer, Berlin (2008) · Zbl 1147.68304
[15] Bringmann, K; Friedrich, T, Approximating the volume of unions and intersections of high-dimensional geometric objects, Comput. Geom., 43, 601-610, (2010) · Zbl 1206.65072
[16] Brockhoff, D., Saxena, D.K., Deb, K., Zitzler, E.: On handling a large number of objectives a posteriori and during optimization. In: Knowles, J., Corne, D., Deb, K. (eds.) Multi-Objective Problem Solving from Nature: From Concepts to Applications, Natural Computing Series, pp. 377-403. Springer (2008). doi:10.1007/978-3-540-72964-8
[17] Brockhoff, D., Zitzler, E.: Dimensionality reduction in multiobjective optimization: the minimum objective subset problem. In: Waldmann, K.H., Stocker, U.M. (eds.) Operations Research Proceedings 2006, pp. 423-429. Springer (2007) · Zbl 1209.90311
[18] Carpenter, G; Grossberg, S, The ART of adaptive pattern recognition by a self-organizing neural network, Computer, 21, 77-88, (1988)
[19] Chambers, J., Cleveland, W., Kleiner, B., Tukey, P.: Graphical Methods for Data Analysis. Wadsworth, Belmont (1983) · Zbl 0532.65094
[20] Coello Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Genetic and Evolutionary Computation. Springer, New York (2007). URL: http://www.springer.com/west/home/computer/foundations?SGWID=4-156-22-173660344-0
[21] Corne, DW; Michalewicz, Z (ed.), Single objective = past, multiobjective = present, ??? = future, (2008), Piscataway
[22] Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, Chichester (2001). ISBN 0-471-87339-X · Zbl 0970.90091
[23] Deb, K; Saxena, DK, Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems, 3352-3360, (2006), Piscataway
[24] Deolalikar, V.: P≠NP. Tech. rep., Hewlett Packard Research Labs, Palo Alto, CA, USA (2010). URL: http://www.scribd.com/doc/35539144/pnp12pt
[25] Fleischer, M.: The measure of Pareto optima. Applications to multi-objective metaheuristics. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003. Springer. Lecture Notes in Computer Science, vol. 2632, pp. 519-533. Faro, Portugal (2003) · Zbl 0960.68602
[26] Fonseca, C.M., Paquete, L., López-Ibánez, M.: An improved dimension-sweep algorithm for the hypervolume indicator. In: 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pp. 1157-1163 (2006) · Zbl 1218.90178
[27] Grossberg, S, How does the brain build a cognitive code?, Psychol. Rev, 87, 1-51, (1980)
[28] Grossberg, S.: Studies of Mind and Brain: Neural Principles of Learning, Perception, Development, Cognition, and Motor Control. Reidel, Boston (1982) · Zbl 0605.92017
[29] 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)
[30] Khare, V., 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.) Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003. Springer. Lecture Notes in Computer Science, vol. 2632, pp. 376-390. Faro, Portugal (2003) · Zbl 1036.90541
[31] Knowles, J., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastic multiobjective optimizers. TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich (2006)
[32] Knowles, J.D.: Local-search and hybrid evolutionary algorithms for Pareto optimization. Ph.D. thesis, The University of Reading, Department of Computer Science, Reading, UK (2002)
[33] Lozano, J.A., Larrañaga, P., Inza, I., Bengoetxea, E. (eds.): Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms. Springer (2006) · Zbl 1089.68121
[34] Mann, HB; Whitney, DR, On a test of whether one of two random variables is stochastically larger than the other, Ann. Math. Stat., 18, 50-60, (1947) · Zbl 0041.26103
[35] Martí, L., García, J., Berlanga, A., Coello Coello, C.A., Molina, J.M.: On current model-building methods for multi-objective estimation of distribution algorithms: shortcommings and directions for improvement. Tech. Rep. GIAA2010E001, Grupo de Inteligencia Artificial Aplicada, Universidad Carlos III de Madrid, Colmenarejo, Spain (2010). URL: http://www.giaa.inf.uc3m.es/miembros/lmarti/model-building
[36] Martí, L; García, J; Berlanga, A; Coello Coello, CA; Molina, JM, MB-GNG: addressing drawbacks in multi-objective optimization estimation of distribution algorithms, Oper. Res. Lett, 39, 150-154, (2011) · Zbl 1218.90178
[37] Martí, L; García, J; Berlanga, A; Molina, JM; Keizer, M (ed.); Antoniol, G (ed.); Congdon, C (ed.); Deb, K (ed.); Doerr, B (ed.); Hansen, N (ed.); Holmes, J (ed.); Hornby, G (ed.); Howard, D (ed.); Kennedy, J (ed.); Kumar, S (ed.); Lobo, F (ed.); Miller, J (ed.); Moore, J (ed.); Neumann, F (ed.); Pelikan, M (ed.); Pollack, J (ed.); Sastry, K (ed.); Stanley, K (ed.); Stoica, A (ed.); Talbi, EG (ed.); Wegener, I (ed.), Introducing MONEDA: scalable multiobjective optimization with a neural estimation of distribution algorithm, 689-696, (2008), New York
[38] Michalski, RS, Learnable evolution model: evolutionary processes guided by machine learning, Mach. Learn., 38, 9-40, (2000) · Zbl 0960.68602
[39] Papadimitriou, C.M.: Computational Complexity. Addison-Wesley, Reading (1994) · Zbl 0833.68049
[40] Pelikan, M., Goldberg, D.E., Lobo, F.: A Survey of Optimization by Building and Using Probabilistic Models. IlliGAL Report No. 99018, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL (1999) · Zbl 0988.90052
[41] Pelikan, M., Sastry, K., Goldberg, D.E.: Multiobjective estimation of distribution algorithms. In: Pelikan, M., Sastry, K., Cantú-Paz, E. (eds.) Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, Studies in Computational Intelligence, pp. 223-248. Springer (2006) · Zbl 1165.90632
[42] Pena, JM; Robles, V; Larrañaga, P; Herves, V; Rosales, F; Pérez, MS, GA-EDA: hybrid evolutionary algorithm using genetic and estimation of distribution algorithms, 361-371, (2004), Heidelberg
[43] Praditwong, K; Yao, X, How well do multi-objective evolutionary algorithms scale to large problems, 3959-3966, (2007), Piscataway
[44] Purshouse, RC; Fleming, PJ, On the evolutionary optimization of many conflicting objectives, IEEE Trans. Evol. Comput, 11, 770-784, (2007)
[45] Sarle, W.S.: Why statisticians should not FART. Tech. rep., SAS Institute, Cary, NC (1995)
[46] Sheri, G; Corne, DW, The simplest evolution/learning hybrid: LEM with KNN, 3244-3251, (2008), Hong Kong
[47] Sheri, G; Corne, DW, Learning-assisted evolutionary search for scalable function optimization: LEM(ID3), (2010), Barcelona
[48] Stewart, TJ; Bandte, O; Braun, H; Chakraborti, N; Ehrgott, M; Göbelt, M; Jin, Y; Nakayama, H; Poles, S; Stefano, D; Branke, J (ed.); Miettinen, K (ed.); Deb, K (ed.); Słowiǹski, R (ed.), Real-world applications of multiobjective optimization, No. 5252, 285-327, (2008), Berlin
[49] Wagner, T; Beume, N; Naujoks, B; Obayashi, S (ed.); Deb, K (ed.); Poloni, C (ed.); Hiroyasu, T (ed.); Murata, T (ed.), Pareto-, aggregation-, and indicator-based methods in many-objective optimization, No. 4403, 742-756, (2007), Heidelberg · Zbl 1159.68305
[50] Wagner, T; Beume, N; Naujoks, B; Obayashi, S (ed.); Deb, K (ed.); Poloni, C (ed.); Hiroyasu, T (ed.); Murata, T (ed.), Pareto-, aggregation-, and indicator-based methods in many-objective optimization, No. 4403, 742-756, (2007), Berlin
[51] While, L; Hingston, P; Barone, L; Huband, S, A faster algorithm for calculating hypervolume, IEEE Trans. Evol. Comput, 10, 29-38, (2006)
[52] Williamson, JR, Gaussian ARTMAP: a neural network for fast incremental learning of noisy multidimensional maps, Neural Netw., 9, 881-897, (1996)
[53] Williamson, JR, A constructive, incremental-learning network for mixture modeling and classification, Neural Comput., 9, 1517-1543, (1997)
[54] Yuan, B; Gallagher, M, On the importance of diversity maintenance in estimation of distribution algorithms, 719-726, (2005), New York
[55] Zhang, Q; Li, H, MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput, 11, 712-731, (2007)
[56] Zhang, Q; Sun, J; Tsang, E, An evolutionary algorithm with guided mutation for the maximum clique problem, IEEE Trans. Evol. Comput., 9, 192-200, (2005)
[57] Zhang, Q; Zhou, A; Jin, Y, RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm, IEEE Trans. Evol. Comput, 12, 41-63, (2008)
[58] Zhang, Q., Zhou, A., Zhao, S., Suganthan, P., Liu, W., Tiwari, S.: Multiobjective optimization test instances for the CEC 2009 special session and competition. Tech. rep., University of Essex, Colchester, UK and Nanyang Technological University, Singapore (2009)
[59] Zitzler, E; Brockhoff, D; Thiele, L; Obayashi, S (ed.); etal., The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration, No. 4403, 862-876, (2007), Berlin
[60] Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms on test functions of different difficulty. In: Wu, A.S. (ed.) Proceedings of the 1999 Genetic and Evolutionary Computation Conference. Workshop Program, pp. 121-122. Orlando, Florida (1999)
[61] Zitzler, E; Laumanns, M; Thiele, L; Fonseca, CM; Grunert da Fonseca, V; Langdon, WB (ed.); Cantú-Paz, E (ed.); Mathias, K (ed.); Roy, R (ed.); Davis, D (ed.); Poli, R (ed.); Balakrishnan, K (ed.); Honavar, V (ed.); Rudolph, G (ed.); Wegener, J (ed.); Bull, L (ed.); Potter, M (ed.); Schultz, A (ed.); Miller, J (ed.); Burke, E (ed.); Jonoska, N (ed.), Why quality assessment of multiobjective optimizers is difficult, 666-673, (2002), San Francisco
[62] Zitzler, E; Thiele, L; Laumanns, M; Fonseca, CM; Grunert da Fonseca, V, Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput, 7, 117-132, (2003)
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.