geneticAlgorithm

50 %
50 %
Information about geneticAlgorithm
Entertainment

Published on October 29, 2007

Author: Amateur

Source: authorstream.com

Genetic Algorithms:  Genetic Algorithms Megan Smedinghoff Quick and Dirty Definition of Genetic Algorithms (courtesy of Wikipedia):  Quick and Dirty Definition of Genetic Algorithms (courtesy of Wikipedia) Choose Initial Population Evaluate Fitness of Each individual Breed New Generation Select Individuals To Reproduce Evaluate Fitness Of Offspring Report Best Solution Introduce Offspring Into Population How do we breed a new generation?:  How do we breed a new generation? Mutation: Having a probability p that a bit b in a solution will be changed from its original state Crossover: Combining two solutions to produce a third solution Original: Mutation: Parent 1: Parent 2: Child: NP-Hard Problems:  NP-Hard Problems Definition: An NP-Hard problem is a problem that cannot be solved in polynomial time. Non-Example: Sorting a list of numbers Examples: Traveling Salesman Problem Subset-Sum Problem Multiple Alignment Building a Phylogenetic Tree Example: The Traveling Salesman Problem:  Example: The Traveling Salesman Problem Definition: Given a set of n cities and distances between the cities, find the shortest way to visit each city and return to your original destination Note: This problem is not solved using a genetic algorithm. It is currently solved using the Lin-Kernighan Heuristic TSP (local version):  TSP (local version) Annapolis Baltimore Silver Spring Rockville TSP (local version):  TSP (local version) Annapolis Baltimore Silver Spring Rockville TSP (local version):  TSP (local version) Annapolis Baltimore Silver Spring Rockville TSP (local version):  TSP (local version) Annapolis Baltimore Silver Spring Rockville Laurel Scary Numbers:  Scary Numbers Solving the Traveling Salesman Problem for n cities requires looking at (n-1)! solutions 5 city version has 24 possible solutions 11 city version has over 3 million solutions 28 city version has over 1028 solutions Solving TSP with a genetic algorithm:  Solving TSP with a genetic algorithm Seattle San Francisco L.A. Phoenix Salt Lake City El Paso Denver Miami New Orleans Houston Dallas Birmingham Memphis Boston New York Philadelphia Washington D.C. Louisville Minneapolis Omaha Buffalo Detroit Chicago Indianapolis St. Louis K.C. Cleveland Pitt Step 1: Pick an initial population:  Step 1: Pick an initial population Step 2a: Mutation:  Step 2a: Mutation Pittsburgh St. Louis Indianapolis Dallas San Francisco New York Phoenix Memphis Denver El Paso Omaha Kansas City Boston Minneapolis Philadelphia Detroit Cleveland Salt Lake City New Orleans Houston Los Angeles Seattle Washington DC Miami Birmingham Chicago Buffalo Louisville Indianapolis Dallas New York Phoenix Memphis El Paso Kansas City Boston Minneapolis Philadelphia Detroit Cleveland Salt Lake City New Orleans Los Angeles Seattle Washington DC Miami Birmingham Buffalo Louisville Step 2a: Mutation:  Step 2a: Mutation Pittsburgh St. Louis Indianapolis Dallas San Francisco New York Phoenix Memphis Denver El Paso Omaha Kansas City Boston Minneapolis Philadelphia Detroit Cleveland Salt Lake City New Orleans Houston Los Angeles Seattle Washington DC Miami Birmingham Chicago Buffalo Louisville Indianapolis Dallas New York Phoenix Memphis El Paso Kansas City Boston Minneapolis Philadelphia Detroit Cleveland Salt Lake City New Orleans Los Angeles Seattle Washington DC Miami Birmingham Buffalo Louisville Denver St. Louis Omaha Pittsburgh San Francisco Chicago Houston Step 2b: Crossover:  Step 2b: Crossover Indianapolis Dallas New York Phoenix Memphis El Paso Kansas City Boston Minneapolis Philadelphia Detroit Cleveland Salt Lake City New Orleans Los Angeles Seattle Washington DC Miami Birmingham Buffalo Louisville Denver St. Louis Omaha Pittsburgh San Francisco Chicago Houston Memphis Chicago Boston Washington DC Indianapolis New York Birmingham Denver Omaha Los Angeles Pittsburgh Buffalo Miami New Orleans Dallas Detroit St. Louis El Paso Houston Philadelphia Minneapolis Phoenix San Francisco Seattle Salt Lake City Cleveland Louisville Kansas City Step 2b: Crossover:  Step 2b: Crossover Indianapolis Dallas New York Phoenix Memphis El Paso Kansas City Boston Minneapolis Philadelphia Detroit Cleveland Salt Lake City New Orleans Los Angeles Seattle Washington DC Miami Birmingham Buffalo Louisville Denver St. Louis Omaha Pittsburgh San Francisco Chicago Houston Memphis Chicago Boston Washington DC Indianapolis New York Birmingham Denver Omaha Los Angeles Pittsburgh Buffalo Miami New Orleans Dallas Detroit St. Louis El Paso Houston Philadelphia Minneapolis Phoenix San Francisco Seattle Salt Lake City Cleveland Louisville Kansas City Step 3: Combine New Generation with Population:  Step 3: Combine New Generation with Population Find the mileage of each route in the new generation Pick a set of routes with comparatively good mileage Replace routes in population that have comparatively bad mileage with the set of routes from the new generation. Step 4: Repeat:  Step 4: Repeat Continue generating new generations until… We have generated a certain number of generations We have run the algorithm for a certain amount of time Our best solution is no longer improving Our best solution is good enough Some Parameters:  Some Parameters Best Results occurred when… Initial population was 1024 Probability of solution being mutated = .35 Probability of bit being mutated = .1 Probability of crossover = 1 Number of generations = 100 Time to run = 33 seconds Best Solution (maybe):  Best Solution (maybe) Seattle San Francisco L.A. Phoenix Salt Lake City El Paso Denver Miami New Orleans Houston Dallas Birmingham Memphis Boston New York Philadelphia Washington D.C. Louisville Minneapolis Omaha Buffalo Detroit Chicago Indianapolis St. Louis K.C. Cleveland Pitt Route Length = 10,966 Miles Paul Lewis Algorithm for creating phylogenetic trees:  Paul Lewis Algorithm for creating phylogenetic trees Improvements from generic algorithm: Don’t always put best solutions from next generation into population Always save best solution Use gamma distribution to mutate branch length Crossover is accomplished by pruning a random subtree from a parent and regrafting it onto another tree Next Level: GARLI:  Next Level: GARLI Improvements over Paul Lewis: Implemented other topological mutations besides subtree pruning/regrafting Optimized branch lengths GARLI examines parameters after every 100 generations and refines them Branch lengths are adjusted before algorithm even begins There are three different stopping conditions Multiple Alignment:  Multiple Alignment TTCAGATAAA TCTTCATTCC ATTCGTAACG ACTTCCGTTC GACTTGCATG ACTAATCA.. .....ATTCT TTAAGCGTAA ATTTTCGTTC GACTTGCATG .......... .....ATCTT CCG...AAGA AGATTCGTTC GACTTGCATG ATGAAATG.. .....TTTCC .......... .....CGTTC GACTTGCATG CCGTCATA.. .....ACTTC A......... ....TCGTTC GACTTGCATG GTGGCATA.. .....ACCCT TCG...GGGA GTGAGCCGTC GA.......A GTGAGCTA.. .....ACTTT T......AGA GGCAGCAGTC GA.......A GTGACCCA.. .....ACCTT T.....TGGA GGGAGCTGTC GA.......A GTGACCTA.. .....ACTGT A.....AAGA AGGAGCTGCC GA.......A GTGACCCA.. .....ACCGT A.....AGGA GGGAGCTGCC GA.......A GTGACCCA.. .....ACCGT A.....AGGA GGGAGCTGCC GA.......A GTGAGGTA.. .....ACCGC A.....AGGA GCCAGCCGTC GA.......A GTGAGGTA.. .....ACCGC A.....AGGA GCCAGCTGCC GA.......A Strategy:  Strategy Start with an alignment generated by an alignment program Move gaps around randomly (mutation) Combine alignments by randomly choosing sequences from each (crossover) Score alignments and combine with population (with higher probability of choosing an alignment with a better score) Results:  Results Population size = 64 Generations = 200 Probability of mutation = 1 Probability of crossover = .15 7.5% improvement in score 50 seconds to run Improved Alignment?:  Improved Alignment? TTCAGATAAA TCTTCATTCC ATTCGTAACG ACTTCCGTTC GACTTGCATG ACTAATCA.A ......TTCT TTAAGCGTAA ATTTTCGTTC GACTTGCATG .........A ......TCTT CCG..A.AGA AGATTCGTTC GACTTGCATG ATGAAATG.. .....TTTCC .......... .....CGTTC GACTTGCATG CCGTCATA.A ....C..TTC A......... ....TCGTTC GACTTGCATG GTGGCATA.A ....C..CCT TCG...GGGA GTGAGCCGTC GA.....A.. GTGAGCTA.A ....C..TTT .T.....AGA GGCAGCAGTC GA.....A.. GTGACCCA.A ....C..CTT .T...TG.GA GGGAGCTGTC GA.....A.. GTGACCTA.A ....C..TGT A....A.AGA AGGAGCTGCC GA.....A.. GTGACCCA.A ....C..CGT A.....AGGA GGGAGCTGCC GA.....A.. GTGACCCA.A ....C..CGT A.....AGGA GGGAGCTGCC GA.....A.. GTGAGGTA.A ....C..CGC A.....AGGA GCCAGCCGTC GA.....A.. GTGAGGTA.A ....C..CGC A.....AGGA GCCAGCTGCC GA.....A.. Possible Improvements:  Possible Improvements Replace current scoring system with one that has an affine gap penalty Try to optimize the probability of crossover Try to find the optimal way of moving a gap (i.e. don’t just move it a random number of space) Try to determine good terminating criteria Adjust parameters based on alignment

