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