Question

In constraint satisfaction, local search is a method for solving the problem. Is this an example of a hill climbing search or gradient decent search? Why? How would you convert the algorithm between the two?

Answer 1

One of the widely discussed examples of Hill climbing algorithm is Traveling-salesman Problem in which we need to minimize the distance traveled by the salesman. It is also called greedy local search as it only looks to its good immediate neighbor state and not beyond that.

https://www.javatpoint.com/hill-climbing-algorithm-in-ai

search is used to minimize the objective function, rather than find a solution. The algorithm runs for a certain amount of time (perhaps including random restarts to explore other parts of the search space), always keeping the best assignment found thus far, and returning this as its answer.

Local search for optimization has one extra complication that does not arise when there are only hard constraints. With only hard constraints, the algorithm has found a solution when there are no conflicts. For optimization, is difficult to determine whether the best total assignment found is the best possible solution. A local optimum is a total assignment that is at least as good, according to the optimality criterion, as any of its possible successors. A global optimum is a total assignment that is at least as good as all of the other total assignments. Without systematically searching the other assignments, the algorithm may not know whether the best assignment found so far is a global optimum or whether a better solution exists in a different part of the search space.

When using local search to solve constrained optimization problems, with both hard and soft constraints, it is often useful to allow the algorithm to violate hard constraints on the way to a solution. This is done by making the cost of violating a hard constraint some large, but finite value.

Continuous Domains

For optimization with continuous domains, a local search becomes more complicated because it is not obvious what the possible successor of a total assignment are.

For optimization where the evaluation function is continuous and differentiable, gradient descent can be used to find a minimum value, and gradient ascent can be used to find a maximum value. Gradient descent is like walking downhill and always taking a step in the direction that goes down the most; this is the direction a rock will tumble if let loose. The general idea is that the successor of a total assignment is a step downhill in proportion to the slope of the evaluation function hh. Thus, gradient descent takes steps in each direction proportional to the negative of the partial derivative in that direction.

https://artint.info/2e/html/ArtInt2e.Ch4.S9.SS2.html