1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 11Milos [email protected] Sennott SquareFinding optimal configurations IICS 1571 Intro to AIM. HauskrechtAnnouncements• Homework assignment 3 due today• Homework assignment 4 is out– Programming and experiments – Simulated annealing + Genetic algorithm– Competition Course web page:http://www.cs.pitt.edu/~milos/courses/cs1571/2CS 1571 Intro to AIM. HauskrechtSearch for the optimal configurationObjective: • find the optimal configurationOptimality:• Is efined by some quality measure Quality measure• reflects our preference towards each configuration (or state)CS 1571 Intro to AIM. HauskrechtExample: Traveling salesman problemProblem:• 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:ABCDEFABCDEF3CS 1571 Intro to AIM. HauskrechtExample: N queens• A CSP problem can be converted to the ‘optimal’ configuration problem• The quality of a configuration in a CSP= the number of constraints violated• Solving: minimize the number of constraint violations# of violations =0# of violations =3 # of violations =1CS 1571 Intro to AIM. HauskrechtIterative optimization methods• Solutions to large ‘optimal’ configuration problems are often found using iterative optimization methods• Why?– Searching systematically for the best configuration with the search methods covered so far may not be the best solution– Running times of DFS and BFS: • Exponential in the number of variables– Uniform cost or A* algorithms would require• Too many partial solutions are kept active • Iterative Optimization Methods: – ?4CS 1571 Intro to AIM. HauskrechtIterative optimization methodsProperties:– Search the space of “complete” configurations– Take advantage of local moves• Operators make “local” changes to “complete” configurations– Keep track of just one state (the current state)• no memory of past states• !!! No search tree is necessary !!!CS 1571 Intro to AIM. HauskrechtHill climbing• Look around at states in the local neighborhood and choose the one with the best value• Problems: ? valuestatesBetterWorse5CS 1571 Intro to AIM. HauskrechtSimulated 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 – temperature)valuestatesAlways upSometimesdownCS 1571 Intro to AIM. HauskrechtSimulated annealing algorithmThe probability of making a move:• A good move (moving into a state with a higher value)– Probability is 1• A “bad” move (moving into a state with a lower value)–is• Proportional to the energy differenceTEeNEXTAcceptp/)(∆=CURRENTNEXTEEE−=∆where6CS 1571 Intro to AIM. HauskrechtSimulated annealing algorithmCurrent configurationEnergy E =167Energy E =145Energy E =180Energy E =191CS 1571 Intro to AIM. HauskrechtSimulated annealing algorithmTTEeeAcceptp/22/)(−∆==CURRENTNEXTEEE−=∆Current configurationEnergy E =167Energy E =145Energy E =180Energy E =191= 145 – 167 = -22Sometimes accept!7CS 1571 Intro to AIM. HauskrechtSimulated annealing algorithmCURRENTNEXTEEE−=∆Current configurationEnergy E =167Energy E =145Energy E =180Energy E =191= 180– 167 > 01)( =AcceptpAlways accept! CS 1571 Intro to AIM. HauskrechtSimulated annealing algorithmThe probability of moving into a state with a lower value is The probability is:– Modulated through a temperature parameter T:• for the probability of any move approaches 1• for the probability that a state with smaller value is selected goes down and approaches 0 • Cooling schedule:– Schedule of changes of a parameter T over iteration steps TEeAcceptp/)(∆=0→TCURRENTNEXTEEE−=∆∞→Twhere8CS 1571 Intro to AIM. HauskrechtSimulated annealing algorithm• Simulated annealing algorithm– developed originally for modeling physical processes (Metropolis et al, 53)• Properties:– If T is decreased slowly enough the best configuration (state) is always reached• Applications:– VLSI design– airline schedulingCS 1571 Intro to AIM. HauskrechtSimulated evolution and genetic algorithms• Limitations of simulated annealing:– Pursues one state configuration at the time;– Changes to configurations are typically localCan we do better? • Assume we have two configurations with good values that are quite different• We expect that the combination of the two individual configurations may lead to a configuration with higher value(Not guaranteed !!!)This is the idea behind genetic algorithms in which we grow a population of individual combinations9CS 1571 Intro to AIM. HauskrechtGenetic algorithmsAlgorithm idea:• Create a population of random configurations• Create a new population through:– Biased selection of pairs of configurations from the previous population– Crossover (combination) of pairs– Mutation of resulting individuals• Evolve the population over multiple generation cycles• Selection of configurations to be combined:– Fitness function = value functionmeasures the quality of an individual (a state) in the populationCS 1571 Intro to AIM. HauskrechtReproduction process in GA• Assume that a state configuration is defined by a set variableswith two values, represented as 0 or 110CS 1571 Intro to AIM. HauskrechtParametric optimizationOptimal configuration search:• Configurations are described in terms of variables and their values• Each configuration has a quality measure• Goal: find the configuration with the best valueWhen the state space we search is finite, the search problem iscalled a combinatorial optimization problemWhen parameters we want to find are real-valued – parametric optimization problemCS 1571 Intro to AIM. HauskrechtParametric optimizationParametric optimization:• Configurations are described by a vector of free parameters (variables) w with real-valued values • Goal: find the set of parameters w that optimize the quality measure f(w)11CS 1571 Intro to AIM. HauskrechtParametric optimization techniques• Special cases (with efficient solutions):– Linear programming– Quadratic programming• First-order methods:– Gradient-ascent (descent)– Conjugate gradient• Second-order methods:– Newton-Rhapson methods – Levenberg-Marquardt• Constrained