Genetic Algorithms: A Tutorial

2y ago
209.81 KB
33 Pages
Last View : 1m ago
Last Download : 2y ago
Upload by : Arnav Humphrey

Genetic Algorithms:A Tutorial“Genetic Algorithms aregood at taking large,potentially huge searchspaces and navigatingthem, looking for optimalcombinations of things,solutions you might nototherwise find in alifetime.”- Salvatore ManganoComputer Design, May 1995Wendy WilliamsMetaheuristic Algorithms1Genetic Algorithms: ATutorial

The Genetic Algorithm Directed search algorithms based onthe mechanics of biological evolutionDeveloped by John Holland, Universityof Michigan (1970’s)To understand the adaptive processes ofnatural systems To design artificial systems software thatretains the robustness of natural systems Wendy WilliamsMetaheuristic Algorithms2Genetic Algorithms: ATutorial

The Genetic Algorithm(cont.) Provide efficient, effective techniquesfor optimization and machine learningapplicationsWidely-used today in business,scientific and engineering circlesWendy WilliamsMetaheuristic Algorithms3Genetic Algorithms: ATutorial

Classes of SearchTechniquesS e a rc h te c h n iq u e sC a lc u lu s - b a s e d t e c h n iq u e sD ir e c t m e t h o d sF in o n a c c iG u id e d ra n d o m s e a rc h te c h n iq u e sI n d ir e c t m e t h o d sN e w to nE v o lu tio n a ry a lg o rith m sE v o lu t io n a r y s t r a t e g ie sWendy WilliamsMetaheuristic AlgorithmsD y n a m ic p r o g r a m m in gG e n e tic a lg o rith m sP a ra lle lC e n tra liz e dS im u la t e d a n n e a lin gE n u m e r a t iv e t e c h n iq u e sS e q u e n tia lD is trib u te d4S te a d y -s ta teG e n e ra tio n a lGenetic Algorithms: ATutorial

Components of a GAA problem to solve, and . Encoding technique(gene, chromosome) Initialization procedure(creation) Evaluation function(environment) Selection of parents(reproduction) Genetic operators(mutation, recombination) Parameter settings(practice and art)Wendy WilliamsMetaheuristic Algorithms5Genetic Algorithms: ATutorial

Simple GeneticAlgorithm{initialize population;evaluate population;while TerminationCriteriaNotSatisfied{select parents for reproduction;perform recombination and mutation;evaluate population;}}Wendy WilliamsMetaheuristic Algorithms6Genetic Algorithms: ATutorial

The GA Cycle fiedchildrenparentspopulationevaluated childrenevaluationdeletedmembersdiscardWendy WilliamsMetaheuristic Algorithms7Genetic Algorithms: ATutorial

PopulationpopulationChromosomes could be: Bit stringsReal numbersPermutations of elementLists of rulesProgram elements. any data structure .Wendy WilliamsMetaheuristic Algorithms(0101 . 1100)(43.2 -33.1 . 0.0 89.2)(E11 E3 E7 . E1 E15)(R1 R2 R3 . R22 R23)(genetic programming)8Genetic Algorithms: ATutorial

arents are selected at random withselection chances biased in relation tochromosome evaluations.Wendy WilliamsMetaheuristic Algorithms9Genetic Algorithms: ATutorial

ChromosomeModificationchildrenmodificationmodified children Modifications are stochastically triggeredOperator types are: Mutation Crossover (recombination)Wendy WilliamsMetaheuristic Algorithms10Genetic Algorithms: ATutorial

Mutation: LocalModification Before:(1 0 1 1 0 1 1 0)After:(0 1 1 0 0 1 1 0)Before:(1.38 -69.4 326.44 0.1)After:(1.38 -67.5 326.44 0.1)Causes movement in the search space(local or global)Restores lost information to the populationWendy WilliamsMetaheuristic Algorithms11Genetic Algorithms: ATutorial

Crossover:RecombinationP1P2*(0 1 1 0 1 0 0 0)(1 1 0 1 1 0 1 0)(0 1 0 0 1 0 0 0)(1 1 1 1 1 0 1 0)C1C2Crossover is a critical feature of geneticalgorithms: It greatly accelerates search early inevolution of a population It leads to effective combination of schemata(subsolutions on different chromosomes)Wendy WilliamsMetaheuristic Algorithms12Genetic Algorithms: ATutorial

