Abstract
Many real-world optimization problems involve uncertainty. In this paper, we consider the case of worst-case optimization, i.e., the user is interested in a solution’s performance in the worst case only. If the number of possible scenarios is large, it is an optimization problem by itself to determine a solution’s worst case performance. In this paper, we apply coevolutionary algorithms to co-evolve the worst case test cases along with the solution candidates. We propose a number of new variants of coevolutionary algorithms, and show that these techniques outperform previously proposed coevolutionary worst-case optimizers on some simple test problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
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
Avigad, G., Branke, J.: Worst-case robustness and related decision support. In: Genetic and Evolutionary Computation Conference, ACM Press, New York (to appear)
Barbosa, H.J.C.: A coevolutionary genetic algorithm for constrained optimization. In: Congress on Evolutionary Computation, vol. 3, pp. 1605–1611 (1999)
Branke, J.: Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers, Norwell (2001)
Daum, D.A., Deb, K., Branke, J.: Reliability-based optimization for multiple constraints with evolutionary algorithms. In: Congress on Evolutionary Computation, pp. 911–918. IEEE Computer Society Press, Los Alamitos (2007)
de Jong, E.: The maxsolve algorithm for coevolution. In: Conference on Genetic and Evolutionary Computation, pp. 483–489. ACM Press, New York (2005)
Herrmann, J.W.: A genetic algorithm for minimax optimization problems. In: Congress on Evolutionary Computation, vol. 2, pp. 1099–1103. IEEE Computer Society Press, Los Alamitos (1999)
Hillis, D.W.: Co-evolving parasites improve simulated evolution in an optimization procedure. Physica D 42, 228–234 (1990)
Jensen, M.T.: Finding worst-case flexible schedules using coevolution. In: Spector, L., et al. (eds.) Genetic and Evolutionary Computation Conference, pp. 1144–1151. Morgan Kaufmann, San Francisco (2001)
Jensen, M.T.: A new look at solving minimax problems with coevolutionary genetic algorithms. Applied Optimization 86, 369–384 (2004)
Korn, R., Steffensen, M.: On worst-case portfolio optimization. SIAM Journal on Control and Optimization 46(6), 2013–2030 (2007)
Luke, S., Wiegand, R.P.: When coevolutionary algorithms exhibit evolutionary dynamics. In: Barry, A.M. (ed.) GECCO 2002: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, pp. 236–241. AAAI Press, Menlo Park (2002)
Ong, Y.-S., Nair, P.B., Lum, K.Y.: Max-min surrogate-assisted evolutionary algorithm for robust design. IEEE Transactions on Evolutionary Computation 10(4), 392–404 (2006)
Pagie, L., Hogeweg, P.: Information integration and red queen dynamics in coevolutionary optimization. In: Proceedings of the 2000 Congress on Evolutionary Computation, vol. 2, pp. 1260–1267 (2000)
Paredis, J.: Coevolutionary computation. Artificial Life 2(4), 355–375 (1995)
Sebald, A.V., Schlenzig, J.: Minimax design of neural net controllers for highly uncertain plants. IEEE Transactions on Neural Networks 5(1), 73–82 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Branke, J., Rosenbusch, J. (2008). New Approaches to Coevolutionary Worst-Case Optimization. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds) Parallel Problem Solving from Nature – PPSN X. PPSN 2008. Lecture Notes in Computer Science, vol 5199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87700-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-87700-4_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87699-1
Online ISBN: 978-3-540-87700-4
eBook Packages: Computer ScienceComputer Science (R0)