Recall: breadth-first search, step by stepImplementation of search algorithmsRecall: breath-first search, step by stepBreadth-first searchSlide 5Slide 6Depth-first searchSlide 8Slide 9Slide 10Last time: search strategiesSlide 12This timeIterative improvementIterative improvement example: vacuum worldIterative improvement example: n-queensHill climbing (or gradient ascent/descent)Slide 18Hill climbingSlide 20Minimizing energySlide 22Local Minima ProblemConsequences of the Occasional AscentsBoltzmann machinesSimulated annealing: basic ideaBoltzmann’s statistical theory of gasesBoltzmann distributionSimulated annealingReal annealing: SwordSimulated annealing in practiceSlide 32Slide 33Simulated annealing algorithmSlide 35Note on simulated annealing: limit casesSlide 37SummarySlide 39CS 561, Session 71Recall: breadth-first search, step by stepCS 561, Session 72Implementation of search algorithmsFunction General-Search(problem, Queuing-Fn) returns a solution, or failurenodes make-queue(make-node(initial-state[problem]))loop doif nodes is empty then return failurenode Remove-Front(nodes)if Goal-Test[problem] applied to State(node) succeeds then return nodenodes Queuing-Fn(nodes, Expand(node, Operators[problem]))endQueuing-Fn(queue, elements) is a queuing function that inserts a set of elements into the queue and determines the order of node expansion. Varieties of the queuing function produce varieties of the search algorithm.CS 561, Session 73Recall: breath-first search, step by stepCS 561, Session 74Breadth-first searchNode queue: initialization# state depth path cost parent #1 Arad 0 0 --CS 561, Session 75Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1 Arad 0 0 --2 Zerind 1 1 13 Sibiu 1 1 14 Timisoara 1 1 1CS 561, Session 76Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1 Arad 0 0 --2 Zerind 1 1 13 Sibiu 1 1 14 Timisoara 1 1 15 Arad 2 2 26 Oradea 2 2 2(get smart: e.g., avoid repeated states like node #5)CS 561, Session 77Depth-first searchCS 561, Session 78Depth-first searchNode queue: initialization# state depth path cost parent #1 Arad 0 0 --CS 561, Session 79Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #2 Zerind 1 1 13 Sibiu 1 1 14 Timisoara 1 1 11 Arad 0 0 --CS 561, Session 710Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #5 Arad 2 2 26 Oradea 2 2 22 Zerind 1 1 13 Sibiu 1 1 14 Timisoara 1 1 11 Arad 0 0 --CS 561, Session 711Last time: search strategiesUninformed: Use only information available in the problem formulation•Breadth-first•Uniform-cost•Depth-first•Depth-limited•Iterative deepeningInformed: Use heuristics to guide the search•Best first:•Greedy search•A* searchCS 561, Session 712Last time: search strategiesUninformed: Use only information available in the problem formulation•Breadth-first•Uniform-cost•Depth-first•Depth-limited•Iterative deepeningInformed: Use heuristics to guide the search•Best first:•Greedy search -- queue first nodes that maximize heuristic “desirability” based on estimated path cost from current node to goal;•A* search – queue first nodes that minimize sum of path cost so far and estimated path cost to goal.CS 561, Session 713This time•Iterative improvement•Hill climbing•Simulated annealingCS 561, Session 714Iterative improvement•In many optimization problems, path is irrelevant;the goal state itself is the solution.•Then, state space = space of “complete” configurations.Algorithm goal:- find optimal configuration (e.g., TSP), or,- find configuration satisfying constraints(e.g., n-queens)•In such cases, can use iterative improvement algorithms: keep a single “current” state, and try to improve it.CS 561, Session 715Iterative improvement example: vacuum worldSimplified world: 2 locations, each may or not contain dirt,each may or not contain vacuuming agent.Goal of agent: clean up the dirt.If path does not matter, do not need to keep track of it.CS 561, Session 716Iterative improvement example: n-queens•Goal: Put n chess-game queens on an n x n board, with no two queens on the same row, column, or diagonal.•Here, goal state is initially unknown but is specified by constraints that it must satisfy.CS 561, Session 717Hill climbing (or gradient ascent/descent)•Iteratively maximize “value” of current state, by replacing it by successor state that has highest value, as long as possible.CS 561, Session 718Question: What is the difference between this problem and our problem (finding global minima)?CS 561, Session 719Hill climbing•Note: minimizing a “value” function v(n) is equivalent to maximizing –v(n),thus both notions are used interchangeably.•Notion of “extremization”: find extrema (minima or maxima) of a value function.CS 561, Session 720Hill climbing•Problem: depending on initial state, may get stuck in local extremum.CS 561, Session 721Minimizing energy•Let’s now change the formulation of the problem a bit, so that we can employ new formalism:- let’s compare our state space to that of a physical system that is subject to natural interactions,- and let’s compare our value function to the overall potential energy E of the system.•On every updating,we have E 0BCABasin of Attraction for CDECS 561, Session 722Minimizing energy•Hence the dynamics of the system tend to move E toward a minimum. •We stress that there may be different such states — they are local minima. Global minimization is not guaranteed. BCABasin of Attraction for CDECS 561, Session 723Local Minima Problem•Question: How do you avoid this local minima?startingpointdescenddirectionlocal minimaglobal minimabarrier to local searchCS 561, Session 724Consequences of the Occasional AscentsHelp escaping the local optima.desired effectMight pass global optima after reaching it adverse effect(easy to avoid bykeeping track ofbest-ever state)CS 561, Session 725Boltzmann machineshThe Boltzmann Machine of Hinton, Sejnowski, and Ackley (1984)uses simulated annealing to escape local minima.To motivate their solution, consider how one might get a ball-bearing traveling along the curve to "probably end up" in the deepest minimum. The idea is to shake the box "about h hard" — then the ball
View Full Document
Unlocking...