top of page
Search

Gravitational Search Algorithm (GSA) -- A Physics-inspired Metaheuristics


Background



  • Proposed by Rashedi et al. in 2009 (“GSA: A Gravitational Search Algorithm”).

  • Belongs to the family of physics-inspired metaheuristics, similar in spirit to PSO (swarm-based) but using Newton’s Law of Gravity and Motion as metaphors.




Mechanisms:


  1. Mass assignment: Better fitness → heavier mass.

  2. Force calculation: Each mass attracts others proportionally to its mass and inversely to the distance squared.

  3. Acceleration: Force/mass → update velocity.

  4. Position update: Like in PSO, positions are updated using velocities.



  • Agents (masses/particles) represent candidate solutions.

  • Each agent has a position in the search space (solution vector).

  • Gravitational forces between agents guide the movement, stronger solutions exert stronger attraction.



Physics


Fij(t) = G(t)*Mi*Mj*(xj-xi)/(Rij+eps). % gravitational force j to i with direction

Fi(t) = sum(Fij(t), j=1..N-1) % Sum force to i ai(t) = Fi(t)/(Mi+eps) % Newton's law

where Mi = mi/sum(mi))

mi = (f(xi)-f_worst)/(f_best-f_worst)

xi = xi + vi % solution update

where vi = rand*Vi + ai


Pseudocode



Input: Objective function f(x), search space bounds, N (agents), T (max iterations),

       G0 (initial gravitational constant), α (decay coefficient)



1. Initialize population X(i) randomly within bounds

2. Initialize velocities V(i) = 0

3. For t = 1 to T do

      a. Evaluate fitness f(X(i)) for all agents

      b. Determine best(t) and worst(t)

      c. Compute masses:

             m(i) = (f(i) - worst) / (best - worst + ε)

             M(i) = m(i) / sum(m)

      d. Update gravitational constant:

             G(t) = G0 * exp(-α * t / T)

      e. For each agent i

             i.   For each agent j ≠ i in Kbest

                     Compute distance R_ij

                     Compute force component F_ij

                   end for

             ii.  Sum to get total force F(i)

             iii. Acceleration: a(i) = F(i) / (M(i) + ε)

             iv.  Update velocity: V(i) = rand*V(i) + a(i)

             v.   Update position: X(i) = X(i) + V(i)

      f. Apply boundary limits

      g. Update global best solution if improved

   End for

Output: Best solution found

bottom of page