Abstract
We consider methods for noisy multiobjective optimization, specifically methods for approximating a true underlying Pareto front when function evaluations are corrupted by Gaussian measurement noise on the objective function values. We focus on the scenario of a limited budget of function evaluations (100 and 250), where previously it was found that an iterative optimization method — ParEGO — based on surrogate modeling of the multiobjective fitness landscape was very effective in the non-noisy case. Our investigation here measures how ParEGO degrades with increasing noise levels. Meanwhile we introduce a new method that we propose for limited-budget and noisy scenarios: TOMO, deriving from the single-objective PB1 algorithm, which iteratively seeks the basins of optima using nonparametric statistical testing over previously visited points. We find ParEGO tends to outperform TOMO, and both (but especially ParEGO), are quite robust to noise. TOMO is comparable and perhaps edges ParEGO in the case of budgets of 100 evaluations with low noise. Both usually beat our suite of five baseline comparisons.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Pareto Front
- Multiobjective Optimization
- Random Search
- Multiobjective Optimization Problem
- Multiobjective Evolutionary Algorithm
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Anderson, B., Moore, A., Cohn, D.: A nonparametric approach to noisy and costly optimization. In: Langley, P. (ed.) Proc. 17th ICML, pp. 17–24. Morgan Kaufmann, San Francisco (2000)
Beyer, H.-G.: Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practice. Computer Methods in Applied Mechanics and Engineering 186(2-4), 239–267 (2000)
Beyer, H.-G., Sendhoff, B.: Robust optimization: A comprehensive survey. Computer Methods in Applied Mechanics and Engineering 196(33-34), 3190–3218 (2007)
Chen, J.-J., Goldberg, D.E., Ho, S.-Y., Sastry, K.: Fitness inheritance in multi-objective optimization. In: Proc. GECCO 2002, pp. 319–326. Morgan Kaufmann, San Francisco (2002)
Corne, D., Jerram, N., Knowles, J., Oates, M.: PESA-II: Region-based selection in evolutionary multiobjective optimization. In: GECCO 2001, pp. 283–290. Morgan Kaufmann, San Francisco (2001)
Davies, Z.S., Gilbert, R.J., Merry, R.J., Kell, D.B., Theodorou, M.K., Griffith, G.W.: Efficient improvement of silage additives by using genetic algorithms. In: Applied and Environmental Microbiology, pp. 1435–1443 (2000)
Deb, K., Goldberg, D.: An Investigation of Niche and Species Formation in Genetic Function Optimization. In: Proc. 3rd International Conference on Genetic Algorithms, pp. 42–50. Morgan Kaufmann, San Francisco (1989)
Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable Test Problems for Evolutionary Multi-Objective Optimization. Technical Report 112, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (2001)
Ducheyne, E.I., De Baets, B., De Wulf, R.: Is fitness inheritance useful for real-world applications? In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 31–42. Springer, Heidelberg (2003)
Dunn, E., Olague, G.: Multi-objective Sensor Planning for Efficient and Accurate Object Reconstruction. In: Raidl, G.R., Cagnoni, S., Branke, J., Corne, D.W., Drechsler, R., Jin, Y., Johnson, C.G., Machado, P., Marchiori, E., Rothlauf, F., Smith, G.D., Squillero, G. (eds.) EvoWorkshops 2004. LNCS, vol. 3005, pp. 312–321. Springer, Heidelberg (2004)
Emmerich, M., Naujoks, B.: Metamodel Assisted Multiobjective Optimisation Strategies and their Application in Airfoil Design. In: Parmee, I. (ed.) Adaptive Computing in Design and Manufacture VI, pp. 249–260. Springer, Heidelberg (2004)
Evans, J.R.G., Edirisinghe, M.J., Eames, P.V.C.J.: Combinatorial searches of inorganic materials using the inkjet printer: science philosophy and technology. Journal of the European Ceramic Society 21, 2291–2299 (2001)
Gaspar-Cunha, A., Vieira, A.S.: A hybrid multi-objective evolutionary algorithm using an inverse neural network. In: Hybrid Metaheuristics (HM 2004) Workshop at ECAI 2004, pp. 25–30 (2004), http://iridia.ulb.ac.be/~hm2004/proceedings/
Hornby, G.S., Takamura, S., Yamamoto, T., Fujita, M.: Autonomous evolution of dynamic gaits with two quadruped robots. IEEE Transactions on Robots 21(3), 402–410 (2005)
Huang, D., Allen, T.T., Notz, W.I., Zeng, N.: Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models. Journal of Global Optimization 34(3), 441–466 (2006)
Jeong, S., Minemura, Y., Obayashi, S.: Optimisation of combustion chamber for diesel engine using kriging model. Journal of Fluid Science and Technology 1(2), 138–146 (2006)
Jeong, S., Suzuki, K., Obayashi, S., Kirita, M.: Improvement of nonlinear lateral characteristics of lifting-body type reentry vehicle using optimization algorithm. In: Proc. of AIAA Infotech-Aerospace Conference 2007, pp. 1–15. AIAA (2007)
Jin, Y.: A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing-A Fusion of Foundations, Methodologies and Applications 9(1), 3–12 (2005)
Jones, D., Schonlau, M., Welch, W.: Efficient global optimization of expensive black-box functions. Journal of Global Optimization 13, 455–492 (1998)
Knowles, J., Corne, D.: On metrics for comparing nondominated sets. In: Congress on Evolutionary Computation (CEC 2002), Piscataway, New Jersey, vol. 1, pp. 711–716. IEEE Service Center, Los Alamitos (2002)
Knowles, J., Hughes, E.J.: Multiobjective Optimization on a Budget of 250 Evaluations. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) EMO 2005. LNCS, vol. 3410, pp. 176–190. Springer, Heidelberg (2005)
Knowles, J.: ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans. Evol. Comp. 10(1), 50–66 (2006)
Knowles, J., Nakayama, H.: Meta-Modeling in Multiobjective Optimization. In: Branke, D., Deb, K., Miettinen, S., Słowiński, R. (eds.) Multiobjective Optimization: Interactive and Evolutionary Approaches. LNCS, vol. 5252. Springer, Heidelberg (2008)
Laumanns, M., Ocenasek, J.: Bayesian optimization algorithms for multi-objective optimization. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 298–307. Springer, Heidelberg (2002)
Miettinen, K.M.: Nonlinear Multiobjective Optimization. Kluwer, Dordrecht (1999)
Nain, P.K.S., Deb, K.: A computationally effective multi-objective search and optimization technique using coarse-to-fine grain modeling. Technical Report Kangal Report No. 2002005, IITK, Kanpur, India (2002)
Nakayama, H., Yun, Y.: Multi-objective Model Predictive Optimization using Computational Intelligence. In: Artificial Intelligence in Theory and Practice II, pp. 319–328. Springer, Heidelberg (2008)
O’Hagan, S., Dunn, W., Knowles, J., Broadhurst, D., Williams, R., Ashworth, J., Cameron, M., Kell, D.: Closed-loop, multiobjective optimization of two-dimensional gas chromatography/mass spectrometry for serum metabolomics. Analytical Chemistry 79(2), 464–476 (2007)
Okabe, T., Jin, Y., Olhofer, M., Sendhoff, B.: On Test Functions for Evolutionary Multi-objective Optimization. In: Parallel Problem Solving from Nature - PPSN VIII, pp. 792–802. Springer, Heidelberg (2004)
Ong, Y.S., Nair, P.B., Keane, A.J., Zhou, Z.Z.: Surrogate-assisted evolutionary optimization frameworks for high-fidelity engineering design problems. In: Jin, Y. (ed.) Knowledge Incorporation in Evolutionary Computation. Springer, Heidelberg (2004)
Press, W., Teukolsky, S., Vetterling, W., Flannery, B.: Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, Cambridge (1992)
Sacks, J., Welch, W., Mitchell, T., Wynn, H.: Design and analysis of computer experiments (with discussion). Statistical Science 4, 409–435 (1989)
Bosman, P.A.N., Thierens, D.: Multi-objective Optimization with the Naive MIDEA. Studies in Fuzziness and Soft Computing 192, 123–157 (2006)
van Veldhuizen, D.A., Lamont, G.B.: Multiobjective Evolutionary Algorithm Test Suites. In: Proc. 1999 ACM Symposium on Applied Computing, pp. 351–357. ACM, New York (1999)
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation 7(2), 117–132 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Knowles, J., Corne, D., Reynolds, A. (2009). Noisy Multiobjective Optimization on a Budget of 250 Evaluations. In: Ehrgott, M., Fonseca, C.M., Gandibleux, X., Hao, JK., Sevaux, M. (eds) Evolutionary Multi-Criterion Optimization. EMO 2009. Lecture Notes in Computer Science, vol 5467. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01020-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-01020-0_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01019-4
Online ISBN: 978-3-642-01020-0
eBook Packages: Computer ScienceComputer Science (R0)