Suppose a graph drawing has too many edge crossings. Randomly placing its vertices gives a cheap starting point, but it ignores nearby arrangements that might be better. Local search starts with a candidate solution, makes a small modification, measures the resulting cost, and uses that feedback to guide the next attempt. section 16.2.3 section 18.1
For a minimization problem, define three things first: a representation of a solution, a cost function that can evaluate it, and a transition that produces another solution. The transition determines what “nearby” means. Moving one graph vertex a short distance, for example, explores a different neighborhood from replacing the entire drawing at random. section 16.2.3 section 17.1.4
A simple randomized version, called hill descent when minimizing cost, repeats these operations:
- Start from a candidate, such as a randomly generated solution. section 16.2.3
- Try a short step in a randomly chosen direction and compute the candidate’s cost. section 17.1
- Keep the new candidate if its cost is lower; otherwise, leave the current solution unchanged and try again. section 17.1
Unlike gradient descent, random local search does not need a differentiable cost function: it needs only a way to compute cost. That makes it useful for a step-like objective such as the number of crossings in a graph drawing. The trade-off is direction. Gradient descent follows the steepest local decrease, while random steps can spend many attempts going the wrong way. Neither approach reliably escapes local minima or plateaus. section 16.2.3 section 17.1
Choosing a neighborhood for a tour
For a traveling-salesperson tour represented as a sequence of vertices, swapping adjacent vertices is a local move: [1,2,3,4] can become [2,1,3,4]. Swapping any two vertices reaches farther; generating a random permutation can jump across the search space. Adjacent swaps favor fine-tuning but make escape from local minima harder. In the reported comparison, random pair swaps produced a lower average best-tour cost than adjacent swaps or random permutations under the stated settings; the choice of transition matters. section 17.2.4
Listing 17.3 Random transition function for TSP
function randomStep(P) #1
which ← randomFloat(0,1) #2
if which < 0.1 then #3
i ← randomInt(0, |P|) #4
swap(i, (i+1) % |P|) #4
elsif which < 0.8 then
i ← randomInt(0, |P|) #5
j ← randomInt(0, |P|)
swap(i, j)
else
P ← randomPermutation(P) #6
return P
The transition-function listing shows how adjacent swaps, arbitrary swaps, and random permutations can be combined with different probabilities rather than treated as exclusive choices. section 17.2.4
Search radius is therefore a practical tuning choice. Small steps concentrate effort on improving the current solution; occasional long-range steps preserve a chance of finding another promising region. Simulated annealing extends this idea by sometimes accepting an uphill move, particularly while its temperature is high, to help move beyond local minima. A schedule can favor smaller moves as the temperature cools while retaining some distant transitions. A memetic algorithm offers another combination: a genetic-algorithm mutation can locally improve each individual, such as by trying single-bit flips and retaining the best result. section 17.1.4 section 18.1 section 18.4.3
The work depends on how many transitions are tried and how expensive each transition and cost evaluation are; no fixed running-time or space bound follows without those choices. Use local search when evaluating a candidate is feasible but exhaustive search is unattractive. Test transition rules against the objective: a very narrow neighborhood may fine-tune quickly yet stall, while broad random jumps may require many attempts before finding an improvement. section 18.1 section 17.1.4 section 17.2.4
