A Hierarchical Sorting Swarm Optimizer for Large-Scale Optimization

Rushi Lan, Li Zhang, Zhiling Tang, Zhenbing Liu, Xiaonan LuoIEEE Access 2019 · DOI

Introduction

Large-scale optimization (LSO) is a cornerstone of modern engineering, essential for tasks ranging from designing wideband metasurfaces to optimizing complex drone flight paths. These problems often involve hundreds or thousands of decision variables, creating an immense search space that challenges traditional computational methods.

Standard Particle Swarm Optimization (PSO) algorithms frequently struggle in these high-dimensional environments. They are prone to "premature convergence," where the swarm becomes trapped in local optima—the mathematical equivalent of settling on a small hill while a mountain remains undiscovered nearby. Furthermore, as dimensions increase, the computational overhead of maintaining individual memory (personal bests, or $pbest$) for every particle becomes a significant bottleneck. The Hierarchical Sorting Swarm Optimizer (HSSO) addresses these challenges by replacing traditional memory-based strategies with a structured, recursive social learning approach.

The HSSO Framework

Sorting and Initialization

The HSSO algorithm begins by abandoning the traditional reliance on individual particle history. Instead, it adopts a population-wide social structure. At the start of each generation, the algorithm performs a global assessment of the swarm.

Particle initialization and sorting by fitness values.

As shown in the figure above, particles are randomly initialized and then sorted based on their "fitness" values—a measure of how effectively they solve the target objective function. This sorting process ranks the swarm from "the bad" to "the good," providing the foundation for the hierarchical division that follows.

Hierarchical Learning and Recursion

The core innovation of HSSO is its recursive partitioning mechanism. Once sorted, the swarm is halved into two distinct hierarchies: a "good group" (G) and a "bad group" (B).

The recursive hierarchical learning mechanism of HSSO.

In this structure, particles in the bad group update their positions by learning from two primary sources: a corresponding particle in the good group and the mean position of the relevant particles. This "social learning" reduces the memory burden on individual particles, as they no longer need to track their own $pbest$.

Crucially, the process is recursive. The "good group" is treated as a new mini-swarm, which is again sorted and halved. This continues until only a single particle remains at the apex of the hierarchy. To ensure scalability, HSSO employs a dynamic swarm sizing formula ($m = M + \lfloor n/10 \rfloor$), automatically adjusting the number of particles based on the problem's dimensionality ($n$). This hierarchical structure ensures that lower-performing particles are constantly pulled toward better regions without the entire swarm collapsing toward a single point too rapidly, thereby maintaining essential diversity.

Experimental Evaluation

To validate its effectiveness, HSSO was tested against a comprehensive suite of 39 benchmark functions, including the CEC’13 (30-D), CEC’08 (up to 500-D), and the CEC’10 (1000-D) sets. The latter is specifically designed to test large-scale optimization capabilities across both separable and non-separable problems.

HSSO was compared against nine state-of-the-art algorithms, including the Competitive Swarm Optimizer (CSO) and Social Learning PSO (SL-PSO). The results demonstrated superior scalability:

  • High-Dimensional Performance: In 1000-dimensional tests, HSSO outperformed or matched competitors on the vast majority of functions. For instance, on separable functions like $f_{13}$, HSSO achieved significantly lower error rates than its peers.
  • Convergence Stability: Qualitative analysis of convergence graphs indicated that HSSO maintains a steady downward trajectory in error, avoiding the early plateaus common in other algorithms.
  • Efficiency: The hierarchical division results in a time complexity of $O(n \log m)$, making it highly efficient for large swarms and complex landscapes.

Discussion and Conclusion

HSSO represents a shift away from individual memory toward a more biologically plausible and computationally efficient social learning model. By using the mean position of groups rather than just a single global best, the algorithm prevents the bias that often leads to premature convergence.

While HSSO is not a "silver bullet"—specialized algorithms still hold an edge on certain specific functions—its robustness across unimodal and multimodal landscapes makes it a powerful tool for large-scale engineering challenges. Future research will focus on applying HSSO to real-world constrained engineering problems and exploring deeper hierarchical structures for problems involving millions of variables.

Summary updated

BibTeX
@article{lan2019hierarchical,
  author = {Rushi Lan and Li Zhang and Zhiling Tang and Zhenbing Liu and Xiaonan Luo},
  title = {{A Hierarchical Sorting Swarm Optimizer for Large-Scale Optimization}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2906082},
}
Figure