Õrn sissejuhatus geneetilisse algoritmi

Pilt geenist

Tehisintellekti uurimist alustades võisite kuulda midagi, mida nimetatakse geneetiliseks algoritmiks. Pärast selle termini nägemist ei pruugi te sellesse süveneda, kuna see sisaldab sõna 'algoritm'. Ära karda! Selles artiklis näitan teile geneetilise algoritmi lihtsust ja loodetavasti inspireerite teid selle oma jaoks üles ehitama.

Mis on geneetiline algoritm?

Geneetiline algoritm on põhimõtteliselt meetod, mis on loodusliku valiku protsessist suuresti inspireeritud, et leida probleemile parim lahendus.

Looduses jäävad ellu ainult tugevad, nõrkade kõrvaldamise protsessi nimetatakse looduslikuks valikuks. Geneetiline algoritm kasutab sama põhimõtet nõrkade lahenduste kõrvaldamiseks ja parima lahenduse leidmiseks.

Tavaliselt kasutatakse geneetilist algoritmi, kui te ei tea, milline lahendus saab olema. Näiteks soovite luua auto, mis võimaldaks liikuda erinevat tüüpi maastikul. Te ei saa teada, kuidas see auto välja näeb, kuid teate selle eesmärki. Sel juhul saab geneetilist algoritmi kasutada auto genereerimiseks erinevate maastike läbimiseks, kuid auto kujunduse otsustab algoritm.

Geneetilise algoritmi tööprotsess

Nagu varem mainitud, on geneetiline algoritm suuresti inspireeritud looduslikust valikust, nii et geneetilise algoritmi toimimiseks peaksite tegelikult uurima, kuidas looduslik valik toimib.

loodusliku valiku protsess (lihtsustatud)

Ülaltoodud diagramm illustreerib loodusliku valiku protsessi. On selge, et see protsess hõlmab viit peamist sammu. Esialgne samm on selektsioon. Selles etapis valib loodus isendid, kellel on tugevad geenid, esialgsest populatsioonist, pärast mida hakkavad nad astuma järgmisesse etappi, mis paaritub. Pärast paaritumisastme saamist sünnitavad nad lapse, mida me kutsume selleks paljunemiseks. Seejärel konkreetne laps muteerus, et lisada geenile mõningaid variatsioone, ja kolis lõpuks tagasi populatsiooni.

Geneetilise algoritmi protsess on üsna sarnane ülaltoodud protsessiga, ainus erinevus on see, et see lisas mõned täiendavad üksikasjad.

geneetilise algoritmi tööprotsess

Alustuseks algab ka geneetilise algoritmi tööprotsess algse populatsiooni olemasolul. Esimene põhietapp on sobivuse arvutamine, sobivuse arvutamist võib pidada valikuprotsessi osaks, kuna seda kasutati põhimõtteliselt iga indiviidi hinde arvutamiseks, et näidata, kas tegemist on tugeva või nõrga isendiga. Seejärel valitakse kõik tugevad üksused ja antakse edasi etapiks, mida nimetatakse ületamiseks. See etapp on nagu eelmise skeemi paaritusetapp. Selles etapis valitakse tugevate olemite loendist 2 juhuslikku lapsevanemat, et teostada nn crossover, mida arutame hiljem. Pärast ristamist luuakse laps ja muteeritakse see ka geenile mõne variatsiooni lisamiseks. Lõpuks taasühineb see laps elanikkonnaga ja protsess kordub uuesti.

Mida kuradit on sobivus

Geneetilises algoritmis mängib sobivus valikufaasis pöördelist rolli. Fitness on üksus, mis valib oma iseloomu edasi andmiseks "hinde". Näiteks kui inimesel on tõsine haigus, on tema sobivuse skoor madal ja tõenäosus saada lapsi on vähem tõenäoline, kuna ka tema lapsed pärivad tema haiguse. Seetõttu, kui lahenduse sobivus on madal, ei pruugi te soovida sellele uut lahenduse baasi luua, kuna tulemus oleks sama halb kui vana lahendus.

Proovige ette kujutada, et teile antakse probleem, probleem on leida parim viis punasele mütsile tema vanaema majja sõitmiseks. Oletame, et ta soovib jõuda oma vanaema majja võimalikult lühikese aja jooksul, seetõttu saab marsruudi sobivust arvutada tema reisimiseks kulunud aja järgi. Kui on marsruut, mille pikkus on 400 meetrit ja mille läbimiseks kulus tal 10 minutit, siis on selle sobivus kindlasti väiksem kui 500 meetri pikkuse marsruudi sobivus, kuid selle läbimiseks kulus ainult 8 minutit, marsruut arvutab baasi sõiduaja, mitte selle pikkuse põhjal. Seetõttu valitakse tõenäolisemalt 500 meetri pikkune marsruut, mis ühendatakse teiste marsruutidega.

