Search Without a Gradient
When there is no slope to follow: a walker that cools, a climber that remembers, a population that breeds, ants that leave trails, and two metaphors whose critics say the moves beneath them are old.
Math Foundations · Algorithms & Data Structures
Before you start
Some lessons here build on lessons from other arcs: The Knapsack Problem.
- 1
Gradient Descentin progress
Math · Calculus · ~25 minFind the bottom of a bowl you cannot see: measure the slope where you stand, step against it, repeat. The learning rate decides whether you crawl, arrive, bounce, or fly off.
- 2
Simulated Annealingin review
Algorithms · Meta-heuristics · ~25 minA walker on a bumpy landscape accepts uphill moves with a chance that shrinks as the temperature cools, so it escapes small basins early and settles late. At zero temperature it is hill climbing.
- 3
Tabu Searchin review
Algorithms · Meta-heuristics · ~25 minA climber with a memory: take the best neighbour even when it is worse, forbid undoing the move for a few rounds, and break the rule only for a new best. With no list it bounces between two states.
- 4
Genetic Algorithmsin review
Algorithms · Meta-heuristics · ~25 minA population of bit strings packs a knapsack: tournaments pick parents, a one-point cut splices them, rare flips mutate, the best survives untouched. Compare it with the exact knapsack table.
- 5
Ant Colony Optimizationin review
Algorithms · Meta-heuristics · ~25 minAnts build tours city by city, each next step a gamble weighted by pheromone and closeness; trails evaporate and the shortest tours lay the most, so the colony converges on good routes.
- 6
Whale Optimization Algorithmin review
Algorithms · Meta-heuristics · ~25 minWhales circle a leader, spiral in, or wander, with a coefficient that shrinks from 2 to 0. A clear look at a 2016 metaheuristic whose moves, critics showed, are old operators under a new story.
- 7
Teaching-Learning-Based Optimizationin review
Algorithms · Meta-heuristics · ~25 minA class learns from its best student and from each other: a teacher phase pulls everyone up, a learner phase pairs them off, and only better moves are kept. Billed parameter-free; read the critique.