Local Search Introduction Local Search

3y ago
44 Views
4 Downloads
1.42 MB
33 Pages
Last View : 18d ago
Last Download : 2m ago
Upload by : Giovanna Wyche
Transcription

Local SearchIntroductionLocal SearchSometimes we don’t need the path that reaches a solution, we searchin the space of solutionsWe want to obtain the best attainable solution in an affordable time(optimal is impossible)We have a function that evaluates the quality of the solution, thisvalue is not related to a path costSearch is performed from an initial solution that we try to improveusing actionsThe actions allow to move in the solution neigbourhood\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20101 / 33

Local SearchIntroductionLocal searchThe heuristic function:Approximates the quality of a solution (it is not a cost)The goal is to optimize it (maximize or minimize)Combines all the elements of the problem and its constraints (possiblyusing different weights for different elements)There are no constrains about how the function can be, it only has torepresent the quality relations among the solutionsIt can be positive or negative\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20102 / 33

Local SearchIntroductionQuality FunctionLocal SearchCurrent SolutionSolutions Space\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20103 / 33

Local SearchIntroductionLocal SearchThe size of the space of solutions doesn’t allow for an optimalsolution searchIt is not possible to perform a systematic searchThe heuristic function is used to prune the space of solutions(solutions that don’t need to be explored)Usually no history of the search path is stored (minimal spacecomplexity)\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20104 / 33

Local SearchHill ClimbingHill climbingFirst-choice Hill climbingFirst action that improves the current solution is takenSteepest-ascent hill climbing, gradient searchThe best action that improves the current solution is taken\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20105 / 33

Local SearchHill ClimbingHill ClimbingAlgorithm: Hill ClimbingCurrent initial stateEnd falsewhile not End doSuccessors generate successor(Current)Successors sort and prune bad solutions(Successors, Current)if not empty?(Successors) thenCurrent best successor(Successors)elseEnd trueendendOnly are considered successors those solutions with a heuristic function valuebetter than the current solution (pruning of the space of solutions)A stack could be used to store the best successors to backtrack, but usuallythe space requirement are prohibitiveThe algorithm may not find any solution even when there are\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20106 / 33

Local SearchHill ClimbingHill climbingThe characteristics of the heuristic function and the initial solutiondetermine the success and the time of the searchThe strategy of this algorithm may end the search in a solution that isonly apparently the optimalProblemsLocal optima: No neighbor solution has a better valuePlateaus: All neighbours have the same valueRidge: A sequence of local optima\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20107 / 33

Local SearchHill ClimbingHill climbingPossible solutionsBacktrack to a previous solution and follow another path (it is onlypossible if we limit the memory used for backtracking, Beam Search)Restart the search from another initial solution looking for a bettersolution (Random-restarting Hill-Climbing )Use two or more actions to explore deeper the neighbourhood aftermaking any decision (expensive in time and space)Parallel Hill-Climbing (for instance: divide the search space in regionsand explore the most promising ones, possibly sharing information)\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20108 / 33

Local SearchHill ClimbingHill Climbing - Example - Knapsack problem\ CBY:DakeSolution: Any combination of objects inside the knapsackInitial solution: Empty knapsackOperators: Put objects in and take objects from the knapsackPP ValueiHeuristic Function: max i Valuei or max i Weighti\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/20109 / 33

Local SearchHill ClimbingHill Climbing - Example - Knapsack problemh(n) 88 /5Kg8 /5Kgh(n) 77 /6Kg12 /10Kg6 /4Kg7 /6Kg16Kg2 /1Kgh(n) 12Sol Inicial3 /1Kg12 /10Kg.\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201010 / 33

Local SearchHill ClimbingHill Climbing - Example - Knapsack problemh(n) 208 /5Kg12 /10Kg8 /5Kgh(n) 197 /6Kg7 /6Kg12 /10Kg12 /10Kg6 /4Kg12 /10Kg2 /1Kg3 /1Kgh(n) 186 /4Kg12 /10Kg.\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201011 / 33

Local SearchHill ClimbingHill Climbing - Example - Knapsack problemh(n) 247 /6Kg12 /10Kg2 /1Kg3 /1Kg8 /5KgOptimal12 /10Kgh(n) 238 /5Kg3 /1Kg6 /4Kg8 /5Kg2 /1Kg8 /5Kg7 /6Kg12 /10Kg6 /4Kgh(n) 223 /1Kg8 /5KgFinal Sol12 /10Kg\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201012 / 33

Local SearchOther AlgorithmsOther local search algorithmsThere are other local search algorithms with different inspirations likephysics or biology:Simulated annealing: Stochastic Hill-climbing inspired in thecontrolled cooling of metal alloys and substances dissolutionGenetic Algorithms: Parallel stochastic Hill-climbing inspired in themechanism of natural selectionBut also Particle Swarm Optimization, Ant Colony Optimization,Intelligent Water Drop, Gravitational search algorithm, .\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201013 / 33

