geneticAlgorithm

Amateur

Download

Post to :

URL :

Related Presentations :

Add to Flag Embed

Uploaded from authorPOINTLite

Views: 663

Category: Entertainment

Presentation Description

No description available.

Comments

By: savitamangalore (20 month(s) ago) Private Comment

this is a good presentation.Can you make it sharing.Thanx

By: aurora2008 (33 month(s) ago) Private Comment

Thanks for your sharing

By: 3354653 (36 month(s) ago) Private Comment

thanks for your help

Presentation Transcript

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 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 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