Class Note for CMPSCI 683 at UMass(18)
Class Note for CMPSCI 683 at UMass(18)
Popular in Course
Popular in Department
This 11 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 22 views.
Reviews for Class Note for CMPSCI 683 at UMass(18)
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: 02/06/15
Victor Lesser CMPSCI 683 Fall 2004 Local Search HillClimbinglterative Improvement Simulated Annealing Stochastic Hill Climbing Beam Search Genetic Algorithm Vlmltf lm Operate using a single current state Paths followed bysearch are not retained Contrastwrth open and closed node lists searchtree Little memoryrequired usuallya constant Sometimes the path to the goal is irrelevant Squeens problemjobshop scheduling circui design computer con guration automatic programming automatic graph drawing Optimization problems may have no obvious goal test or path cost Continuous functions vrnuamrm Very simple to implement Very little memory is needed Can often find reasonable solutions in very large continuous state spaces for which systematic algorithms are not suitable Vlmltf lm Unsolvability Isthere asolution Start Search with complete but nonoptimal e Systematlc can reclull39e exhaustlve examll latlol l ofexpol iel ltlal s lu n Search space Modify incorrectlnonoptimal solution to e Stochastlc cannot determlrie unsolvablllty move it closer to correctoptimal solution CompletenessOptimality 7 Systematlc complete 7 Stochastlc incomplete Speed 7 Nelther l5 Lil39llformly superlolquot each does better lordlffereritsorts ot problems Local Search is an example of Stochastic Search v uxxicssmrmm 5 v uxxicssmrmm a What is the search space The main iterative improvement algorithm is hillclimbin Search space of complete solutions vs partial g solutions Continually move In the direction of When useful increasmg value of all successor states until a maximum is reached Tradeoff between time to select a move more and Operator to modify complete solution time to reach goal state less This is sometimes called steepest ascent HC S t f me no Ion 0 progress and is called gradient descent search if the evaluation function is based on cost rather than quality reasonable complete solution can be generated Measure of complete Solutlon ll l terms of Col lstl alrlt Vlolatlol ls orari evaluate function v uxxicssmrmm 7 v uxxicssmrmm a A simple form of local search Continually move in the direction of increasing value nhjecm funcunn Alone mmimum Greedy Local search grabs good neighbor 39hrmlder kmvlrm mum without thinking ahead vm39 1an mumhum mm mm uncnl s M v lessercsnm mm v iesemsm mm function HILLCLIMBINGl39 problem returns a slate dial is a local maximum inputs problem a problem locnlvnriables CitTen anode neighbor a node unirem MAKENODEHNITIAL STATE pmblemD loop do Looks at all neighbark a lughestV39alned successor of current successo s if V LL Eneighbur lt VALL1EcmTenL then return STMEL3914W2n 01117511 neighbm39 end L6 G 21 initial sale L G 5 LBGZB lom Add 1 pointh every block Liam esuns on the thing ms supposed In be resnng on seems l pmntfm every blmkthat is mung on the Mung thing eoas Fm each blunklhalhas wecunecl51mmquot s1mrluveo 2 lhe cumplele s1mrluve undemealh n is exacllv as A shame be and 1 puimlur every black m lhe suppun slrucluve Fm each blunklhal has an moaned suppemunme mm une pumlluv werv muck m lhe Exismg suppun slmclure 1 lessercs m mm v lessens mm a h c L4 Gaa LA 546 L4 545 Local criterion results in no available moves that increase evaluation r V 2 quotJr 9 l Pr iwfii h lHJillll 97Jmhib imig39 Can get stuck at a local maximum solution deadend Local maXImum Unable to find its way off a plateau olution deadend X Plateau Cannot climb along a narrow ridge when almost all steps go down continuous space v Lesser cseas F2004 13 RidgeKnife edges l Simulated annealing is a variation of hill climbing in which at the beginning of the process some downhill moves may be made The idea is to do enough exploration of the whole space early on so that the final solution is relatively insensitive to the starting state This should lower the chances of getting caught at a local maximum a plateau or a ridge Randomlyjump to alternative nonlocally optimal moves based on p e39AET more time goes less willing to explore nonoptimal path v Lesser cseas F2004 15 Ways to overcome the weaknesses Stochastic hillclimbing Simulated Annealing choose at random an uphill move among the successors Sometimes take downhill steps You may have to get worse to get better Firstchoice hill climbing generate successors randomly until finding an uphill move Randomrestart hill climbing restart search from randomly generated initial states V Lesser C8683 F2004 14 Sim Lilquot 7 1 Evaluate the initial state If it is also a goal state then return it and quit Otherwise continue with the initial state as the current state 2lnitialize BESTSOFAR as the current state 3lnitialize Taccording to the annealing schedule V Lesser C5683 F2004 16 1 fi 4 Loop until a solmion is found or until there are no new operators left to be applied in the current state a Select an operator randomly that has not yet been applied to the current state and apply it b Evaluate the new state Compute AE value of current value of new state 7 ifttlenewstateis agoal state return It and quit r if It Is not a goal state but Is better than the current state then make It the current state so szsrsonvm this new sate iihetierthan current BESTsoFAR r Kiln blmmthl aumm Illmltml mm jl m vaw pquot c Revise Taccording to the annealing schedule 5 Return BESTSOFAR as the answer v uxxicssmrmm n red it function StM ULAI weltle cALlNutpititileiii schedule mums a solution state inputs pl Db lll a problem Et llt dlllt a mapping from time in ielupemtule local variables Lili39l L Vll Ll node rim 3 node 1 ti ls mpel uiul equot controlling lite prubablllty or duunwtird steps twrrz39rlls1leKENDDEilixlTlALSTATE Lp lb illill fatter 110 as do ieiiihedulelil if T7 0 then return t lAl lYiii mi e i randomly selected successor ottiiiwiil AR VAI lllltlldl7VAi t riivinwil it A gt 0 llten immil H mm else L lll mlli i7 motility with piribaliiliryeA M v uxxlcssmrmm a Keep track of K states rather thanjust one a Modified breadthaflrst contour created dynamically Start with K randomly generated states Stop if any goal state Multiple Successors generated for each of the k states Choose top K successor states in next cycle Contrast with Random Restart 7 Positive quotSharing information across ditterentsearcnes 7 Negative 7 May eliminate diversity coming from random starting points v uxxicssmrmm 19 Beam Search patterned after biological evolution Learning as Search Metaphor of Natural Selection Offspring are similar to their parents The more t are more likely to have children Occasionally random mutations occur v uxxlcssmrmm m Localized Beam Search Speciaiized approacn for generating successors and 39 Saleemquot for seiecting next states More fit members are iikeiy to be in next generation An indiViduai soiution is represented by a sequence of 39 Mutation genes K Tne seiection strategy is randomized Witii probabiiity ct seiection proportionai to fitness indiViduais seiected for reproduction are randomiy Random aitering of cnaracteristics Crossover paired certain genes are crossedoven and some are Combine two members of popuiation quotimam Crossoverisprnbabiytne keyidea v Exploit relative independence 17 certain subpmblem solutions imbedded in diiiereni members wmm 1i mmitsumm 21 What is the fitness function Represent Outlook Overcmt v Ram A WmdSt rong by How is an indiViduaI represented 0mm mm 011 10 LgtSunnyno LgtWeakno How are individuals selected Represent IFWmFStmng THEN PlayTenntxrjie by How do indiViduaIs reproduce Meek Wine Pla enme 111 10 10 wwsmm 2 mmitsumm 2b 1mm Shrugs ammmh D sumg weanmm W umum mmmmm gt WHUWUUU lt mummmm WWW mu Twpa39ntcmmn H m HUMWWU gtUWWUUUU lt mnmmm ummunmm llnilumcvu U Emmi W001 mm W gt WWDWW lt MOE an WMWM Hmmm mmumm gtwmmmn GAF2meuF2meuitbthulipmm mum p p randnm hypntheses mm fvr eachhmP mmpmenmxrh Wh1e maxh mm lt nmwmmm 1 mm Pmbabrhsucally select 1 0p membmfpmdmm lmmag ml 2Plnmmhj z L muuver mbabmsmany salt251 pm nfhypntheses frva Fur each pairh1h2 pruduce twu uffspnng by applymgthe Crussuver 9mm Add a1 uffspnng mpx 3 Mulate Invert a randomly selected bit in m p random members of P5 4 Update P P5 5 Evaluate for each hin P compute Fitnessh Return the hypothesis from P that has the highest lness nmunmum I mi I umnm wmnmum mman 7 mm nmnm anmmmn nummmmw p m mmmm wmmmnn Dawn nummnm WWW WWW We Mew WWW m 9me Numerame m mammscngzgm gm mWmmmmmmmwm WWW mam we mmmmmemuMegan mm mm MWWWWe mgmmmmcwmsmnmmm nemme Fitness proportionate selection Fitnexxthl quot231 nut2 can lead to crowding lack oi diversity Pith Tournament Selection 1310th h at random thn vnttorm probabtltty thn probabllttyp selecttne more ttt Rank Selection Sort all nypotneses by tttness Probabth of selectton 1s proporttonal to rank wwsmm 2 Lean dtsuncttve set at propostttonat rules oompettttve vvtn CA5 Fltness Fitnexxhcwn39ecth Heptesentatlon IF aTn a2F THEN T IF a2T THEN 1F repesented by a1 a 5 a1 a 5 10 I1 1 11 1D I Geneucopaatnts Wmtva1aplelengtnrule sets a solutons Wmtonly Welttonned utstnng nypotneses mnmsumm 17 Start with a a c a a c n10 01 1 11110 0 n01i10 10 010 1 choose Etossovet polnts 10l hegattetblts1v 2 Nowtesttlct palms In n tn those that ptoauce bltsttlngs vvttn wellaetlnea semantlcseg 13 186v Itvvecnoose 1 it Iesultls a1 a 393 a1 a 9 I13 11 10 0 11 10 0 a1 a 393 a1 a 393 I14 00 01 1 10 01 0 wwsmm 1 Add new genetic operators also applied probabilistically 1 Add Alternative generalize constraint on a by changing a Dto 1 2 Drop Condition generalize constraint on a by changing every Dto 1 And add newlield to bitstring to daermine whether to allowthese aagc aagc AADC 011101001010 So nowthe learning strategy evolves mnmsumm 11 Performance of GABIL comparable to symbolic ruldtree learning methods C45 Population of programs represented by ID5R1AQ14 trees sinlx iW y Average performance on a set of12 synthetic problems GABIL withoutAA and DC operators 921 accuracy GABIL AA and DC operators 952 accuracy Symbolic learning methods ranged from 912 to 966 x Determining the set of terminals Determining the set of functions Determining the tness measure gtlt Determining the parameters Determining the method for designating a result and the criterion for terminating a run mnmsumm an 1 TERMINAL SET 1 1mnn1 Dz Dk z FUNCTION SETF F AND OR mum NOR a FITNESS MEASURE Thefnness cam amhe Z39comhinations with unwind in 1 MM aanuamzm fnnass M a Smmssion istha sum ovum Z39fmuss mus with um Manning diaanup hmwem lha Boolean wlue Mum by ha Sexpms39on and ha coma valua Mthetarga Indian Boolean mn panylunnioni OR AND mot no mom mun on m 10R 10R 01 mm mm mom 4 CONTROL PARAMETERS Population Sin M moo 39Generations c 51 5TERMINATION CRITERIA AND RESULT DESIGNATION Tanuinata when tness equals a 239 MRI or mm c 51 genemions 39 D ignal h lGoIal individual as the solution mnmsumm OR NOT an AND on m 10R 10R 01 NOT on mnmsumm mun NOT am NOT n1 More interesting example design electronic Have been app ed to a Wide range of filter circuits problems Individuals are programs that transform beginning circuit to final circuit by Results are sometimes very good and addingsubtracting components and Somet39mes Very Poor39 connections The technique is relatively easy to Use population of 640000 run on 64node apply and in many cases it is beneficial parallel processor to see if it works before thinking about Discovers circuits competitive with best another approach human designs v uxxvcssmrmm M v uxxvcssmrmm 42 RepairDebugging GSAT Interacting Subproblems More on CSP problems texture measures Multilevel Search blackboard v uxxvcssmrmm a
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'