Ensemble multi-objective biogeography-based optimization with application to automated warehouse scheduling

Haiping Ma, Shufei Su, Dan Simon, Minrui FeiEngineering Applications of AI 2015 · DOI

TL;DR

This paper introduces an "Ensemble Multi-objective Biogeography-Based Optimization" (EMBBO) algorithm, which combines multiple biogeography-based optimization techniques to improve performance on complex problems. They demonstrate EMBBO's effectiveness on both standard benchmark functions and a real-world automated warehouse scheduling problem, showing it outperforms its individual components and is competitive with state-of-the-art algorithms.

What Problem Does This Paper Address?

Warehouse scheduling is a critical and complex task in supply chain management, often falling into the NP-hard category. The challenge lies in optimizing multiple, often conflicting, objectives such as minimizing travel distance and maximizing scheduling quality. Traditional optimization algorithms may struggle with the intricate nature of these problems, leading to suboptimal solutions. This paper aims to develop a more robust and efficient optimization approach for automated warehouse scheduling by leveraging the strengths of ensemble learning and biogeography-based optimization.

Methods

The core of this paper is the development of the Ensemble Multi-objective Biogeography-Based Optimization (EMBBO) algorithm. EMBBO is an ensemble approach that combines three existing multi-objective biogeography-based optimization (MBBO) algorithms:

  • Vector Evaluated Biogeography-Based Optimization (VEBBO)
  • Non-dominated Sorting Biogeography-Based Optimization (NSBBO)
  • Niched Pareto Biogeography-Based Optimization (NPBBO)

These constituent algorithms are run in parallel, each operating on its own subpopulation. The offspring generated by each algorithm are then combined, and the best individuals (selected using non-dominated sorting) are used to update all parent populations. This "ensemble" approach aims to harness the diverse search capabilities of the individual MBBO algorithms, leading to a more adaptable and effective overall optimizer. The paper also formulates a real-world automated warehouse scheduling problem as a constrained multi-objective optimization problem.

Datasets

The paper evaluates EMBBO on:

  • 10 unconstrained multi-objective benchmark functions (U01-U10) from the CEC 2009 benchmark set.
  • 10 constrained multi-objective benchmark functions (C01-C10) from the CEC 2009 benchmark set.
  • A newly formulated real-world automated warehouse scheduling problem, based on specific parameters for warehouse dimensions, S/R machine capacity, velocities, and task times. Five different implementation schemes for this problem are considered, varying the number of storage and outgoing products.

Key Insights and Ideas

  • Ensemble learning for optimization: The "no free lunch" theorem suggests that no single algorithm is best for all problems. By combining multiple specialized algorithms (VEBBO, NSBBO, NPBBO) in an ensemble, EMBBO can adapt to different problem characteristics and search phases, leading to superior performance.
  • Parallel populations enhance efficiency: Running multiple smaller subpopulations in parallel, as EMBBO does, can be computationally more efficient than a single large population, especially for operations like roulette-wheel selection. This also opens avenues for parallel processing.
  • Synergy of MBBO algorithms: The combination of VEBBO (vector evaluated), NSBBO (non-dominated sorting), and NPBBO (niched Pareto) provides a diverse set of search strategies that complement each other.

Key Results

  • Benchmark Performance: EMBBO outperformed its constituent MBBO algorithms on a majority of both unconstrained (7 out of 10) and constrained (6 out of 10) benchmark functions.
  • Competitive with State-of-the-Art: EMBBO was found to be competitive with the best algorithms from the 2009 CEC competition. It was better than the top CEC algorithms on 5 out of 10 unconstrained functions and 3 out of 10 constrained functions.
  • Warehouse Scheduling: For the automated warehouse scheduling problem, EMBBO outperformed its constituent algorithms on 4 out of 5 schemes and was better than the best CEC 2009 algorithms on 2 out of 5 schemes.
  • Efficiency: The average running time of EMBBO was significantly less than its constituent MBBO algorithms, attributed to the use of smaller, parallel subpopulations.

Limitations and Future Work

  • No single best: While EMBBO generally performs well, it's not always the absolute best. For instance, MOEAD and MTS outperformed EMBBO on some unconstrained benchmark functions, and DMOEADD on some constrained ones.
  • Generalizability: The paper suggests that the framework of combining multiple MBBO algorithms could be extended to other types of optimization algorithms.
  • Warehouse Model: The warehouse scheduling model is based on specific assumptions (e.g., constant velocity, simplified pickup/set down times). Future work could explore more complex real-world scenarios.
  • Number of Populations: The paper uses three parallel populations, but notes that more could be used if additional MBBO algorithms are available, suggesting potential for further scaling.

Summary updated

BibTeX
@article{ma2015ensemble,
  author = {Haiping Ma and Shufei Su and Dan Simon and Minrui Fei},
  title = {{Ensemble multi-objective biogeography-based optimization with application to automated warehouse scheduling}},
  journal = {Engineering Applications of AI},
  year = {2015},
  doi = {10.1016/j.engappai.2015.05.009},
}
Figure