Evaluationevaluatedchildren modifiedchildrenevaluationThe evaluator decodes a chromosome andassigns it a fitness measureThe evaluator is the only link between aclassical GA and the problem it is solvingWendy WilliamsMetaheuristic Algorithms13Genetic Algorithms: ATutorial

Deletionpopulationdiscarded membersdiscard Generational GA:entire populations replaced with each iterationSteady-state GA:a few members replaced each generationWendy WilliamsMetaheuristic Algorithms14Genetic Algorithms: ATutorial

An Abstract ExampleDistribution of Individuals in Generation 0Distribution of Individuals in Generation NWendy WilliamsMetaheuristic Algorithms15Genetic Algorithms: ATutorial

A Simple Example“The Gene is by far the most sophisticated program around.”- Bill Gates, Business Week, June 27, 1994Wendy WilliamsMetaheuristic Algorithms16Genetic Algorithms: ATutorial

A Simple ExampleThe Traveling Salesman Problem:Find a tour of a given set of cities so thateach city is visited only once the total distance traveled is minimized Wendy WilliamsMetaheuristic Algorithms17Genetic Algorithms: ATutorial

RepresentationRepresentation is an ordered list of citynumbers known as an order-based GA.1) London2) Venice3) Dunedin4) SingaporeCityList1(3 5 7 2 1 6 4 8)CityList2(2 5 7 6 8 1 3 4)Wendy WilliamsMetaheuristic Algorithms5) Beijing 7) Tokyo6) Phoenix 8) Victoria18Genetic Algorithms: ATutorial

