New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Artificial Intelligence

by: Dr. Humberto Beier

Artificial Intelligence 22C 145

Marketplace > University of Iowa > ComputerScienence > 22C 145 > Artificial Intelligence
Dr. Humberto Beier
GPA 3.87


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.