geneticAlgorithm

Information about geneticAlgorithm

Published on October 29, 2007

Author: Amateur

Source: authorstream.com

Content

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

Related presentations


Other presentations created by Amateur

Time Management
19. 06. 2007
0 views

Time Management

genitourinary surgery
30. 04. 2008
0 views

genitourinary surgery

musso
28. 04. 2008
0 views

musso

JBEIT Procurement
18. 04. 2008
0 views

JBEIT Procurement

Rodgers
17. 04. 2008
0 views

Rodgers

IPsec Business
16. 04. 2008
0 views

IPsec Business

1narongchai
14. 04. 2008
0 views

1narongchai

ch03 4e sp07
13. 04. 2008
0 views

ch03 4e sp07

EntretiensMD 061005 VA
10. 04. 2008
0 views

EntretiensMD 061005 VA

The story of Abraham 3 10
19. 06. 2007
0 views

The story of Abraham 3 10

low cost strategy 040405
13. 03. 2008
0 views

low cost strategy 040405

PP Latin America Unit XX
22. 10. 2007
0 views

PP Latin America Unit XX

C6436 11th Family
24. 02. 2008
0 views

C6436 11th Family

reniers film history
20. 02. 2008
0 views

reniers film history

08 Osborne Use of Methanol
07. 11. 2007
0 views

08 Osborne Use of Methanol

Notes Japan
09. 10. 2007
0 views

Notes Japan

Pablo NERUDA
16. 10. 2007
0 views

Pablo NERUDA

indiaglorious
16. 10. 2007
0 views

indiaglorious

Greeklegacies
17. 10. 2007
0 views

Greeklegacies

CRP 1000 Presentation
19. 10. 2007
0 views

CRP 1000 Presentation

CrossingtheFinishLine
05. 09. 2007
0 views

CrossingtheFinishLine

RAI Status Report
23. 10. 2007
0 views

RAI Status Report

distribution aufait
23. 10. 2007
0 views

distribution aufait

comma
05. 09. 2007
0 views

comma

MIE2006 Workshop
05. 09. 2007
0 views

MIE2006 Workshop

PlenaryPovertyNarayan
29. 11. 2007
0 views

PlenaryPovertyNarayan

ubicomp smart homes
27. 08. 2007
0 views

ubicomp smart homes

ShirleyJackson
27. 08. 2007
0 views

ShirleyJackson

Culture Conflict Resolution
27. 08. 2007
0 views

Culture Conflict Resolution

Ed Moyle 2006 RSA
27. 08. 2007
0 views

Ed Moyle 2006 RSA

anxiety
27. 08. 2007
0 views

anxiety

NYpanel 4 DATAUSE
05. 09. 2007
0 views

NYpanel 4 DATAUSE

Influenza 2006
25. 10. 2007
0 views

Influenza 2006

mals russia trip
26. 10. 2007
0 views

mals russia trip

june7
15. 11. 2007
0 views

june7

The Romans WWtbaM
14. 12. 2007
0 views

The Romans WWtbaM

Lsn 3 Egypt
10. 10. 2007
0 views

Lsn 3 Egypt

Economics of ClimateChange
30. 12. 2007
0 views

Economics of ClimateChange

Amateur Satellites
03. 01. 2008
0 views

Amateur Satellites

bio refinery
03. 01. 2008
0 views

bio refinery

Nobelpreise
15. 10. 2007
0 views

Nobelpreise

Impact of Metrology Eng
22. 10. 2007
0 views

Impact of Metrology Eng

DensityNotes
06. 11. 2007
0 views

DensityNotes

All Star Grill
17. 12. 2007
0 views

All Star Grill

Slivovsky CPE350 Lecture5
07. 01. 2008
0 views

Slivovsky CPE350 Lecture5

Obesity Trends Map
09. 08. 2007
0 views

Obesity Trends Map

Obesity Prevalence
09. 08. 2007
0 views

Obesity Prevalence

Logics of Enquiry
09. 08. 2007
0 views

Logics of Enquiry

Obesity workshop
09. 08. 2007
0 views

Obesity workshop

CAIRO NOTABLE EARTHQUAKES
23. 11. 2007
0 views

CAIRO NOTABLE EARTHQUAKES

Robotalk
03. 01. 2008
0 views

Robotalk

Potts Whipple
12. 10. 2007
0 views

Potts Whipple

07 wifi Hovis
29. 10. 2007
0 views

07 wifi Hovis

prop50information
03. 01. 2008
0 views

prop50information

Angola MTB
19. 10. 2007
0 views

Angola MTB

PP JA FUENTES
22. 10. 2007
0 views

PP JA FUENTES

cowie
19. 11. 2007
0 views

cowie

myers12
09. 08. 2007
0 views

myers12

wehrle
15. 10. 2007
0 views

wehrle

