AdvancedComputerGraphics-Virginia：先进的计算机图形-弗吉尼亚

《AdvancedComputerGraphics-Virginia：先进的计算机图形-弗吉尼亚》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、AdvancedComputerGraphicsSpring2002ProfessorBroganSimulatedAnnealingMonteCarloapproachforminimizingmultivariatefunctionsMonteCarlo=Random=StochasticRequiresone‘goodness’metric–resultofevaluationfunctionMultivariate–selectsmultipleparametervaluestominimizeevaluationfunctionAl

2、gorithmOutlineSelectsomeinitialguessofevaluationfunctionparameters:x0Evaluateevaluationfunction,E(x0)=vComputearandomdisplacement,x’0TheMonteCarloeventEvaluateE(x’0)=v’Ifv’

3、tisAnnealing?Usedtotreatwork-hardenedpartsmadeoutoflow-carbonsteelsHeattoaspecifictemperature,thensoak,andthencoolslowlyThermodynamics–moleculescanmovearoundwhentheyareathightemps.SlowcoolingpermitsselforganizationintominimumenergyconfigurationsBacktoourSituationWeapproxima

4、tenature’salignmentofmoleculesbyallowinguphilltransitionsexp(-E/kT)BoltzmannProbabiltyDistributionEvenwhenTissmall,adisruptionispossibleexp(-(E2-E1)/kT)MetropolisStepTherateatwhichTisdecreasedandtheamountitisdecreasedisprescribedbyanannealingscheduleWhathavewegot?Alwaysm

5、ovedownhillifpossibleSometimesgouphillOptimalityguaranteedwithslowannealingscheduleNoneedforsmoothsearchspaceNoderivativesCanbediscretesearchspaceTravelingsalesmanproblemOptimizationGiven:Whatvalueofminimizesf()?Expensivetocomputerf()?Expensivetocomputepartialsoff()=Jacobia

6、n?Globalvs.localsolutionsConstrainedOptimizationMinimizeSubjectto:ThereareapriorilimitationsonthepossiblevaluesoftheindependentvariablesLinearProgrammingSpecialtypeofconstrainedoptimizationFunctionf()andconstraintsarelinear