Valides hea!

Geneetilise algoritmi valimisetapis on sobiva lahenduse valimine. Pärast sobivuse skoori arvutamist on järgmine samm mõne salapärase meetodi kasutamine lahenduste loendi valimiseks, mida hiljem saab kasutada parema lahenduse saamiseks.

Ehkki saate luua oma viisi sobivate lahenduste valimiseks, saate kasutada mõnda kuulsat meetodit:

  • Fitnessiga proportsionaalne valik
  • Turniiride valik
  • Kärbimise valik
  • Fitnessi vormiriietus

Ülaltoodud loetelu ei ole piisav, täiendavate meetodite leiate siit.

Võtame näitena esimese meetodi. Erinevalt selle nimest on selle meetodi tegelik kontseptsioon absurdselt lihtne. Sobivuse proportsionaalne valik AKA rulettratta valik on meetod, mille abil valitakse rekombineerimiseks potentsiaalsed lahendused.

Kujutage ette, kui kotis on 10 marmorit, täpsemalt 5 sinist, 3 punast ja 2 valget marmorit. Saate hõlpsasti arvutada, et kui valite kotist juhusliku marmori, on teil 5/10 võimalus valida sinine, 3/10 punaseks ja 2/10 valgeks. Nii töötab sobivuse proportsionaalne valik, protsess on siiski pisut erinev.

Sobivuse proportsionaalse valiku korral valitakse esmalt juhuslik arv, seejärel võrreldakse seda juhuslikult valitud lahenduse sobivusega. Treeningväärtuse väärtus on tavaliselt piiratud 0 ja 1 vahel. Kui juhuslik väärtus on sellest sobivuse skoorist väiksem, valitakse lahendus. Seega, mida kõrgem on lahenduse sobivus, seda suurem on tõenäosus, et see valitakse. Näiteks kui juhuslik arv läheb vahemikku 0 kuni 1, on 50%, see on väiksem kui 0,5 ja 80%, see on väiksem kui 0,8, kuid see ei ole tõenäoliselt väiksem kui 0,2, see tähendab, et kui lahenduse sobivus on 0,8, 80% sellest valitakse rekombinatsiooniks ja 0,2 sobivusega lahenduse jaoks on vaja valida ainult 20%. 0,2 sobivuse lahendust valitakse küll harva, kuid see aitab ka lahenduse omadusi varieerida, kuna see lahendus võib sisaldada mõningaid atribuute, mida on vaja hilisemaks õnnestumiseks.

Crossoveri teostamine

Crossover on etapp, kus valitud lahendused ühendatakse uuteks lahendusteks. Nii nagu valimisetapp, on ka ristsuhtumiseks palju tehnikaid ja neid leiate siit.

Sarnaselt valikuetapiga saate ka üleminekuetapis leiutada oma ristmõtetehnikaid, kuid on ka mõnda tehnikat, mida saate kasutada:

  • Ühepunktiline crossover
  • Kahepunktiline crossover
  • Ühtne ristside
  • Kolm vanemat crossoverit

Paremaks mõistmiseks selgitan ühtlast ristmõtetehnikat, mis on tehnika, mida pean kõige kergemaks rakendada.

Ühtse ristmeetodiga valiti juhuslikult osa 2 lahuse geenist, et kombineerida ja luua uus (loodetavasti parem) lahendus.

Ühtlase ristumise esimene samm on eelmises valimisetapis valitud lahenduste hulgast 2 juhusliku lahenduse valimine. Seejärel valitakse kahe lahuse iga osa, et lisada lapselahenduse alus muutujale, mida nimetatakse segamise suhteks. Segamissuhe on asi, mis otsustab võimaluse, et tõenäoliselt valitakse mõni lahendus lapselahendusele. Näiteks on 2 lahendust: A ja B ning soovite, et lapselahendusel oleks rohkem osi, mis on lahusest A võetud, võite suurendada segamissuhet, pärast seda silmus läbi lahuse A ja B kõigi osade, igas silmus , looge uus juhuslik arv ja võrrelge seda segamissuhtega, kui see on väiksem kui segamissuhe, siis vali lahendus A-osa, vali teine ​​variant B. Samamoodi, kui segamise suhe on 0,5, siis A ja B-l on umbes 50% valitakse.

