AMOBH: Adaptive Multiobjective Black Hole Algorithm

Chong Wu, Tao Wu, Kaiyuan Fu, Yuan Zhu, Yongbo Li, Wangyong He, Shengwen TangComput. Intell. Neurosci 2017 · DOI

TL;DR

This paper introduces AMOBH, an adaptive multiobjective black hole algorithm designed to tackle complex optimization problems with multiple conflicting objectives. By incorporating a novel "cell density" metric for diversity assessment and an adaptive strategy based on Shannon entropy, AMOBH demonstrates improved performance in balancing convergence and diversity compared to existing state-of-the-art algorithms.

What Problem Does This Paper Address?

Many real-world problems, from engineering design to path planning, involve optimizing multiple objectives simultaneously. These objectives are often conflicting, meaning improving one can worsen another. This leads to a set of optimal solutions known as the Pareto front. Traditional methods for handling these multiobjective optimization problems (MOPs) often struggle with either finding a diverse set of solutions or converging efficiently to the Pareto front. Specifically, existing evolutionary algorithms face challenges in maintaining a good balance between convergence (finding optimal solutions) and diversity (spreading solutions across the Pareto front), and can be prone to premature convergence or high computational costs.

Methods

The core of AMOBH is an adaptation of the Black Hole (BH) algorithm, originally designed for single-objective optimization. The key innovations include:

  • Adaptive Multiobjective Black Hole Algorithm (AMOBH): This is the main proposed algorithm.
  • Cell Density: A new metric to assess the density of solutions within a "parallel cell coordinate system" (PCCS). This system maps the approximate Pareto front to a 2D grid, allowing for efficient density estimation. Cell density aims to balance convergence and diversity with low computational complexity.
  • Shannon Entropy: Used to dynamically estimate the algorithm's evolutionary status (convergence, diversity, or stagnation). This information is then used to adapt the algorithm's strategies.
  • Cell Dominance: A fitness evaluation method that combines cell density with a dominance strength assessment.
  • Adaptive Global Optimum Selection: The algorithm selects a dynamic set of "global optimum solutions" (black holes) based on the evolutionary status, aiming to balance selection pressure.
  • Adaptive Elite Mutation Strategy: Inspired by previous work, this strategy uses a Gaussian distribution to update elite solutions (global optimums) and helps escape local optima.

Datasets

The paper evaluates AMOBH on seven standard multiobjective test functions: ZDT1, ZDT3, ZDT4, DLTZ2, DLTZ4, DLTZ5, and DLTZ7. These functions are chosen to represent various challenges, including convexity, concavity, discreteness, non-uniformity, and multimodality, with dimensions ranging from 10 to 30.

Key Insights and Ideas

  • Cell Density as a Novel Diversity Metric: The introduction of "cell density" in the PCCS offers a computationally efficient way to assess solution distribution, proving effective in maintaining diversity.
  • Shannon Entropy for Adaptive Control: Using Shannon entropy to gauge the evolutionary state allows AMOBH to dynamically adjust its search behavior, leading to better performance across different problem types.
  • Balancing Convergence and Diversity is Crucial: The paper consistently emphasizes the challenge of balancing these two aspects and how AMOBH's combined strategies aim to achieve this.
  • Black Hole Algorithm's Adaptability: The research demonstrates that the core concept of the black hole algorithm can be effectively extended to multiobjective optimization with appropriate modifications.

Key Results

AMOBH demonstrated strong performance across the tested functions.

  • Convergence and Diversity: AMOBH achieved good results in terms of both convergence (getting close to the true Pareto front) and diversity (spreading solutions evenly across the front) on most test problems.
  • Comparative Performance: When compared to SPEA-II, PESA-II, NSGA-II, and MOEA/D, AMOBH generally outperformed them, particularly on complex, high-dimensional, or multimodal problems, as measured by the Inverted Generation Distance (IGD) metric.
  • Efficiency: AMOBH showed significantly better average CPU runtime compared to the other algorithms, indicating higher computational efficiency.
  • Scalability: The algorithm performed well on problems with an increased number of objectives (from 2 to 3), suggesting good scalability.

Limitations and Future Work

  • Convergence Rate on Multimodal Problems: The paper notes that AMOBH's convergence rate might be affected on some multimodal problems, requiring more time to stabilize.
  • Future Work: The authors plan to apply AMOBH to more complex multiobjective optimization problems, such as many-objective optimization and DC motor parameter optimization. They also aim to further improve the algorithm's convergence rate on multimodal problems.

Summary updated

BibTeX
@article{wu2017amobh,
  author = {Chong Wu and Tao Wu and Kaiyuan Fu and Yuan Zhu and Yongbo Li and Wangyong He and Shengwen Tang},
  title = {{AMOBH: Adaptive Multiobjective Black Hole Algorithm}},
  journal = {Comput. Intell. Neurosci.},
  year = {2017},
  doi = {10.1155/2017/6153951},
}
Figure