Biased randomisation of greedy heuristics
Greedy heuristics are fast but deterministic. Pure random search explores but wastes effort. Biased randomisation with a geometric distribution combines the two with a single parameter, as a comparison on a hard knapsack instance shows.
A greedy algorithm selects the locally best option at each step. It is fast and usually performs reasonably well, but it always returns the same solution, so a mediocre result cannot be improved by running it again.
Pure random search has the opposite properties: it explores widely but rarely finds good solutions efficiently.
Biased randomisation combines the two: it follows the greedy order of preference, but not strictly. It is one of the most useful ideas I met in the optimisation courses of my doctoral programme, and it fits in a single formula. This article examines whether a suitably shaped random choice can turn a good greedy rule into a near-optimal method.
A delivery company planning the day's routes illustrates the idea. A greedy planner sends each van to the nearest unvisited address; the routes are sensible but always the same, so a poor sequence is repeated every day. A biased-randomised planner usually chooses the nearest address, sometimes the second nearest and occasionally the third. Each run produces a different but still sensible set of routes, and the best of several hundred runs is kept.
The greedy randomised adaptive search procedure (GRASP) of Feo and Resende (1995) introduced randomness into greedy construction by choosing uniformly among a restricted list of top candidates. Biased randomisation replaces that uniform choice with a skewed distribution, most often geometric; Grasas and colleagues (2017) survey the approach and its applications. Ferone and colleagues (2019) showed that adding biased randomisation to GRASP improves results on several problem families, including vehicle routing. A broader review by Juan and colleagues (2023) reports that, averaged over many problems, simple constructive heuristics were about 4% from the best known solutions, biased-randomised algorithms about 1.8%, and full metaheuristics about 0.7%, at much higher development and computing cost. For test instances, Pisinger (2005) describes which knapsack problems are hard for greedy rules.
Greedy and random construction
For the 0/1 knapsack problem, a greedy rule adds items in order of value per unit of weight until nothing else fits. In one of my assignments, comparing it with pure random search on random instances, the greedy rule won at every size I tried, by about 13% with 50 items and about 32% with 1,000 items, and ran roughly a thousand times faster. Random search is not useless: on a smooth convex test function it found the minimum to within about 0.002 in a fraction of a second. The structure of the problem determines the outcome. Combinatorial problems have structure a good rule captures and blind sampling does not.
Geometric selection
Keep the greedy ranking, but choose the next item at random with probabilities that decrease along the list. With a geometric distribution and parameter , the candidate at position (counting from 0) is chosen with probability
which can be sampled in constant time from a uniform random number :
(The modulo wraps the rare draws beyond the end of the list back to the start.) As the method becomes the greedy rule; as it approaches a uniform choice. Values around 0.2 to 0.4 are common.
Properties and parallelisation
Each run produces a different solution, but every solution is built mostly along the greedy logic, so none is unreasonable. Many runs explore the neighbourhood of the greedy solution far more efficiently than random search explores the whole space. And because runs are independent, they can run on separate cores: with enough cores, the wall-clock time is that of a single greedy run. Juan's group calls this agile optimisation. For the delivery company it means that the routes can be recomputed within seconds when a van breaks down or an urgent order arrives during the day.
The figure below compares the three methods and illustrates three points: (1) the positions actually chosen follow ; (2) biased randomisation beats both pure greedy and pure randomness on a hard instance; (3) β controls the trade-off.
The figure builds a random 40-item knapsack of the "strongly correlated" kind (value = weight + 10), which Pisinger identifies as hard for greedy rules, and solves it exactly by dynamic programming so that every method can be measured against the true optimum.
- Selection distribution. The bars show how often each position in the greedy order was picked; the dots show . They match.
- Comparison. With β = 0.3 and 200 runs, the biased-randomised line usually reaches the optimum, or within a fraction of a percent, while pure greedy sits about 3% below and uniform random stays further away. Repeating with "New knapsack" confirms that the result is not due to chance.
- Effect of β. Set β to 1: the blue line becomes flat at the greedy value, because every run is identical. Set β to 0.02: the method behaves almost like uniform random construction. The best performance lies between these values.
- Few runs. Reduce the runs to 10. Even a handful of biased-randomised runs usually beats greedy, which is why the method works in real time.
Derivation of the sampling formula. If is uniform on (0,1), then . Hence , the geometric distribution.
Before adopting a complex metaheuristic, it is worth testing whether a good greedy rule combined with suitably shaped randomness already achieves most of the benefit. On a hard knapsack instance it closes most of the gap to the optimum with one parameter and a few lines of code, and the runs can be parallelised without additional effort.
References
- T. A. Feo and M. G. C. Resende, "Greedy randomized adaptive search procedures", Journal of Global Optimization, 6, 109-133, 1995.
- D. Pisinger, "Where are the hard knapsack problems?", Computers & Operations Research, 32(9), 2271-2284, 2005.
- A. Grasas, A. A. Juan, J. Faulin, J. de Armas and H. Ramalhinho, "Biased randomization of heuristics using skewed probability distributions: a survey and some applications", Computers & Industrial Engineering, 110, 216-228, 2017.
- D. Ferone, A. Gruler, P. Festa and A. A. Juan, "Enhancing and extending the classical GRASP framework with biased randomisation and simulation", Journal of the Operational Research Society, 70(8), 1362-1375, 2019.
- A. A. Juan, P. Keenan, R. Martí, S. McGarraghy, J. Panadero, P. Carroll and D. Oliva, "A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics", Annals of Operations Research, 320, 831-861, 2023.