4B2006
22. 10. 2007
0 views

4B2006

Energizing your online presence
27. 08. 2007
0 views

Energizing your online presence

PRC56 Amanda open
27. 09. 2007
0 views

PRC56 Amanda open

ufrj 2003
28. 12. 2007
0 views

ufrj 2003

voting
27. 08. 2007
0 views

voting

copyright law
30. 10. 2007
0 views

copyright law

My name is Meth
02. 10. 2007
0 views

My name is Meth

PAAB Presentation Kelly
27. 02. 2008
0 views

PAAB Presentation Kelly

healthy eating SC
04. 03. 2008
0 views

healthy eating SC

Future Naval Capabilities
06. 03. 2008
0 views

Future Naval Capabilities

FP7 FAFB Information 2
27. 11. 2007
0 views

FP7 FAFB Information 2

RigandShip experience
07. 11. 2007
0 views

RigandShip experience

MORTON
07. 11. 2007
0 views

MORTON

Pakistan RSpresentation
30. 03. 2008
0 views

Pakistan RSpresentation

Preciosa factura 1949
19. 06. 2007
0 views

Preciosa factura 1949

Postales de Amistad 1970
19. 06. 2007
0 views

Postales de Amistad 1970

Kickoff Presentation 2007
30. 10. 2007
0 views

Kickoff Presentation 2007

Simplemente Espectacular 1 1714
19. 06. 2007
0 views

Simplemente Espectacular 1 1714

Regalos Originales
19. 06. 2007
0 views

Regalos Originales

Regalito 1713
19. 06. 2007
0 views

Regalito 1713

realidad
19. 06. 2007
0 views

realidad

Toda mujer deberia 1971
19. 06. 2007
0 views

Toda mujer deberia 1971

The three wise men 2 of 12
19. 06. 2007
0 views

The three wise men 2 of 12

Tanga mania 2016
19. 06. 2007
0 views

Tanga mania 2016

srs presentation
19. 06. 2007
0 views

srs presentation

SOAP
19. 06. 2007
0 views

SOAP

slideshoweou
19. 06. 2007
0 views

slideshoweou

HEARTof Darkness pres2
27. 08. 2007
0 views

HEARTof Darkness pres2

smpp tuberculosis janssens
15. 10. 2007
0 views

smpp tuberculosis janssens

AFD 070425 016
27. 08. 2007
0 views

AFD 070425 016

Rocks and Minerals
15. 10. 2007
0 views

Rocks and Minerals

corso studi fisica
15. 10. 2007
0 views

corso studi fisica

TL China
25. 03. 2008
0 views

TL China

Proverbios Animados 1951
19. 06. 2007
0 views

Proverbios Animados 1951

errors funny fatal
27. 08. 2007
0 views

errors funny fatal

20060828091411514
12. 10. 2007
0 views

20060828091411514

08 Neil Scales
16. 11. 2007
0 views

08 Neil Scales

Refleja Lo Que Piensas 1954
19. 06. 2007
0 views

Refleja Lo Que Piensas 1954

Recomenzar 1911
19. 06. 2007
0 views

Recomenzar 1911

ATAMS Pre Bid Presentation 2
28. 02. 2008
0 views

ATAMS Pre Bid Presentation 2

Newspapers drive sales for web2
04. 10. 2007
0 views

Newspapers drive sales for web2

Koonce et al Poster
09. 08. 2007
0 views

Koonce et al Poster

kottmann pl
18. 03. 2008
0 views

kottmann pl

The Lizards
19. 06. 2007
0 views

The Lizards

vet2
21. 10. 2007
0 views

vet2

Burger Ch07 Magnetics
05. 01. 2008
0 views

Burger Ch07 Magnetics

Robo en cajeros II 2080
19. 06. 2007
0 views

Robo en cajeros II 2080

Robo en cajeros 1908
19. 06. 2007
0 views

Robo en cajeros 1908

Quien Snoopy 1952
19. 06. 2007
0 views

Quien Snoopy 1952

hietala materiaali
27. 08. 2007
0 views

hietala materiaali

Lilas
09. 08. 2007
0 views

Lilas

454
16. 03. 2008
0 views

454

thor
05. 09. 2007
0 views

thor

Para enviar 1934
19. 06. 2007
0 views

Para enviar 1934

aug12 rita VeenaJha
17. 10. 2007
0 views

aug12 rita VeenaJha

Posiciones incorrectas 2012
19. 06. 2007
0 views

Posiciones incorrectas 2012

Heminger IBTTA VII
14. 11. 2007
0 views

Heminger IBTTA VII

PowerPointslaveshipi nternet
27. 08. 2007
0 views

PowerPointslaveshipi nternet

educators presentation
16. 02. 2008
0 views

educators presentation

Diversity in the Family
24. 02. 2008
0 views

Diversity in the Family