# Niching-Driven Divide-and-Conquer Hill Exploration
## 1 Introduction  
Many optimization problems have a large number of local optima. To locate the desired optima--normally the global ones--a variety of evolutionary computation (EC) methods have been proposed. Due to their mechanisms for initializing and updating the population, EC methods are considered to be able to search around a wide range of optima in the early stage and concentrate on the promising ones in the latter stage. The mechanisms for updating the population, which are usually termed survivor selection mechanisms, help the EC methods save fitness evaluations in areas around those local optima with poor fitness values. However, if an EC method identifies a desired optimum as a poor local one early on, it may struggle to revisit it later. This scenario happens a lot when the basin of attraction (BoA) of an optimum differs greatly from theBoA of another optimum, which leads to a significant difference between these two BoAs in the probability of finding good individuals [1]. A mainstream idea for addressing the above issue is to change the mode of survivor selection from _global competition_ to _restricted competition_. In _global competition_, an individual can be replaced with any individual that is better than it. In _restricted competition_, an individual can only be replaced by a better individual that is in its neighborhood. As EC methods with _restricted competition_ are more commonly known as niching methods in the field of multimodal optimization, the techniques they used for implementing _restricted competition_ are termed niching techniques in this paper. Existing niching techniques can be classified into five categories according to their ways to form the neighborhood, namely the _radial repulsion_[2; 3; 4; 5; 6; 7], _k-nearest neighbors_[8; 9; 10; 11; 12], _clustering with a specified number of groups_[13; 14; 12], _clustering with an adaptive number of groups_[15; 16; 17; 18; 19; 20; 21], and _valley detection_[22; 23; 24; 25]. Each category of niching technique has one or more key parameters to adjust the range of neighborhoods for restricted competition, allowing them to address the increasing challenge as the differences between BoAs increase. However, it can be observed through both mechanistic analysis (refer to Section 2) and experimental validation (refer to Section 4) that the number of evaluations used to locate optima with varying degrees of attractiveness is quite imbalanced. Specifically, the numbers of evaluations within the BoAs of different optima are always proportional to their attractiveness. If this imbalance remains unaddressed, the limitations of niching techniques will become more pronounced as the disparity in attractiveness between optima increases: either it becomes increasingly difficult to set effective parameters, or an unsustainable number of evaluations are wasted on optima with greater attractiveness. To address this imbalance issue, we believe it is necessary to learn the explicit boundaries of the BoAs of optima online during the evolutionary process. To verify this point, we propose a hierarchical divide-and-conquer framework, which can be integrated with existing niching methods. The framework is named niching-driven divide-and-conquer hill exploration (NDDCHE). Its main idea is that a problem with a large number of optima to find can be hierarchically divided into a series of subproblems with a much smaller number of optima to locate. An intuitive illustration is shown in Figure 1. The contour lines depict the fitness landscape of a two-dimensional optimization problem with five optima, which are denoted by white crosses. Although there are significant differences in the size of BoA between the five optima, it is not hard to find the two optima with the largest two BoAs. If these two prominent BoAs can be told apart, the problem can be divided into two subproblems, whose search spaces are the largest BoA and the remaining four BoAs, respectively.