LocalSearch.ppt

LocalandStochasticSearch basedonRussGreiner snotes ADifferentApproach Sofar systematicexploration Explorefullsearchspace possibly usingprincipledpruning A Bestsuchalgorithms IDA canhandle10100states 500binary valuedvariables ballparkfiguresonly but somereal worldproblemhave10 000to100 000variables1030 000statesWeneedacompletelydifferentapproach LocalSearchMethodsorIterativeImprovementMethods LocalSearchMethods ApplicablewhenseekingGoalState don tcarehowtogetthere E g N queens mapcoloring VLSIlayout planning scheduling TSP time tabling Many most realOperationsResearchproblemsaresolvedusinglocalsearch E g Deltaairlines RandomSearch Select random initialstate initialguessatsolution MakelocalmodificationtoimprovecurrentstateRepeatStep2untilgoalstatefound oroutoftime Requirements generatearandom probably not optimal guessevaluatequalityofguessmovetootherstates well definedneighborhoodfunction anddotheseoperationsquickly Example 4Queen States 4queensin4columns 256states Operators movequeenincolumnGoaltest noattacksEvaluation h n numberofattacks Example GraphColoring StartwithrandomcoloringofnodesChangecolorofonenodestoreduce ofconRepeat2 Hill Climbing IfContinuous But ProblemswithHillClimbing ProblemswithHillClimbing Foothills LocalOptimal Noneighborisbetter butnotatglobaloptimum Maze mayhavetomoveAWAYfromgoaltofind best solution Plateaus Allneighborslookthesame 8 puzzle perhapsnoactionwillchange oftilesoutofplace Ridge goinguponlyinanarrowdirection SupposenochangegoingSouth orgoingEast butbigwingoingSEIgnoranceofthepeak AmIdone Issues TheGoalistofindGLOBALoptimum HowtoavoidLOCALoptima Howlongtoplateauwalk Whentostop Climbdownhill When LocalSearchExample SAT Manyreal worldproblemscanbetranslatedintopropositionallogic AvBvC BvCvD Av CvD solvedbyfindingtruthassignmenttovariables A B C thatsatisfiestheformulaApplicationsplanningandschedulingcircuitdiagnosisandsynthesisdeductivereasoningsoftwaretesting SatisfiabilityTesting Best knownsystematicmethod Davis PutnamProcedure 1960 Backtrackingdepth firstsearch DFS throughspaceoftruthassignments withunit propagation GreedyLocalSearch GSAT GSAT 1 Guessrandomtruthassignment2 Flipvalueassignedtothevariablethatyieldsthegreatest ofsatisfiedclauses Note Flipevenifnoimprovement 3 Repeatuntilallclausessatisfied orhaveperformed enough flips4 Ifnosat assignfound repeatentireprocess startingfromadifferentinitialrandomassignment Systematicvs Stochastic Systematicsearch DPsystematicallychecksallpossibleassignments Candetermineiftheformulaisunsatisfiable Stochasticsearch Oncewefindit we redone Guidedrandomsearchapproach Can tdetermineunsatisfiability GSATvs DPonHardRandomInstances WhatMakesaSATProblemHard Supposewehavenvariablestowritemclauseswithkvariableseach Wenegatetheresultingvariablesrandomly flipanunbiasedcoin Whatisthenumberofpossiblesentencesintermsofn m andk Whatiftherearemanyvariablesandonlyasmallernumberofclauses Whatiftherearemanyclausesandonlyasmallernumberofvariables PhaseTransition For3 SATm n4 3 overconstrained nearlyallsentencesunsat m n 4 26 criticallyconstrained needtosearch PhaseTransition Under constrainedproblemsareeasy justguessanassignment Over constrainedproblemsareeasy justsay unsatisfiable ofteneasytoverifyusingDavis Putnam Atam nratioofaround4 26 thereisaphasetransitionbetweenthesetwodifferenttypesofeasyproblems Thistransitionsharpensasnincreases Forlargen hardproblemsareextremelyrare insomesense ImprovementstoBasicLocalSearch Issue Howtomovemorequicklytosuccessivelybetterplateaus Avoid gettingstuck localminima Idea Introduceuphillmoves noise toescapefromplateaus localminimaNoisestrategies 1 SimulatedAnnealingKirkpatricketal 1982 Metropolisetal 19532 MixedRandomWalkSelmanandKautz1993 SimulatedAnnealing PickarandomvariableIfflipimprovesassignment doit Elseflipwithprobabilityp e T goingthewrongway ofadditionalclausesbecomingunsatisfiedT temperature Highertemperature greaterchanceofwrong waymoveSlowlydecreaseTfromhightemperaturetonear0 Q WhatispasTtendstoinfinity asTtendsto0 For 0 SimulatedAnnealingAlgorithm NotesonSA Noisemodelbasedonstatisticalmechanics introducedasanaloguetophysicalprocessofgrowingcrystalsKirkpatricketal 1982 Metropolisetal 1953Convergence 1 W exponentialschedule willconvergetoglobaloptimum2 Nomore preciseconvergencerate RecentworkonrapidlymixingMarkovchains Keyaspect upwards sidewaysmovesExpensive but ifhaveenoughtime canbebestHundredsofpapers year Manyapplications VLSIlayout factoryscheduling PureWalkSat PureWalkSat formula GuessinitialassignmentWhileunsatisfieddoSelectunsatisfiedclausec Xiv Xjv XkSelectvariablevinunsatisfiedclausecFlipv Example MixingRandomWalkwithGreedyLocalSearch Usualissues TerminationconditionsMultiplerestartsValueofpdeterminedempirically byfindingbestsettingforproblemclass Findingthebestvalueofp WalkSat p W probp flipvarinunsatisfiedclauseW prob1 p makeagreedyfliptominimize ofunsatisfiedclausesQ Whatvalueforp Let Q p c bequalityofusingWalkSat p onproblemc Q p c Timetoreturnanswer or 1ifWalkSat p return correct answerwithin5minutesand0otherwise or perhapssomecombinationofboth Then findpthatmaximizetheaverageperformanceofWalkSat p onasetofchallengeproblems ExperimentalResults HardRandom3CNF TimeinsecondsEffectiveness prob thatrandominitialassignmentleadstoasolution Completemethods suchasDP upto400variablesMixedWalkbetterthanSimulatedAnnealingbetterthanBasicGSATbetterthanDavis Putnam OvercomingLocalOptimumandPlateau RandomrestartsSimulatedannealingMixed inrandomwalkTabusearch preventrepeatedstates Others Geneticalgorithms programming OtherTechniques randomrestarts restartatnewrandomstateafterpre defined oflocalsteps DonebyGSAT tabu preventreturningquicklytosamestate Implement Keepfixedlengthqueue tabulist Addmostrecentsteptoqueue dropoldeststep Nevermakestepthat soncurrenttabulist Example withouttabu flipv1 v2 v4 v2 v10 v11 v1 v10 v3 withtabu length5 possiblesequence flipv1 v2 v4 v10 v11 v1 v3 Tabuverypowerful competitivew simulatedannealingorrandomwalk dependingonthedomain GeneticAlgorithms AclassofprobabilisticoptimizationalgorithmsAgeneticalgorithmmaintainsapopulationofcandidatesolutionsfortheproblemathand andmakesitevolvebyiterativelyapplyingasetofstochasticoperatorsInspiredbythebiologicalevolutionprocessUsesconceptsof NaturalSelection and GeneticInheritance Darwin1859 OriginallydevelopedbyJohnHolland 1975 Examples Recipe Tofindoptimalquantityofthreemajoringredients sugar wine sesameoil denotingounces Useanalphabetof1 9denotingounces Solutionsmightbe1 1 1 2 1 4 3 3 1 TheAlgorithm Randomlygenerateaninitialpopulation Selectparentsand reproduce thenextgenerationEvaluatethefitnessofthenewgenerationReplacetheoldgenerationwiththenewgenerationRepeatstep2though4tilliterationN StochasticOperators Cross overdecomposestwodistinctsolutionsandthenrandomlymixestheirpartstoformnovelsolutionsMutationrandomlyperturbsacandidatesolution 1010111 1100011 Parent1 Parent2 1010011 1100110 Child1 Child2 Mutation GeneticAlgorithmOperatorsMutationandCrossover Examples Mutation Therecipeexample 1 2 3maybechangedto1 3 3or3 2 3 ParameterstoadjustHowoften Howmanydigitschange Howbig Mo