Tehisintellekti valdkonnas on evolutsiooniline algoritm (EA) metaheuristilisel optimeerimisel põhinevate kogupopulatsiooni arvutuste alamhulk. EA kasutab bioloogilisest arengust inspireeritud mehhanisme, nagu paljunemine, mutatsioon, rekombinatsioon ja valik. Evolutsiooniliste optimeerimisalgoritmide probleemi kandidaatlahendus mängib populatsioonis indiviidide rolli. Ja ka sobivuse funktsioon määrab vastuste kvaliteedi.
Evolutsioonilised algoritmid annavad sageli ligikaudsed lahendused igat tüüpi probleemidele. Sest ideaaljuhul ei tee nad aluseks oleva fitnessmaastiku kohta mingeid oletusi. Evolutsiooniliseks modelleerimiseks ja geneetilisteks algoritmideks kasutatavad meetodid piirduvad tavaliselt mikroevolutsiooniprotsesside ja rakufaasidel põhinevate planeerimismudelite uurimisega. Enamikus tõelistes EA rakendustes on arvutuslik keerukus ülemäärane tegur.
Tegelikultsee probleem on seotud sobivuse funktsiooni hindamisega. Fitnessi lähendamine on üks lahendus selle raskuse ületamiseks. Pe altnäha lihtne EA võib aga lahendada sageli keerulisi probleeme. Seetõttu ei saa jada keerukuse ja probleemi vahel olla otsest seost. Rohkem üksikasju leiate raamatutest "Evolutionary Algorithms".
Rakendamine
Esimene samm on luua juhuslikult indiviidide esialgne populatsioon.
Teine samm on hinnata sellesse rühma kuuluvate inimeste sobivust (ajapiirang, piisav valmisolek jne).
Kolmas samm – korrake lõpuni järgmisi regenereerimise etappe:
- Valige aretuseks sobivaimad inimesed (vanemad).
- Tooge uusi indiviide, kes on läbinud evolutsioonilise algoritmi, kasutades järglaste saamiseks crossoveri ja mutatsiooni.
- Hinda uute inimeste individuaalset vormi.
- Asendage kõige vähem sobivam populatsioon nendega.
Tüübid
Genetic Algorithm on evolutsiooniline jada, kõige populaarsem Expert Advisori tüüp. Probleemile otsitakse lahendust arvujadade kujul (tavaliselt binaarsed, kuigi parimad esitused on tavaliselt need, mis peegeldavad lahendatavas ülesandes rohkem), rakendades selliseid operaatoreid nagu rekombinatsioon ja mutatsioon (mõnikord üks, mõnel juhul mõlemad). Seda tüüpi ekspertnõustajaid kasutatakse sageli optimeerimisprobleemide lahendamisel. Selle teine nimi on fetura (ladina keelest "sünd"):
- Geneetiline programmeerimine. See esitab lahendused arvutikoodidena ja nende sobivuse määrab nende võime täita arvutusülesandeid.
- Evolutsiooniline programmeerimine. Sarnane evolutsioonilise geneetilise algoritmiga, kuid struktuur on fikseeritud ja selle numbrilised parameetrid võivad muutuda.
- Geeniekspressiooni programmeerimine. Arendab arvutirakendusi, kuid uurib genotüübi-fenotüübi süsteemi, kus erineva suurusega projektid on kodeeritud fikseeritud pikkusega lineaarsetele kromosoomidele.
- Strateegia. Töötab reaalarvude vektoritega kui lahenduste esitusviisidega. Tavaliselt kasutab isekohanduvaid evolutsioonilise mutatsioonikiiruse algoritme.
- Diferentsiaalne areng. Põhineb vektorite erinevustel ja sobib seetõttu eelkõige numbrilise optimeerimise probleemide lahendamiseks.
- Neuroevolutsioon. Sarnaselt evolutsioonilise programmeerimise ja geneetiliste algoritmidega. Kuid viimased on kunstlikud närvivõrgud, mis kirjeldavad ühenduste struktuuri ja kaalu. Genoomi kodeering võib olla otsene või kaudne.
Võrdlus bioloogiliste protsessidega
Paljude evolutsiooniliste algoritmide võimalikuks piiranguks on selge eristuse puudumine genotüübi ja fenotüübi vahel. Looduses läbib viljastatud munarakk küpseks saamiseks keeruka protsessi, mida nimetatakse embrüogeneesiks. Arvatakse, et selline kaudne kodeerimine muudab geneetilised otsingud usaldusväärsemaks (st ei põhjusta surmavaid mutatsioone) ja võib samuti parandada organismi arenguvõimet. Selline kaudne (teisisõnugeneratiivsed või arenduslikud) kodeeringud võimaldavad evolutsioonil ka keskkonna korrapärasust ära kasutada.
Hiljutine töö kunstliku embrüogeneesi või arendussüsteemide vallas püüab neid probleeme lahendada. Geeniekspressiooni programmeerimisel uuritakse eduk alt genotüübi-fenotüübi piirkonda, kus esimene koosneb fikseeritud pikkusega lineaarsetest mitmegeenilistest kromosoomidest ja teine paljudest erineva suuruse ja kujuga ekspressioonipuudest või arvutiprogrammidest.
Seotud tehnikad
Algoritmide hulka kuuluvad:
- Sipelgate kolooniate optimeerimine. See põhineb ideel, et putukad otsivad toitu, luues ühenduse feromoonidega, moodustades teid. Sobib eelkõige kombinatoorseks optimeerimiseks ja graafikuülesanneteks.
- Juur-liuguri algoritm. Looja sai inspiratsiooni taimejuurte funktsioonist looduses.
- Algoritm kunstlike mesilasperede jaoks. Mesilaste käitumise põhjal. Seda soovitatakse peamiselt arvuliseks optimeerimiseks ja laiendatakse kombinatoorsete, piiratud ja mitmeobjektiivsete probleemide lahendamiseks. Mesilaste algoritm põhineb putukate toitumiskäitumisel. Seda on rakendatud paljudes rakendustes, nagu marsruutimine ja ajastamine.
- Osakeste sülemi optimeerimine – põhineb loomakarja käitumise ideedel. Ja sobib ka eelkõige numbriliste protsessiülesannete jaoks.
Muud populaarsed metaheuristilised meetodid
- Jahiotsing. Meetod, mis põhineb teatud loomade, näiteks huntide rühmapüüdmisel, misjaotavad oma ülesanded saaklooma ümbritsemiseks. Iga evolutsioonilise algoritmi liige on mingil moel teistega seotud. See kehtib eriti juhi kohta. See on pidev optimeerimismeetod, mis on kohandatud kombinatoorse protsessi meetodina.
- Otsi mõõtude järgi. Erinev alt looduspõhistest metaheuristlikest meetoditest ei kasuta adaptiivse protsessi algoritm oma põhiprintsiibina metafoori. Pigem kasutab see lihtsat jõudlusele orienteeritud meetodit, mis põhineb otsingu mõõtmete suhte parameetri värskendamisel igal iteratsioonil. Firefly algoritm on inspireeritud sellest, kuidas tulekärbsed üksteist oma vilkuriga meelitavad. See on eriti kasulik multimodaalsel optimeerimisel.
- Otsige harmooniat. Lähtudes ideedest muusikute käitumisest. Sel juhul on kombinatoorse optimeerimise viis kasutada evolutsioonilised algoritmid.
- Gaussi kohanemine. Infoteooria põhjal. Kasutatakse jõudluse ja keskmise kättesaadavuse maksimeerimiseks. Evolutsiooniliste algoritmide näide selles olukorras: entroopia termodünaamikas ja teabeteoorias.
Memetic
Hübriidmeetod, mis põhineb Richard Dawkinsi ideel meemist. Tavaliselt on see populatsioonipõhise algoritmi vormis, mis on kombineeritud individuaalsete õppeprotseduuridega, mis on võimelised tegema kohalikke täpsustusi. Rõhutab probleemispetsiifiliste teadmiste kasutamist ja katseid korraldada peeneteralisi ja globaalseid otsinguid sünergiliselt.
Evolutsioonilinealgoritmid on heuristiline lähenemine probleemidele, mida ei saa polünoomilise aja jooksul kergesti lahendada, näiteks klassikaliselt NP-rasked probleemid ja kõik muu, mille ammendav töötlemine võtaks liiga kaua aega. Kui neid kasutatakse iseseisv alt, kasutatakse neid tavaliselt kombinatoorsete probleemide lahendamiseks. Siiski kasutatakse geneetilisi algoritme sageli koos teiste meetoditega, mis toimivad kiire viisina leida mitu optimaalset töökohta.
Evolutsioonilise algoritmi (tuntud kui nõuandja) eeldus on üsna lihtne, arvestades, et olete tuttav loodusliku valiku protsessiga. See sisaldab nelja peamist sammu:
- initsialiseerimine;
- valik;
- geneetilised operaatorid;
- lõpp.
Iga neist sammudest vastab ligikaudu loodusliku valiku teatud aspektile ja pakub lihtsaid viise selle kategooria algoritmide moduleerimiseks. Lihtsam alt öeldes jäävad EA-s kõige paremad liikmed ellu ja paljunevad, samas kui kõlbmatud liikmed surevad ega panusta järgmise põlvkonna genofondi.
Initsialiseerimine
Algoritmi käivitamiseks peate esm alt looma lahenduste komplekti. Populatsioon sisaldab meelevaldset arvu võimalikke probleemiavaldusi, mida sageli nimetatakse liikmeteks. Need genereeritakse sageli juhuslikult (ülesande piirangute piires) või, kui teatud eelteadmised on teada, keskenduvad esialgu ideaalseks peetavale. On oluline, et elanikkond hõlmaks laia valikut lahendusi,sest see on sisuliselt genofond. Seega, kui soovite algoritmi raames uurida paljusid erinevaid võimalusi, tuleks püüda kasutada palju erinevaid geene.
Valik
Kui populatsioon on loodud, tuleb selle liikmeid hinnata vastav alt sobivuse funktsioonile. Fitness-funktsioon võtab liikme omadused ja annab numbrilise esituse selle kohta, kui heas vormis liige on. Nende loomine võib sageli olla väga keeruline. Oluline on leida hea süsteem, mis andmeid täpselt esitab. See on probleemile väga spetsiifiline. Nüüd on vaja välja arvutada kõikide osalejate sobivus ja valida välja mõned parimad liikmed.
Mitu eesmärgifunktsiooni
EA-sid saab ka nende süsteemide kasutamiseks laiendada. See muudab protsessi mõnevõrra keerulisemaks, sest ühe optimaalse punkti tuvastamise asemel saadakse nende kasutamisel komplekt. Lahenduste komplekti nimetatakse Pareto piiriks ja see sisaldab elemente, mis on võrdselt sobivad selles mõttes, et ükski neist ei domineeri teistes.
Geneetilised operaatorid
See samm sisaldab kahte alametappi: ristumine ja mutatsioon. Pärast parimate terminite (tavaliselt 2 parimat, kuid see arv võib varieeruda) valimist kasutatakse neid nüüd algoritmi järgmise põlvkonna loomiseks. Valitud vanemate omadusi rakendades sünnivad uued lapsed, kes on segu omadustest. See võib sageli olenev alt andmete tüübist olla keeruline, kuid tavaliselt kombinatoorsete probleemide korralkehtivaid kombinatsioone on täiesti võimalik segada ja väljastada.
Nüüd on vaja põlvkonda juurutada uut geneetilist materjali. Kui seda olulist sammu ei astuta, takerdub teadlane väga kiiresti kohalikesse äärmustesse ega saa optimaalseid tulemusi. See samm on mutatsioon ja seda tehakse üsna lihts alt, muutes väikest osa lastest nii, et need ei peegeldaks valdav alt vanemate geenide alamhulka. Mutatsioon toimub tavaliselt tõenäosuslikult, kuna tõenäosus, et laps seda saab, ja ka selle raskusaste määratakse jaotuse järgi.
Lõpetamine
Lõpuks peab algoritm lõppema. See juhtub tavaliselt kahel juhul: kas see on saavutanud teatud maksimaalse täitmisaja või jõudlusläve. Sel hetkel valitakse välja ja tagastatakse lõplik lahendus.
Evolutsiooniliste algoritmide näide
Nüüd, et illustreerida selle protsessi tulemust, peate nägema nõustajat tegutsemas. Selleks võime meenutada, kuidas mitu põlvkonda dinosauruseid õppisid kõndima (järk-järgult maad omandama), optimeerides oma keha struktuuri ja rakendades lihasjõudu. Kuigi varajase põlvkonna roomajad ei osanud kõndida, suutis nõustaja neid aja jooksul mutatsioonide ja ristumisega muuta kõndimisvõimeliseks.
Need algoritmid muutuvad kaasaegses maailmas üha aktuaalsemaks, kuna nendel põhinevaid lahendusi kasutatakse üha enam sellistes tööstusharudes nagu digitaalne turundus, rahandus jatervishoid.
Kus EA-sid kasutatakse?
Laiemas plaanis kasutatakse evolutsioonilisi algoritme väga erinevates rakendustes, nagu pilditöötlus, sõidukite marsruutimine, mobiilside optimeerimine, tarkvaraarendus ja isegi tehisnärvivõrgu koolitus. Need tööriistad on paljude inimeste igapäevaselt kasutatavate rakenduste ja veebisaitide keskmes, sealhulgas Google Maps ja isegi sellised mängud nagu The Sims. Lisaks kasutab meditsiinivaldkond EA-d vähiraviga seotud kliiniliste otsuste tegemisel. Tegelikult on evolutsioonilised algoritmid nii tugevad, et neid saab kasutada peaaegu kõigi optimeerimisprobleemide lahendamiseks.
Moore'i seadus
EO kasvav levimus on tingitud kahest peamisest tegurist: saadaolev arvutusvõimsus ja suurte andmekogumite kogunemine. Esimest saab kirjeldada Moore'i seadusega, mis sisuliselt ütleb, et arvutusvõimsuse hulk arvutis kahekordistub ligikaudu iga kahe aasta järel. See ennustus on kehtinud aastakümneid. Teine tegur on seotud kasvava sõltuvusega tehnoloogiast, mis võimaldab asutustel koguda uskumatult palju andmeid, mis võimaldab analüüsida suundumusi ja optimeerida tooteid.
Kuidas saavad evolutsioonilised algoritmid turundajaid aidata?
Turutingimused muutuvad kiiresti ja on väga konkurentsivõimelised. See on sundinud turundusjuhte paremate otsuste tegemise nimel võistlema. Saadaval oleva koguse suureneminearvutusvõimsus on pannud töötajad kasutama probleemide lahendamiseks EA-d.
Konversioonide optimeerimine
Üks peamisi eesmärke on suurendada saidi külastajate arvu. See probleem taandub nende kasutajate arvu optimeerimisele, kes teevad seda, mida turundaja soovib. Näiteks kui ettevõte müüb sülearvuteid, on ideaalne suurendada saidi külastajate arvu, kes lõpuks toote ostavad. See on konversioonimäära optimeerimise olemus.
Üks üllatav alt olulisi aspekte on kasutajaliidese valik. Kui veebidisain ei ole väga kasutajasõbralik, on neid, kes ühel või teisel põhjusel jätavad toote ostmata. Eesmärk on siis vähendada nende kasutajate arvu, kes lõpuks konversiooni ei too, mis suurendab üldist kasumit.
