资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,Advanced Computer Graphics,Spring 2002,Professor Brogan,Simulated Annealing,Monte Carlo approach for minimizing multivariate functions,Monte Carlo=Random=Stochastic,Requires one goodness metric result of evaluation function,Multivariate selects multiple parameter values to minimize evaluation function,Algorithm Outline,Select some initial guess of evaluation function parameters:x,0,Evaluate evaluation function,E(x,0,)=v,Compute a random displacement,x,0,The Monte Carlo event,Evaluate E(x,0,)=v,If v v;set new state,x,1,=x,0,Else set x,1,=x,0,with,Prob,(E,T),This is the Metropolis step,Repeat with updated state and temp,What is Annealing?,Used to treat work-hardened parts made out of low-carbon steels,Heat to a specific temperature,then soak,and then cool slowly,Thermodynamics molecules can move around when they are at high temps.Slow cooling permits self organization into minimum energy configurations,Back to our Situation,We approximate natures alignment of molecules by allowing uphill transitions,exp(-E/,kT,),Boltzmann Probabilty,Distribution,Even when T is small,a disruption is possible,exp(-(E,2,-E,1,)/,kT,),Metropolis Step,The rate at which T is decreased and the amount it is decreased is prescribed by an,annealing schedule,What have we got?,Always move downhill if possible,Sometimes go uphill,Optimality guaranteed with slow annealing schedule,No need for smooth search space,No derivatives,Can be discrete search space,Traveling salesman problem,Optimization,Given:,What value of minimizes f()?,Expensive to computer f()?,Expensive to compute partials of f()=,Jacobian,?,Global vs.local solutions,Constrained Optimization,Minimize,Subject to:,There are,a priori,limitations on the possible values of the independent variables,Linear Programming,Special type of constrained optimization,Function f()and constraints are linear,
展开阅读全文