Biologyvs.Optimization Candidate solutions to the optimizationproblem playtheroleofindividualsinapopulation (or chromosomes)Cost/fitness/objectivefunctiondeterminestheenvironment within which the solutions"live11DNA imagefromhttp://static.howstuffworks.com/gif/cell-dna.jpg
11 Biology vs. Optimization z Candidate solutions to the optimization problem play the role of individuals in a population (or chromosomes) z Cost/fitness/objective function determines the environment within which the solutions “live” DNA image from http://static.howstuffworks.com/gif/cell-dna.jpg
Featuresof Genetic AlgorithmsNottoofastbutcoverlargesearchspaceCapableof quicklyfindingpromisingregionsofthesearchspacebut maytakearelativelylongtimeto reachtheoptimal solution.Solution: hybrid algorithmsGoodheuristicsforcombinatorial problemsUsuallyemphasizecombininginformationfromgoodparents(crossover)DifferentGAsusedifferentRepresentationsMutationsCrossoversSelectionmechanisms12
12 Features of Genetic Algorithms z Not too fast but cover large search space – Capable of quickly finding promising regions of the search space but may take a relatively long time to reach the optimal solution. Solution: hybrid algorithms z Good heuristics for combinatorial problems z Usually emphasize combining information from good parents (crossover) z Different GAs use different – Representations – Mutations – Crossovers – Selection mechanisms
RepresentationChromosomes can be:- Bit strings(0110,0011,1101,...)-Realnumbers(33.2,-12.11,5.32,...)-Permutationsofelement（1234,3241,4312,...）Listsofrules(R1,R2, R3, ... Rn...)-Programelements(geneticprogramming)-AnyotherdatastructureEncoding(representation)Decoding(inverserepresentation)13
13 Representation z Chromosomes can be: – Bit strings (0110, 0011, 1101, .) – Real numbers (33.2, -12.11, 5.32, .) – Permutations of element (1234, 3241, 4312, .) – Lists of rules (R1, R2, R3, . Rn .) – Program elements (genetic programming) – Any other data structure 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 Encoding (representation) Decoding (inverse representation)
RepresentationExampleGenerationO:4 candidatesolutions34.57~1000010101101”GenerationN23.99~100000111111014
14 Representation Example z Generation 0: 4 candidate solutions z Generation N 34.57 ~ “1000010101101” 23.99 ~ “1000001111110
1-PointCrossoverChoosearandompointSplitparentsatthiscrossoverpointCreatechildrenbyexchangingtailsProbabilityof crossover is typically in range (0.6,0.9)ParentsChildren1115
15 1-Point Crossover z Choose a random point z Split parents at this crossover point z Create children by exchanging tails z Probability of crossover is typically in range (0.6, 0.9) 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 Parents Children