# Niching-Driven Divide-and-Conquer Hill Exploration
## 3 Methodology  
To provide a more intuitive approach to balance search resources among the optima of varying attractiveness, thus efficiently allocating adequate search resources to the neighborhoods of optima with lesser attractiveness, a hierarchical divide-and-conquer framework for niching method is proposed in this paper. The framework is named niching-driven divide-and-conquer hill exploration and abbreviated as NDDCHE. The general process of NDDCHE is described in Algorithm 1. A set of seed solutions \(\mathbf{U}\) is maintained, which stores the best solutions found in different BoAs. The search space is divided into a set of hill regions \(\mathbb{H}\), which are the online learning estimation of BoAs. \(\mathbb{H}\) initially consists of a single hill region, which is equal to the entire search space. The process of NDDCHE consists of repeated cycles. In each cycle, a hill region \(\mathbf{H}\) is randomly selected, and a niching method is started from \(\mathbf{H}\), which means that its population is initialized inside \(\mathbf{H}\). Once the population become stagnant, seed solutions will be updated according to the population. After that, the hill regions will be updated to make each seed solution have its own hill region, and the next cycle comes. ```
Input: search space \(\mathbb{X}\)
1 Initialize the sets of seeds \(\mathbf{U}\leftarrow\emptyset\) and hills \(\mathbb{H}\leftarrow\{\mathbb{X}\}\);
2 whiletermination conditions are not reacheddo
3\(\mathbf{H}\leftarrow\) Randomly select a hill from \(\mathbb{H}\);
4\(\mathbf{P}\leftarrow\) Initialize a population in \(\mathbf{H}\);
5 whileP is not stagnant and termination conditions are not reacheddo
6\(\mathbf{P}\leftarrow\) evolve(\(\mathbf{P}\));
7
8 end while
9 iftermination conditions are not reachedthen
10\(\mathbf{U}\leftarrow\) updateSeeds(\(\mathbf{U},\mathbf{P},\mathbb{H}\));
11\(\mathbb{H}\leftarrow\) updateHills(\(\mathbb{H},\mathbf{U}\));
12
13 end if
14
15 end while
```  
**Algorithm 1**NDDCHE. The process of updating seed solutions is shown in Algorithm 2. First, some potential seed solutions, which are termed candidate solutions \(\mathbf{C}\), are selected from the population. Then, for each candidate solution \(\mathbf{c}\), it will be checked against existing seed solutions that are located in the same hill region as \(\mathbf{c}\). If \(\mathbf{c}\) is better than an existing seed solution located in the same BoA as \(\mathbf{c}\), the seed solution is replaced with \(\mathbf{c}\). If \(\mathbf{c}\) does not share the same BoA with any of the seed solutions, it will be added into the set of seed solutions. ```
Input: seed solutions \(\mathbf{U}\), population \(\mathbf{P}\), hills \(\mathbb{H}\) Output: seed solutions \(\mathbf{U}\)
1\(\mathbf{C}\leftarrow\text{identityCandidates}(\mathbf{P})\);
2 foreach\(\mathbf{c}\in\mathbf{C}\)do
3\(\mathbf{H}\leftarrow\mathbf{H}^{\prime}\in\mathbb{H}\ |\ \mathbf{c}\in\mathbf{H}^{\prime}\);
4\(distinct\gets true\);
5 foreach\(\mathbf{u}\in\mathbf{U}\cap\mathbf{H}\)do
6 if\(\text{sameBoA}(\mathbf{c},\mathbf{u})\)then
7 if\(\mathbf{c}\) is better than \(\mathbf{u}\)then\(\mathbf{u}\leftarrow\mathbf{c}\);
8\(distinct\gets false\);
9 break



\[\text{B}(\mathbf{x},\mathbf{X})=\{\mathbf{x}^{\prime}\in\mathbf{X}\mid\mathbf{x}^{\prime}\text{ is better than }\mathbf{x}\},\ \ \mathbf{x}\in\mathbf{X} \tag{1}\]

\[\text{NB}(\mathbf{x},\mathbf{X})=\operatorname*{arg\,min}_{\mathbf{x}^{\prime}\in\text{B}( \mathbf{x},\mathbf{X})}\|\mathbf{x}^{\prime}-\mathbf{x}\|,\ \ \mathbf{x}\in\mathbf{X}\wedge\text{B}(\mathbf{x},\mathbf{X})\
eq\emptyset \tag{2}\]

\[\text{NBD}(\mathbf{x},\mathbf{X})=\min_{\mathbf{x}^{\prime}\in\text{B}(\mathbf{x},\mathbf{X})}\| \mathbf{x}^{\prime}-\mathbf{x}\|,\ \ \mathbf{x}\in\mathbf{X}\wedge\text{B}(\mathbf{x},\mathbf{X})\
eq\emptyset \tag{3}\]

An intuitive flow of the above processes can be illustrated in Figure 2. First, a hill region is selected and the population is initialized inside the hill region. Different hill regions are denoted by rectangles of different colors.