Ühtlane ristmik segamissuhtega 0,5

Ülaloleval pildil näidatakse lahuse A ja B abil saadud lapselahus C, mille segusuhe on 0,5 või 50%. Mõlema lahuse iga osa otsustati valida segamise suhte alusel või mitte, ja otsustamiseks võrreldi segamissuhet juhusliku arvuga. See on nagu mündi viskamine, et valida, kus B tuleks kasutada A asemel ja vastupidi.

Muteerige laps!

Ei ei ei, me ei muuda oma lapsi mõneks metallküüntega tüübiks ja laseme neil juhusliku puutüve peal surra!

Selle asemel on lapsele mutatsiooni lisamine just nagu aitamine

Erinevalt mõeldes saab indiviid kas karja juhiks või täielikuks lolliks.

Mutatsiooni näide

Nagu näete, läheb punane laps teiste lastega võrreldes teist teed. Selle põhjuseks on asjaolu, et kui punane laps karja jälgib, lisasime talle mõne mutatsiooni ja aitame tal seetõttu valida teistsugune tee. Muidugi võib see erinev tee olla ka ummikseis, kuid ilmselgelt viib see tee eduni! See on mutatsiooni etapi tegelik eesmärk.

Lapse muteerimiseks on olemas ka mitmesuguseid tehnikaid, mida saate kasutada:

  • Biti stringi mutatsioon
  • Pööra natuke
  • Mittemoodne
  • Ühtne

Nendest leiate rohkem siit.

Selle paremaks mõistmiseks demonstreerin “bitstringi mutatsiooni” tehnikat.

Kujutage ette, et teete robotit, et vältida selle ees olevaid esemeid. Robot peab vältima kõigi objektide jõudmist lõppsihtkohta ja selle loomulik olek liigub edasi. Objekti vältimiseks on selle geenis rida vasakut ja paremat stringi, mis näitab, kuidas bot liigub.

Binaarstringi jaoks kasutatakse tavaliselt „bitistringi mutatsiooni”, kuna see meetod pöörab geenis 1 või enam juhuslikult valitud bitti. Näiteks:

Näide bitistringi mutatsioonist

Proovige nüüd muuta 1 ja 0 vasakule ja paremale ning mõelge, kuidas robot töötab. Kuna robot võib takerduda suure objektiga kokku puutudes, aitab mutatsioon selle järglastel valida uue liikumissuuna ja vältida seda objekti. Kujutage ette, paljude põlvkondade vältel pöörab robot paremale alles siis, kui kohtub objektiga ja sureb, kuid järgmises põlvkonnas pööras robot ühtäkki vasakule, kuna selle geeni parem string keerati vasakule ja robot jõudis lõpuks sihtkohta. Põhimõtteliselt see, kuidas "bitistringi mutatsioon" töötab.

Protsessi lõpp

Pärast lapse muteerimist ühendatakse see uue muteerunud lapsega, et reformida uut populatsiooni ja kogu protsess algab otsast peale.

Millal see siis peatub? Vastus on äärmiselt lihtne, kui lõpetate kümne sõrmega klaviatuuri tippimise harjutamise? Kui teie kirjutamisoskus on muidugi täiuslik. Sama asi geneetilise algoritmiga, protsess peatub, kui teatud lahenduse sobivus saavutab soovitud sobivuse. Näiteks soovite, et eelmises näites sisalduv robot jõuaks sihtkohta võimalikult väikse ajakuluga.

Seadistate sobivusläveni 4 minutit, kui robotil on aega rohkem kui 4 minutit, see tähendab, et protsessi korratakse seni, kuni robotilõpuaeg on vähem kui 4 minutit või sellega võrdne.

Järeldus

See on minu artikli lõpp, ma loodan, et pärast seda artiklit saate parema ülevaate geneetilisest algoritmist, mis on inspireerinud omaenda loomise.

Siin on mõned lingid, mille abil saate geneetilise algoritmi kohta rohkem teada saada:

  • Daniel Shiffmani videod geneetilise algoritmi kohta:
  • Minu näide geneetilise algoritmi kasutamise kohta pääsukoodi arvamiseks
  • tutorialspoint juhendamine geneetilise algoritmi kohta
  • Goran Murici video näitest, kus kasutatakse tee leidmiseks geneetilist algoritmi