Random-Restart Schedule¶
Scheduling policy — instantiates Bounded Random-Walk Navigation
Teleports a stalled or trapped walk back to a fresh random starting point on a set schedule, so no single dead-end region can hold the search forever.
A Random-Restart Schedule is a policy that periodically abandons the walk's current position and relaunches it from a new random start, deliberately discarding accumulated location in order to escape traps, local optima, and dead ends. Its signature is the relaunch: where an absorbing trigger ends a walk for good, a restart resets it to explore again — the reset is a fresh beginning, not a termination. It answers a single recurring question — "this stretch isn't going anywhere; jump somewhere new and try again" — and it does so on a defined trigger rather than by hope.
Example¶
A logistics solver is optimizing a delivery route across thousands of stops using randomized local search: it improves the current route by small random swaps of stop order. The trouble with local search is that it keeps getting stuck in local optima — a route that cannot be improved by any single swap yet is far from the best possible. The restart schedule watches for the stall: after a set number of consecutive non-improving swaps (the reset condition), it records the best route found so far and relaunches the search from a completely fresh, randomly generated route (the restart policy). Over dozens of restarts it keeps only the best route seen across all of them. The result routinely beats any single run, because no one unlucky starting basin can trap the whole search — the relaunch is exactly what lets it escape.
How it works¶
- Define the restart trigger. A fixed interval, a stall (N steps without improvement), or an exhausted per-attempt budget.
- On trigger, save and relaunch. Store the incumbent best, then reset the walk's position to a fresh random draw.
- Keep the best across attempts. The answer is the best state seen over all restarts, not the last one.
- Repeat within the overall budget. More restarts diversify coverage; fewer let each attempt mature.
The defining act is the reset-to-fresh-start; nothing about position is carried over.
Tuning parameters¶
- Restart trigger — interval-based versus stall-detected versus budget-exhausted; stall-detection adapts to the terrain but can misfire on a temporary plateau.
- Number of restarts — more attempts raise the odds of a good basin but split a fixed budget thinner.
- Start distribution — uniform random versus biased away from already-visited basins; steering restarts improves coverage but adds bookkeeping.
- Elitism — whether the best incumbent is always retained across restarts (it should be, or good work is thrown away).
- Restart frequency annealing — restart often early for coverage, less often later to let a promising basin settle.
When it helps, and when it misleads¶
Its strength is robustness against local traps at almost no conceptual cost: a search that would otherwise die in the first basin it wanders into gets many independent chances, and the best-across-restarts rule banks the luckiest one. This is the logic of random-restart hill climbing and of basin-hopping.[n1]
Its failure mode is mistiming the reset. Restart too often and you throw away almost-good progress, never letting a promising region mature into a real improvement; restart too rarely and the run burns its budget stuck in one dead end. The classic misuse is restarting on noise — reading a brief plateau as a dead end and relaunching just before the walk would have broken through. The guarding discipline is to tie the restart trigger to evidence of a genuine stall (sustained non-improvement, not one flat step) rather than to an impatient timer.
How it implements the components¶
random_restart_policy— specifies where and how each relaunch draws its fresh starting point.stopping_or_reset_rule— defines the condition (a detected stall, an exhausted per-attempt budget) that ends the current attempt and resets it.
Its reset is a relaunch, not an end, so it does not define the absorbing_failure_state a walk can never leave — that terminal, irreversible halt is Absorbing-State Trigger, whose stop is permanent where a restart's is a fresh beginning — and it moves position wholesale rather than scaling steps, so the step_size_schedule belongs to Step-Size Throttle.
Related¶
- Instantiates: Bounded Random-Walk Navigation — it is the escape hatch that keeps a wandering search from being permanently trapped.
- Sibling mechanisms: Random-Walk Simulation · Cumulative Displacement Dashboard · Drift vs. Noise Test · Exploration Capture Protocol · Path-Trace Audit · Reflecting-Boundary Rule · Step-Size Throttle · Walk-Budget Review · Absorbing-State Trigger
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Random-Restart Schedule operates as an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution because it teleports a stalled or trapped walk back to a fresh random starting point on a set schedule, so no single dead-end region can hold the search forever.
Independent corroboration: The frozen evidence defines Random-Restart Schedule as 'Teleports a stalled or trapped walk back to a fresh random starting point on a set schedule, so no single dead-end region can hold the search forever', so its operative form is Analysis, Modeling & Optimization.
Nearest alternative: Control, Automation & Runtime — Random-Restart Schedule includes features of a live operational control that automatically routes, enforces, adapts, or responds during execution, but its defining operation is an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Multi-domain
Rationale: Scheduled random restarts are an algorithmic technique for escaping trapped search or walk states.
Related originating lineages:
- Mathematics — Markov-chain restart models supplied formal coverage and hitting-time analysis.
- Operations Research — Stochastic optimization materially shapes restart cadence.
Review resolution: Both blind reviewers agree on computer_science as the primary origin. Explicit reconciliation resolves alternate_origin_disagreement, origin_mode_disagreement, domain_reach_disagreement, encyclopedia_synthesis_disagreement. The merged alternate lineages retain only domains the reviewers identified as materially formative; domain_reach=multi_domain records later applicability separately from origin breadth.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Random-restart hill climbing runs a local search repeatedly from independent random starting points and keeps the best result, a standard remedy for the local-optimum problem; basin-hopping is the closely related global-optimization strategy of perturbing to a new basin and re-optimizing. Both rely on the relaunch — discarding the current position — to reach ground a single run cannot. ↩