Micro-macro decomposition of particle swarm optimization methods

Michaël Herty, Sara Veneruso

TL;DR

This paper introduces a hybrid "micro-macro" framework for Particle Swarm Optimization (PSO) that blends individual particle dynamics with fluid-like macroscopic density models. By combining this decomposition with an adaptive penalization strategy, the authors create a robust method for solving complex, constrained optimization problems that shifts computational weight between scales as the swarm converges.

What Problem Does This Paper Address?

Particle Swarm Optimization (PSO) is a popular "derivative-free" method used to find the minimum value of complex mathematical functions. It works by simulating a "swarm" of candidate solutions (particles) that move through a search space, influenced by their own best-known positions and the best position found by the whole group.

However, PSO faces two major hurdles:

  1. Constraints: Real-world problems often have "no-go zones" (constraints). Standard PSO is designed for unconstrained space, and forcing it to stay within specific boundaries can be difficult.
  2. Scalability vs. Accuracy: Simulating thousands of individual particles (the microscopic scale) is accurate but computationally expensive. Conversely, treating the swarm as a continuous "fluid" or probability density (the macroscopic scale) is efficient but can lose the fine-grained detail needed to escape local traps.

The authors aim to bridge this gap by creating a system that can handle constraints and dynamically switch between "particle mode" and "fluid mode."

Methods

The researchers introduced two primary innovations:

  • Adaptive Exact Penalization: To handle constraints, they modified the objective function by adding a penalty term. Unlike static penalties, they used an adaptive strategy. If the swarm violates a constraint, the penalty strength ($\beta$) increases; if the swarm is well-behaved, the tolerance for testing the constraint becomes stricter. This allows the algorithm to solve constrained problems without needing the function to be differentiable.
  • Micro-Macro Decomposition: This is the core novelty. The authors represent the swarm's total probability density as a mix of two parts:
  • Micro: Individual particles following stochastic differential equations.
  • Macro: A continuous "Maxwellian" distribution (similar to a Gaussian curve) governed by hyperbolic conservation laws (fluid dynamics).
  • Dynamic Coupling: They introduced a weighting function, $\zeta(t, x)$, that decides how much of the "mass" belongs to the particles versus the fluid. As the particles begin to move in unison (reaching a "consensus"), the algorithm shifts mass to the macroscopic scale, which is faster to compute.

Datasets

The paper evaluates the algorithm using standard mathematical "benchmark" functions rather than external datasets. These functions are chosen because they are notoriously difficult to optimize (non-convex with many local minima):

  • Ackley Function: A "holey" function with many local pits and one deep global minimum at the center.
  • Rastrigin Function: A highly multi-modal function used to test an algorithm's ability to avoid getting stuck in local traps.

Key Insights and Ideas

  • The "Fluid" Swarm: The authors demonstrate that a swarm of particles can be mathematically treated as a fluid. By using the "mean-field limit," they can derive equations that describe the swarm's density and velocity without tracking every single particle.
  • Mass Shifting, Not Particle Deletion: Instead of deleting particles to save time, the algorithm changes the weight of the particles. If the microscopic particles are behaving exactly like the macroscopic fluid model, their weight decreases, and the fluid model takes over.
  • Emergent Gradient Descent: Interestingly, the "consensus point" (the weighted average of the swarm) tends to follow a path similar to gradient descent, even though the algorithm never actually calculates a gradient (derivative).

Key Results

  • Constraint Success: In tests using the Ackley function with complex, disconnected "feasible zones" (represented as several green circles), the penalized PSO successfully steered the particles into the valid regions to find the global minimum.
  • Convergence at Scale: The macroscopic model (the fluid version) was shown to be "strictly hyperbolic," meaning it is mathematically stable and well-posed for these types of problems.
  • Efficiency via Decomposition: In the Rastrigin tests, the value of $\zeta$ (the microscopic weight) decreased over time. This confirms that as the optimization progresses, the system naturally favors the macroscopic scale, potentially offering significant speedups for high-dimensional problems.

Limitations and Future Work

  • Dimensionality: Most numerical examples were performed in 1D or 2D spaces. The authors acknowledge that in very high-dimensional problems, the macroscopic "fluid" behavior becomes much more complex and might require different mathematical "closures."
  • Initial Instability: The paper notes that "strong mass fluctuations" can occur at the very beginning of the simulation. To counter this, they had to implement a delay ($t^*$) before allowing the micro-macro mass shifting to begin.
  • Choice of Closure: The macroscopic model relies on a "Maxwellian" assumption. Future work could explore different probability distributions to see if they better represent the behavior of swarms in specific types of landscapes.

Summary updated

Abstract

Solving non-convex minimization problems using multi-particle metaheuristic derivative-free optimization methods is still an active area of research. Popular methods are Particle Swarm Optimization (PSO) methods, that iteratively update a population of particles according to dynamics inspired by social interactions between individuals. We present a modification to include constrained minimization problems using exact penalization. Additionally, we utilize the hierarchical structure of PSO to introduce a micro-macro decomposition of the algorithm. The probability density of particles is written as a convex combination of microscopic and macroscopic contributions, and both parts are propagated separately. The decomposition is dynamically updated based on heuristic considerations. Numerical examples compare the results obtained using the algorithm in the microscopic scale, in the macroscopic scale, and using the new micro-macro decomposition.
BibTeX
@inproceedings{herty2025micro,
  author = {Michaël Herty and Sara Veneruso},
  title = {{Micro-macro decomposition of particle swarm optimization methods}},
  booktitle = {Kinetic},
  year = {2025},
  doi = {10.3934/krm.2025016},
}

Loading related content...

Figure