Heuristic — swarm metaheuristic· v2.0.0

▶ Open interactive explainer →

Gravitational Search Algorithm

Alias gsa, gravitational_search
Type Heuristic — swarm metaheuristic
Complexity O(epochs · pop · n) + 2-opt polish
Auto-seeds from shuffle (agent 0); the rest of the population is NN-seeded internally
Benchmarks published results ↓

Description

Physics-inspired swarm metaheuristic where each agent is a candidate tour with a mass proportional to its fitness. Heavier agents (shorter tours) attract lighter ones. Each epoch, an agent samples one attractor from the current Kbest set, weighted by mass, and moves toward it with an order crossover. Kbest shrinks linearly from N to 1 and the gravitational constant decays, shifting the algorithm from broad exploration to convergence. A 2-opt reversal supplies local exploration, and the best tour is finally polished with 2-opt.

TSP-specific adaptations (deviations from Rashedi et al. 2009; this is a memetic adaptation, not a published algorithm):

Adaptation Reason
Force → mass-weighted order crossover toward one sampled Kbest agent A summed swap-list force breaks up to four edges per swap and is blind to rotation; sampling one mass-weighted attractor gives the same expected pull without stale rank lists
Kbest shrinks linearly N → 1 Rashedi’s exploration-to-exploitation schedule; the fixed top-half was a v1 simplification
Greedy accept the combined move GSA has no per-agent memory; always-accepting an unconditional reversal drifts the whole swarm to a noise floor and freezes gbest at the best seed
2-opt reversal after the attraction Explores the edge neighbourhood the tour is scored on, and keeps a move alive after the population collapses
Half the population seeded from nearest-neighbour tours A constructive start is worth many epochs on TSP
Final 2-opt polish The swarm explores; the polish exploits the best tour found

Auto-expands to pipeline(shuffle, gsa).

procedure GravitationalSearch(cities, n_agents, epochs):
    agents ← half_nn_seeded(half_random(n_agents, cities))
    gbest ← best_tour(agents)
    for epoch in 1..epochs:
        G ← G0 · exp(-α · epoch / epochs)
        masses ← spread_based_mass(agents)
        kbest ← top_mass(masses, kbest_size(epoch))
        for each agent i:
            j ← sample(kbest, weights=masses, exclude=i)
            candidate ← order_crossover(agents[i], agents[j], G · masses[j])
            candidate ← random_2opt_reversal(candidate)
            if length(candidate) < length(agents[i]):
                agents[i] ← candidate
        gbest ← best_tour(agents)
    return 2opt_polish(gbest)

Options

Flag Description Default
--epochs Maximum iterations 10 000
--n_nearest Number of agents (floored at 25); also the candidate width for the final 2-opt polish (floored at 16) 25

Usage

teeline solve gsa -i ./data/tsplib/berlin52.tsp
teeline solve gravitational_search -i ./data/tsplib/berlin52.tsp --epochs=500
teeline solve gsa -i ./data/tsplib/berlin52.tsp --n_nearest=50

References

  • Rashedi, E., Nezamabadi-pour, H. & Saryazdi, S. (2009) — GSA: A Gravitational Search Algorithm. Information Sciences, 179(13), 2232–2248.
  • Davis, L. (1985) — “Applying Adaptive Algorithms to Epistatic Domains”, Proc. 9th International Joint Conference on Artificial Intelligence (IJCAI), pp. 162–163. ijcai.org
  • Croes, G. A. (1958) — “A Method for Solving Traveling-Salesman Problems”, Operations Research, 6(6), 791–812. DOI: 10.1287/opre.6.6.791
  • Gravitational search algorithm (Wikipedia) — general overview

Changelog

Version Date Change
2.0.0 22 Nov 2026 Replaced the summed swap-list force with a mass-weighted order crossover toward a sampled Kbest attractor, added greedy acceptance, a 2-opt reversal, a Kbest schedule shrinking N → 1, half-NN seeding, and a final 2-opt polish. Tier A median gap: 190.52% → 3.24%; dsj1000: 2503.87% → 11.98%.

Benchmarks

Loading published results…