Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, December 03, 2024, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Johannes Lengler

The complex parameter landscape of Estimation of Distribution Algorithms

Estimation-of-distribution algorithms (EDAs) are optimization algorithms which maintain a probability distribution over the search space: their belief of where good solutions are. In each round, they sample from the distribution and update it based on the fitness of the samples. There has been a lot of theoretical work on EDAs in recent years.

In this talk, I will present two results on such an algorithm, the compact Genetic Algorithm cGA. This algorithm operates on the hypercube, and its distribution is a product measure, i.e., it treats all bits independently. In every round it samples two search points, and updates the marginal probability of each bit towards the fitter of the two search points.

This simple algorithm shows a surprisingly complex performance landscape even on the simple OneMax function. There are two optimal parameter setting for the step size 1/K of updates: K=\Theta(\log n) and K = \Theta(\sqrt{n}\log n). Both lead to runtimes \Theta(n\log n), and all other parameter choices (larger, smaller, or in between) give asymptotically worse runtimes. Understanding the reason for this multimodal runtime behaviour leads to two different algorithmic paradigms, an aggressive and a conservative one. In recent work, we have shown that for other linear functions the aggressive regime can still find the optimum in time \tilde O(n), while the conservative is substantially slowed down to \Omega(n^2).

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login