Local Searchwalksat,ant colonies,and genetic algorith：当地searchwalksat蚁群算法与遗传算法

1、Local Search:walksat, ant colonies, and genetic algorithmsTonightCourse evaluationsLocal searchFinal examIssueHow to search really large spaces1030,000 + statessystematic search hopeless!Local searchiterative repair, hill climbing, gradient descent, guess a start staterepeat until satisfied: make sm

2、all changemove to a local neighborExamplesLearning weights in a neural networkSpace: set of weightsNeighborhood: small deltaLearning CPTs in a Bayesian networkEM algorithmThese are optimization problems what about local search for decision problems?N-QueensN-Queens DemoGSATGuess a random truth assig

3、nmentwhile (#unsat clauses 0)flip a variable that minimizes number of unsatisfied clausesRoom for improvementLess dramatic performance on structured problems (e.g. planning)Too greedy can become stuck in local minimaSolution: allow some “uphill” moves many different strategies possibleSimulated anne

4、alingTabu listsAlternate GSAT + random flipsRandom WalkGuess a random truth assignmentwhile (#unsat clauses 0)pick an unsat clauseflip any variable in the clause Suppose clauses are of length 2; what is probably a flip is “correct”?Solves 2-SAT in O(n2) time!Greediness + RandomnessIf clause length 2

5、, then pure random walk is very unlikely to convergeSuppose we random walk greedily?WalksatGuess a random truth assignmentwhile (#unsat clauses 0)pick an unsat clausewith probability p flip a variable that minimizes number of newly-unsatisfied clauses otherwise flip any variable in clause Walksat re

6、sultsBest known method for many problemsgraph coloring(certain) planning problemshard random problemsFor many (all?) other domains, can mix random walk & backtrack searchrun backtrack DPLL until time outrestart with new random seed for choosing branching variablesStochastic Backtrack SearchQuasigrou

7、p Completion DemoParallel local searchTechniques considered so far only look at one point on the search space at a timeEasy to run many copies in parallel with different random seedsCalled portfolio approachOften gives super-linear speedup!Run time distributionsOften there is a great variability in

8、run time depending on random seedsAs parallel processes are added, probability of getting a “lucky” short run can increase quickly!Informed parallel searchCan we further improve performance by exchanging information between the parallel processes?Genetic algorithmsAnt colony algorithmsGenetic algori

9、thmsIdea: the genetic code of an individual is a point in the search spacea gene = a dimension in the search spaceReproduction = local movesAsexual reproduction (mutation) = create a child by a small change in the parentSexual reproduction = create a child by mixing genes of two parentsThe GA Cycle

10、of Reproductionreproductionpopulationevaluationmodificationdiscarddeleted membersparentschildrenmodifiedchildrenevaluated childrenA Simple ExampleThe Traveling Salesman Problem:Find a tour of a given set of cities so that each city is visited only oncethe total distance traveled is minimizedRepresen

11、tationRepresentation is an ordered list of citynumbers known as an order-based GA.1) London 3) Dunedin 5) Beijing 7) Tokyo2) Venice 4) Singapore 6) Phoenix 8) VictoriaCityList1 (3 5 7 2 1 6 4 8)CityList2 (2 5 7 6 8 1 3 4)CrossoverCrossover combines inversion andrecombination: * *Parent1 (3 5 7 2 1 6

12、 4 8)Parent2 (2 5 7 6 8 1 3 4)Child (5 8 7 2 1 6 3 4)This operator is called the Order1 crossover.Mutation involves reordering of the list: * *Before: (5 8 7 2 1 6 3 4)After: (5 8 6 2 1 7 3 4)MutationTSP GA Demo TSP Example: 30 CitiesSolution i (Distance = 941)Solution j(Distance = 800)Solution k(Di

13、stance = 652)Best Solution (Distance = 420)Overview of PerformancePractical ApplicationsDesign of small sorting circuitsOptimization of code fragmentsUsed in Windows kernel?Training neural networksCan outperform backpropAirport scheduling(Generally) unanswered questions:Would other local search tech

14、niques work just as well?Is crossover really key?Ant colony optimizationIdea: Each ant in a colony is local search processAnts (processes) communicate by laying down phenoromes at visited states (“this place looked good to me”)When deciding where to move, ants prefer (with some probability) to follo

15、w trail left by other antsPhenorome eventually “evaporates”Real antsWhy might it work?More “intelligent” noiseAnt B t10Ant A t3gradientgradientnot gradient, but a good alternativeBeyond phenomeronesCombine local gradients to get more global viewAnt B t10Ant A t10gradientgradientmove by weighted sum

16、of Bs own gradient and As gradientDoes it work?Many successful applications in engineering & scienceAppears to outperform single-thread local search procedures for quadratic programmingMore work needed to determine exactly why metaphor works when it does!SummaryLocal search is an important tool for

17、large, complex optimization and decision problemsIdeas: Iterative repairNoise to escape local optimaMuch work on parallel local searchPortfoliosGenetic algorithmsAnt colony optimizationSo.End of the course.Is that all there is?Where was the artificial intelligence?! In my viewAI is the study of gene

18、ral problem-solving strategies“Meta” algorithms 101Life: one damned problem after anotherStrategies evolve at many levelsGenetic “real” evolutionIndividual human logical thinkingSociety spread of innovation UnityA relatively small number of conceptsvarious state-space search strategiessyntactic structure (both formal logic & natural language)learning strategies minimizing entropy, error, complexityarise over and over again in