Add a comment

Related presentations

Related pages

Genetic algorithm - Wikipedia, the free encyclopedia

In the field of artificial intelligence, a genetic algorithm (GA) is a search heuristic that mimics the process of natural selection. This heuristic (also ...
Read more

Genetic Algorithm .NET Code And Library

Genetic Algorithm .NET C# Sample Code ... Have you ever think to have a full working GA source code that match to what you have read in tutorial?
Read more

Genetic Algorithm - MathWorks - MATLAB and Simulink for ...

Learn how to find global minima to highly nonlinear problems using the genetic algorithm. Resources include videos, examples, and documentation.
Read more

Main page - Introduction to Genetic Algorithms - Tutorial ...

Introduction to genetic algorithms, tutorial with interactive java applets, Main page
Read more

Genetic Algorithm -- from Wolfram MathWorld

Genetic Algorithm. A genetic algorithm is a class of adaptive stochastic optimization algorithms involving search and optimization. Genetic algorithms were ...
Read more

Genetic-algorithm | Define Genetic-algorithm at Dictionary.com

genetic algorithm in Technology Expand (GA) An evolutionary algorithm which generates each individual from some encoded form known as a "chromosome" or ...
Read more

Genetic Algorithm Tutorial

Genetic Algorithms in Plain English . Introduction. The aim of this tutorial is to explain genetic algorithms sufficiently for you to be able to use them ...
Read more

Genetic Algorithm Library - CodeProject

Before a genetic algorithm finishes the production of a new chromosome, after it performs a crossover operation, it performs a mutation operation.
Read more

Genetic Algorithm Description - Introduction to Genetic ...

Introduction to genetic algorithms, tutorial with interactive java applets, Genetic Algorithm Description
Read more

Q1.1: What's a Genetic Algorithm (GA)?

Q1.1: What's a Genetic Algorithm (GA)? The GENETIC ALGORITHM is a model of machine learning which derives its behavior from a metaphor of the processes ...
Read more