6  Local Search

Optimization problems

  • In many optimization problems, path is irrelevant; the goal state itself is the solution
  • “Pure optimization” problems
    • All states have an objective function
    • Goal is to find state with max (or min) objective value
    • Does not quite fit into path-cost/goal-state formulation
    • Local search can do quite well on these problems.
  • Then state space = set of “complete” configurations
    • find optimal configuration, e.g., TSP
    • find configuration satisfying constraints, e.g., timetable

Local search algorithms

  • Local search
    • Keep track of single current state
    • Move only to neighboring states
    • Ignore paths
  • Advantages:
    • Use very little memory
    • Can often find reasonable solutions in large or infinite (continuous) state spaces.

State-space landscape

  • An useful landscape has both “location” (defined by the state) and “elevation’” (defined by the value of the heuristic cost function or objective function)

  • A one-dimensional state-space landscape in which elevation corresponds to the objective function

6.2 Simulated Annealing

Simulated Annealing

  • Simulated Annealing = physics inspired twist on random walk
  • A metal alloy or dissolution is heated at high temperatures and progressively cooled in a controlled way
  • If the cooling process is adequate the minimal state of energy of the system is achieved (global minimum)

Algorithm

function Simulated-Annealing(problem, schedule) returns a solution state

inputs: problem, a problem
        schedule, a mapping from time to "temperature"

  current ← Make-Node(problem.Initial-State)
  for t=1 to infinity do
    T ← schedule(t)
    if T = 0 then return current
    next ← a randomly selected successor of current
    DeltaE ← next.Value - current.Value
    if DeltaE > 0 then current ← next
    else current ← next only with probability exp(DeltaE / T)

Physical Interpretation of Simulated Annealing

  • A Physical Analogy:
    • imagine letting a ball roll downhill on the function surface \tothis is like hill-climbing (for minimization)
    • now imagine shaking the surface, while the ball rolls, gradually reducing the amount of shaking \to this is like simulated annealing
  • Annealing = physical process of cooling a liquid or metal until particles achieve a certain frozen crystal state
    • free variables are like particles
    • seek “low energy” (high quality) configuration
    • slowly reducing temp. T with particles moving around randomly

TSP Problem

  • Given a list of cities and the distances
  • What is the shortest possible route \{(x_{1},y_{1}),...,(x_{n},y_{n})\} that visits each city exactly once and returns to the origin city?

  • Intial a list of cities

  • An energy function (sum of the distance among the cities, following the order in the list)

    f=\sum_{i=1}^{n}\sqrt{(x_{i}-x_{i+1})^{2}+(y_{i}-y_{i+1})^{2}}

  • Action: swap two cities

6.4 Genetic Algorithms

Genetic algorithms

  • A genetic algorithm (or GA) is a variant of stochastic beam search in which successor states are generated by combining two parent states rather than by modifying a single state.

  • The analogy to natural selection is the same as in stochastic beam search, except that now we are dealing with sexual rather than asexual reproduction.

  • The GA begins with a set of k randomly generated states, called the population.

  • Each state is rated by the objective function, called the fitness function.

    • Higher values for better state

  • Produce the next generation by “simulated evolution”

    • Random selection
    • Crossover
    • Random mutation

Algorithm

function Genetic-Algorithm(population, Fitness-Fn) returns an individual

inputs: population, a set of individuals
        Fitness-Fn, a function that measures the fitness of an individual

  repeat
    new_population ← empty set
    for i = 1 to SIZE(population) do
      x ← Random-Selection(population, Fitness-Fn)
      y ← Random-Selection(population, Fitness-Fn)
      child ← Reproduce(x, y)
      if (small random probability) then child ← Mutate(child)
      add child to new_population
    population ← new_population
  until some individual is fit enough, or enough time has elapsed
  return the best individual in population, according to Fitness-Fn

function Reproduce(x, y) returns an individual

inputs: x, y, parent individuals

  n ← Length(x);
  c ← random number from 1 to n
  return Append(SubString(x, 1, c), SubString(y, c+1, n))

Illustration

  • Representation of Individuals
    • Each state, or individual, is represented as a string over a finite alphabet – most commonly, a string of 0s and 1s.
    • Alternatively, the state could be represented as 8 digits, each in the range from 1 to 8.
  • The genetic algorithm, illustrated for digit strings representing 8-queens states. The initial population in (a) is ranked by the fitness function in (b), resulting in pairs for mating in (c). They produce offspring in (d), which are subject to mutation in (e).

  • The 8-queens states corresponding to the first two parents in Figure 3(c) and the first offspring in Figure 3(d). The shaded columns are lost in the crossover step and the unshaded columns are retained.

