Innen kunstig intelligens er en evolusjonsalgoritme (EA) en undergruppe av totalberegninger basert på metaheuristisk optimalisering. EA bruker mekanismer inspirert av biologisk utvikling som reproduksjon, mutasjon, rekombinasjon og seleksjon. Kandidatløsningen i problemet med evolusjonære optimaliseringsalgoritmer spiller rollen som individer i befolkningen. Og også treningsfunksjonen bestemmer kvaliteten på svarene.
Evolusjonære algoritmer tilnærmer ofte løsninger på alle typer problemer godt. Fordi de ideelt sett ikke gjør noen antakelser om det underliggende treningslandskapet. Metoder som brukes for evolusjonsmodellering og genetiske algoritmer er vanligvis begrenset til studier av mikroevolusjonære prosesser og planleggingsmodeller basert på cellulære stadier. I de fleste ekte EA-applikasjoner er beregningskompleksitet en uoverkommelig faktor.
Faktiskdette problemet er relatert til estimering av fitnessfunksjon. Fitness tilnærming er en løsning for å overvinne denne vanskeligheten. Imidlertid kan en tilsynelatende enkel EA løse ofte komplekse problemer. Derfor kan det ikke være noen direkte sammenheng mellom kompleksiteten til sekvensen og problemet. Flere detaljer finner du i bøkene "Evolutionary Algorithms".
Implementering
Trinn én er å opprette en innledende populasjon av individer tilfeldig.
Trinn to er å vurdere egnetheten til hver enkelt i denne gruppen (tidsbegrensning, tilstrekkelig beredskap osv.).
Trinn tre – gjenta følgende regenereringstrinn til fullføring:
- Velg de mest passende personene for avl (foreldre).
- Ta med nye individer som har bestått den evolusjonære algoritmen ved å bruke crossover og mutasjon for å få avkom.
- Vurder den individuelle egnetheten til nye mennesker.
- Bytt ut den minst passende befolkningen med dem.
Typer
Genetisk algoritme er en evolusjonær sekvens, den mest populære typen Expert Advisor. En løsning på problemet søkes i form av tallstrenger (tradisjonelt binære, selv om de beste representasjonene vanligvis er de som reflekterer mer i problemet som løses) ved å bruke operatorer som rekombinasjon og mutasjon (noen ganger en, i noen tilfeller begge deler)). Denne typen Expert Advisor brukes ofte i optimaliseringsproblemer. Et annet navn for dette er fetura (fra latin for "fødsel"):
- Genetisk programmering. Den presenterer løsninger som datakoder, og deres egnethet bestemmes av deres evne til å utføre beregningsoppgaver.
- Evolusjonær programmering. Ligner på den evolusjonære genetiske algoritmen, men strukturen er fast og dens numeriske parametere kan endres.
- Programmering av genuttrykk. Utvikler dataapplikasjoner, men utforsker genotype-fenotype-systemet, der prosjekter av forskjellige størrelser er kodet på lineære kromosomer med fast lengde.
- Strategi. Arbeider med vektorer av reelle tall som representasjoner av løsninger. Bruker vanligvis selvadaptive evolusjonære mutasjonshastighetsalgoritmer.
- Differensiell utvikling. Basert på vektorforskjeller og derfor først og fremst egnet for numeriske optimaliseringsproblemer.
- Neuroevolution. Ligner på evolusjonær programmering og genetiske algoritmer. Men sistnevnte er kunstige nevrale nettverk, som beskriver strukturen og vekten av forbindelsene. Genomkoding kan være direkte eller indirekte.
Sammenligning med biologiske prosesser
En mulig begrensning av mange evolusjonære algoritmer er mangelen på et klart skille mellom genotype og fenotype. I naturen gjennomgår et befruktet egg en kompleks prosess kjent som embryogenese for å bli moden. Denne indirekte kodingen antas å gjøre genetiske søk mer pålitelige (dvs. mindre sannsynlighet for å forårsake dødelige mutasjoner) og kan også forbedre organismens evne til å utvikle seg. Slike indirekte (med andre ord,generative eller utviklingsmessige) kodinger tillater også evolusjon å utnytte regularitet i miljøet.
Nylig arbeid innen kunstig embryogenese eller utviklingssystemer søker å løse disse problemene. Når du programmerer genuttrykk, utforskes genotype-fenotype-regionen med suksess, der den første består av lineære multigenkromosomer med fast lengde, og den andre av mange ekspresjonstrær eller dataprogrammer av forskjellige størrelser og former.
Relaterte teknikker
Algorithms include:
- Optimalisering av maurkolonier. Den er basert på ideen om at insekter søker etter mat ved å koble seg til feromoner for å danne stier. Primært egnet for kombinatorisk optimalisering og grafiske problemer.
- Rotskyvealgoritme. Skaperen ble inspirert av plantens røtters funksjon i naturen.
- Algorithme for kunstige biekolonier. Basert på oppførselen til honningbier. Det er først og fremst foreslått for numerisk optimalisering og utvidet til å løse kombinatoriske, avgrensede og multiobjektive problemer. Bie-algoritmen er basert på søkingsadferden til insekter. Det har blitt brukt i mange applikasjoner som ruting og planlegging.
- Partikkelsvermoptimalisering - basert på ideer om dyreflokkadferd. Og også primært egnet for numeriske prosessoppgaver.
Andre populære metaheuristiske metoder
- Jaktsøk. En metode basert på gruppefangst av visse dyr, som ulv, for eksempel, somfordele sine plikter for å omringe byttet. Hvert av medlemmene i den evolusjonære algoritmen forholder seg til de andre på en eller annen måte. Dette gjelder spesielt for lederen. Dette er en kontinuerlig optimaliseringsmetode tilpasset som en kombinatorisk prosessmetode.
- Søk etter mål. I motsetning til naturbaserte metaheuristiske metoder, bruker ikke den adaptive prosessalgoritmen metafor som hovedprinsipp. Snarere bruker den en enkel ytelsesorientert metode basert på oppdatering av søkedimensjonsforholdsparameteren ved hver iterasjon. Firefly-algoritmen er inspirert av hvordan ildfluer tiltrekker hverandre med sitt blinkende lys. Dette er spesielt nyttig for multimodal optimalisering.
- Søk etter harmoni. Basert på ideene om oppførselen til musikere. I dette tilfellet er evolusjonsalgoritmer veien å gå for kombinatorisk optimalisering.
- Gaussisk tilpasning. Basert på informasjonsteori. Brukes for å maksimere ytelse og gjennomsnittlig tilgjengelighet. Et eksempel på evolusjonsalgoritmer i denne situasjonen: entropi i termodynamikk og informasjonsteori.
Memetic
En hybridmetode basert på Richard Dawkins' idé om et meme. Det tar vanligvis form av en populasjonsbasert algoritme kombinert med individuelle læringsprosedyrer som er i stand til å utføre lokale forbedringer. Legger vekt på bruk av problemspesifikk kunnskap og forsøk på å organisere finmaskede og globale søk på en synergistisk måte.
EvolusjonærAlgoritmer er en heuristisk tilnærming til problemer som ikke lett kan løses i polynomisk tid, for eksempel klassiske NP-harde problemer og alt annet som vil ta for lang tid å behandle uttømmende. Når de brukes uavhengig, brukes de vanligvis til kombinatoriske problemer. Imidlertid brukes genetiske algoritmer ofte sammen med andre metoder, og fungerer som en rask måte å finne flere optimale startsteder å jobbe med.
Forutsetningen for den evolusjonære algoritmen (kjent som en rådgiver) er ganske enkel gitt at du er kjent med prosessen med naturlig utvalg. Den inneholder fire hovedtrinn:
- initialisering;
- choice;
- genetiske operatorer;
- end.
Hvert av disse trinnene tilsvarer omtrent et visst aspekt ved naturlig utvalg og gir enkle måter å modularisere den kategorien av algoritmer. Enkelt sagt, i EA, vil de sterkeste medlemmene overleve og reprodusere, mens de uegnete medlemmene vil dø og ikke bidra til neste generasjons genmasse.
initialisering
For å starte algoritmen må du først lage et sett med løsninger. Populasjonen vil inneholde et vilkårlig antall mulige problemformuleringer, ofte omt alt som medlemmer. De genereres ofte tilfeldig (innenfor oppgavens begrensning) eller, hvis noen forkunnskaper er kjent, tentativt sentrert rundt det som anses som ideelt. Det er viktig at befolkningen dekker et bredt spekter av løsninger,fordi det egentlig er en genpool. Derfor, hvis man ønsker å utforske mange forskjellige muligheter innenfor en algoritme, bør man strebe etter å ha mange forskjellige gener.
Choice
Når populasjonen er opprettet, må medlemmene nå vurderes i henhold til treningsfunksjonen. Fitness-funksjonen tar et medlems egenskaper og gir en numerisk representasjon av hvor pass form medlemmet er. Å lage dem kan ofte være veldig vanskelig. Det er viktig å finne et godt system som nøyaktig representerer dataene. Dette er veldig spesifikt for problemet. Nå er det nødvendig å beregne egnetheten til alle deltakerne og velge noen av de beste medlemmene.
Flere målfunksjoner
EAer kan også utvides til å bruke disse systemene. Dette kompliserer prosessen noe, fordi i stedet for å identifisere ett optim alt punkt, oppnås et sett når du bruker dem. Settet med løsninger kalles Pareto-grensen og inneholder elementer som er like egnet i den forstand at ingen av dem dominerer noen andre.
Genetiske operatører
Dette trinnet inkluderer to undertrinn: crossover og mutasjon. Etter å ha valgt de beste termene (vanligvis topp 2, men dette tallet kan variere), brukes de nå til å lage neste generasjon i algoritmen. Ved å anvende egenskapene til de utvalgte foreldrene skapes nye barn som er en blanding av kvaliteter. Dette kan ofte være vanskelig avhengig av type data, men vanligvis i kombinatoriske problemerdet er fullt mulig å blande og skrive ut gyldige kombinasjoner.
Nå er det nødvendig å introdusere nytt genetisk materiale i generasjonen. Hvis dette viktige skrittet ikke blir tatt, vil forskeren veldig raskt sette seg fast i lokale ytterpunkter og ikke få optimale resultater. Dette trinnet er en mutasjon, og det gjøres ganske enkelt ved å endre en liten del av barna på en slik måte at de overveiende ikke reflekterer undergrupper av foreldrenes gener. Mutasjon skjer vanligvis sannsynlig, siden sannsynligheten for at et barn vil få det, så vel som alvorlighetsgraden, bestemmes av distribusjon.
Oppsigelse
Til slutt må algoritmen avsluttes. Dette skjer vanligvis i to tilfeller: enten har den nådd en viss maksimal utførelsestid, eller så har den nådd en ytelsesterskel. På dette tidspunktet er den endelige løsningen valgt og returnert.
Eksempel på evolusjonære algoritmer
Nå, for å illustrere resultatet av denne prosessen, må du se rådgiveren i aksjon. For å gjøre dette kan vi huske hvordan flere generasjoner av dinosaurer lærte å gå (gradvis mestre landet), optimalisere strukturen til kroppen og bruke muskelstyrke. Selv om den tidlige generasjonen reptiler ikke kunne gå, var rådgiveren i stand til å utvikle dem over tid gjennom mutasjon og crossover til en form som kunne gå.
Disse algoritmene blir stadig mer relevante i den moderne verden, ettersom løsninger basert på dem i økende grad brukes i bransjer som digital markedsføring, finans oghelsetjenester.
Hvor brukes EA-er?
Evolusjonære algoritmer brukes i et bredt spekter av applikasjoner som bildebehandling, kjøretøyruting, mobilkommunikasjonsoptimalisering, programvareutvikling og til og med opplæring i kunstig nevrale nettverk. Disse verktøyene er kjernen i mange av appene og nettstedene folk bruker på daglig basis, inkludert Google Maps og til og med spill som The Sims. I tillegg bruker det medisinske feltet EA for å hjelpe med å ta kliniske beslutninger angående kreftbehandling. Faktisk er evolusjonsalgoritmer så robuste at de kan brukes til å løse nesten alle optimaliseringsproblemer.
Moores lov
Den økende utbredelsen av EO er drevet av to hovedfaktorer: tilgjengelig datakraft og akkumulering av store datasett. Den første kan beskrives av Moores lov, som i hovedsak sier at mengden datakraft i en datamaskin dobles omtrent hvert annet år. Denne spådommen har holdt i flere tiår. Den andre faktoren er knyttet til den økende avhengigheten av teknologi, som lar institusjoner samle inn en utrolig stor mengde data, som lar dem analysere trender og optimalisere produkter.
Hvordan kan evolusjonære algoritmer hjelpe markedsførere?
Markedsforholdene endrer seg raskt og er svært konkurransedyktige. Dette har tvunget markedssjefer til å konkurrere om bedre beslutningstaking. Økning i tilgjengeligdatakraft har fått arbeidere til å bruke EA for problemløsning.
Konverteringsoptimalisering
Et av hovedmålene er å øke antallet besøkende på nettstedet. Dette problemet koker ned til å optimalisere antall brukere som gjør det markedsføreren ønsker. For eksempel, hvis et selskap selger bærbare datamaskiner, er det ideelle å øke antallet besøkende på nettstedet som ender opp med å kjøpe produktet. Dette er essensen av konverteringsfrekvensoptimalisering.
Et av de overraskende viktige aspektene er valget av brukergrensesnitt. Hvis webdesignet ikke er veldig brukervennlig, er det de som ender opp med å ikke kjøpe produktet av en eller annen grunn. Målet er da å redusere antall brukere som ender opp med å ikke konvertere, noe som øker den totale fortjenesten.
