Iterative impro ent algorit hm LOCAL SEARCH ALGORITHM MAKE-NOD ATE og with amnesi Hill-climbing (or gradient ascent/desce Example:n-queens
Local search algorithms Chapter 4, Sections 3–4 Chapter 4, Sections 3–4 1 Outline ♦ Hill-climbing ♦ Simulated annealing ♦ Genetic algorithms (briefly) ♦ Local search in continuous spaces (very briefly) Chapter 4, Sections 3–4 2 Iterative improvement algorithms In many optimization problems, path is irrelevant; the goal state itself is the solution Then state space = set of “complete” configurations; find optimal configuration, e.g., TSP or, find configuration satisfying constraints, e.g., timetable In such cases, can use iterative improvement algorithms; keep a single “current” state, try to improve it Constant space, suitable for online as well as offline search Chapter 4, Sections 3–4 3 Example: Travelling Salesperson Problem Start with any complete tour, perform pairwise exchanges Variants of this approach get within 1% of optimal very quickly with thousands of cities Chapter 4, Sections 3–4 4 Example: n-queens Put n queens on an n × n board with no two queens on the same row, column, or diagonal Move a queen to reduce number of conflicts h = 5 h = 2 h = 0 Almost always solves n-queens problems almost instantaneously for very large n, e.g., n = 1million Chapter 4, Sections 3–4 5 Hill-climbing (or gradient ascent/descent) “Like climbing Everest in thick fog with amnesia” function Hill-Climbing( problem) returns a state that is a local maximum inputs: problem, a problem local variables: current, a node neighbor, a node current ← Make-Node(Initial-State[problem]) loop do neighbor ←a highest-valued successor of current if Value[neighbor] ≤ Value[current] then return State[current] current ← neighbor end Chapter 4, Sections 3–4 6
T decreased if T-0ther Properties of simulated annealing ANO E(IXTTIAL-STKTEApro6fem] pr心gpN Simulated annealing Useful to consider state space landscape Hill-climbing contd. GAs evolution:e.g.. real GAs require states encoded as strings (GPs use programs) Genetic algorithms contd. 33548213#1M124445124 24415121-30037751411 encode replication =stochast local beam search generate suc Genetic algorithms ldea:chooesuc randomly,biased towards ood on Problem:qute often,allstates end up on same localhill ldea:keepstates imstead of 1:choose topof all their successor Local beam search 2441s7-2441547 2t52口 132748552132748752 essors from pairs of states
Hill-climbing contd. Useful to consider state space landscape state current objective function state space global maximum local maximum "flat" local maximum shoulder Random-restart hill climbing overcomes local maxima—trivially complete Random sideways moves escape from shoulders loop on flat maxima Chapter 4, Sections 3–4 7 Simulated annealing Idea: escape local maxima by allowing some “bad” moves but gradually decrease their size and frequency function Simulated-Annealing( problem,schedule) returns a solution state inputs: problem, a problem schedule, a mapping from time to “temperature” local variables: current, a node next, a node T, a “temperature” controlling prob. of downward steps current ← Make-Node(Initial-State[problem]) for t ← 1 to ∞ do T ← schedule[t] if T = 0 then return current next ←a randomly selected successor of current ∆E ← Value[next] – Value[current] if ∆E > 0 then current ←next else current ←next only with probability e ∆ E/T Chapter 4, Sections 3–4 8 Properties of simulated annealing At fixed “temperature” T, state occupation probability reaches Boltzman distribution p(x) = αe E(x) kT T decreased slowly enough =⇒ always reach best state x ∗ because e E(x ∗) kT /e E(x) kT = e E(x ∗)−E(x) kT 1 for small T Is this necessarily an interesting guarantee?? Devised by Metropolis et al., 1953, for physical process modelling Widely used in VLSI layout, airline scheduling, etc. Chapter 4, Sections 3–4 9 Local beam search Idea: keep k states instead of 1; choose top k of all their successors Not the same as k searches run in parallel! Searches that find good states recruit other searches to join them Problem: quite often, all k states end up on same local hill Idea: choose k successors randomly, biased towards good ones Observe the close analogy to natural selection! Chapter 4, Sections 3–4 10 Genetic algorithms = stochastic local beam search + generate successors from pairs of states 32252124 Selection Cross−Over Mutation 24415124 32752411 24748552 20 23 24 32543213 11 14% 26% 29% 31% 24415124 32752411 24748552 32752411 24415411 32752124 24752411 32748552 24415417 24752411 32748152 Fitness Pairs Chapter 4, Sections 3–4 11 Genetic algorithms contd. GAs require states encoded as strings (GPs use programs) Crossover helps iff substrings are meaningful components + = GAs 6= evolution: e.g., real genes encode replication machinery! Chapter 4, Sections 3–4 12
Continuous state spaces
Continuous state spaces Suppose we want to site three airports in Romania: – 6-D state space defined by (x1, y2), (x2, y2), (x3, y3) – objective function f(x1, y2, x2, y2, x3, y3) = sum of squared distances from each city to nearest airport Discretization methods turn continuous space into discrete space, e.g., empirical gradient considers ±δ change in each coordinate Gradient methods compute ∇f = ∂f ∂x1 , ∂f ∂y1 , ∂f ∂x2 , ∂f ∂y2 , ∂f ∂x3 , ∂f ∂y3 to increase/reduce f, e.g., by x ← x + α∇f(x) Sometimes can solve for ∇f(x) = 0 exactly (e.g., with one city). Newton–Raphson (1664, 1690) iterates x ← x − H−1 f (x)∇f(x) to solve ∇f(x) = 0, where Hij = ∂ 2 f/∂xi∂xj Chapter 4, Sections 3–4 13