Heuristic — nature-inspired metaheuristic· v2.0.0
▶ Open interactive explainer →Flower Pollination Algorithm
| Alias | fpa, flower_pollination |
| Type | Heuristic — nature-inspired metaheuristic |
| Complexity | O(epochs · pop · n) + 2-opt polish |
| Auto-seeds from | shuffle (flower 0); the rest of the population is NN-seeded internally |
| Benchmarks | published results ↓ |
Description
Nature-inspired metaheuristic modelling the pollination process of flowering plants. Maintains a population of flowers (candidate tours). Each epoch, each flower applies either:
- Global pollination (probability
switch_prob): a Lévy-flight-scaled order crossover toward the global best tour — the permutation analogue ofx + γ·L·(g* − x). The copied segment isγ·|L|of the tour, clamped. - Local pollination (probability
1 − switch_prob): a small ε-scaled order crossover toward a random neighbour, followed by a 2-opt reversal — the permutation analogue ofx + ε·(x_j − x_k).
The switch probability controls the balance between exploitation (global) and exploration (local). The best tour is finally polished with 2-opt.
TSP-specific adaptations (deviations from Yang 2012; this is a memetic adaptation, not a published algorithm):
| Adaptation | Reason |
|---|---|
| Global pollination → Lévy-scaled order crossover toward gbest | A rank-swap prefix breaks four edges at once and is blind to rotation; copying a segment keeps the target’s internal edges |
γ = 0.1 on the Lévy step |
The raw Lévy median saturates the segment cap, turning global moves into fixed half-best copies |
| Local pollination → ε-scaled order crossover toward a neighbour + 2-opt reversal | The x_j − x_k difference has no clean permutation form; borrowing a small segment from a neighbour is the edge-preserving analogue |
| ε capped at 0.3 | Uniform ε can copy the whole neighbour |
| Half the population seeded from nearest-neighbour tours | A constructive start is worth many epochs on TSP |
| Final 2-opt polish | The population explores; the polish exploits the best tour found |
switch_prob floored at 0.8 when mutation_probability < 0.01 |
Prevents degeneration to 99.9 % local-only search under default CLI options |
Auto-expands to pipeline(shuffle, fpa).
procedure FlowerPollination(cities, n_flowers, p, epochs):
flowers ← half_nn_seeded(half_random(n_flowers, cities))
gbest ← best_tour(flowers)
for epoch in 1..epochs:
for each flower i:
if random() < p:
L ← |levy_flight()|
candidate ← order_crossover(flowers[i], gbest, γ·L)
else:
j ← random neighbour of i
ε ← random()
candidate ← order_crossover(flowers[i], flowers[j], ε·0.3)
candidate ← random_2opt_reversal(candidate)
if length(candidate) < length(flowers[i]):
flowers[i] ← candidate
gbest ← best_tour(flowers)
return 2opt_polish(gbest)
Options
| Flag | Description | Default |
|---|---|---|
--epochs |
Maximum iterations | 10 000 |
--n_nearest |
Number of flowers (floored at 25); also the candidate width for the final 2-opt polish (floored at 16) | 25 |
--mutation_probability |
Switch probability (global vs local pollination) | 0.8 |
Usage
teeline solve fpa -i ./data/tsplib/berlin52.tsp
teeline solve flower_pollination -i ./data/tsplib/berlin52.tsp --epochs=500
teeline solve fpa -i ./data/tsplib/berlin52.tsp --n_nearest=50 --mutation_probability=0.8
References
- Yang, X.-S. (2012) — “Flower Pollination Algorithm for Global Optimization”, in Unconventional Computation and Natural Computation (UCNC 2012), LNCS 7445, pp. 240–249, Springer
- 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
- Flower pollination algorithm (Wikipedia) — general overview
Changelog
| Version | Date | Change |
|---|---|---|
| 2.0.0 | 22 Nov 2026 | Replaced the swap-prefix moves with a Lévy-scaled order crossover toward gbest, an ε-scaled crossover toward a neighbour plus a 2-opt reversal, half-NN seeding, and a final 2-opt polish. Tier A median gap: 253.94% → 5.31%; dsj1000: 2654.97% → 9.25%. |
Benchmarks
Loading published results…