6.5 Local Search in Continuous Spaces

Optimization of Continuous Functions

  • Discrete environments: Use hill-climbing

  • Continuous environments: Use gradient descent

Example

  • Suppose we want to site three airports in Romania:
    • 6-D state space defined by (x_{1},y_{2}), (x_{2},y_{2}), (x_{3},y_{3})
    • Objective function f(\boldsymbol{x})=f(x_{1},y_{2},x_{2},y_{2},x_{3},y_{3}) = sum of squared distances from each city to nearest airport

Gradient descent

  • Discretization methods turn continuous space into discrete space

    • E.g., empirical gradient considers \pm\delta change in each coordinate

  • Gradient descent methods using \nabla f=\left(\frac{\partial f}{\partial x_{1}},\frac{\partial f}{\partial y_{1}},\frac{\partial f}{\partial x_{2}},\frac{\partial f}{\partial y_{2}},\frac{\partial f}{\partial x_{3}},\frac{\partial f}{\partial y_{3}}\right)

  • Init \boldsymbol{x}\gets\boldsymbol{x}_{0}

  • To reduce f, update \boldsymbol{x} \boldsymbol{x}\leftarrow\boldsymbol{x}-\eta\nabla f where \eta is learning rate (0<\eta<1)

  • Newton–Raphson methods update \boldsymbol{x} \boldsymbol{x}\leftarrow\boldsymbol{x}-\eta H^{-1}\nabla f where H is a Hesian matrix

    H=\left(\begin{array}{cccc} \frac{\partial^{2}f}{\partial x_{1}\partial x_{1}} & \frac{\partial^{2}f}{\partial x_{1}\partial x_{2}} & \cdots & \frac{\partial^{2}f}{\partial x_{1}\partial x_{n}}\\ \frac{\partial^{2}f}{\partial x_{2}\partial x_{1}} & \frac{\partial^{2}f}{\partial x_{2}\partial x_{2}} & \cdots & \frac{\partial^{2}f}{\partial x_{2}\partial x_{n}}\\ \vdots & \vdots & \ddots & \vdots\\ \frac{\partial^{2}f}{\partial x_{n}\partial x_{1}} & \frac{\partial^{2}f}{\partial x_{n}\partial x_{2}} & \cdots & \frac{\partial^{2}f}{\partial x_{n}\partial x_{n}} \end{array}\right)

  • x_{i} approach to the optimal point

6.6 Searching With Nondeterministic Actions

The erratic vacuum world

In the erratic vacuum world, the Suck action works as follows:

  • When applied to a dirty square the action cleans the square and sometimes cleans up dirt in an adjacent square, too.
  • When applied to a clean square the action sometimes deposits dirt on the carpet.
  • The eight possible states of the vacuum world; states 7 and 8 are goal states.

AND–OR search trees

  • In this problem, a Results function that returns a set of possible outcome states

  • The solution to the problem is not a sequence but a contingency plan (also known as a strategy) that specifies what to do depending on what percepts are received

  • The first two levels of the search tree for the erratic vacuum world. State nodes are OR nodes where some action must be chosen. At the AND nodes, shown as circles, every outcome must be handled, as indicated by the arc linking the outgoing branches. The solution found is shown in bold lines.

Algorithm

function And-Or-Graph-Search(problem) returns a conditional plan, or failure
  Or-Search(problem.Initial-State, problem, empty set)

function Or-Search(state, problem, path) returns a conditional plan, or failure
  if problem.Goal-Test(state) then return the empty plan
  if state is on path then return failure
  for each action in problem.Actions(state) do
    plan ← And-Search(Results(state, action), problem, [state | path])
    if plan ≠ failure then return [action | plan]
  return failure

function And-Search(states, problem, path) returns a conditional plan, or failure
  for each s_i in states do
    plan_i ← Or-Search(s_i, problem, path)
    if plan_i = failure then return failure
  return [if s_1 then plan_1
          else if s_2 then plan_2
          else if ...
          else if s_{n-1} then plan_{n-1}
          else plan_n]

6.7 References