Slide 1ReferencesSlide 3Introduction To Genetic Algorithms (GAs)History Of Genetic AlgorithmsDarwin’s Theory of EvolutionBiological BackgroundOperation of Genetic AlgorithmsInitializationSelectionSimple Example for Genetic AlgorithmsMethodology Associated with GAsA Single Loop thru a Number of Evolving PopulationsNature Vs Computer - MappingEncoding Using StringEncoding MethodsEncoding Methods (contd.)Slide 18Slide 20Slide 21Slide 22Fitness FunctionExample Of SelectionRoulette Wheel Selection (Fitness-Proportionate Selection)Tournament SelectionTournament Selection (Pseudo Code)ElitismRank SelectionHierarchical SelectionCrossoverCrossoverSlide 33Slide 34Slide 35Crossover (contd.)MutationExample Of MutationRecombinationRecombinationCrossover Vs MutationSimple Genetic Algorithm (Reproduction Cycle)Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64ObjectiveTypes of data miningPattern RepresentationPatternsPattern Templates and EvaluationThe Genetic AlgorithmExplicit Rule PatternDistribution Shift PatternSlide 73Slide 74Advantages of GAs (contd.)Questions ?Genetic Algorithms Team Members for Presentation1. Durga Mahesh Arikatla2. Rajiv Raja3. Manikant Pachineelam4. Kannan Dhanasekaran Professor: Dr. Anita Wasilewska Presented on 05/04/2006ReferencesD. E. Goldberg, ‘Genetic Algorithm In Search, Optimization And Machine Learning’, New York: Addison – Wesley (1989)Kalyanmoy Deb, ‘An Introduction To Genetic Algorithms’, Sadhana, Vol. 24 Parts 4 And 5.‘DATA MINING Concepts and Techniques’ Jiawei Han, Micheline Kamber Morgan Kaufman Publishers, 2003 http://docserver.ingentaconnect.com/deliver/connect/tandf/08839514/v10n6/s5.pdf?expires=1146764654&id=28870440&titleid=37&accname=SUNY+at+Stony+Brook%2C+Main+Library&checksum=F6D024A9C53BBF577C7A1D1C315D8075http://www.tjhsst.edu/~ai/AI2001/GA.HTMhttp://www.rennard.org/alife/english/gavintrgb.htmlhttp://citeseer.ist.psu.edu/cache/papers/cs/27564/http:zSzzSzwww.cs.msstate.eduzSz~bridgeszSzpaperszSznissc2000.pdf/fuzzy-data-mining-and.pdfhttp://citeseer.ist.psu.edu/cache/papers/cs/3487/http:zSzzSzwww.quadstone.co.ukzSz~ianzSzaikmszSzkdd96a.pdf/flockhart96genetic.pdfIntroduction To Genetic Algorithms (GAs)Concepts & Algorithmic AspectsApplication Areas & A Case StudyConclusionsPresentation SummaryIntroduction To Genetic Algorithms (GAs) - History of Genetic Algorithms- Darwin’s Theory of Evolution- Biological Background- Operation of Genetic Algorithm- Simple Example of Genetic Algorithms- Methodology associated with Genetic AlgorithmsHistory Of Genetic Algorithms“Evolutionary Computing” was introduced in the 1960s by I. Rechenberg.John Holland wrote the first book on Genetic Algorithms ‘Adaptation in Natural and Artificial Systems’ in 1975. In 1992 John Koza used genetic algorithm to evolve programs to perform certain tasks. He called his method “Genetic Programming”.Darwin’s Theory of Evolution “problems are solved by an evolutionary process resulting in a best (fittest) solution (survivor) , -In Other words, the solution is evolved” 1. Inheritance – Offspring acquire characteristics 2. Mutation – Change, to avoid similarity 3. Natural Selection – Variations improve survival 4. Recombination - CrossoverBiological BackgroundChromosome All Living organisms consists of cells. In each cell there is a same set of Chromosomes. Chromosomes are strings of DNA and consists of genes, blocks of DNA. Each gene encodes a trait, for example color of eyes. Reproduction During reproduction, recombination (or crossover) occurs first. Genes from parents combine to form a whole new chromosome. The newly created offspring can then be mutated. The changes are mainly caused by errors in copying genes from parents. The fitness of an organism is measure by success of the organism in its life (survival)Operation of Genetic Algorithms Two important elements required for any problem before a genetic algorithm can be used for a solution are Method for representing a solutionex: string of bits, numbers, character Method for measuring the quality of any proposed solution, using fitness functionex: Determining total weight Sequence of steps 1. Initialization 2. Selection 3. Reproduction 4. TerminationInitialization Initially many individual solutions are randomly generated to form an initial population, covering the entire range of possible solutions (the search space) Each point in the search space represents one possible solution marked by its value( fitness) There are no of ways in which we would find a suitable solution and they don’t provide the best solution. One way of finding solution from search space is Genetic Algorithms.Selection A proportion of the existing population is selected to bread a new bread of generation. ReproductionGenerate a second generation population of solutions from those selected through genetic operators: crossover and mutation. Termination A solution is found that satisfies minimum criteria Fixed number of generations found Allocated budget (computation, time/money) reached The highest ranking solution’s fitness is reaching or has reachedSimple Example for Genetic Algorithms NP Complete problems Problems in which it is very difficult to find solution, but once we have it, it is easy to check the solution. Nobody knows if some faster algorithm exists to provide exact answers to NP-problems. An example of alternate method is the genetic algorithm. Example: Traveling salesman problem.Methodology Associated with GAsBeginInitialize populationOptimum Solution?T=T+1SelectionCrossoverMutation NEvaluate SolutionsYStopT =0A Single Loop thru a Number of Evolving PopulationsSimple_Genetic_Algorithm(){Initialize the Population;Calculate Fitness Function;While(Fitness Value != Optimal Value){Selection;//Natural Selection, Survival Of FittestCrossover;//Reproduction, Propagate favorable characteristicsMutation;//MutationCalculate Fitness Function;}}Nature Vs Computer - MappingNature ComputerPopulationIndividualFitnessChromosomeGeneReproductionSet of solutions.Solution to a problem.Quality of a solution.Encoding for a Solution.Part of the encoding