Local SearchSimulated AnnealingSimulated AnnealingStochastic Hill-Climbing (a successor is randomly chosen from theneighbor solutions using a probability distribution, the successor couldhave worst evaluation than the current solution)A random walk of the space of solutions is performedInspired in the physics of controlled annealing (crystallization, metalalloys tempering)A metal alloy or dissolution is heated at high temperatures andprogressively cooled in a controlled wayIf the cooling process is adequate the minimal state of energy of thesystem is achieved (global minimum)\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201014 / 33

Local SearchSimulated AnnealingSimulated Annealing\ CBY:(LSI-FIB-UPC)\ CBY:DoITPoMS, University of CambridgeArtificial IntelligenceTerm 2009/201015 / 33

Local SearchSimulated AnnealingSimulated Annealing - MethodologyWe have to identify the elements of the problem with the elements ofthe physics analogyTemperature, control parameterEnergy, quality of the solution f (n)Acceptance function, allows to decide if to pick a successor solutionF( f , T ), function of the temperature and the difference of qualitybetween the current solution and the candidate solutionThe lower temperature, the lower the chance to choose a successorwith worst evaluationCooling strategy, number of iterations to perform, how to lower thetemperature and how many successors to explore each temperaturestep\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201016 / 33

Local SearchSimulated AnnealingSimulated annealing - canonical algorithmAlgorithm: Simulated AnnealingAn initial temperature is chosenwhile temperature above zero do// Random walk the space of solutionsfor the chosen number of iterations doNewSol generate random successor(CurrentSol) E f (CurrentSol) f (NewSol)if E 0 thenCurrentSol NewSolelsewith probability e E /T : CurrentSol NewSolendendReduce the temperatureend\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201017 / 33

Local SearchSimulated AnnealingSimulated AnnealingHill ClimbingFunción ObjetivoSimulated AnnealingEspacio de Soluciones\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201018 / 33

Local SearchSimulated AnnealingSimulated Annealing - ApplicationsUsed for combinatorial optimization problems (optimal configurationof a set of components) and continuous optimization (optimal in aN-dimensional space)Adequate for large sized problems in which the global optimal couldbe surrounded by lots of local optimumsAdequate for problems where to find a discriminant heuristic isdifficult (a random choice is as good as any other choice)Applications: TSP, Design of VLSI circuitsProblems: To determine the value of the parameters of the algorithmrequires experimentation (sometimes very extensive)\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201019 / 33

Local SearchSimulated AnnealingSimulated annealing - Example - TSPTraveler salesman problem (TSP): Search space N!Possible actions to change a solution: Inversions, translation,interchangeAn energy function (Sum of the distance among the cities, followingthe order in the solution)n qqX22E (xi xi 1 ) (yi yi 1 ) (xN x1 )2 (yN y1 )2i 1We should define an initial temperature (experimentation)We should determine the number of iterations for each temperaturestep and how is the temperature decreased\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201020 / 33

Local SearchSimulated AnnealingSimulated annealing - Example - TSP1h(n) 10012Swap(2,3)354h(n) 1202Swap(5,3)3512It1OK4h(n) t4OK3544h(n) 90h(n) 98KOSwap(2,5)21KO Swap(3,3)12It5354h(n) 99\ CBY:(LSI-FIB-UPC)Artificial Intelligence5It634h(n) 101Term 2009/201021 / 33

Local SearchGenetic AlgorithmsGenetic AlgorithmsInspired in the mechanisms of natural selectionAll living things adapt to environment because of the characteristicsinherited from their parentsThe probability of survival and reproduction is related to the quality ofthese characteristics (fitness of the individual to the environment)The combination of good individuals could result in better adaptedindividualsWe can translate this analogy to local searchThe solutions are individualsThe fitness function indicates the quality of the solutionCombining good solutions we could obtain better solutions\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201022 / 33

