Artificial Intelligence 22C 145
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 19 page Class Notes was uploaded by Dr. Humberto Beier on Friday October 23, 2015. The Class Notes belongs to 22C 145 at University of Iowa taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/228051/22c-145-university-of-iowa in ComputerScienence at University of Iowa.
Reviews for Artificial Intelligence
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/23/15
22c145 Artificial Intelligence Fall 2005 Informed Search and Exploration III Cesare Tinelli The University of Iowa Copyright 200105 Cesare Tinelli and Hantao Zhang 8 8 These notes are copyrighted material and may not be used in other course settings outside of the University of Iowa in their current or modified form without the express written permission of the copyright holders 22c145 Artificial Intelligence Fall 05 p1139 Readings l Chap 4 of Russell and Norvig 2003 22c145 Artificial Intelligence Fall 05 p2139 Iterative Improvement Algorithms I In many optimization problems the goal state itself is the solution I The state space is a set of complete configurations I Search is about finding the optimal configuration as in TSP or just a feasible configuration as in scheduling problems I In such cases one can use iterative improvement or local search algorithms I An evaluation or objective function h must be available that measures the quality of each state I Main Idea Start with an initial configuration and make small changes to it that improve its quality 22c145 Artificial Intelligence Fall 05 p3139 Local Search The Landscape Metaphor l Ideally the evaluation function h should be monotonic the closer a state to an optimal goal state the better its hvalue l Each state can be seen as a point on a surface I The search consists in moving on the surface looking for its highest peaks or lowest valleys the optimal solutions 22c145 Artificial Intelligence Fall 05 p4139 Local Search Example TSP l TSP Travelling Salesperson Problem I h length of the tour I Strategy Start with any complete tour perform painvise exchanges 22c145 Artificial Intelligence Fall 05 p5139 Local Search Example TSP l TSP Travelling Salesperson Problem I h length of the tour I Strategy Start with any complete tour perform painvise exchanges Variants of this approach get within 1 of optimal very quickly with thousands of cities 22c145 Artificial Intelligence Fall 05 p5139 Local Search Example nqueens I Put n queens on an n gtlt n board with no two queens on the same row column or diagonal l h number of conflicts l Strategy Move a queen to reduce number of conflicts 22c145 Artificial Intelligence Fall 05 p6139 Local Search Example nqueens I Put n queens on an n gtlt n board with no two queens on the same row column or diagonal l h number of conflicts l Strategy Move a queen to reduce number of conflicts h5 h2 h0 Almost always solves nqueens problems almost instantaneously for very large n eg n 106 22c145 Artificial Intelligence Fall 05 p6139 HillClimbing or Gradient Descent Search Like climbing Everest in thick fog with amnesia function HILLCLIMBINGprobIem returns a state that is a local maximum inputs problem a problem local variables current a node neighbor a node currentlt MAKENODEINITIALSTATEprobem loop do neighborlt a highestvalued successor of current if VALUEneighbor lt VALUECurrent then return STATEcurrent current lt neighbor end 22c145 Artificial Intelligence Fall 05 p7139 HillClimbing Shortcomings l Depending on the initial state it can get stuck on local maxima I It may converge very slowly I In continuous spaces choosing the stepsize is nonobvious obj ectiVj function global maximum shoulder local maximum quot atquot local maximum stats space current State 2201145 Artificial Intelligence Fall 05 p8139 Hill Climbing Improvements Various possible alternatives l Restart from a random point in the space I Expand up to m gt 1 generations of descendants before choosing best node I Allow downhill moves sometimes I Keep n gt 1 nodes in the fring at each step 22c145 Artificial Intelligence Fall 05 p9139 Beyond Hill Climbing Simulated Annealing Search l Allows occasional downhill steps to minimize the probability of getting stuck in a local maximum l Downhill steps taken randomly but with probability that decreases with time l Probability controlled by a given annealing schedule for a temperature parameter T I If schedule lowers T slowly enough search will end in a global maximum I It may take several tries with test problems to devise a good annealing schedule 22c145 Artificial Intelligence Fall 05 p10139 Simulated Annealing Algorithm function SIMULATEDANNEALINGprobem 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 lt MAKENODEINITIALSTATEprobem for tlt 1 to 00 do T lt scheduet if T 0 then return current next lt a randomly selected successor of current AElt VALUEnext VALUEcurrent if AE gt 0 then currentlt next else current lt next only With probability 6A ET Erratum In first if replace T 0 with T 0 or sGOALSTATEcurrent 22c145 Artificial Intelligence Fall 05 p11139 Properties of Simulated Annealing l The smaller iAEi the greater eA TE the greater T the greater AE 6T I At fixed temperature T state occupation probability reaches Boltzman distribution T decreased slowly enough gt always reach best state I This is not necessarily an interesting guarantee I Devised by Metropolis et al 1953 for physical process modelling l V dely used in VLSI layout airline scheduling etc 22c145 Artificial Intelligence Fall 05 p12139 Beyond Hill Climbing Local Beam Search l Idea keep k states instead of 1 choose top k of all their successors I Not the same as k searches run in parallel Searches that find good states recruit other searches to join them I Problem quite often all k states end up on same local maximum l Solution choose k successors randomly biased towards good ones I Observe the close analogy to natural selection 22c145 Artificial Intelligence Fall 05 p13139 Beyond Hill Climbing Genetic Algorithms l Inspired by Darwin s theory of natural selection I Each state is seen as an individual in a population I A genetic algorithm applies selection and reproduction operators to an initial population l The aim is to generate individuals that are most successful according to a given fitness function I It is basically a stochastic local beam search but with successors generated from pairs of states I Local maxima are avoided by giving a nonzero chance of reproduction to lowscoring individuals 22c145 Artificial Intelligence Fall 05 p14139 The Basic Genetic Algorithm function GENETICALGORITHM population FITNESSFN returns an individual inputs population a set of individuals FITNESSFN a function that measures the tness of an individual repeat parents SELECTION population FITNESSFN population REPRODUCTION parents until some individual is t enough return the best individual in population according to FITNESSFN 22c145 Artificial Intelligence Fall 05 p15139 Genetic Algorithms Classic Approach l Each state is represented by a finite string over a finite alphabet l Each character in the string is a gene l The selection mechanism is randomized with the probability of selection proportional to the fitness measure I Reproduction is accomplished by crossover and mutation 24748552 24 31 E52411 327482 a b C d e Initial Population Fitness Function Selection Croerver Mutation 22c145 Artificial Intelligence Fall 05 p16139 Encodings for Genetic Algorithms Choosing the right encoding of state configurations to strings is crucial Crossover helps only if substrings are meaningful components that can be reassembled into a new meaningful configuration Note GAs are not evolution eg real genes encode replication machinery 22c145 Artificial Intelligence Fall 05 p17139
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'