Genetisk Algoritme Forex Matlab

VII. Parametre for GA Crossover og Mutability Sannsynlighet Det er to grunnleggende parametere for GA - crossover sannsynlighet og mutasjon sannsynlighet. Crossover sannsynlighet sier hvor ofte blir crossover utført. Hvis det ikke er noen crossover, er avkom nøyaktig kopi av foreldre. Hvis det er en crossover, er avkom laget av deler av foreldre kromosom. Hvis crossover sannsynlighet er 100. da alle avkom er laget av crossover. Hvis det er 0. helt ny generasjon er laget av eksakte kopier av kromosomer fra gammel befolkning (men dette betyr ikke at den nye generasjonen er den samme). Crossover er laget i håp om at nye kromosomer vil ha gode deler av gamle kromosomer og kanskje de nye kromosomene blir bedre. Det er imidlertid godt å la en del av befolkningen overleve til neste generasjon. Mutssannsynligheten sier hvor ofte vil være deler av kromosommutert. Hvis det ikke er noen mutasjon, blir avkom tatt etter crossover (eller kopi) uten endring. Hvis mutasjon utføres, endres en del av kromosomet. Hvis mutasjonssannsynlighet er 100. hele kromosom er endret, hvis det er 0. ingenting er endret. Mutation er laget for å hindre fallende GA til lokal ekstrem, men det bør ikke forekomme veldig ofte, fordi da GA faktisk vil bytte til tilfeldig søk. Andre parametere Det er også noen andre parametere for GA. En viktig parameter er også befolkningsstørrelsen. Befolkningsstørrelse sier hvor mange kromosomer er i befolkningen (i en generasjon). Hvis det er for få kromosomer, har GA noen muligheter til å utføre crossover, og bare en liten del av søkeområdet utforskes. På den annen side, hvis det er for mange kromosomer, senkes GA. Forskning viser at etter en grense (som hovedsakelig avhenger av koding og problemet), er det ikke nyttig å øke populasjonsstørrelsen, fordi det ikke løser problemet raskere. Noen anbefalinger for alle parametere finnes i ett av følgende kapitler. Eksempel Her kan du se eksempel som ligner på forrige. Men her kan du prøve å endre crossover og mutasjon sannsynlighet. Du kan også kontrollere elitisme. På grafen nedenfor kan du se resultatene til GA. Rød er den beste løsningen, blå er gjennomsnittsverdi (fitness) for hele befolkningen. Prøv å endre parametere og se hvordan GA oppfører seg. Her er applet, men nettleseren din støtter ikke Java. Hvis du vil se applets, vennligst sjekk nettleserens krav. Spørsmål: Hvis du prøver å øke mutasjonssannsynligheten til 100, vil GA begynne å oppføre meg veldig merkelig, nesten som om mutasjonssannsynligheten er 0. Vet du hvorfor Du kan bruke et hint og hvis du fortsatt ikke vet, se på løsning Genetisk Algoritmer ble oppfunnet for å etterligne noen av prosessene observert i naturlig utvikling. Mange mennesker, inkludert biologer, er forbauset over at livet på nivået av kompleksitet som vi observerer kunne ha utviklet seg på den relativt korte tiden foreslått av fossilregistreringen. Ideen med GA er å bruke denne evnen til å løse optimaliseringsproblemer. Faren til den opprinnelige genetiske algoritmen var John Holland, som oppfant det tidlig på 1970-tallet. Hva er Genetic Algorithms Genetic Algorithms (GAs) er adaptiv heuristisk søkealgoritme basert på evolusjonerende ideer om naturlig utvalg og genetikk. Som sådan representerer de en intelligent utnyttelse av et tilfeldig søk som brukes til å løse optimaliseringsproblemer. Selv om randomiserte, er GA ikke på noen måte tilfeldige, men i stedet utnytter de historisk informasjon for å lede søket inn i regionen med bedre ytelse i søkeområdet. De grunnleggende teknikkene til GA-ene er utformet for å simulere prosesser i naturlige systemer som er nødvendige for evolusjon, spesielt de følger prinsippene som først ble fastsatt av Charles Darwin for å overleve de sterkeste. Siden i naturen resulterer konkurransen blant enkeltpersoner for skarpe ressurser i de fitteste enkeltpersoner dominerer over svakere. Hvorfor genetiske algoritmer Det er bedre enn konvensjonelle AI fordi det er mer robust. I motsetning til eldre AI-systemer bryter de ikke lett, selv om inngangene endres litt, eller i nærvær av fornuftig støy. Også ved å søke i en stor statlig plass, multimodal tilstandsrom eller n-dimensjonal overflate, kan en genetisk algoritme gi betydelige fordeler over mer typisk søk ​​på optimaliseringsteknikker. (lineær programmering, heuristisk, dybde-første, pusten-først og praksis.) Genetisk algoritmer Oversikt GAs simulerer overlevelse av de sterkeste blant enkeltpersoner over sammenhengende generasjon for å løse et problem. Hver generasjon består av en populasjon av tegnstrenger som er analoge med kromosomet som vi ser i vårt DNA. Hvert individ representerer et poeng i et søkerom og en mulig løsning. Individer i befolkningen blir da gjort for å gå gjennom en evolusjonsprosess. GA er basert på en analogi med den genetiske strukturen og oppførselen til kromosomer i en befolkning av individer som bruker følgende fundament: Enkeltpersoner i en befolkning konkurrerer om ressurser og kompiser. De individene som lykkes mest i hver konkurranse, vil produsere flere avkom enn de personene som utfører dårlig. Gen fra gode individer former seg over hele befolkningen slik at to gode foreldre noen ganger kan produsere avkom som er bedre enn foreldrene. Dermed vil hver suksessiv generasjon bli mer egnet til sitt miljø. Søkeplass En befolkning av individer er opprettholdt innenfor søkeområdet for en GA, som hver representerer en mulig løsning på et gitt problem. Hver enkelt person er kodet som en endelig vektorgrave av komponenter, eller variabler, i form av noe alfabet, vanligvis det binære alfabetet. For å fortsette den genetiske analogien, sammenlignes disse individene med kromosomer, og variablene er analoge med gener. Dermed er et kromosom (løsning) sammensatt av flere gener (variabler). En treningsscore er tilordnet hver løsning som representerer evnen til et individ til å konkurrere. Personen med optimal (eller generelt nær optimal) treningspoeng er søkt. GA har til hensikt å bruke selektiv oppdrett av løsningene for å produsere avkom bedre enn foreldrene ved å kombinere informasjon fra kromosomene. GA opprettholder en befolkning av n kromosomer (løsninger) med tilhørende treningsverdier. Foreldre er utvalgt til å kompisere, på grunnlag av deres egnethet, å produsere avkom via en reproduktiv plan. Derfor gir høypasningsløsninger flere muligheter til å reprodusere, slik at avkom arver egenskaper fra hver forelder. Som foreldre passer og produserer avkom, må rom gjøres for nyankomne siden befolkningen holdes i en statisk størrelse. Personer i befolkningen dør og blir erstattet av de nye løsningene, og til slutt skaper en ny generasjon når alle parringsmuligheter i den gamle befolkningen har blitt oppbrukt. På denne måten håper vi at bedre løsninger vil trives i løpet av flere generasjoner mens de minst passende løsningene dør ut. Nye generasjoner av løsninger produseres som inneholder i gjennomsnitt flere gode gener enn en typisk løsning i en tidligere generasjon. Hver påfølgende generasjon vil inneholde mer gode delvise løsninger enn tidligere generasjoner. Til slutt, når befolkningen har konvergert og ikke produserer avkom merkbart forskjellig fra de i tidligere generasjoner, sies algoritmen selv å ha konvergert til et sett med løsninger på problemet ved hånden. Implementeringsdetaljer Basert på naturlig utvalg Etter at en første populasjon er tilfeldig generert, utvikler algoritmen de tre operatørene: valg som tilsvarer overlevelse av den fitteste crossover som representerer parring mellom individer mutasjon som introduserer tilfeldige modifikasjoner. 1. Valgoperatørnøkkelide: Gi prefence til bedre individer, slik at de kan overføre sine gener til neste generasjon. Godheten til hvert individ er avhengig av treningen. Fitness kan bestemmes av en objektiv funksjon eller ved en subjektiv vurdering. 2. Crossover Operator Prime fremtredende faktor for GA fra andre optimaliseringsteknikker To personer er valgt fra populasjonen ved hjelp av seleksjonsoperatøren. En crossover-side langs bitstrengene er tilfeldig valgt. Verdiene av de to strengene utveksles opp til dette punktet. Hvis S1000000 og s2111111 og crossover punktet er 2 da S1110000 og s2001111 De to nye avkomene som er opprettet fra denne paringen, blir lagt inn i neste generasjon av befolkningen. Ved å kombinere deler av gode individer, vil denne prosessen trolig skape enda bedre individer. 3. Mutation Operator Med litt lavt Sannsynligheten vil en del av de nye personene ha noen av sine biter vendt. Hensikten er å opprettholde mangfold i befolkningen og hemme for tidlig konvergens. Mutasjon alene fremkaller en tilfeldig spasertur gjennom søkeområdet. Mutation og valg (uten kryssoverføring) skaper en parallell, støytolerant, bergklatringsalgoritmer. Effekter av genetiske operatører Bruk av valg alene vil pleie å fylle befolkningen med kopier av det beste individet fra befolkning Ved å bruke utvalgte og crossover operatører vil det få algoritmer til å konvergere på en god, men suboptimal løsning. Bruk av mutasjon alene gir en tilfeldig spasertur gjennom søkeområdet. Bruk av valg og mutasjon skaper en parrallell, støytolerant, fjellklatringsalgoritme. Algoritmene tilfeldigvis initialiserer populasjonen (t) bestemmer pasientens evne til å gjenta. Velg foreldre fra befolkning (t) utføre crossover på foreldre som skaper befolkning (t1) utfører mutasjon av befolkning (t1) fastslår pasientenes befolkning (t1) til det beste individet er godt nok I foregående ledd er det hevdet at via operasjonene av utvelgelse, crossover og mutasjon vil GA konvergere over suksessive generasjoner mot den globale (eller nær globale) optium. hvorfor denne enkle operasjonen skal produsere en rask, nyttig og robust teknikker skyldes i stor grad at GAs kombinerer retning og sjanse i søket på en effektiv og effektiv måte. Siden befolkningen implisitt inneholder mye mer informasjon enn bare de enkelte treningspoengene, kombinerer GAs den gode informasjonen som er skjult i en løsning med god informasjon fra en annen løsning for å produsere nye løsninger med god innormasjon arvet fra begge foreldre, uunngåelig (forhåpentligvis) ledende towrads optimalitet. Algoritmenes evne til å utforske og utnytte samtidig, en økende mengde teoretisk begrunnelse og vellykket søknad på virkelige problemer styrker konklusjonen at GA er en kraftig og robust optimaliseringsteknikk. En introduksjon til genetiske algoritmer. mit press redigert av Melanie Mitchell Genetiske algoritmer i ingeniørfag og datavitenskap redigert av G. Winter. et al. c1995 Grunnlag av genetiske algoritmer redigert av Gregory J. E. Rawlins. c1991 For detaljer om bruk av genetikkalgoritmer, vennligst se vennen min, Chun s article. Genetic Algorithms in Plain English Målet med denne opplæringen er å forklare genetiske algoritmer tilstrekkelig for at du skal kunne bruke dem i dine egne prosjekter. Dette er en avklart-til-den-bare-essensielle typen opplæring. Jeg kommer ikke til å gå i stor dybde, og jeg kommer ikke til å skremme de med deg med matteangst ved å kaste onde ligninger på deg hver få setninger. Faktisk, jeg kommer ikke til å kaste noen ekkel ligninger på deg i det hele tatt Ikke i denne spesielle opplæringen uansett. ltsmileg Denne opplæringen er utformet for å bli lest gjennom to ganger. så ikke bekymre deg hvis lite av det er fornuftig første gang du studerer det. (En leser, Daniel, har lett oversatt denne opplæringen til tysk. Du kan finne den her.) (En annen leser, David Lewin, har oversatt opplæringen til fransk. Du finner den her.) For det første har en biologi-leksjon hver organisme et sett med regler, en tegning så å si, som beskriver hvordan denne organismen er bygget opp fra de små byggeblokkene i livet. Disse reglene er kodet i gener av en organisme, som igjen er forbundet sammen i lange strenger kalt kromosomer. Hvert gen representerer et spesifikt trekk av organismen, som øyenfarge eller hårfarge, og har flere forskjellige innstillinger. For eksempel kan innstillingene for et hårfargegen være blond, svart eller auburn. Disse gener og deres innstillinger blir vanligvis referert til som en genotype av organismer. Det fysiske uttrykket av genotypen - selve organismen - kalles fenotypen. Når to organismer kompis deler de sine gener. Det resulterende avkom kan ende opp med å ha halvparten av gener fra en forelder og en halv fra den andre. Denne prosessen kalles rekombination. Svært av og til kan et gen bli mutert. Normalt vil dette muterte genet ikke påvirke fenotypens utvikling, men det vil ofte bli uttrykt i organismen som et helt nytt trekk. Livet på jorden har utviklet seg til å være som det er gjennom prosessene med naturlig utvalg, rekombination og mutasjon. For å illustrere hvordan disse prosessene jobber sammen for å produsere det mangfoldige spekteret av flora og fauna, deler vi planeten vår med, la meg fortelle deg en liten historie. En gang levde en art av skapninger kalt Hooters. Hooters hadde utviklet seg helt innenfor de mørke grensene til et stort hulsystem skjult dypt i tarmene i et fjellkjede. Theyd hadde et lett liv, følelse og lukter rundt de fuktige huleveggene for algerne de så elsket å spise, oser mellom steiner og, i parringstid, lyttet nøye til hodene til andre Hooters. Det var ingen rovdyr i hulene, det var bare Hooters, alger og sporadisk vennlig slug, så Hooters hadde aldri noe å frykte (bortsett fra kanskje en og annen dårlig temperert Hooter). En underjordisk elv rann gjennom hulsystemet og vann droppet kontinuerlig ned gjennom vanntabellen og brakte med seg de friske næringsstoffene som algene blomstret på, så det var alltid mye å spise og drikke. Imidlertid, selv om Hooters kunne føle og høre godt, hadde de aldri behov for øyne i hulhøyden i hulene, og var derfor helt blinde. Dette syntes aldri å bekymre seg for noen av Hooters skjønt, og de alle hadde en hval av en tid som knuste og hørte i mørket. Så en dag forårsaket et jordskjelv en del av hulsystemet å kollapse og for første gang i mange årtusener følte Hooters varmen fra sollyset på huden og den myke fjærheten av mose under føttene. Noen få dristige Hooters smakte moset og fant at det var enda bedre å spise enn hulalger. quotOooooooooohquot de hooted mellom mouthfuls av mose og straks ble gobbled opp av marauding eagles som hadde fløyet inn for å se hva all opprør var om. For en stund så det ut som om Hooters kan bli jaktet til utryddelse, for selv om de likte å spise moset, kunne de aldri fortelle om en ørn flyr over. Ikke bare det, de kunne ikke engang fortelle om de var skjult under en stein eller ikke, med mindre det var lavt nok til å nå frem med sine følere. Hver dag ville mange Hooters snuble ut fra hulene med den søte lukten av mose i neseborene for å bli båret raskt og spist av en ørn. Deres situasjon virket grusomt. Heldigvis har befolkningen i Hooters i løpet av årene vokst til å være enorm i hulenes sikkerhet, og nok av dem var overlevende til makker. En eagle kan etter alt bare spise så mye. En dag ble en brød av Hooters født som delte et mutert hudcellegen. Dette bestemte genet var ansvarlig for utviklingen av hudceller på pannen. Under utviklingen av babyen Hooters, da deres hudceller vokste fra de muterte geninstruksjonene, var de litt lysfølsomme. Hver ny baby Hooter kunne fornemme om noe var å blokkere lyset til pannen eller ikke. Da disse lille babyhopperne vokste opp i større Hooters og dristet seg inn i lyset for å spise mossen, kunne de fortelle om det var noe som swooping overhead eller ikke. Så disse Hooters vokste opp for å ha en litt bedre sjanse for overlevelse enn deres helt blinde fettere. Og fordi de hadde en bedre sjanse for overlevelse, reproduserte de mye mer, og passerte derfor det nye lysfølsomme hudcellegenet til sine avkom. Etter en kort stund ble befolkningen dominert av Hooters med denne lille fordelen. Nå kan vi zip noen få tusen generasjoner inn i fremtiden. Hvis du ekstrapolerer denne prosessen over mange år og involverer mange små mutasjoner som forekommer i hudcellegenene, er det lett å forestille seg en prosess hvor en lysfølsom celle kan bli en klump av lysfølsomme celler, og deretter hvordan de indre cellene i klumpen kan mutere til herding i et lite objektivformet område, noe som vil bidra til å samle lyset og fokusere det på ett sted. Det er ikke for vanskelig å forestille seg en mutasjon som gir opphav til to av disse lyssamlingsområdene, og derved gir kikkertvisjon på Hooters. Dette ville være en stor fordel i forhold til deres cyklopsiske fettere som Hooters ville nå kunne dømme avstander nøyaktig og ha et større synsfelt. Som du kan se prosessene med naturlig utvalg - overlevelse av de fitteste - og genmutasjonen har svært sterke roller å spille i utviklingen av en organisme. Men hvordan passer rekombination inn i ordningen med ting Vel å vise deg at jeg trenger å fortelle om noen andre Hooters. På samme tid var Hooters med de lysfølsomme cellene frolicking rundt i mosen og retet ørene, en annen Hooters-stamme hadde blitt født som delte et mutert gen som påvirket deres hooter. Denne mutasjonen ga opphav til en litt større hooter enn deres fettere, og fordi den var større kunne de nå hoot over lengre avstander. Dette viste seg å være nyttig i den raskt avtagende befolkningen fordi Hooters med de større hooters kunne ringe til potensielle kompiser som ligger langt borte. Ikke bare det, men den kvinnelige Hooters begynte å vise en liten preferanse til menn med større hooters. Resultatet av dette var selvfølgelig at de bedre støttede Hooters sto en mye bedre sjanse for parring enn noen som ikke var så bra av Hooters. Over en periode ble store hooters utbredt i befolkningen. Så en fin dag møtte en kvinnelig Hooter med genet for lysfølsomme hudceller en mannlig Hooter med genet for å produsere store hootere. De ble forelsket, og kort tid etter produserte de en nydelig baby Hooters. Nå, fordi babyens kromosomer var en rekombinasjon av begge foreldre kromosomer, delte noen av babyene begge spesielle gener og vokste opp, ikke bare for å ha lysfølsomme hudceller, men også store hootere. Disse nye avkomene var ekstremt gode for å unngå ørene og reprodusere så utviklingsprosessen begynte å favorisere dem, og igjen ble denne nye forbedrede typen Hooter dominerende i befolkningen. Og så videre. Og så videre. Genetiske algoritmer er en måte å løse problemer ved å etterligne de samme prosessene som moder natur bruker. De bruker samme kombinasjon av utvalg, rekombination og mutasjon for å utvikle en løsning på et problem. Ryddig huh Vend siden for å finne ut nøyaktig hvordan det er gjort.