5.Constraint Satisfaction and Local Search

DFBB: Intermediate solutions(Depth-First Branch and Bound )

In order to find an optimal solution of CSP, we use DFBB

Implement

♦ Use lower bound estimate L of the cost of solutions extending the current partial assignment
— underestimates the objective function at each node

♦ Also use a bound B
— overestimates the objective function (globally)
— initialise to infinity (or a known overestimate)

♦ Traverse the search tree e.g. depth first

♦ Backtrack if L≥B

♦ Each time a solution is found, set B to its objective value

♦ B is monotone decreasing as solutions are found

♦ So search tree branches tend to get shorter towards the end

Effect

♦ First solution is at the bottom of the leftmost (complete) branch
— Fast: Likely to be found quickly
— Dirty: Likely to be of low quality

♦ Always trying to improve on the best so far — Any improvement will do

♦ So DFBB produces a sequence of (strictly) improving solutions

♦ We can interrupt the search at any time
— when the current solution is good enough
— when a time limit expires
— when the next process needs to start
— when we just get fed up with waiting

♦ Intermediate solutions are valuable, because optimal ones can be very expensive to compute (and proofs of optimality even more expensive).

1. FD solvers commonly use Depth-First Branch and Bound (DFBB)
   — Use a lower bound L on the objective and an upper bound B
   — Backtrack whenever L ≥ B
   — Revise B whenever a solution is found

2. DFBB fits well with backtracking CSP solution methods.

Local Search

The general idea: search in the space of total assignments.
局部搜索是解决最优化问题的一种元启发式算法,也是一种任一时间算法：即便它运行中被强行中止，也能返回正确的解。

steps:(example for satisfaction)

1. Start with a random assignment of values to all variables (Of course, this doesn’t satisfy all constraints)
2. Repeatedly:
   Choose a variable (random choice is good)
   Revise its value to minimise its constraint violations Stop when all constraints are satisfied or time is up.

Local search___Iterative improvement algorithms

General idea: keep a single “current” state, try to improve it
— perform local moves in the neighbourhood of the current state
— no guarantee of completeness (may fail to find any solution)
— no guarantee of optimality
— no possibility of showing unsatisfiability

Advantage:

1. Small memory requirements, suitable for online as well as offline search.
2. method scales up better than complete search in many domains.

Local search__Hill-climbing(爬山算法)

General idea: Moves to the** best** neighbor.

1. Random-restart hill climbing overcomes local maxima—trivially complete(出现局部最小解后的处理办法)

Local search__Simulated annealing（退火算法）

Idea: escape local maxima by allowing some “bad” moves.
目的：因为一味地取最优值，可能会造成局部最优解。所以我们允许一定概率地取一部分比当前状态较差的值。
这样可能会造成一些坏的影响。

Local search__Large Neighbourhood Search（大规模邻域搜索算法）

Given a current solution:

1. Destroy part of it by forgetting the values of some variables
2. See the problem of assigning values to those variables as a CSP
3. Solve [optimally] using a complete search method such as DFBB

Performance is sensitive to the choice of what to destroy.
The old solution is still in the neighborhood, so there is always a next solution available, given enough search.

What to destroy?
A solution could be partially destroyed by randomly selecting decision vari- ables and forgetting their values—this resembles random decay.

We are more likely to do the partial destruction systematically, to make intuitive sense, say by forgetting the values of all variables that mention two of the machines, or the schedules of a random selection of the employees.

Notice:

1. Local optima are still a problem, as with all local search — random restart is commonly used to escape.

2. We may choose to abstract from the current solution
   — use only some decision variables, for a partial description
   — designed so the rest can be recovered by easy search
   — destroy part of the abstract solution
   — gives the complete search freedom to optimize minor aspects

3. There is always a tradeoff between neighborhood size and speed
   — Large neighborhoods increase the chance of improvement
   — but they may create hard problems for the complete search