Local Search vs Classical Search

Question

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?

Answer 1

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.

Answer 2

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?

A local search would typically start from an arbitrary solution. For example in the case of SAT, each variable could be assigned either a 0 or a 1 with independent equal 1/2 probability. What you describe next is not related to what you start with. But yes, you could then follow a general strategy of checking whether or not you have a feasible solution, and perhaps move on to the neighboring states following some strategy.

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

A goal state is a state which satisfies your constraints. For example in the case of 8-queens, a goal state would be any placement of the queens so that they don't attack each other. All other states are not goal states.

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?

In general, it would be more accurate to say that the search is conducted in the whole search space, which includes all possible states. The rest of your question depends totally on the search method used. For example, you could try to greedily improve on the solution found so far. If you then encounter a solution that is not better anymore, or as you say not even a valid solution, you would return the last known best solution.