Abstract
In many applications one is faced with the problem that multiple objectives have to be optimized at the same time. Since typically the solution set of such multi-objective optimization problems forms a manifold which cannot be computed analytically, one is in many cases interested in a suitable finite size approximation of this set. One widely used approach is to find a representative set that maximizes the dominated hypervolume that is defined by the images in objective space of these solutions and a given reference point.
In this paper, we propose a new point-wise iterative search procedure, Hypervolume Directed Search (HVDS), that aims to increase the hypervolume of a given point in an archive for bi-objective unconstrained optimization problems. We present the HVDS both as a standalone algorithm and as a local searcher within a specialized evolutionary algorithm. Numerical results confirm the strength of the novel approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Beume, N.: S-metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation 17(4), 477–492 (2009)
Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research (2006)
Brown, M., Smith, R.E.: Directed multi-objective optimisation. International Journal of Computers, Systems and Signals 6(1), 3–17 (2005)
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, Chichester (2001) ISBN 0-471-87339-X
Emmerich, M.T.M., Deutz, A.H., Kruisselbrink, J.W.: On quality indicators for black-box level set approximation. In: Tantar, E., Tantar, A.-A., Bouvry, P., Del Moral, P., Legrand, P., Coello Coello, C.A., Schütze, O. (eds.) EVOLVE- A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation. SCI, vol. 447, pp. 153–184. Springer, Heidelberg (2013)
Griewank, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. Frontiers in Appl. Math., vol. 19. SIAM, Philadelphia (2000)
Hillermeier, C.: Nonlinear Multiobjective Optimization: A Generalized Homotopy Approach. Springer (2001) ISBN-13:9783764364984
Jaszkiewicz, A., Ishibuchi, H., Zhang, Q.: Multiobjective memetic algorithms. In: Neri, F. (ed.) Handbook of Memetic Algorithms. SCI, vol. 379, pp. 201–217. Springer, Heidelberg (2011)
Lara, A., Alvarado, S., Salomon, S., Avigad, G., Coello Coello, C.A., Schütze, O.: The gradient free directed search method as local search within multi-objective evolutionary algorithms. In: Schütze, O., Coello Coello, C.A., Tantar, A.-A., Tantar, E., Bouvry, P., Del Moral, P., Legrand, P. (eds.) EVOLVE - A Bridge Between Probability, Set Oriented Numerics, and Evolutionary Computation II. AISC, vol. 175, pp. 153–168. Springer, Heidelberg (2012)
Lara, A., Coello Coello, C.A., Schütze, O.: A painless gradient-assisted multi-objective memetic mechanism for solving continuous bi-objective optimization problems. In: 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE, IEEE Press (2010)
Mejia, E., Schütze, O.: A predictor corrector method for the computation of boundary points of a multi-objective optimization problem. In: International Conference on Electrical Engineering, Computing Science and Automati Control (CCE 2010), pp. 1–6 (2007)
Schäffler, S., Schultz, R., Weinzierl, K.: A stochastic method for the solution of unconstrained vector optimization problems. Journal of Optimization Theory and Applications 114(1), 209–222 (2002)
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., Lara, A., Coello Coello, C.A.: The directed search method for unconstrained multi-objective optimization problems. Technical Report TR-OS-2010-01 (2010)
Schütze, O., Lara, A., Coello Coello, C.A.: The directed search method for unconstrained multi-objective optimization problems. In: Proceedings of the EVOLVE – A Bridge Between Probability, Set Oriented Numerics, and Evolutionary Computation (2011)
Schütze, O., Lara, A., Coello Coello, C.A.: On the influence of the number of objectives on the hardness of a multiobjective optimization problem. IEEE Transactions on Evolutionary Computation 15(4), 444–455 (2011)
Trautmann, H., Rudolph, G., Dominguez-Medina, C., Schütze, O.: Finding evenly spaced Pareto fronts for three-objective optimization problems. In: Schütze, O., Coello Coello, C.A., Tantar, A.-A., Tantar, E., Bouvry, P., Del Moral, P., Legrand, P. (eds.) EVOLVE - A Bridge Between Probability, Set Oriented Numerics, and Evolutionary Computation II. AISC, vol. 175, pp. 89–105. Springer, Heidelberg (2012)
Witting, K.: Numerical Algorithms for the Treatment of Parametric Optimization Problems and Applications. PhD thesis, University of Paderborn (2012)
Zitzler, E., Deb, K., Thiele, L.: Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evol. Comput. 8(2), 173–195 (2000)
Zitzler, E., Thiele, L.: Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg (1998)
Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation 3(4), 257–271 (1999)
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
Sosa Hernández, V.A., Schütze, O., Rudolph, G., Trautmann, H. (2013). The Directed Search Method for Pareto Front Approximations with Maximum Dominated Hypervolume. 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_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-01128-8_13
Publisher Name: Springer, Heidelberg
Print ISBN: 978-3-319-01127-1
Online ISBN: 978-3-319-01128-8
eBook Packages: EngineeringEngineering (R0)