Randomrestart

Random restart is a strategy used in search, optimization, and constraint solving to mitigate the risk of getting trapped in local optima or poor regions of the search space. The idea is to repeatedly restart the procedure from a new randomly chosen starting point, rather than continuing a single run that may have stagnated.

In practice, random restart is typically paired with a local search or heuristic. Each restart runs the base algorithm for a limited budget, such as a fixed number of iterations or a time limit, before restarting from a new random initial state. Variants differ in how they manage restarts: some discard all progress and begin anew, while others preserve and seed from the best solution found so far. Starting points are drawn from a distribution over the problem space, often uniform over feasible configurations.

Restart schedules vary. Some use a fixed per-run budget, others employ adaptive or dynamic strategies that adjust the interval based on observed progress. In certain domains, restart intervals follow predefined sequences, such as the Luby sequence, which is designed to optimize worst-case expected time for randomized algorithms.

Common domains for random restart include combinatorial optimization (for example, graph coloring, traveling salesman problems), constraint satisfaction problems (such as SAT solvers and scheduling), and other metaheuristic settings where local search can easily become stuck.

Advantages of random restart include simplicity, low implementation cost, and improved robustness to initialization. It can significantly reduce expected solution time when many local optima exist. Disadvantages include potential waste of computation on fruitless restarts and sensitivity to the choice of restart budget, randomness seed, and problem structure.