Optimizing Niche Center for Multimodal Optimization Problems

Yi Jiang, Zhi‐Hui Zhan, Kay Chen Tan, Jun Zhang

Abstract

Many real-world optimization problems require searching for multiple optimal solutions simultaneously, which are called multimodal optimization problems (MMOPs). For MMOPs, the algorithm is required both to enlarge population diversity for locating more global optima and to enhance refine ability for increasing the accuracy of the obtained solutions. Thus, numerous niching techniques have been proposed to divide the population into different niches, and each niche is responsible for searching on one or more peaks. However, it is often a challenge to distinguish proper individuals as niche centers in existing niching approaches, which has become a key issue for efficiently solving MMOPs. In this article, the niche center distinguish (NCD) problem is treated as an optimization problem and an NCD-based differential evolution (NCD-DE) algorithm is proposed. In NCD-DE, the niches are formed by using an internal genetic algorithm (GA) to online solve the NCD optimization problem. In the internal GA, a fitness-entropy measurement objective function is designed to evaluate whether a group of niche centers (i.e., encoded by a chromosome in the internal GA) is promising. Moreover, to enhance the exploration and exploitation abilities of NCD-DE in solving the MMOPs, a niching and global cooperative mutation strategy that uses both niche and population information is proposed to generate new individuals. The proposed NCD-DE is compared with some state-of-the-art and recent well-performing algorithms. The experimental results show that NCD-DE achieves better or competitive performance on both the accuracy and completeness of the solutions than the compared algorithms.

Introduction

In many real-world scenarios—from protein structure prediction to machine learning—finding a single global optimum is often insufficient. Instead, practitioners require all high-quality solutions to provide alternatives or deeper insights into the problem landscape. These are known as Multimodal Optimization Problems (MMOPs).

To address MMOPs, researchers employ "niching" techniques to divide the population into subgroups, each targeting a different peak. However, traditional niching methods often struggle with the "Goldilocks" problem: determining the optimal number and location of niche centers. Static parameters like a fixed niche radius often fail to adapt as the population evolves. Poorly chosen centers lead to missed peaks or redundant exploration.

Methodology

The proposed NCD-DE (Niche Center Distinguish-based Differential Evolution) algorithm addresses these challenges by treating niche selection as a secondary optimization problem, solved "online" during the main evolutionary process.

NCD as an Optimization Problem

The task of identifying niche centers is transformed into a binary optimization problem. For a population of size $NP$, a binary vector of length $NP$ represents which individuals serve as niche centers. As shown in Figure 1, individuals positioned near peaks (like B and C) are encoded as '1', while others (like A and D) are encoded as '0'.

Encoding niche centers as a binary optimization problem.

Internal Genetic Algorithm (GA)

To solve this binary problem, an "internal GA" is embedded within the main DE loop. This internal GA runs every generation to identify the most promising set of niche centers based on the current population state. A key advantage is that the internal GA uses fitness values already calculated by the main DE, meaning it requires no extra "expensive" function evaluations.

Fitness-Entropy Measurement (FEM)

The internal GA uses a novel Fitness-Entropy Measurement (FEM) objective function. This function balances two critical factors:

  • Quality: Centers should possess high fitness values.
  • Diversity (Entropy): Centers should be well-distributed across the search space. By using an entropy-based metric rather than simple Euclidean distance, the algorithm ensures better coverage and avoids redundant niches.

Overall Framework

The NCD-DE framework integrates the internal GA with a main DE loop. A "Niching and Global Cooperative Mutation" (NGCM) strategy utilizes niche-level information for exploitation and global information for exploration. An archive technique is also employed to preserve found optima during the search process.

Flowchart of the NCD-DE algorithm framework.

Experimental Results

The NCD-DE algorithm was rigorously evaluated on the CEC2013 benchmark suite and a real-world Multiple Competitive Facilities Location and Design (MCFLD) problem.

Key Findings

  • Performance: NCD-DE consistently outperformed 13 state-of-the-art algorithms in terms of Peak Ratio (finding more optima) and Success Rate.
  • Stability: The algorithm maintained high performance even as the required solution accuracy ($\epsilon$) was tightened from $10^{-3}$ to $10^{-5}$.
  • Real-World Application: In the MCFLD problem, NCD-DE successfully identified over 60 global optima, significantly surpassing competing algorithms like CDE and NCDE, which found fewer than 5.

Conclusion

NCD-DE introduces a robust meta-optimization approach to niching. By dynamically optimizing niche centers using an internal GA and an entropy-based fitness metric, it effectively balances exploration and exploitation in complex multimodal landscapes. Future work will explore alternative internal solvers and the scalability of this approach to high-dimensional problems.

Summary updated

Abstract

Many real-world optimization problems require searching for multiple optimal solutions simultaneously, which are called multimodal optimization problems (MMOPs). For MMOPs, the algorithm is required both to enlarge population diversity for locating more global optima and to enhance refine ability for increasing the accuracy of the obtained solutions. Thus, numerous niching techniques have been proposed to divide the population into different niches, and each niche is responsible for searching on one or more peaks. However, it is often a challenge to distinguish proper individuals as niche centers in existing niching approaches, which has become a key issue for efficiently solving MMOPs. In this article, the niche center distinguish (NCD) problem is treated as an optimization problem and an NCD-based differential evolution (NCD-DE) algorithm is proposed. In NCD-DE, the niches are formed by using an internal genetic algorithm (GA) to online solve the NCD optimization problem. In the internal GA, a fitness-entropy measurement objective function is designed to evaluate whether a group of niche centers (i.e., encoded by a chromosome in the internal GA) is promising. Moreover, to enhance the exploration and exploitation abilities of NCD-DE in solving the MMOPs, a niching and global cooperative mutation strategy that uses both niche and population information is proposed to generate new individuals. The proposed NCD-DE is compared with some state-of-the-art and recent well-performing algorithms. The experimental results show that NCD-DE achieves better or competitive performance on both the accuracy and completeness of the solutions than the compared algorithms.
BibTeX
@article{jiang2021optimizing,
  author = {Yi Jiang and Zhi‐Hui Zhan and Kay Chen Tan and Jun Zhang},
  title = {{Optimizing Niche Center for Multimodal Optimization Problems}},
  journal = {IEEE Transactions on Cybernetics},
  year = {2021},
  doi = {10.1109/tcyb.2021.3125362},
}
Figure