Abstract
Here we address the problem of computing the set of approximate solutions of a given multi-objective optimization problem (MOP). This set is of potential interest for the decision maker since it might give him/her additional solutions to the optimal ones for the realization of the project related to the MOP. In this study, we make a first attempt to adapt well-known cell mapping techniques for the global analysis of dynamical systems to the problem at hand. Due to their global approach, these methods are well-suited for the thorough investigation of small problems, including the computation of the set of approximate solutions. We conclude this work with the presentation of three academic bi-objective optimization problems including a comparison to a related evolutionary approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Lara, A.: Using Gradient Based Information to build Hybrid Multi-objective Evolutionary Algorithms. PhD thesis (2012)
Blesken, M., Chebil, A., Rückert, U., Esquivel, X., Schütze, O.: Integrated circuit optimization by means of evolutionary multi-objective optimization. In: Genetic and Evolutionary Computation Conference (GECCO 2011), pp. 807–812 (2011)
Blesken, M., Rückert, U., Steenken, D., Witting, K., Dellnitz, M.: Multiobjective optimization for transistor sizing of CMOS logic standard cells using set-oriented numerical techniques. In: 27th Norchip Conference (2009)
Bursal, F.H., Hsu, C.S.: Application of a cell-mapping method to optimal control problems. International Journal of Control 49(5), 1505–1522 (1989)
Coello Coello, C.A., Lamont, G., Van Veldhuizen, D.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Springer (2007)
Coello Coello, C.A., Cruz Cortés, N.: Solving multiobjective optimization problems using an artificial immune system. Genetic Programming and Evolvable Machines 6(2), 163–190 (2005)
Crespo, L.G., Sun, J.Q.: Stochastic optimal control of nonlinear dynamic systems via bellman’s principle and cell mapping. Automatica 39(12), 2109–2114 (2003)
Das, I., Dennis, J.: Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal of Optimization 8, 631–657 (1998)
Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. Wiley (2001)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA–II. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
Dellnitz, M., Hohmann, A.: A subdivision algorithm for the computation of unstable manifolds and global attractors. Numerische Mathematik 75, 293–317 (1997)
Dellnitz, M., Ober-Blöbaum, S., Post, M., Schütze, O., Thiere, B.: A multi-objective approach to the design of low thrust space trajectories using optimal control. Celestial Mechanics and Dynamical Astronomy 105, 33–59 (2009)
Dellnitz, M., Schütze, O., Hestermeyer, T.: Covering Pareto sets by multilevel subdivision techniques. Journal of Optimization Theory and Applications 124, 113–155 (2005)
Eichfelder, G.: Adaptive Scalarization Methods in Multiobjective Optimization. Springer, Heidelberg (2008) ISBN 978-3-540-79157-7
Fliege, J.: Gap-free computation of Pareto-points by quadratic scalarizations. Mathematical Methods of Operations Research 59, 69–89 (2004)
Heinonen, J.: Lectures on Analysis on Metric Spaces. Springer, New York (2001)
Hillermeier, C.: Nonlinear Multiobjective Optimization - A Generalized Homotopy Approach. Birkhäuser (2001)
Hsu, C.S.: A theory of cell-to-cell mapping dynamical systems. Journal of Applied Mechanics 47, 931–939 (1980)
Hsu, C.S.: A discrete method of optimal control based upon the cell state space concept. Journal of Optimization Theory and Applications 46(4), 547–569 (1985)
Hsu, C.S.: Cell-to-cell mapping: a method of global analysis for nonlinear systems. In: Applied Mathematical Sciences. Springer (1987)
Fliege, J., Svaiter, B.F.: Steepest Descent Methods for Multicriteria Optimization. Mathematical Methods of Operations Research 51(3), 479–494 (2000)
Jahn, J.: Multiobjective search algorithm with subdivision technique. Computational Optimization and Applications 35(2), 161–175 (2006)
Klamroth, K., Tind, J., Wiecek, M.: Unbiased approximation in multicriteria optimization. Mathematical Methods of Operations Research 56, 413–437 (2002)
Loridan, P.: ε-solutions in vector minimization problems. Journal of Optimization, Theory and Application 42, 265–276 (1984)
Schütze, O., Lara, A., Coello Coello, C.A.: The Directed Search Method for Unconstrained Multi-Objective Optimization Problems. Technical Report COA-R1, CINVESTAV-IPN (2010)
Schütze, O., Laumanns, M., Tantar, E., Coello Coello, C.A., Talbi, E.-G.: Computing Gap Free Pareto Front Approximations with Stochastic Search Algorithms. Evolutionary Computation 18(1)
Pareto, V.: Manual of Political Economy. The MacMillan Press (1971); original edition in French (1927)
Rudolph, G., Naujoks, B., Preuß, M.: Capabilities of emoa to detect and preserve equivalent pareto subsets. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 36–50. Springer, Heidelberg (2007)
Schäffler, S., Schultz, R., Weinzierl, K.: A stochastic method for the solution of unconstrained vector opimization problems. Journal of Optimization, Theory and Application 114(1), 209–222 (2002)
Schütze, O.: Set Oriented Methods for Global Optimization. PhD thesis, University of Paderborn (2004), http://ubdata.uni-paderborn.de/ediss/17/2004/schuetze/
Schütze, O., Coello Coello, C.A., Talbi, E.-G.: Approximating the ε-efficient set of an MOP with stochastic search algorithms. In: Gelbukh, A., Kuri Morales, Á.F. (eds.) MICAI 2007. LNCS (LNAI), vol. 4827, pp. 128–138. Springer, Heidelberg (2007)
Schütze, O., Coello Coello, C.A., Tantar, E., Talbi, E.-G.: Computing finite size representations of the set of approximate solutions of an MOP with stochastic search algorithms. In: GECCO 2008: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 713–720. ACM, New York (2008)
Schütze, O., Dell’Aere, A., Dellnitz, M.: On continuation methods for the numerical treatment of multi-objective optimization problems. In: Branke, J., Deb, K., Miettinen, K., Steuer, R.E. (eds.) Practical Approaches to Multi-Objective Optimization. Dagstuhl Seminar Proceedings, vol. 04461. Internationales Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany (2005), http://drops.dagstuhl.de/opus/volltexte/2005/349
Schütze, O., Esquivel, X., Lara, A., Coello Coello, C.A.: Using the averaged Hausdorff distance as a performance measure in evolutionary multi-objective optimization. IEEE Transactions on Evolutionary Computation 16(4), 504–522 (2012)
Schütze, O., Vasile, M., Coello Coello, C.A.: Computing the set of epsilon-efficient solutions in multiobjective space mission design. Journal of Aerospace Computing, Information, and Communication 8, 53–70 (2011)
Schütze, O., Vasile, M., Junge, O., Dellnitz, M., Izzo, D.: Designing optimal low thrust gravity assist trajectories using space pruning and a multi-objective approach. Engineering Optimization 41, 155–181 (2009)
Schütze, O., Vasile, M., Junge, O., Dellnitz, M., Izzo, D.: Designing optimal low thrust gravity assist trajectories using space pruning and a multi-objective approach. Engineering Optimization 41(2), 155–181 (2009)
Van Veldhuizen, D.A.: Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations. PhD thesis, Department of Electrical and Computer Engineering. Graduate School of Engineering. Air Force Institute of Technology, Wright-Patterson AFB, Ohio (May 1999)
Zhang, Q., Li, H.: MOEA/D: A multi-objective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11(6), 712–731 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Hernández, C., Sun, JQ., Schütze, O. (2013). Computing the Set of Approximate Solutions of a Multi-objective Optimization Problem by Means of Cell Mapping Techniques. In: Emmerich, M., et al. EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IV. Advances in Intelligent Systems and Computing, vol 227. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-01128-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-01128-8_12
Publisher Name: Springer, Heidelberg
Print ISBN: 978-3-319-01127-1
Online ISBN: 978-3-319-01128-8
eBook Packages: EngineeringEngineering (R0)