Local SearchGenetic AlgorithmsGenetic algorithms (II)To solve a problem using GA we need:To code the characteristics of the solutions (for example as a binarystring)A function that measures the quality of a solution (fitness function)Operators that combine solutions to obtain new solutions (crossoveroperations)The number of individuals in the initial populationAn strategy about how to match the individuals\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201023 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - CodingUsually the coding of the individuals is a binary string (it is notalways the best)0[00 11 10 01]12[0,3,2,1]3The coding defines the size of the search space and the crossoveroperators that are needed\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201024 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - OperatorsThe combination of individuals is done using crossover operatorsThe basic operator is the one-point crossoverA cutting point in the coding is chosen randomlyThe information of the two individuals is interchanged using this point[000 101 010 001 100 100]\ CBY:(LSI-FIB-UPC)[010 001 100 000 011 101]Artificial Intelligence[000 101 100 000 011 101]Term 2009/201025 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - Operators (II)There are other possibilities:two-points crossoverrandom bit interchangingspecific operators depending on the codingMutation operators:Following the analogy to genetics and reproduction, sometimes a partof the gene changes randomlyThe basic mutation operator is to change with a probability a randomlychosen bit in the coding\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201026 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - MatchingEach step in the search a new generation of individuals is obtainedmaintaining the size of the population constant (N)To obtain the next generation the individuals to combine(intermediate generation) are chosen following a criteria, for example:Each individual is chosen with a probability proportional to its fitnessN random tournaments are performed among pairs of individuals, theindividual that wins is chosenA linear ranking among the individuals is defined using the fitnessfunctionAlways some individuals will appear more that once and some will notappear at all\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201027 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - canonical algorithmThe basics steps of a GA are:N individuals are chosen from the current generation to form theintermediate generation (using a specific criteria)Individuals are paired and for each pair:12With probability (P crossover) the crossover operator is applied andtwo new individuals are obtainedWith probability (P mutation) the new individuals are mutatedThese individuals conform the new generationIterate until the population converges or a specific number of iterationsis performed34The crossover probability has a crucial influence in the diversity of thenext generationThe probability of mutation is always very low to avoid random search\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201028 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - Canonical algorithmP MutP CrossP MutP MutP CrossP MutP MutP CrossP MutP MutP CrossP MutGeneration i\ CBY:(LSI-FIB-UPC)IntermediateGeneration iCrossoverArtificial IntelligenceMutationGeneration i 1Term 2009/201029 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - ApplicationsAre used virtually in any kind of problemThey allow to solve problems that not have a known good heuristicUsually will perform worst than using hill climbing with a goodheuristicApplications: InnumerableProblems: Coding the solutions, find the good parameters of thealgorithm (size of the population, number of iterations, probability ofcrossover and mutation)In some problems GA perform poorly\ CBY:(LSI-FIB-UPC)Artificial IntelligenceTerm 2009/201030 / 33

Local SearchGenetic AlgorithmsGenetic algorithms - ExampleN-queens problemsA solution can be coded as a binary stringIndividual Concat(i 1.N; Binary(column(queeni )))Fitness function number of pairs of queens that attack each otherCrossover operator one-point crossoverSel

Local Search Simulated Annealing Simulated Annealing - Methodology We have to identify the elements of the problem with the elements of the physics analogy Temperature, control parameter Energy, quality of the solution f(n) Acceptance function, allows to decide if to pick a successor solution

Related Documents:

However, when a consumer is engaged in local search, he or she is generally a bit further down the funnel: 43% of local search leads to a walk-in of Americans use local search to find a local 66% business 88% of mobile search queries lead to a purchase within 24 hours Thus, a local search that contains the word restaurant

Paid vs. Organic Search Search Engine Marketing (SEM) is a term used to describe the various means of marketing a website via search engines, and entails both organic search engine optimization and paid search strategies. Organic search is based on unpaid, natural rankings determined by search engine algorithms, and can be optimized

abstract, but not the full-text. To access the full-text, search the DDUH/TCD Library catalogues 5. Search Limits Limit your search in the search tab at the top of your search results. 6. Advanced search / Search Manager . The Cochrane Library consists of 6 distinct databases: Cochrane Database of Systematic Reviews (Cochrane Reviews)

With your search results displayed, click the “Search/Browse” drop-down menu and select within results. Type a new search expression in the Search Expression field . Click Go. CCH IntelliConnect searches for your new search expression within the search results of the selected search, and your results display .

The results displayed on a search engine include paid search ads and organic (or un-paid) search links. Online advertisers pay the search engine for all impressions or clicks to their ads, but do not pay for organic search links. Importantly, search ads always appear at the top of the page, followed by organic search links (see Figure1).

Both paid search advertising and organic search engine optimization are essential tools to help you show up in search engine results. SEARCH 93% Of consumers begin on a search engine.13 75% Of searchers never scroll past the first page of search results.14 50% Paid search ads provide 50% incremental clicks even when a business ranks #1 for

consumers conduct local searches 4 on search engines. They search on: in5 Computer/ Tablet 88% 84% Smartphone CONSUMERS SEARCH WITH LOCAL INTENT ACROSS DEVICESWHAT WE FOUND Base: Used device to search for information on most recent vertical purchase (n 115-233 for smartphone, n 333-437 for computer/tablet) Google/Ipsos Survey Q8.

The search algorithms we have seen so far include systematic search (breadth-first, depth-first, iterative deepening, etc.) where we look at the entire search space in a systematic manner till we have found a goal (or all goals, if we have to). We also have seen heuristic search (best-first, A*-search) where we compute