local search

so far:

backtracking

change a partial solution until a solution is found or none is proved to exist

constraint propagation

make the consequences of the constraints explicit

generalization

backtracking and constraint propagation are example of two classes of methods:

search

look for a solution

inference

find new constraints or restrict the old ones

local search: first class

local search: principle

mantain a total assigment to all variables
(not partial, like in backtracking)

may satisfy some constraints, but not all

change the value of a single variable
to try to increase the number of satisfied constraints

aim: satisfy all constraints

example of increase

constraints: x<z, y<z, z<k
assigment x=1, y=1, z=0, k=2

change from z=0 in z=2:

one satisfied constraint ⇒ two satisfied constraints

not all satisfied: repeat

when to stop

change to z=1: last constraint satisfied, first two violated

change to k=3: all satisfied

local search: generalization

a total assignment satisfies some constraints, possibly all

changing some values, some constraints may:

• go from satisfied to violated
• go from violated to satisfied

change the assignment to increase the number of satisfied constraints
as much as possible

all satisfied = solution

local search: basic step

current total assignment

consider only the assigments that differ from that only on one variable

switch to the best one among them

cost

cost = number of unsatisfied constraints
(in the current assigment

local search tries to minimize it (zero = solution)

visualization

space of total assigments

local search moves from one to one next to it

completeness

a solution may not be found, even if one exists

local minima: the current assignement cannot be improved by changing a single variable
but a solution that differ on three variables or more exists

example: the current assignment

• violates a constraint
• changing a single variables, the violates constraints becomes two
• a solution that differ on three variables exists

local minima: example

all domains are {0,1,2,3}

constraints:

assigment:

x=0, y=0, z=1, k=1, s=2, r=2

only one violated constraint: z<k

decrease number of violated constraints:
change z or k

z=0

violates x<z and y<z

k=2 or k=3

violates k<s ed k<r

no single variable change decreases the number of violated constraint

yet, a solution exists: x=0,y=0,z=1,k=2,s=3,r=3
differs on three variables

hill climbing

choose the single change resulting in a minimal cost

in the example: only choices that maintain the cost
change to s=3 or r=3

current assigment: x=0, y=0, z=1, k=1, s=2, r=2

changing to s=3: assigment x=0, y=0, z=1, k=1, s=3, r=2
still a violated constraint

k=2 is one of the best moves
assigment x=0, y=0, z=1, k=2, s=3, r=2

with r=3, solution reached

hill climbing

best change of a single variable

disregard cost of current assigment
choose the best among the next around it

still: local minima possible

local minima

domain {0,1,2}

assigment: 0,0,0,1,1,1,1

only one violated constraint: 1<1

change a single variable ⇒ two violated constraints
except with 0,0,0,0,1,1,1
only one violated constraint

again: all changes violate two constraints
except for 0,0,0,1,1,1,1
same assigment as before

solution exists: 0,0,0,1,2,2,2

hill climbing: incompleteness

can be seen in two ways:

• local minima of cost: no single change escapes from it
• algorithm keep doing the same changes over and over
  (central variable: 0 ⇒ 1 → 0…)

variants for solving this problem

constraint weight

from the example:

• when trying to satisfy some violated constraints
  hill climbing tries not to violate others
• satifies the same constraints over and over

way out: weight constraints

• initial cost of each constraint is 1
• choose the change of minimal cost
• violated constraints have their cost increased

constraint weight, on the example

every time a constraint is violated, increase its cost

cross = extra cost 1

best change:

crosses are not removed
only added when the constraint is violated

best change:

change k=0 has the same cost of m=2
assume bad choice: k=0

again:

now the best choice is m=2

now it's easy:

constraint weights: principle

problem with hill climbing:

• many satisfied constraints
• changing one variable violates many
• but they have to be changed to get a solution

weights decrease the importance of these constraints
at some points, they can be violated

tabu search

other solution to cycling over assignments

different principle: avoid repeating the same choices

tabu list

tabu list = last last changes made

avoid repeating a change in the tabu list

tabu list: definition

is actually a fixed-length queue

contains pairs variable = value

queue full = oldest pair removed

tabu search: overall

like hill climbing:

keep a current assigment
consider all possible changes of the value of a variable

unlike hill climbing

every time x is changed to v, put x=v in the queue
never change z to v if x=v is in the queue