CrossoverCrossover combines inversion andrecombination:**Parent1(3 5 7 2 1 6 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.Wendy WilliamsMetaheuristic Algorithms19Genetic Algorithms: ATutorial

MutationMutation involves reordering of the list:Before:**(5 8 7 2 1 6 3 4)After:(5 8 6 2 1 7 3 4)Wendy WilliamsMetaheuristic Algorithms20Genetic Algorithms: ATutorial

TSP Example: 30 0xWendy WilliamsMetaheuristic Algorithms21Genetic Algorithms: ATutorial

Solution i (Distance 941)TSP30 (Performance Wendy WilliamsMetaheuristic Algorithms22Genetic Algorithms: ATutorial

Solution j(Distance 800)TSP30 (Performance Wendy WilliamsMetaheuristic Algorithms23Genetic Algorithms: ATutorial

Solution k(Distance 652)TSP30 (Performance Wendy WilliamsMetaheuristic Algorithms24Genetic Algorithms: ATutorial

Best Solution (Distance 420)TSP30 Solution (Performance Wendy WilliamsMetaheuristic Algorithms25Genetic Algorithms: ATutorial

Overview ofPerformanceTSP30 - Overview of 5791113151719Generations (1000)Wendy WilliamsMetaheuristic Algorithms26212325272931BestWorstAverageGenetic Algorithms: ATutorial

Considering the GATechnology“Almost eight years ago .people at Microsoft wrotea program [that] usessome genetic things forfinding short codesequences. Windows 2.0and 3.2, NT, and almostall Microsoft applicationsproducts have shippedwith pieces of codecreated by that system.”- Nathan Myhrvold, Microsoft AdvancedTechnology Group, Wired, September 1995Wendy WilliamsMetaheuristic Algorithms27Genetic Algorithms: ATutorial

Issues for GAPractitioners Choosing basic implementation issues: representationpopulation size, mutation rate, .selection, deletion policiescrossover, mutation operatorsTermination CriteriaPerformance, scalabilitySolution is only as good as the evaluationfunction (often hardest part)Wendy WilliamsMetaheuristic Algorithms28Genetic Algorithms: ATutorial

Benefits of GeneticAlgorithms Concept is easy to understandModular, separate from applicationSupports multi-objective optimizationGood for “noisy” environmentsAlways an answer; answer gets betterwith timeInherently parallel; easily distributedWendy WilliamsMetaheuristic Algorithms29Genetic Algorithms: ATutorial

Benefits of Genetic Algorithms(cont.) Many ways to speed up and improve aGA-based application as knowledgeabout problem domain is gainedEasy to exploit previous or alternatesolutionsFlexible building blocks for hybridapplicationsSubstantial history and range of useWendy WilliamsMetaheuristic Algorithms30Genetic Algorithms: ATutorial

When to Use a GA Alternate solutions are too slow or overlycomplicatedNeed an exploratory tool to examine newapproachesProblem is similar to one that has already beensuccessfully solved by using a GAWant to hybridize with an existing solutionBenefits of the GA technology meet key problemrequirementsWendy WilliamsMetaheuristic Algorithms31Genetic Algorithms: ATutorial

Some GA ApplicationTypesDomainApplication TypesControlgas pipeline, pole balancing, missile evasion, pursuitDesignSchedulingsemiconductor layout, aircraft design, keyboardconfiguration, communication networksmanufacturing, facility scheduling, resource allocationRoboticstrajectory planningMachine LearningSignal Processingdesigning neural networks, improving classificationalgorithms, classifier systemsfilter designGame Playingpoker, checkers, prisoner’s dilemmaCombinatorialOptimizationset covering, travelling salesman, routing, bin packing,graph colouring and partitioningWendy WilliamsMetaheuristic Algorithms32Genetic Algorithms: ATutorial

ConclusionsQuestion:‘If GAs are so smart, why ain’t they rich?’Answer:‘Genetic algorithms are rich - rich inapplication across a large and growing number ofdisciplines.’- David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine LearningWendy WilliamsMetaheuristic Algorithms33Genetic Algorithms: ATutorial

Metaheuristic Algorithms Genetic Algorithms: A Tutorial “Genetic Algorithms are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might not otherwise find in a lifetime.” - Salvatore Mangano Computer Design, May 1995 Genetic Algorithms: A Tutorial

Related Documents:

genetic algorithms, namely, representation, genetic operators, fitness evaluation, and selection. We discuss several advanced genetic algorithms that have proved to be efficient in solving difficult design problems. We then give an overview of applications of genetic algorithms to different domains of engineering design.

The Genetic Code and DNA The genetic code is found in a acid called DNA. DNA stands for . DNA is the genetic material that is passed from parent to and affects the of the offspring. The Discovery of the Genetic Code FRIEDRICH MIESCHER Friedrich Miescher discovered in white blood . The Discovery of the Genetic Code MAURICE WILKINS

2. Genetic Algorithm 2.1. The Principle of Genetic Algorithm In computer science and operations research, genetic algorithm (GA) is a me-thod inspired by the natural selection process and belongs to a larger class of evolutionary algorithms (EA). Genetic algorithms are often used to generate

Memetic Algorithms. The approach combines a hierarchical design technique, Genetic Algorithms, constructive techniques and advanced local search to solve VLSI circuit layout in the form of circuit partitioning and placement. Results obtained indicate that Memetic Algorithms based on local search, clustering and good initial solutions im-

Tutorial Process The AVID tutorial process has been divided into three partsÑ before the tutorial, during the tutorial and after the tutorial. These three parts provide a framework for the 10 steps that need to take place to create effective, rigorous and collaborative tutorials. Read and note the key components of each step of the tutorial .

Tutorial Process The AVID tutorial process has been divided into three partsÑ before the tutorial, during the tutorial and after the tutorial. These three parts provide a framework for the 10 steps that need to take place to create effective, rigorous and collaborative tutorials. Read and note the key components of each step of the tutorial .

Tutorial 1: Basic Concepts 10 Tutorial 1: Basic Concepts The goal of this tutorial is to provide you with a quick but successful experience creating and streaming a presentation using Wirecast. This tutorial requires that you open the tutorial document in Wirecast. To do this, select Create Document for Tutorial from the Help menu in Wirecast.

Government Construction Strategy Implementation Report July 2012 Overview One year on from the launch of the Government Construction Strategy (the Strategy), this publication takes stock of progress to date against the targets it set for reducing the costs of construction to Government, for the reform of the industry and for fostering innovation and growth. The overarching aim is to reduce the .