Tekoälyn alalla evoluutioalgoritmi (EA) on metaheuristiseen optimointiin perustuvien kokonaispopulaatiolaskelmien osajoukko. EA käyttää biologisen kehityksen inspiroimia mekanismeja, kuten lisääntyminen, mutaatio, rekombinaatio ja valinta. Evoluutiooptimointialgoritmien ongelman ratkaisuehdokkaana on yksilöiden rooli populaatiossa. Ja myös kuntotoiminto määrittää vastausten laadun.
Evoluutioalgoritmit lähestyvät usein ratkaisuja kaikentyyppisiin ongelmiin. Koska ihannetapauksessa he eivät tee mitään oletuksia taustalla olevasta kuntoilusta. Evoluutiomallinnuksen ja geneettisten algoritmien menetelmät rajoittuvat yleensä mikroevoluutioprosessien tutkimuksiin ja soluvaiheisiin perustuviin suunnittelumalleihin. Useimmissa todellisissa EA-sovelluksissa laskennallinen monimutkaisuus on esteellinen tekijä.
Itse asiassatämä ongelma liittyy kuntotoimintojen arviointiin. Kuntoarvio on yksi ratkaisu tämän vaikeuden voittamiseksi. Näennäisesti yksinkertainen EA voi kuitenkin ratkaista usein monimutkaisia ongelmia. Siksi sekvenssin monimutkaisuuden ja ongelman välillä ei voi olla suoraa yhteyttä. Lisätietoja löytyy kirjoista "Evolutionary Algorithms".
Toteutus
Vaihe yksi on luoda ensimmäinen yksilöiden populaatio satunnaisesti.
Vaihe kaksi on jokaisen tässä ryhmässä olevan henkilön sopivuuden arvioiminen (aikaraja, riittävä valmius jne.).
Vaihe kolme - toista seuraavat regenerointivaiheet loppuun asti:
- Valitse jalostukseen sopivimmat ihmiset (vanhemmat).
- Tuo uusia yksilöitä, jotka ovat läpäisseet evoluutioalgoritmin crossoverin ja mutaation avulla jälkeläisten saamiseksi.
- Arvioi uusien ihmisten yksilöllinen kunto.
- Vaihda heikoimmassa kunnossa oleva väestö niillä.
Tyypit
Genetic Algorithm on evolutionaarinen sekvenssi, suosituin Expert Advisor -tyyppi. Ratkaisua ongelmaan etsitään numerojonojen muodossa (perinteisesti binäärinä, vaikka parhaat esitykset ovat yleensä sellaiset, jotka heijastavat enemmän ratkaistavassa ongelmassa) käyttämällä operaattoreita, kuten rekombinaatio ja mutaatio (joskus yksi, joissain tapauksissa molemmat). Tämän tyyppistä Expert Advisoria käytetään usein optimointiongelmissa. Toinen nimi tälle on fetura (latinan kielestä "syntymä"):
- Geneettinen ohjelmointi. Se esittää ratkaisut tietokonekoodeina, ja niiden soveltuvuuden määrää niiden kyky suorittaa laskennallisia tehtäviä.
- Evoluutioohjelmointi. Samanlainen kuin evolutionaarinen geneettinen algoritmi, mutta rakenne on kiinteä ja sen numeeriset parametrit voivat muuttua.
- Geeniekspression ohjelmointi. Kehittää tietokonesovelluksia, mutta tutkii genotyyppi-fenotyyppijärjestelmää, jossa erikokoiset projektit koodataan kiinteäpituisiin lineaarisiin kromosomeihin.
- Strategia. Toimii reaalilukujen vektorien kanssa ratkaisuesityksenä. Käyttää yleensä itsesopeutuvia evolutionaarisia mutaationopeusalgoritmeja.
- Erilainen kehitys. Perustuu vektorieroihin ja siksi soveltuu ensisijaisesti numeeriseen optimointiongelmiin.
- Neuroevoluutio. Samanlainen kuin evoluutioohjelmointi ja geneettiset algoritmit. Mutta jälkimmäiset ovat keinotekoisia hermoverkkoja, jotka kuvaavat yhteyksien rakennetta ja painoa. Genomikoodaus voi olla suoraa tai epäsuoraa.
Vertailu biologisiin prosesseihin
Monien evoluutioalgoritmien mahdollinen rajoitus on selkeän eron puuttuminen genotyypin ja fenotyypin välillä. Luonnossa hedelmöitetty munasolu käy läpi monimutkaisen prosessin, joka tunnetaan nimellä alkiosynty, kypsyäkseen. Tämän epäsuoran koodauksen uskotaan tekevän geneettisistä hauista luotettavampia (eli aiheuttavan vähemmän todennäköisesti kohtalokkaita mutaatioita) ja voi myös parantaa organismin kykyä kehittyä. Tällainen epäsuora (toisin sanoengeneratiiviset tai kehittävät) koodaukset mahdollistavat myös evoluution hyödyntää ympäristön säännöllisyyttä.
Viimeaikainen työ keinotekoisen embryogeneesin tai kehitysjärjestelmien parissa pyrkii käsittelemään näitä kysymyksiä. Geeniekspressiota ohjelmoitaessa tutkitaan onnistuneesti genotyyppi-fenotyyppi-aluetta, jossa ensimmäinen koostuu kiinteän pituisista lineaarisista monigeenisistä kromosomeista ja toinen monista erikokoisista ja -muotoisista ilmentymispuista tai tietokoneohjelmista.
Aiheeseen liittyvät tekniikat
Algoritmeja ovat:
- Muurahaispesäkkeiden optimointi. Se perustuu ajatukseen, että hyönteiset etsivät ruokaa yhdistämällä feromonien kanssa polkuja. Soveltuu ensisijaisesti kombinatoriseen optimointiin ja graafiongelmiin.
- Juuriliukusäädinalgoritmi. Tekijä sai inspiraationsa kasvien juurien toiminnasta luonnossa.
- Algoritmi keinotekoisille mehiläisyhdyskunnille. Perustuu mehiläisten käyttäytymiseen. Sitä ehdotetaan ensisijaisesti numeeriseen optimointiin ja sitä laajennetaan ratkaisemaan kombinatorisia, rajoitettuja ja moniobjektiivisia ongelmia. Mehiläisalgoritmi perustuu hyönteisten ravinnonhakukäyttäytymiseen. Sitä on käytetty monissa sovelluksissa, kuten reitityksessä ja ajoituksessa.
- Partikkeliparven optimointi - perustuu eläinlauman käyttäytymisideoihin. Ja sopii myös ensisijaisesti numeerisiin prosessitehtäviin.
Muita suosittuja metaheuristisia menetelmiä
- Metsästyshaku. Menetelmä, joka perustuu tiettyjen eläinten, kuten esimerkiksi susien, ryhmäpyyntiinjakaa velvollisuutensa saaliin ympäröimiseksi. Jokainen evoluutioalgoritmin jäsenistä liittyy jollain tavalla muihin. Tämä koskee erityisesti johtajaa. Tämä on jatkuva optimointimenetelmä, joka on sovitettu kombinatoriseksi prosessimenetelmäksi.
- Hae mittojen mukaan. Toisin kuin luontopohjaiset metaheuristiset menetelmät, adaptiivinen prosessialgoritmi ei käytä metaforaa pääperiaatteenaan. Sen sijaan se käyttää yksinkertaista suorituskykyyn suuntautunutta menetelmää, joka perustuu hakuulottuvuussuhdeparametrin päivittämiseen jokaisessa iteraatiossa. Firefly-algoritmi on saanut inspiraationsa siitä, kuinka tulikärpäset houkuttelevat toisiaan vilkkuvalla valollaan. Tämä on erityisen hyödyllistä multimodaalisessa optimoinnissa.
- Etsi harmoniaa. Perustuu ideoihin muusikoiden käyttäytymisestä. Tässä tapauksessa evoluutioalgoritmit ovat oikea tapa kombinatoriseen optimointiin.
- Gaussin mukautus. Perustuu informaatioteoriaan. Käytetään maksimoimaan suorituskyvyn ja keskimääräisen saatavuuden. Esimerkki evoluutioalgoritmeista tässä tilanteessa: entropia termodynamiikassa ja informaatioteoriassa.
Memetic
Hybridimenetelmä, joka perustuu Richard Dawkinsin ideaan meemistä. Se on yleensä populaatiopohjaisen algoritmin muodossa yhdistettynä yksittäisiin oppimismenettelyihin, jotka pystyvät suorittamaan paikallisia tarkennuksia. Korostaa ongelmakohtaisen tiedon käyttöä ja pyrkimyksiä järjestää hienojakoiset ja globaalit haut synergistisellä tavalla.
EvoluutiotaAlgoritmit ovat heuristinen lähestymistapa ongelmiin, joita ei voida ratkaista helposti polynomiajassa, kuten klassisen NP-kovat ongelmat ja kaikki muu, jonka tyhjentävä käsittely kestäisi liian kauan. Itsenäisesti käytettynä niitä käytetään yleensä kombinatorisiin ongelmiin. Geneettisiä algoritmeja käytetään kuitenkin usein yhdessä muiden menetelmien kanssa, ja ne toimivat nopeasti tapana löytää useita optimaalisia aloituspaikkoja työskentelylle.
Evoluutioalgoritmin (tunnetaan neuvonantajana) lähtökohta on melko yksinkertainen, koska olet perehtynyt luonnollisen valinnan prosessiin. Se sisältää neljä päävaihetta:
- alustaminen;
- valinta;
- geneettiset operaattorit;
- loppu.
Jokainen näistä vaiheista vastaa karkeasti tiettyä luonnonvalinnan osa-aluetta ja tarjoaa helppoja tapoja moduloida tämä algoritmiluokka. Yksinkertaisesti sanottuna EA:ssa vahvimmat jäsenet selviävät ja lisääntyvät, kun taas sopimattomat jäsenet kuolevat eivätkä osallistu seuraavan sukupolven geenipooliin.
Alustus
Algoritmin aloittamiseksi sinun on ensin luotava joukko ratkaisuja. Yleisö sisältää mieliv altaisen määrän mahdollisia ongelmalauseita, joita usein kutsutaan jäseniksi. Ne luodaan usein satunnaisesti (tehtävän rajoitusten puitteissa) tai, jos jonkin verran aiempaa tietoa tiedetään, alustavasti keskittyvät ihanteellisena pidetyn asian ympärille. On tärkeää, että väestö kattaa laajan valikoiman ratkaisuja,koska se on pohjimmiltaan geenipooli. Siksi, jos haluaa tutkia monia erilaisia mahdollisuuksia algoritmin sisällä, on pyrittävä käyttämään monia erilaisia geenejä.
Valinta
Kun populaatio on luotu, sen jäsenet on nyt arvioitava kuntofunktion mukaan. Kuntotoiminto ottaa jäsenen ominaisuudet ja antaa numeerisen esityksen jäsenen kuntosta. Niiden luominen voi usein olla hyvin vaikeaa. On tärkeää löytää hyvä järjestelmä, joka esittää tiedot tarkasti. Tämä liittyy hyvin ongelmaan. Nyt on tarpeen laskea kaikkien osallistujien sopivuus ja valita parhaat jäsenet.
Useita tavoitefunktioita
EA:ita voidaan myös laajentaa käyttämään näitä järjestelmiä. Tämä mutkistaa prosessia jonkin verran, koska yhden optimaalisen pisteen tunnistamisen sijaan niitä käytettäessä saadaan joukko. Ratkaisujoukkoa kutsutaan Pareto-rajaksi ja se sisältää elementtejä, jotka ovat yhtä sopivia siinä mielessä, että mikään niistä ei hallitse muita.
Geneettiset operaattorit
Tämä vaihe sisältää kaksi alavaihetta: crossover ja mutaatio. Kun olet valinnut parhaat termit (yleensä kaksi parasta, mutta tämä määrä voi vaihdella), niitä käytetään nyt seuraavan sukupolven luomiseen algoritmissa. Valittujen vanhempien ominaisuuksia soveltamalla syntyy uusia lapsia, jotka ovat sekoitus ominaisuuksia. Tämä voi usein olla vaikeaa datatyypistä riippuen, mutta yleensä kombinatorisissa ongelmissaon täysin mahdollista sekoittaa ja tulostaa kelvollisia yhdistelmiä.
Nyt on tarpeen tuoda uutta geneettistä materiaalia sukupolveen. Jos tätä tärkeää askelta ei oteta, tiedemies juuttuu hyvin nopeasti paikallisiin äärimmäisyyksiin eikä saa optimaalisia tuloksia. Tämä vaihe on mutaatio, ja se tehdään yksinkertaisesti, muuttamalla pientä osaa lapsista siten, että ne eivät pääasiassa heijasta vanhempien geenien osajoukkoja. Mutaatio tapahtuu yleensä todennäköisyydellä, koska todennäköisyys, että lapsi saa sen, sekä sen vakavuus määräytyy jakauman perusteella.
Päättäminen
Lopulta algoritmin on loputtava. Tämä tapahtuu yleensä kahdessa tapauksessa: joko se on saavuttanut jonkin enimmäissuoritusajan tai se on saavuttanut suorituskynnyksen. Tässä vaiheessa lopullinen ratkaisu valitaan ja palautetaan.
Esimerkki evoluutioalgoritmeista
Nyt tämän prosessin tuloksen havainnollistamiseksi sinun on nähtävä neuvonantaja toiminnassa. Tätä varten voimme muistaa, kuinka useat sukupolvet dinosauruksia oppivat kävelemään (asteittain hallitsemaan maata), optimoimalla kehonsa rakenteen ja käyttämällä lihasvoimaa. Vaikka varhaisen sukupolven matelijat eivät kyenneet kävelemään, neuvonantaja pystyi kehittämään ne ajan myötä mutaatioiden ja risteytysten kautta käveleväksi muodoksi.
Näistä algoritmeista on tulossa yhä tärkeämpiä nykymaailmassa, kun niihin perustuvia ratkaisuja käytetään yhä enemmän aloilla, kuten digitaalisessa markkinoinnissa, rahoituksessa jaterveydenhuolto.
Missä EA:ita käytetään?
Laajemmin evolutionaarisia algoritmeja käytetään monenlaisissa sovelluksissa, kuten kuvankäsittelyssä, ajoneuvojen reitityksessä, matkaviestinnän optimoinnissa, ohjelmistokehityksessä ja jopa keinotekoisessa hermoverkkokoulutuksessa. Nämä työkalut ovat keskeisiä monissa sovelluksissa ja verkkosivustoissa, joita ihmiset käyttävät päivittäin, mukaan lukien Google Maps ja jopa pelit, kuten The Sims. Lisäksi lääketieteen ala käyttää EA:ta syövänhoitoa koskevien kliinisten päätösten tekemiseen. Itse asiassa evolutionaariset algoritmit ovat niin kestäviä, että niitä voidaan käyttää lähes minkä tahansa optimointiongelman ratkaisemiseen.
Mooren laki
EO:n kasvava yleisyys johtuu kahdesta päätekijästä: käytettävissä olevasta laskentatehosta ja suurten tietokokonaisuuksien kerääntymisestä. Ensimmäistä voidaan kuvata Mooren lailla, joka pohjimmiltaan sanoo, että tietokoneen laskentatehon määrä kaksinkertaistuu noin kahden vuoden välein. Tämä ennuste on pitänyt paikkansa vuosikymmeniä. Toinen tekijä liittyy kasvavaan riippuvuuteen teknologiasta, jonka avulla laitokset voivat kerätä uskomattoman suuren määrän tietoa, jonka avulla ne voivat analysoida trendejä ja optimoida tuotteita.
Miten evolutionaariset algoritmit voivat auttaa markkinoijia?
Markkinaolosuhteet muuttuvat nopeasti ja ovat erittäin kilpailukykyisiä. Tämä on pakottanut markkinointipäälliköt kilpailemaan paremmasta päätöksenteosta. Lisäys saatavillalaskentateho on saanut työntekijät käyttämään EA:ta ongelmanratkaisuun.
Tuloksen optimointi
Yksi päätavoitteista on lisätä sivuston kävijämääriä. Tämä ongelma tiivistyy niiden käyttäjien määrän optimointiin, jotka tekevät mitä markkinoija haluaa. Jos yritys esimerkiksi myy kannettavia tietokoneita, ihanteellinen on lisätä sivuston kävijöiden määrää, jotka päätyvät ostamaan tuotteen. Tämä on tulosprosentin optimoinnin ydin.
Yksi yllättävän tärkeistä seikoista on käyttöliittymän valinta. Jos web-suunnittelu ei ole kovin käyttäjäystävällinen, on niitä, jotka eivät syystä tai toisesta osta tuotetta. Tavoitteena on sitten vähentää niiden käyttäjien määrää, jotka eivät tuota tulosta, mikä lisää kokonaisvoittoa.
