A single unlucky starting state can spoil an otherwise useful optimization run. In k-means, poorly placed initial centroids can slow convergence; a centroid with no assigned points may even be removed. Random restart reduces dependence on that first choice: run the algorithm several times with fresh random initial states, compare the results, and keep the best. section 12.2
To add restarts to an optimizer:
- Choose a number of runs and a rule for comparing completed solutions. Initialize the best score to infinity when lower is better. section 16.5.2
- Start each run from a newly randomized state, then execute the underlying algorithm to its stopping condition or iteration limit. section 12.2 section 16.5.2
- Score the returned solution. Replace the saved solution only when the new score is better; return the best after all runs. section 16.5.2
The comparison rule depends on the problem. For a force-directed graph drawing, gradient descent updates randomly initialized vertex positions, but the restart wrapper also needs the cost function to compare finished drawings. Multiple starts give the search chances to descend toward different local minima; they do not guarantee the global minimum. section 16.5.1 section 16.5.2
Choosing a graph embedding
To seek a drawing with fewer edge crossings, randomly place the vertices, reject placements that violate vertex-and-edge constraints, and count crossings in each valid drawing. Repeat and retain the valid drawing with the fewest crossings. This is random sampling: unlike restarting gradient descent, each attempt evaluates a newly generated drawing without first optimizing it. section 16.1.1
Listing 16.6 Method forceDirectedEmbeddingWithRestart
function forceDirectedEmbeddingWithRestart(graph, alpha, runs, maxSteps)
bestCost ← inf
for _ in {1..runs} do
(x,y) ← forceDirectedEmbedding(graph, alpha, maxSteps)
if cost(graph, x, y) < bestCost then
(bestX, bestY, bestCost) ← (x, y, cost(graph, x, y))
return (bestX,bestY)
The wrapper calls the randomly initialized force-directed optimizer for a fixed number of runs and saves the coordinates with the lowest cost. section 16.5.2
The trade-off is repeated work: for R runs, total time is roughly R times one run plus R solution comparisons, while the wrapper retains a best solution alongside the current one. Restart is useful when starts strongly affect results or local minima are troublesome. It can also help simulated annealing when cooling or small update steps leave a run far from the best region. section 16.5.2 section 17.1.5
