  This paper investigates the performance of multistart next ascent
hillclimbing and well-known evolutionary algorithms incorporating diversity
preservation techniques on instances of the multimodal problem generator. This
generator induces a class of problems in the bitstringdomain which is
interesting to study from a theoretical perspective in the context of
multimodal optimization, as it is a generalization of the classical OneMax and
TwoMax functions for an arbitrary number of peaks. An average-case runtime
analysis for multistart next ascent hill-climbing is presented for uniformly
distributed equal-height instances of this class of problems. It is shown
empirically that conventional niching and mating restriction techniques
incorporated in an evolutionary algorithm are not sufficient to make them
competitive with the hillclimbing strategy. We conjecture the reason for this
behaviour is the lack of structure in the space of local optima on instances of
this problem class, which makes an optimization algorithm unable to exploit
information from one optimum to infer where another optimum might be. When no
such structure exist, it seems that the best strategy for discovering all
optima is a brute-force one. Overall, our study gives insights with respect to
the adequacy of hillclimbers and evolutionary algorithms for multimodal
optimization, depending on properties of the fitness landscape.
