Local Search vs Classical Search

Problem Detail: 

I have some questions regarding local search / optimization as explained in chapter 4 of the book : http://aima.cs.berkeley.edu/

In classical search (Chap 3), the search starts from an initial node, then the search continues based on strategies of BFS, DFS, etc. What I am unsure of is the process of local search (Chap 4).

1. Does the local search algorithm start from one node in state space? Check if constraints are satisfied? If Yes, this is goal? If not, move to neighbours?

2. Is the entire state space considered goal state? Even nodes that don't satisfy the constraints?

3. In optimization, the search is conducted in a part of search space where all constraints are met, but tries to find a better solution. In that case, what if the search algorithm moves to nodes where they don't satisfy the constraints?

Asked By : Martin H. L.

Answered By : Yuval Filmus

Classical local search works as follows. We're trying to optimize some function under some constraints. We start with some feasible point (a point satisfying all constraints). At each step, we consider small changes to the current point which (1) keep it feasible, (2) improve the objective function. If we find such a small change, we modify the point accordingly. Eventually, we reach a local optimum, and we hope that it's not too bad relative to the global optimum.

A classical example is the simplex algorithm for linear programming. The algorithm starts with some feasible point (it's not immediately obvious how to do it; a trick is required). At each step, we try to modify the point by switching one tight constraint with another in a way that improves the objective function while keeping the point feasible. Eventually we reach a local optimum, which turns out to be a global optimum (in this particular case).

The interior-point algorithm for linear programming work differently. They start at some point, and move in a direction that (1) makes the point more feasible, and (2) improves the objective function. In the end, you get close to a feasible local optimum, which turns out to be a global optimum. This is not local search, but it's an example of an algorithm which does not maintain a feasible solution.

Non-oblivious local search is a variant on the theme of local search, in which instead of trying to optimize the actual objective function, you direct the local search using an auxiliary objective function. Sometimes this improves the quality of the local optimum. You can read all about it in a recent PhD thesis by Justin Ward.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10491