Dirbtinio intelekto srityje evoliucinis algoritmas (EA) yra visos populiacijos skaičiavimų, pagrįstų metaeuristiniu optimizavimu, poaibis. EA naudoja biologinio vystymosi įkvėptus mechanizmus, tokius kaip reprodukcija, mutacija, rekombinacija ir atranka. Evoliucinio optimizavimo algoritmų problemos sprendimo kandidatas vaidina individų vaidmenį populiacijoje. Taip pat kūno rengybos funkcija lemia atsakymų kokybę.
Evoliuciniai algoritmai dažnai gerai suderina visų tipų problemų sprendimus. Nes idealiu atveju jie nedaro jokių prielaidų apie pagrindinį fitneso kraštovaizdį. Evoliuciniam modeliavimui ir genetiniams algoritmams naudojami metodai paprastai apsiriboja mikroevoliucinių procesų tyrimais ir planavimo modeliais, pagrįstais ląstelių stadijomis. Daugumoje realių EA programų skaičiavimo sudėtingumas yra pernelyg didelis veiksnys.
Tiesą sakantši problema susijusi su kūno rengybos funkcijos įvertinimu. Fitneso apytikslis įvertinimas yra vienas iš sprendimų, kaip įveikti šį sunkumą. Tačiau iš pažiūros paprastas EA gali išspręsti dažnai sudėtingas problemas. Todėl negali būti tiesioginio ryšio tarp sekos sudėtingumo ir problemos. Daugiau informacijos rasite knygose „Evoliuciniai algoritmai“.
Įdiegimas
Pirmas žingsnis – atsitiktinai sukurti pradinę individų populiaciją.
Antras žingsnis – įvertinti kiekvieno asmens tinkamumą šioje grupėje (laiko limitą, pakankamą pasirengimą ir pan.).
Trečias veiksmas – pakartokite šiuos regeneravimo veiksmus iki galo:
- Pasirinkite veisimui tinkamiausius žmones (tėvus).
- Atveskite naujus asmenis, kurie išlaikė evoliucinį algoritmą, naudodami kryžminimą ir mutaciją, kad susilauktumėte palikuonių.
- Įvertinkite naujų žmonių individualų tinkamumą.
- Pakeiskite jais mažiausiai tinkančius gyventojus.
Tipai
Genetinis algoritmas yra evoliucinė seka, populiariausias ekspertų patarėjo tipas. Problemos sprendimo ieškoma skaičių eilučių (tradiciškai dvejetainių, nors geriausi atvaizdai dažniausiai yra tie, kurie labiau atspindi sprendžiamą problemą) forma, taikant tokius operatorius kaip rekombinacija ir mutacija (kartais vienas, kai kuriais atvejais abu). Šio tipo ekspertų patarėjas dažnai naudojamas optimizavimo problemoms spręsti. Kitas pavadinimas yra fetura (iš lotynų kalbos reiškia „gimimas“):
- Genetinis programavimas. Jame sprendimai pateikiami kaip kompiuteriniai kodai, o jų tinkamumą lemia jų gebėjimas atlikti skaičiavimo užduotis.
- Evoliucinis programavimas. Panašus į evoliucinį genetinį algoritmą, tačiau struktūra yra fiksuota ir jos skaitiniai parametrai gali keistis.
- Genų ekspresijos programavimas. Kuria kompiuterines programas, bet tyrinėja genotipo-fenotipo sistemą, kai skirtingų dydžių projektai yra užkoduoti fiksuoto ilgio linijinėse chromosomose.
- Strategija. Veikia su realiųjų skaičių vektoriais kaip sprendinių atvaizdais. Paprastai naudojami savaime prisitaikantys evoliucinio mutacijų greičio algoritmai.
- Diferencinis vystymas. Remiantis vektorių skirtumais, todėl pirmiausia tinka skaitmeninio optimizavimo problemoms spręsti.
- Neuroevoliucija. Panašiai kaip evoliucinis programavimas ir genetiniai algoritmai. Tačiau pastarieji yra dirbtiniai neuroniniai tinklai, apibūdinantys jungčių struktūrą ir svorį. Genomo kodavimas gali būti tiesioginis arba netiesioginis.
Palyginimas su biologiniais procesais
Galimas daugelio evoliucinių algoritmų apribojimas yra tai, kad nėra aiškaus skirtumo tarp genotipo ir fenotipo. Gamtoje apvaisintas kiaušinėlis subręsta vykstant sudėtingam procesui, vadinamam embriogeneze. Manoma, kad dėl šio netiesioginio kodavimo genetinės paieškos tampa patikimesnės (t. y. mažesnė tikimybė sukelti mirtinas mutacijas), taip pat gali pagerinti organizmo gebėjimą vystytis. Tokie netiesioginiai (kitaip tariant,generatyvinės arba raidos) koduotės taip pat leidžia evoliucijai išnaudoti aplinkos dėsningumą.
Naujasis darbas dirbtinės embriogenezės ar vystymosi sistemų srityje siekia išspręsti šias problemas. Programuojant genų raišką, sėkmingai tyrinėjama genotipo-fenotipo sritis, kur pirmoji susideda iš fiksuoto ilgio linijinių daugiagenių chromosomų, o antroji – iš daugybės įvairių dydžių ir formų ekspresijos medžių ar kompiuterinių programų.
Susijusios technikos
Algoritmai apima:
- Skruzdžių kolonijų optimizavimas. Jis pagrįstas idėja, kad vabzdžiai ieško maisto jungdamiesi su feromonais, kad sudarytų kelius. Visų pirma tinka kombinatoriniam optimizavimui ir grafiko problemoms spręsti.
- Šakninio slankiklio algoritmas. Kūrėją įkvėpė augalų šaknų funkcija gamtoje.
- Dirbtinių bičių šeimų algoritmas. Remiantis bičių elgesiu. Jis pirmiausia siūlomas skaitmeniniam optimizavimui ir išplėstas kombinatorinėms, ribotosioms ir daugiatikslėms problemoms spręsti. Bičių algoritmas pagrįstas vabzdžių ieškant maisto. Jis buvo pritaikytas daugelyje programų, tokių kaip maršruto parinkimas ir planavimas.
- Dalelių spiečių optimizavimas – pagrįstas gyvūnų bandos elgesio idėjomis. Taip pat pirmiausia tinka skaitmeninių procesų užduotims.
Kiti populiarūs metaeuristiniai metodai
- Medžioklės paieška. Metodas, pagrįstas grupiniu tam tikrų gyvūnų, pavyzdžiui, vilkų, gaudymupaskirstyti savo pareigas apsupti grobį. Kiekvienas evoliucinio algoritmo narys tam tikru būdu yra susijęs su kitais. Tai ypač pasakytina apie lyderį. Tai nuolatinio optimizavimo metodas, pritaikytas kaip kombinacinio proceso metodas.
- Ieškokite pagal išmatavimus. Skirtingai nuo gamtos pagrįstų metaeuristinių metodų, adaptyvaus proceso algoritmas nenaudoja metaforos kaip pagrindinio principo. Atvirkščiai, jis naudoja paprastą į našumą orientuotą metodą, pagrįstą paieškos matmenų santykio parametro atnaujinimu kiekvienoje iteracijoje. Firefly algoritmas yra įkvėptas to, kaip ugniažolės traukia viena kitą mirksinčia šviesa. Tai ypač naudinga atliekant daugiarūšį optimizavimą.
- Ieškokite harmonijos. Remiantis muzikantų elgesio idėjomis. Šiuo atveju evoliuciniai algoritmai yra kombinatorinio optimizavimo būdas.
- Gauso adaptacija. Remiantis informacijos teorija. Naudojamas siekiant maksimaliai padidinti našumą ir vidutinį prieinamumą. Evoliucinių algoritmų pavyzdys šioje situacijoje: entropija termodinamikoje ir informacijos teorijoje.
Memetic
Mišrus metodas, pagrįstas Richardo Dawkinso idėja apie memą. Paprastai tai yra populiacijos algoritmas, derinamas su individualiomis mokymosi procedūromis, galinčiomis atlikti vietinius patobulinimus. Pabrėžia konkrečioms problemoms būdingų žinių naudojimą ir bandymus organizuoti smulkias ir visuotines paieškas sinergiškai.
Evoliucinisalgoritmai yra euristinis požiūris į problemas, kurių negalima lengvai išspręsti daugianario laiku, pvz., klasikinės NP sudėtingos problemos ir bet kas kita, kurios išsamus apdorojimas užtruktų per ilgai. Kai naudojami atskirai, jie dažniausiai naudojami kombinatorinėms problemoms spręsti. Tačiau genetiniai algoritmai dažnai naudojami kartu su kitais metodais, padedančiais greitai rasti kelias optimalias darbo pradžios vietas.
Evoliucinio algoritmo (žinomo kaip patarėjas) prielaida yra gana paprasta, nes esate susipažinę su natūralios atrankos procesu. Jį sudaro keturi pagrindiniai žingsniai:
- inicializacija;
- pasirinkimas;
- genetiniai operatoriai;
- pabaiga.
Kiekvienas iš šių žingsnių apytiksliai atitinka tam tikrą natūralios atrankos aspektą ir suteikia paprastus būdus moduliuoti šios kategorijos algoritmus. Paprasčiau tariant, EA stipriausi nariai išgyvens ir dauginsis, o netinkami nariai mirs ir neprisidės prie naujos kartos genofondo.
Inicializacija
Norėdami pradėti algoritmą, pirmiausia turite sukurti sprendimų rinkinį. Visuomenėje bus savavališkai daug galimų problemų teiginių, dažnai vadinamų nariais. Jie dažnai generuojami atsitiktinai (neviršijant užduoties apribojimų) arba, jei žinomos tam tikros išankstinės žinios, preliminariai sutelktos į tai, kas laikoma idealia. Svarbu, kad gyventojai apimtų platų sprendimų spektrą,nes tai iš esmės yra genofondas. Todėl, jei norime ištirti daugybę skirtingų algoritmo galimybių, reikia stengtis turėti daug skirtingų genų.
Pasirinkimas
Sukūrus populiaciją, jos nariai dabar turi būti įvertinti pagal kūno rengybos funkciją. Fitneso funkcija atsižvelgia į nario charakteristikas ir pateikia skaitinį nario tinkamumo vaizdą. Jas sukurti dažnai gali būti labai sunku. Svarbu rasti gerą sistemą, kuri tiksliai atvaizduotų duomenis. Tai labai specifinė problema. Dabar reikia apskaičiuoti visų dalyvių tinkamumą ir atrinkti geriausius narius.
Kelios tikslo funkcijos
EA taip pat gali būti išplėsta, kad būtų galima naudoti šias sistemas. Tai šiek tiek apsunkina procesą, nes vietoj vieno optimalaus taško identifikavimo juos naudojant gaunamas rinkinys. Sprendimų rinkinys vadinamas Pareto siena ir apima elementus, kurie yra vienodai tinkami ta prasme, kad nė vienas iš jų nedominuoja jokioje kitoje.
Genetiniai operatoriai
Šį veiksmą sudaro du poveiksmiai: kryžminimas ir mutacija. Pasirinkus geriausius terminus (dažniausiai 2 geriausius, bet šis skaičius gali skirtis), dabar jie naudojami kuriant naujos kartos algoritmą. Taikant pasirinktų tėvų savybes, sukuriami nauji vaikai, kurie yra savybių mišinys. Tai dažnai gali būti sudėtinga, atsižvelgiant į duomenų tipą, bet dažniausiai dėl kombinacinių problemųvisiškai įmanoma maišyti ir išvesti galiojančius derinius.
Dabar būtina į kartą įvesti naują genetinę medžiagą. Jei šis svarbus žingsnis nebus žengtas, mokslininkas labai greitai įklimps į vietinius kraštutinumus ir negaus optimalių rezultatų. Šis žingsnis yra mutacija, ir tai daroma gana paprastai, pakeičiant nedidelę vaikų dalį taip, kad jie daugiausia neatspindėtų tėvų genų pogrupių. Mutacija dažniausiai įvyksta tikimybiškai, nes tikimybę, kad vaikas ją susirgs, taip pat jos sunkumą lemia pasiskirstymas.
Nutraukimas
Galų gale algoritmas turi baigtis. Paprastai tai nutinka dviem atvejais: arba jis pasiekė maksimalų vykdymo laiką, arba pasiekė našumo slenkstį. Šiuo metu galutinis sprendimas pasirenkamas ir grąžinamas.
Evoliucinių algoritmų pavyzdys
Dabar, norėdami iliustruoti šio proceso rezultatą, turite pamatyti, kaip patarėjas veikia. Norėdami tai padaryti, galime prisiminti, kaip kelios dinozaurų kartos išmoko vaikščioti (palaipsniui įvaldė žemę), optimizuodami savo kūno struktūrą ir pritaikydami raumenų jėgą. Nors ankstyvosios kartos ropliai nemokėjo vaikščioti, patarėjas laikui bėgant sugebėjo juos paversti mutacijomis ir pereiti į tokią formą, kuri galėtų vaikščioti.
Šie algoritmai tampa vis aktualesni šiuolaikiniame pasaulyje, nes jais pagrįsti sprendimai vis dažniau naudojami tokiose pramonės šakose kaip skaitmeninė rinkodara, finansai irsveikatos priežiūra.
Kur naudojami EA?
Plačiau kalbant, evoliuciniai algoritmai naudojami įvairiose programose, tokiose kaip vaizdo apdorojimas, transporto priemonių maršruto parinkimas, mobiliojo ryšio optimizavimas, programinės įrangos kūrimas ir net dirbtinio neuroninio tinklo mokymas. Šie įrankiai yra daugelio žmonių kasdien naudojamų programų ir svetainių, įskaitant „Google“žemėlapius ir net tokius žaidimus kaip „The Sims“, pagrindas. Be to, medicinos sritis naudoja EA, kad padėtų priimti klinikinius sprendimus dėl vėžio gydymo. Tiesą sakant, evoliuciniai algoritmai yra tokie tvirti, kad juos galima naudoti sprendžiant beveik bet kokią optimizavimo problemą.
Moore'o įstatymas
Didėjantį EO paplitimą lemia du pagrindiniai veiksniai: turima skaičiavimo galia ir didelių duomenų rinkinių kaupimas. Pirmąjį galima apibūdinti Moore'o dėsniu, kuris iš esmės teigia, kad skaičiavimo galios kiekis kompiuteryje padvigubėja maždaug kas dvejus metus. Ši prognozė galioja dešimtmečius. Antrasis veiksnys yra susijęs su didėjančia priklausomybe nuo technologijų, kurios leidžia institucijoms surinkti neįtikėtinai daug duomenų, o tai leidžia analizuoti tendencijas ir optimizuoti produktus.
Kaip evoliuciniai algoritmai gali padėti rinkodaros specialistams?
Rinkos sąlygos greitai keičiasi ir labai konkurencingos. Tai privertė rinkodaros vadovus konkuruoti dėl geresnių sprendimų priėmimo. Galimybės padidėjimasSkaičiavimo galia paskatino darbuotojus naudoti EA problemoms spręsti.
Konversijų optimizavimas
Vienas iš pagrindinių tikslų – padidinti svetainės lankytojų skaičių. Ši problema susijusi su vartotojų, kurie daro tai, ko nori rinkodaros specialistas, skaičiaus optimizavimas. Pavyzdžiui, jei įmonė parduoda nešiojamuosius kompiuterius, idealu yra padidinti svetainės lankytojų, kurie galiausiai perka produktą, skaičių. Tai yra konversijų rodiklio optimizavimo esmė.
Vienas iš stebėtinai svarbių aspektų yra vartotojo sąsajos pasirinkimas. Jei interneto dizainas nėra labai patogus vartotojui, yra tokių, kurie dėl vienokių ar kitokių priežasčių produkto neperka. Tada tikslas yra sumažinti naudotojų, kurie nevykdo konversijos, skaičių, o tai padidina bendrą pelną.
