Global OptimizationGenetic AlgorithmsOlesyaPeshko
1 Global Optimization Genetic Algorithms Olesya Peshko
OutlineEvolution in biologyAlgorithmProsandconsApplicationsExampleSoftwareMatlabtoolboxes2
2 Outline z Evolution in biology z Algorithm z Pros and cons z Applications z Example z Software z Matlab toolboxes
EvolutioninBiologyArchean3Imagefromhttp://www.geo.au.dk/besoegsservice/foredrag/evolution
3 Evolution in Biology Image from http://www.geo.au.dk/besoegsservice/foredrag/evolution
EvolutioninBiologyIOrganismsproduceanumberofoffspringsimilartothemselves but can have variations due to:Mutations(randomchanges)Sexualreproduction(offspringhavecombinationsoffeaturesinheritedfromeachparent)十Imagesadaptedfromhttp://www.wpclipart.com
4 Evolution in Biology I z Organisms produce a number of offspring similar to themselves but can have variations due to: – Mutations (random changes) – Sexual reproduction (offspring have combinations of features inherited from each parent) Images adapted from http://www.wpclipart.com
Evolution inBiology IlSomeoffspringsurvive,andproducenextgenerations, and some don't:The organisms adapted to theenvironment betterhavehigherchancetosurviveOver time, the generations become more and more adaptedbecausethefittestorganismssurvive5Imagesadaptedfromhttp://www.wpclipart.com
5 Evolution in Biology II z Some offspring survive, and produce next generations, and some don’t: – The organisms adapted to the environment better have higher chance to survive – Over time, the generations become more and more adapted because the fittest organisms survive Images adapted from http://www.wpclipart.com
TheGeneticAlgorithms6Imagefromhttp://www.genetic-programming.org
6 The Genetic Algorithms Image from http://www.genetic-programming.org
The Genetic Algorithms (GA)Based onthemechanics of biological evolutionInitially developed by John Holland, University ofMichigan(1970s)Tounderstandprocessesinnatural systemsTodesignartificialsystemsretainingtherobustnessandadaptationpropertiesofnaturalsystemsHolland's original GAis known as the simple geneticalgorithm (SGA)Provideefficienttechniques for optimizationandmachine learningapplicationsWidely used inbusiness, scienceandengineering7Imageadaptedfromhttp:/today.mun.ca/news.php?news_id=2376
7 The Genetic Algorithms (GA) z Based on the mechanics of biological evolution z Initially developed by John Holland, University of Michigan (1970’s) – To understand processes in natural systems – To design artificial systems retaining the robustness and adaptation properties of natural systems z Holland’s original GA is known as the simple genetic algorithm (SGA) z Provide efficient techniques for optimization and machine learning applications z Widely used in business, science and engineering Image adapted from http://today.mun.ca/news.php?news_id=2376
GeneticAlgorithms TechniquesGAs areaparticularclassof evolutionaryalgorithmsThetechniquescommontoallGAsare:InheritanceMutationSelectionCrossover(alsocalledrecombination)GAs arebest used when the objective functionis:DiscontinuousHighlynonlinearStochastic-Has unreliable orundefinedderivatives8
8 Genetic Algorithms Techniques z GAs are a particular class of evolutionary algorithms. The techniques common to all GAs are: – Inheritance – Mutation – Selection – Crossover (also called recombination) z GAs are best used when the objective function is: – Discontinuous – Highly nonlinear – Stochastic – Has unreliable or undefined derivatives
PerformanceGAscanprovidesolutionsforhighlycomplexsearchspacesGAsperformwell approximatingsolutionstoalltypesofproblemsbecausetheydonotmakeanyassumptionaboutthe underlyingfitnesslandscape(theshape of the fitness function, or objectivefunction)However,GAscanbeoutperformedbymorefieldspecificalgorithms9
9 Performance z GAs can provide solutions for highly complex search spaces z GAs perform well approximating solutions to all types of problems because they do not make any assumption about the underlying fitness landscape (the shape of the fitness function, or objective function) z However, GAs can be outperformed by more fieldspecific algorithms
Biological Terminology Gene - a single encoding of part of thesolution space,i.e.either single bits orshortblocks of adjacentbitsthatencodeanelement of thecandidate solution1Chromosome - a string of genes thatrepresents a solutionOPopulation-thenumberofchromosomesavailabletotest10
10 Biological Terminology z Gene – a single encoding of part of the solution space, i.e. either single bits or short blocks of adjacent bits that encode an element of the candidate solution z Chromosome – a string of genes that represents a solution z Population – the number of chromosomes available to test 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0