/AI-Advanced-Search-Algorithms

Implementation of Artificial Intelligence advanced search algorithms

Primary LanguagePythonMIT LicenseMIT

AI-Advanced-Search-Algorithms

Implementation of Artificial Intelligence advanced search algorithms

Hill climbing

Very simple idea: Start from some state s, Move to a neighbor t with better score. Repeat.

Question: What’s a neighbor?

• (vaguely) Problems tend to have structures. A small change produces a neighboring state. • The neighborhood must be small enough for efficiency • Designing the neighborhood is critical. This is the real ingenuity – not the decision to use hill climbing.

Question: Pick which neighbor?

The best one (greedy)

Question: What if no neighbor is better than the current state?

Stop. (Doh!)

Hill climbing algorithm

  1. Pick initial state s
  2. Pick t in neighbors(s) with the largest f(t)
  3. IF f(t) <= f(s) THEN stop, return s
  4. s = t. GOTO 2.

Simulated annealing

Simulated annealing algorithm

  1. Pick initial state s
  2. Randomly pick t in neighbors(s)
  3. IF f(t) better THEN accept st.
  4. ELSE /* t is worse than s */
  5. accept st with a small probability
  6. GOTO 2 until bored.

current = Initial-State(problem) for t = 1 to infinit do

  • T = Schedule(t) ; // T is the current temperature, which is monotonically decreasing with t
  • if T=0 then return current ; //halt when temperature = 0
  • next = Select-Random-Successor-State(current)
  • deltaE = f(next) - f(current) ; // If positive, next is better than current. Otherwise, next is worse than current.
  • if deltaE > 0 then current = next; // always move to a better state
  • else current = next with probability p = exp(deltaE / T); // as T -> 0, p -> 0; as deltaE -> -infinit , p -> 0
    end

Simulated Annealing issues

• Cooling scheme important
• Neighborhood design is the real ingenuity, not the decision to use simulated annealing.
• Not much to say theoretically
• With infinitely slow cooling rate, finds global optimum with probability 1.
• Proposed by Metropolis in 1953 based on the analogy that alloys manage to find a near global minimum energy state, when annealed slowly.
• Easy to implement.
• Try hill-climbing with random restarts first!