Hybrid biogeography-based evolutionary algorithms

Haiping Ma, Dan Simon, Minrui Fei, Xinzhan Shu, Zixiang ChenEngineering Applications of AI 2014 · DOI

TL;DR

This paper introduces novel "biogeography-based hybridization" strategies to combine existing evolutionary algorithms (EAs). By leveraging the migration principles of Biogeography-Based Optimization (BBO), these new hybrid EAs demonstrate significantly improved performance on complex optimization problems and real-world challenges like the Traveling Salesman Problem, often outperforming their individual components.

What Problem Does This Paper Address?

The field of evolutionary computation has seen a proliferation of algorithms, each with its own strengths and weaknesses. While individual algorithms are effective for certain problem types, many real-world optimization tasks are complex and require a balance of exploration (searching broadly) and exploitation (refining promising solutions). Hybridizing EAs, by combining multiple algorithms, offers a promising avenue to achieve this balance and improve overall performance. However, the how of hybridization – the strategies for combining these algorithms – remains an active area of research. This paper specifically addresses the challenge of developing effective hybridization strategies by proposing a novel approach inspired by the migration mechanisms of Biogeography-Based Optimization (BBO).

Methods

The core contribution of this paper is the development of two novel biogeography-based hybridization strategies:

  • Iteration-Level Hybridization: This approach treats the optimization process as a sequence of stages. One EA is used to quickly narrow down the search space to promising regions, and then BBO is applied to further refine these solutions. This is akin to a "coarse-to-fine" search.
  • Algorithm-Level Hybridization: This more sophisticated method involves running multiple EAs (or subpopulations) independently and then using BBO's migration principles to exchange information between them. This allows for parallel exploration and exploitation, with BBO guiding the information flow between the different algorithmic "habitats."

The authors applied these strategies to hybridize several recently developed EAs, including CMA-ES, SGA, SaDE, PSO2011, LPSO, and CPSO, with BBO. They then rigorously tested these hybrids against their constituent algorithms and other state-of-the-art methods.

Datasets

The paper evaluates the proposed hybrid algorithms on two main sets of benchmarks:

  • 2013 Congress on Evolutionary Computation (CEC) Continuous Optimization Benchmarks: A standard suite of 28 functions designed to test the performance of optimization algorithms on various challenges, including unimodal, multimodal, and composition functions. These benchmarks were used with a dimensionality of 50 and a function evaluation limit of 500,000.
  • Traveling Salesman Problem (TSP) Benchmarks: Seven real-world TSP instances (Bays-29, Berlin-52, St-70, Ch-130, Brg-180, Rat-575, and D-1291) were used to assess the algorithms' performance on a representative combinatorial optimization problem.

Key Insights and Ideas

  • BBO's Migration as a Universal Hybridization Tool: The paper demonstrates that BBO's core migration mechanism, which governs how species (solutions) move between habitats (regions of the search space), can be effectively adapted to facilitate information exchange between different evolutionary algorithms. This is a novel application of BBO's principles.
  • Algorithm-Level Hybridization Outperforms Iteration-Level: The study consistently shows that algorithm-level hybridization, where multiple EAs run in parallel and exchange information, generally yields better results than the sequential iteration-level approach. This suggests that parallel exploration and adaptive information sharing are more beneficial for complex problems.
  • SaDE/BBO-A as a Top Performer: The hybrid algorithm combining Self-Adaptive Differential Evolution (SaDE) with algorithm-level BBO hybridization (SaDE/BBO-A) emerged as a leading performer, achieving the best results on a significant number of benchmark functions and demonstrating strong performance on TSP instances.
  • Robustness to Tuning: While tuning parameters can influence performance, the study suggests that the proposed hybrid algorithms, particularly SaDE/BBO-A, exhibit a degree of robustness, with variations in parameters not drastically degrading performance.

Key Results

  • Superior Performance: The proposed hybrid algorithms consistently outperformed their individual constituent algorithms on the 2013 CEC benchmark functions.
  • Competitive with State-of-the-Art: SaDE/BBO-A was ranked as the third-best algorithm among a competitive set of seven algorithms accepted for the 2013 CEC competition, demonstrating its strong performance against established methods.
  • TSP Success: SaDE/BBO-A achieved the best cost (shortest traveling distance) for five out of seven TSP benchmarks, showcasing its effectiveness on real-world combinatorial problems.
  • Algorithm-Level Advantage: Algorithm-level hybrids were generally found to be more effective than iteration-level hybrids.
  • Computational Efficiency: While hybrid algorithms generally took longer to run than their individual components, algorithm-level hybrids were often faster than iteration-level hybrids due to their parallel nature.

Limitations and Future Work

  • Limited Set of EAs: The study focused on a representative but not exhaustive set of EAs. Future work could explore hybridizing other popular EAs.
  • Parameter Tuning: While robustness was investigated, further research into optimal parameter settings for the hybrid algorithms, especially for new problem domains, is warranted.
  • Additional Benchmarks and Problem Types: The authors suggest testing on more diverse benchmark functions, higher dimensions, noisy functions, and other real-world problems to further validate the proposed strategies.
  • Exploring Other BBO Migration Models: Investigating non-linear migration curves and other variations of BBO's migration operators could lead to further improvements.
  • Developing Other Hybridization Strategies: The paper proposes that ideas from other EAs (like DE, PSO, SGA) could be used to develop new hybridization strategies, which could then be compared to the biogeography-based approach.

Summary updated

BibTeX
@article{ma2014hybrid,
  author = {Haiping Ma and Dan Simon and Minrui Fei and Xinzhan Shu and Zixiang Chen},
  title = {{Hybrid biogeography-based evolutionary algorithms}},
  journal = {Engineering Applications of AI},
  year = {2014},
  doi = {10.1016/j.engappai.2014.01.011},
}
Figure