Hill climbing is an iterative local-search technique: start with a candidate solution, inspect nearby alternatives, and move to one with a better objective value. For minimization, the same approach is called hill descent. It improves solutions without requiring a differentiable cost function, provided the cost can be computed. section 16.0 section 17.1
A practical iteration follows this pattern:
- Choose a current solution and explore a small neighborhood around it. section 16.2.3
- Try random directions or parameter changes, including increases and decreases when the useful direction is unknown. section 16.2.3
- Compute the objective for each trial and move only when the result improves. section 16.2.3 section 17.1
- Stop improving when the neighborhood offers no better position, recognizing that local minima and plateaus can prevent global optimality. section 16.2.3
Reducing edge crossings
Represent a graph drawing as a candidate solution, then move vertices slightly and recalculate its crossing number. Keep a move when it reduces crossings; otherwise retain the current arrangement and try another nearby move. section 16.0 section 16.2.3
Figure 16.12 How a generic randomized heuristic with local optimization works, explained using the marble analogy. Notice that we need to try to update x in both directions and check if we get an improvement.
Compare nearby updates in both directions and check whether either produces an improvement. section 16.2.3
