Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 18 page Class Notes was uploaded by Jonas Bartell on Monday October 26, 2015. The Class Notes belongs to CS1571 at University of Pittsburgh taught by MilosHauskrecht in Fall. Since its upload, it has received 43 views. For similar materials see /class/229381/cs1571-university-of-pittsburgh in ComputerScienence at University of Pittsburgh.
Reviews for INTROTOARTIFICLINTELLIGENCE
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/26/15
CS 1571 Introduction to AI Lecture 10 Finding optimal configurations combinatorial optimization Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Constraint satisfaction problem CSP Constraint satisfaction problem CSP is a configuration search problem where A state is de ned by a set of variables Goal condition is represented by a set constraints on possible variable values Special properties of the CSP allow more speci c procedures to be designed and applied for solving them 381571 Intro to AI M Hauskrecht Example of a CSP N queens Goal n queens placed in nonattacking positions on the board Variables Represent queens one for each column 7 Q15Q25Q35Q4 0 Values 7 Row placement of each queen on the board Q1 21Q2 4 1 2 3 4 C0DStFaintS Q 3 Q J Two queens not in the same row i Qi Q i i i i Two queens not on the same diagonal CS 1571 Intro to AI M Hauskrecht Solving a CSP problem Initial state No variable is assigned a value 0 Operators Assign a value to one of the unassigned variables Goal condition All variables are assigned no constraints are violated Unassigned Q Q2 Q3 7 Q Assigned UnassignedQ2 Q3 Q4 UnassignedQ2 Q3 Q4 Assigned Q1 1 AssignedQ 2 Unassigned ngQA Ega AssignedQi 2v Q2 4 n n CS 1571 Intro to AI M Hauskrecht Solving a CSP problem Search strateg Unassigied QthQsQ 11 Assi ed 7 Unassigied Q2 ngQ Assi ed Q11 o 0 cs 1571 Intrntn AI M quskrechl Solving a CSP problem Search strateg DFS Constraints may be violated earlier Unassxgied QthstyQt Assi ed Unassigied Q2 Q Q Assi ed Q1 2 Unassigied ngQ Assi ed Q1 2sz 7quot Unassigqed Q QOsts 1 Assi ed 1 u cs 1571 Intrntn AI M quskrechl Solving a CSP problem Search strateg DFS Constraints may be violated earlier 7 constraint propagation infers valid and invalid assignments Unassigied QthQhQL 11 Assi ed 7 Unassigied Q2 ngQ Assi ed Q11 o 0 cs 1571 Intrntn AI M quskrechl Constraint propagation Three known techniques for propagating the effects of past assignments and constraints Value propagation Arc consistency Forward checking Difference 7 Completeness of inferences 7 Time complexity of inferences cs 1571 Intrn In AI M quskrechl Solving a CSP problem Search strategy DFS Constraint propagation infers valid and invalid assignments What candidate to expand first in the DFS UnassignedQ2 3 Q3 3 Q4 Assi ned Q1 1 Unassigned Q33Q4 AssignedEQ1 2yQ2 4 cs 1571 Intro to AI Heuristics for CSP Examples map coloring Heu ristics Most constrained variable c RED 7 Country E is the most constrained one cannot use Red Green M Hauskrecht Least constraining value 7 Assume we have chosen variable C 7 Red is the least constraining valid color for the future cs 1571 Intro to AI M Hauskrecht Search for the optimal configuration Objective find the optimal con guration Optimality De ned by some quality measure Quality measure re ects our preference towards each con guration or state CS 1571 Intro to AI M Hauskrecht Example Traveling salesman problem Problem A graph with distances Goal find the shortest tour which Visits every city once and returns to the start An example of a valid tour ABCDEF CS 1571 Intro to AI M Hauskrecht Example N queens A CSP problem can be converted to the optimal con guration problem The quality of a con guration in a CSP the number of constraints violated Solving minimize the number of constraint violations of violations 3 of violations 1 of violations 0 CS 1571 Intro to AI M Hauskrecht Iterative optimization methods Searching systematically for the best configuration with the DFS may not be the best solution Worst case running time Exponential in the number of variables Solutions to large optimal con guration problems are often found using iterative optimization methods Methods Hill climbing Simulated Annealing Genetic algorithms CS 1571 Intro to AI M Hauskrecht Iterative optimization methods Properti s 7 Search the space of complete con gurations 7 Take advantage of local moves Operators make local changes to complete con gurations 7 Keep track of just one state the current state no memory of past states H No search tree is necessary cs 1571 lnlrn In All M quskrecht Example N queens Local operators for generating the next state 7 Select a variable a queen 7 Reallocate its position cs 1571 lnlrn In All M quskrecht Example Traveling salesman problem Local operator for generating the next state divide the existing tour into two parts reconnect the two parts in the opposite order Example ABCDEF B ABCD EF Part 2 I ABCDFE CS 1571 Intro to Al M Hauskrecht Example Traveling salesman problem Local operator 7 generates the next configuration state CS 1571 Intro to AIC M Hauskrecht Searching the configuration space Search algorithms keep only one con guration the current con guration Problem How to decide about which operator to apply CS 1571 Intro to AI M Hauskrecht Search algorithms Two strategies to choose the con guration state to be Visited next 7 Hill climbing 7 Simulated annealing Later Extensions to multiple current states 7 Genetic algorithms Note Maximization is inverse of the minimization min fXcgt max fX CS 1571 Intro to AI M Hauskrecht Hill climbing I one with the best Value m e mm to maximize the Betta Wmse as 1571 mm Al M HauskrscM Hill climbing Always choose the next best successor state stop when no improvement possible mum Momma WW a sumquot the no proIvum t none HnunH Mmmonzt leALVSYAIEImevom h Inn In mt a mghmmhnd ht em ormnw il stuzhmn s VALUELLHHCHH Ilmn v townHm nd tumer as 1571 mm Al M HauskrscM I Hill climbing Look around at states in the local neighborhood and choose the one with the best value value Better Worse states What can go wrong CS 1571 Intro to Al M Hauskrecht Hill climbing Hill climbing can get trapped in the local optimum No more value local improvement Better states What can go wrong CS 1571 Intro to AI M Hauskrecht Hill climbing Hill climbing can get clueless on plateaus value plateau states CS 1571 Intro to Al M Hauskrecht Hill climbing and nqueens The quality of a con guration is given by the number of constraints violated Then Hill climbing reduces the number of constraints Mincon ict strategy heuristic 7 Choose randomly a variable With con icts 7 Choose its value such that it violates the fewest constraints Success But not always The local optima problem CS 1571 Intro to Al M Hauskrecht Simulated annealing Permits bad moves to states with lower value thus escape the local optima Gradually decreases the frequency of such moves and their size parameter controlling it 7 temperature value Always up Sometimes down states CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm The probability of making a move The probability of moving into a state with a higher value is 1 The probability of moving into a state with a lower value is pAccept NEXT 6 where AE ENEXT ECURRENT 7 The probability is Proportional to the energy difference CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm Current con guration Energy E 145 Energy E 167 Energy E 180 Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm AE ENEXT ECURREMquot 145 7167 22 AET ZZT e e A 1 Current con guration P 91 E E 145 nergy Sometimes accept Energy E 167 Energy E 180 Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm Energy E 145 Current con guration AEEMXT ECURREM 1807167 gt 0 pAccept 1 Energy E 167 Energy E 180 Always accept Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm The probability of moving into a state with a lower value is pAccept 6 Where AE ENEXT ECURRENT The probability is 7 Modulated through a temperature parameter T for T gt 00 the probability of any move approaches 1 for T gt 0 the probability that a state with smaller value is selected goes down and approaches 0 Cooling schedule 7 Schedule of changes of a parameter T over iteration steps CS 1571 Intro to AI M Hauskrecht Simulated annealing LAIED7 pm nhlm i lunclinnSlMU aummalpmmm MumMIMI as soliilieosme wame LIL tl39UI 1mnplxlllghnwllmem lamlmmhllc mm to on um Me 139 n icomemlme mulling lhe malailnliuv a lmmimld slcus HNL NH lmexsoun lNlYlALSYAYEIpmHem ll tor m l lo m do 1 Lwrl39n do n elm iiecessei ul comm izluurtl 7 VALUEh39tllrur39ll ilAE v n llILn Cunarer elm limite nm oulyi minimum ES1571MmloAl M Halsme Simulated annealing algorithm Simulated annealing algorithm 7 developed originally for modeling physical processes Metropolis et a1 53 Prop erties 7 Ii T is decreased slowly enough the best conliguration state is always reached Applications 7 VLSI design 7 airline scheduling ES1571MmloAl M Halsme Simulated evolution and genetic algorithms Limitations of simulated annealing 7 Pursues one state con guration at the time 7 Changes to con gurations are typically local Can we do better Assume we have two con gurations with good values that are quite different We expect that the combination of the two individual con gurations may lead to a con guration with higher value Not guaranteed M This is the idea behind genetic algorithms in which we grow a population of individual combinations CS 1571 Intro to AI M Hauskrecht
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'