A Population-Based Algorithm for the Sphere Packing Problem
Résumé
In this paper, the sphere packing problem is approximately solved with a population-based method. The sphere packing problem, known as the three-dimensional knapsack, occurs in several real-world applications and because of its NP-hardness it is however computationally challenging. The designed method combines a population approach and a tolerance strategy: the population tries to maintain the diversity of a series of subsets of configurations reached throughout an iterative procedure while the tolerance strategy tries to highlight the quality of the solutions throughout the search process. The performance of the designed approach is evaluated on reference instances of the literature, where its achieved bounds are compared to those obtained by more recent algorithms.