Theoretische Analyse der Robustheit stochastischer Optimierungsprozesse

• Applicant: Professorin Dr. Beate Bollig, since 2/2010
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 15253112

• Final Report Year: 2011

Final Report Abstract

Randomisierte Suchheuristiken haben sich vielfach in praktischen Anwendungen als robuste Optimierer bewährt. Das DFG-Projekt "Theoretische Analyse der Robustheit stochastischer Optimierungsprozesse“ hat verschiedenen Aspekte der Robustheit solcher Heuristiken vom theoretischen Standpunkt aus beleuchtet. Für das Cliquenproblem wurden unter anderem das Laufzeitverhalten einfacher Suchheuristiken für verschiedene semizufällige Eingabemodelle betrachtet. Dabei konnte erstmals die wesentliche Steigerung der Effizienz einer einfachen randomisierten Suchheuristik durch den Einsatz einer großen Elternpopulation bewiesen werden. Für das Cliquenproblem auf planaren Graphen hat sich mittels der Betrachtungen der Black-Box-Komplexität des Problems ein Metropolis-Algorithmus als optimale Suchheuristik für verschiedene Eingabemodelle erwiesen. Die Betrachtungen von Transformationen der Zielfunktion haben zu einer Charakterisierung randomisierter Suchheuristiken und ihrer Komponenten geführt. Dies demonstriert die unterschiedlichen Grade der Robustheit von stochastischen Optimierungsprozessen gegenüber Änderungen der Parameter des Problems. Darüberhinaus wurden Auswirkungen von Änderungen der Algorithmenparameter randomisierter Suchheuristiken analysiert. Zum einen konnte trotz wesentlich verschiedener globaler Strategien zweier Suchheuristiken nachgewiesen werden, dass diese beim Überwinden von Hindernissen in der Fitnesslandschaft ein sehr ähnliches Verhalten zeigen. Zum anderen konnte für zwei sehr ähnliche Suchheuristiken der wechselseitige Einfluss der Nachkommenpopulationsgröße und des Selektionsoperators illustriert werden. Ergebnis des Projekts ist auch eine Erweiterung der bestehenden Beweistechniken.

Publications

• (2006). A rigorous analysis of the compact genetic algorithm for linear functions. Natural Computing 5(3):257–283
  S. Droste
  
• (2006). How comma selection helps with the escape from local optima. In: International Conference on Parallel Problem Solving From Nature IX – PPSN, 52–61
  J. Jägersküpper und T. Storch
  
• (2006). How randomized search heuristics find maximum cliques in planar graphs. In: Genetic and Evolutionary Computation Conference – GECCO, 567–574
  T. Storch
  
• (2006). On the impact of objective function transformations on evolutionary and black-box algorithms. Genetic Programming and Evolvable Machines 7(2):171–193
  T. Storch
  
• (2006). The local performance of simulated annealing and the (1+1) evolutionary algorithm. In: Genetic and Evolutionary Computation Conference – GECCO, 469–475
  T. Jansen und I. Wegener
  
• (2007). Design und Analyse randomisierter Suchheuristiken – Populationen und Cliquen. Dissertation, Universität Dortmund
  T. Storch
  
• (2007). Faster evolutionary algorithms by superior graph representation. In: Proceedings of the IEEE Symposium on Foundations of Computational Intelligence – FOCI, 245–250
  B. Doerr, C. Klein und T. Storch
  
• (2007). Finding large cliques in sparse semi-random graphs by simple randomized search heuristics. Theoretical Computer Science 386(1-2): 114–131
  T. Storch
  
• (2007). When the plus strategy outperforms the comma strategy – and when not. In: Proceedings of the IEEE Symposium on Foundations of Computational Intelligence – FOCI, 25–32
  J. Jägersküpper und T. Storch
  
• (2010). Information Complexity and Data Stream Algorithms for Basic Problems. Dissertation, Technische Universität Dortmund
  A. Gronemeier