Previous Up Next

13.4  Introduction to Local Search

13.4.1  Changing Tentative Values

From a technical point of view, the main difference between tree search and local (or move-based) search is that tree search adds assignments while local search changes them. During tree search constraints get tightened when going down the tree, and this is undone in reverse order when backing up the tree to a parent node. This fits well with the idea of constraint propagation.

It is characteristic of local search that a move produces a small change, but it is not clear what effect this will have on the constraints. They may become more or less satisfied. We therefore need implementations of the constraints that monitor changes rather than propagate instantiations.

Local search can be implemented quite naturally in ECLiPSe using the repair library. In essence, the difference between implementing tree search techniques and local search in ECLiPSe is that, instead of instantiating variables during search, local search progresses by changing tentative values of variables. For the satisfiability example of the last section, we can change min_conflicts to local_search by simply replacing the guess predicate by the predicate move: 

local_search(Vars) :-
    conflict_constraints(cs,List), 
    ( List = [] -> 
        set_to_tent(Vars)
    ; List = [Constraint|_] ->
        term_variables(Constraint,[Var|_]),
        move(Var),
        local_search(Vars)
    ).

move(Var) :-
    Var tent_get Value,
    NewValue is (1-Value),
    Var tent_set NewValue.

There is no guarantee that this move will reach a better assignment, since NewValue may violate more constraints than the original Value.

13.4.2  Hill Climbing

To find a neighbour which overall increases the number of satisfied constraints we could replace local_search with the predicate hill_climb: 

hill_climb(Vars) :-
    conflict_constraints(cs,List), 
    length(List,Count),
    ( Count = 0 -> 
          set_to_tent(Vars) 
    ; try_move(List,NewCount), NewCount < Count ->
          hill_climb(Vars)
    ;
          write(’local optimum: ’), writeln(Count)
    ).

try_move(List,NewCount) :-
      select_var(List,Var),
      move(Var),
      conflict_constraints(cs,NewList), 
      length(NewList,NewCount).

select_var(List,Var) :-
    member(Constraint,List),
    term_variables(Constraint,Vars),
    member(Var,Vars).

Some points are worth noticing:

The code for try_move is very inefficient, because it repeatedly goes through the whole list of conflict constraints to count the number of constraints in conflict. The facility to propagate tentative values supports more efficient maintenance of the number constraints in conflict. This technique is known as maintenance of invariants (see [18]). For the propositional satisfiability example we can maintain the number of satisfied clauses to make the hill climbing implementation more efficient.

The following program not only monitors each clause for conflict, but it also records in a boolean variable whether the clause is satisfied. Each tentative assignment to the variables is propagated to the tentative value of the boolean. The sum of the boolean BSum records for any tentative assignment of the propositional variables, the number of satisfied clauses. This speeds up hill climbing because, after each move, its effect on the number of satisfied clauses is automatically computed by the propagation of tentative values. 

prop_sat_2(Vars) :-
    Vars = [X1,X2,X3],
    tent_init(Vars),
    clause_cons(X1 or neg X2 or X3,B1),
    clause_cons(neg X1 or neg X2,B2),
    clause_cons(X2 or neg X3,B3),
    BSum tent_is B1+B2+B3,
    hill_climb_2(Vars,BSum).

clause_cons(Clause,B) :- 
    Clause $= 1 r_conflict cs,
    B tent_is Clause.

hill_climb_2(Vars,BSum) :-
    conflict_constraints(cs,List),
    BSum tent_get Satisfied,
    ( List=[] -> 
          set_to_tent(Vars) 
    ; select_var(List,Var), move(Var), tent_get(BSum) > Satisfied ->
          hill_climb_2(Vars,BSum)
    ;
          write(’local optimum: ’), writeln(Count)
    ).

To check whether the move is uphill, we retrieve the tentative value of BSum before and after the move is done. Remember that, since the move operator changes the tentative values of some variable, the tent_is primitive will automatically update the BSum variable.

This code can be made more efficent by recording more invariants, as described in [28].

Local search can be implemented in ECLiPSe with the repair library. Invariants can be implemented by tentative value propagation using tent_is/2.
Figure 13.4: Local Search and Invariants
Previous Up Next