ITCS 3153 Artificial IntelligenceSubproblemsGenetic Algorithms (GAs)Genetic AlgorithmsCrossoverMutationGA AnalysisSlide 8Continuous SpacesIn terms of searching?Derivative directs future stepsAn ExampleAirport ExampleSlide 14Computing the GradientDerivative = 0 at Max/MinNewton-RaphsonBut we’re not finding Zero of f(x)HessianNewton RaphsonOnline SearchesSlide 22Learning in Online SearchITCS 3153Artificial IntelligenceLecture 7Lecture 7Informed SearchesInformed SearchesLecture 7Lecture 7Informed SearchesInformed SearchesSubproblems•Is 4-piece subproblem an admissible heuristic?Is 4-piece subproblem an admissible heuristic?–it can never overestimate the true costit can never overestimate the true cost•Is it consistent?Is it consistent?–h(n) <= c(n, a, n’) + h(n’)h(n) <= c(n, a, n’) + h(n’)•Is 4-piece subproblem an admissible heuristic?Is 4-piece subproblem an admissible heuristic?–it can never overestimate the true costit can never overestimate the true cost•Is it consistent?Is it consistent?–h(n) <= c(n, a, n’) + h(n’)h(n) <= c(n, a, n’) + h(n’)Genetic Algorithms (GAs)Another randomized search algorithmAnother randomized search algorithmStart with k initial guessesStart with k initial guesses•they form a they form a populationpopulation•each each individualindividual from the population is a fixed-length string from the population is a fixed-length string (gene)(gene)•each individual’s each individual’s fitness fitness is evaluatedis evaluated•successors are generated from individuals according to successors are generated from individuals according to fitness functionfitness function results resultsAnother randomized search algorithmAnother randomized search algorithmStart with k initial guessesStart with k initial guesses•they form a they form a populationpopulation•each each individualindividual from the population is a fixed-length string from the population is a fixed-length string (gene)(gene)•each individual’s each individual’s fitness fitness is evaluatedis evaluated•successors are generated from individuals according to successors are generated from individuals according to fitness functionfitness function results resultsGenetic Algorithms•ReproductionReproduction–ReuseReuse–CrossoverCrossover•MutationMutation•ReproductionReproduction–ReuseReuse–CrossoverCrossover•MutationMutationCrossover•Early states are diverseEarly states are diverse–Crossover explores state broadlyCrossover explores state broadly•Later stages are more similarLater stages are more similar–Crossover fine tunes in small regionCrossover fine tunes in small region•Early states are diverseEarly states are diverse–Crossover explores state broadlyCrossover explores state broadly•Later stages are more similarLater stages are more similar–Crossover fine tunes in small regionCrossover fine tunes in small region}Like simulated annealingMutationCould screw up a good solutionCould screw up a good solution•Like metropolis step in simulated annealingLike metropolis step in simulated annealingCould explore untapped part of search spaceCould explore untapped part of search spaceCould screw up a good solutionCould screw up a good solution•Like metropolis step in simulated annealingLike metropolis step in simulated annealingCould explore untapped part of search spaceCould explore untapped part of search spaceGA AnalysisCombinesCombines•uphill tendencyuphill tendency•random explorationrandom exploration•exchange information between multiple threadsexchange information between multiple threads–like stochastic beam searchlike stochastic beam searchCrossover is not needed – theoreticallyCrossover is not needed – theoretically•if starting states are sufficiently randomif starting states are sufficiently randomCombinesCombines•uphill tendencyuphill tendency•random explorationrandom exploration•exchange information between multiple threadsexchange information between multiple threads–like stochastic beam searchlike stochastic beam searchCrossover is not needed – theoreticallyCrossover is not needed – theoretically•if starting states are sufficiently randomif starting states are sufficiently randomGA AnalysisIt’s all in the representationIt’s all in the representation•GA works best if representation stores related pieces of the GA works best if representation stores related pieces of the puzzle in neighboring cells of stringpuzzle in neighboring cells of string•Not all problems are amenable to crossoverNot all problems are amenable to crossover–TSPTSPIt’s all in the representationIt’s all in the representation•GA works best if representation stores related pieces of the GA works best if representation stores related pieces of the puzzle in neighboring cells of stringpuzzle in neighboring cells of string•Not all problems are amenable to crossoverNot all problems are amenable to crossover–TSPTSPContinuous SpacesWhat does continuous mean to you?What does continuous mean to you?What does continuous mean to you?What does continuous mean to you?A function is continuous if its graph can be drawn without A function is continuous if its graph can be drawn without lifting the pencil from the paper Descartelifting the pencil from the paper DescarteA function is continuous if its graph can be drawn without A function is continuous if its graph can be drawn without lifting the pencil from the paper Descartelifting the pencil from the paper DescarteIn terms of searching?Continuous search spaces have neighbors for all Continuous search spaces have neighbors for all statesstatesThat means they have derivativesThat means they have derivativesCan the derivative help out here?Can the derivative help out here?Continuous search spaces have neighbors for all Continuous search spaces have neighbors for all statesstatesThat means they have derivativesThat means they have derivativesCan the derivative help out here?Can the derivative help out here?Derivative directs future stepsOne dimensional functionOne dimensional function•Left or right?Left or right?Two dimensional functionTwo dimensional function•Direction in 3-spaceDirection in 3-spaceN-dimensional functionN-dimensional function•GradientGradientOne dimensional functionOne dimensional function•Left or right?Left or right?Two dimensional functionTwo dimensional function•Direction in 3-spaceDirection in 3-spaceN-dimensional functionN-dimensional