  Recently a mechanism called stagnation detection was proposed that
automatically adjusts the mutation rate of evolutionary algorithms when they
encounter local optima. The so-called $SD-(1+1)EA$ introduced by Rajabi and
Witt (GECCO 2020) adds stagnation detection to the classical $(1+1)EA$ with
standard bit mutation, which flips each bit independently with some mutation
rate, and raises the mutation rate when the algorithm is likely to have
encountered local optima.
  In this paper, we investigate stagnation detection in the context of the
$k$-bit flip operator of randomized local search that flips $k$ bits chosen
uniformly at random and let stagnation detection adjust the parameter $k$. We
obtain improved runtime results compared to the $SD-(1+1)EA$ amounting to a
speed-up of up to $e=2.71\dots$ Moreover, we propose additional schemes that
prevent infinite optimization times even if the algorithm misses a working
choice of $k$ due to unlucky events. Finally, we present an example where
standard bit mutation still outperforms the local $k$-bit flip with stagnation
detection.
