Uvod v genetske algoritme v strojnem učenju

introduction genetic algorithms machine learning

vprašanja in odgovori za skrbnike informatica

Ta vadnica genetskega algoritma podrobno pojasnjuje, kaj so genetski algoritmi in njihova vloga pri strojnem učenju :

V Prejšnja vadnica smo spoznali modele umetnih nevronskih mrež - večplastni perceptron, povratno razmnoževanje, radialne pristranskosti in Kohonenove samoorganizirajoče se zemljevide, vključno z njihovo arhitekturo.

Osredotočili se bomo na genetske algoritme, ki so se pojavili prej kot na nevronske mreže, zdaj pa je GA prevzel NN. Čeprav ima GA še vedno aplikacije v resničnem življenju, kot so težave z optimizacijo, kot so razporejanje, igranje iger, robotika, oblikovanje strojne opreme, težave s prodajalci itd.

Genetski algoritmi so algoritmi, ki temeljijo na evolucijski ideji naravne selekcije in genetike. GA so prilagodljivi hevristični algoritmi iskanja, to pomeni, da algoritmi sledijo iterativnemu vzorcu, ki se s časom spreminja. To je vrsta učenja okrepitve, pri kateri so potrebne povratne informacije, ne da bi povedali pravilno pot. Povratne informacije so lahko pozitivne ali negativne.

=> Preberite celotno serijo usposabljanja za strojno učenje

Kaj se boste naučili:

• Zakaj uporabljati genetske algoritme
  • Biološko ozadje genetskih algoritmov
• Kaj so genetski algoritmi
  • Korelacija kromosoma z GA
  • Pomembna terminologija v GA
  • Preprost genetski algoritem
  • Način izbire kolesa za ruleto
  • Druge izbirne metode
  • Crossover
  • Mutacija
  • Kdaj ustaviti genetski algoritem
• Prednosti in slabosti genetskega algoritma
• Aplikacije genetskih algoritmov
• Zaključek
  • Priporočeno branje

Zakaj uporabljati genetske algoritme

GA so močnejši algoritmi, ki jih lahko uporabimo za različne optimizacijske probleme. Ti algoritmi v prisotnosti šuma ne odstopajo zlahka, za razliko od drugih algoritmov AI. GA lahko uporabimo pri iskanju velikega prostora ali multimodalnega prostora.

Biološko ozadje genetskih algoritmov

Genetika izhaja iz grške besede 'geneza', kar pomeni rasti. Genetika določa dejavnike dednosti, podobnosti in razlike med potomci v procesu evolucije. Genetski algoritmi izhajajo tudi iz naravnega razvoja.

Nekatere terminologije v biološkem kromosomu

• Kromosomi: Vse genetske informacije o vrsti so shranjeni kromosomi.
• Geni: Kromosomi so razdeljeni na več delov, imenovanih geni.
• Aleli: Geni prepoznajo značilnosti posameznika. Možnost kombinacije genov za oblikovanje lastnosti se imenuje Alleles. Gen ima lahko različne alele.
• Genski bazen: Vse možne kombinacije genov, ki so vsi aleli v populacijskem združenju, se imenuje genski sklad.
• Genom: Nabor genov vrste se imenuje genom.
• Locus: Vsak gen ima položaj v genomu, ki se imenuje lokus.
• Genotip: Popolna kombinacija genov pri posamezniku se imenuje genotip.
• Fenotip: Nabor genotipov v dekodirani obliki se imenuje fenotip.

Kaj so genetski algoritmi

Genetski algoritmi spodbujajo proces kot v naravnih evolucijskih sistemih. Charles Darwin je navedel teorijo evolucije, da se v naravni evoluciji biološka bitja razvijajo po načelu 'preživetja najmočnejših'. Iskanje GA je namenjeno spodbujanju teorije o »preživetju najsposobnejših«.

GA izvajajo naključno iskanje za reševanje optimizacijskih problemov. GA uporablja tehnike, ki uporabljajo prejšnje pretekle informacije za usmerjanje iskanja v optimizacijo v novem iskalnem prostoru.

Korelacija kromosoma z GA

Človeško telo ima kromosome, ki so narejeni iz genov. Skupina vseh genov določene vrste se imenuje genom. Pri živih bitjih so genomi shranjeni v različnih kromosomih, medtem ko so v GA vsi geni shranjeni v istem kromosomu.

Primerjava med naravno evolucijo in terminologijo genetskega algoritma

Pomembna terminologija v GA

• Prebivalstvo: Gre za skupino posameznikov. Populacija vključuje število preizkušenih posameznikov, informacije o vesoljskem iskanju in parametre fenotipa. Na splošno je populacija naključno inicializirana.
• Posamezniki: Posamezniki so ena sama rešitev v populaciji. Posameznik ima nabor parametrov, imenovanih geni. Geni skupaj tvorijo kromosome.
• Geni: Geni so gradniki genetskih algoritmov. Kromosom je sestavljen iz genov. Rešitev problema lahko določijo geni. Predstavljeni so z bitnim (0 ali 1) nizom naključne dolžine.
• Fitnes: Fitnes pove vrednost fenotipa težave. Fitnes funkcija pove, kako blizu je rešitev optimalni rešitvi. Kondicijska funkcija je določena na več načinov, na primer vsota vseh parametrov, povezanih s problemom - evklidska razdalja itd. Za oceno telesne pripravljenosti ni pravila.

Preprost genetski algoritem

Preprost GA ima populacijo posameznih kromosomov. Ti kromosomi predstavljajo možne rešitve. Na teh naborih kromosomov se uporabljajo reprodukcijski operaterji za izvajanje mutacij in rekombinacije. Zato je pomembno najti ustrezne reprodukcijske operaterje, saj je vedenje GA odvisno od tega.

Preprost genetski algoritem je naslednji:

# 1) Začnite z naključno ustvarjeno populacijo.

#two) Izračunajte kondicijsko funkcijo vsakega kromosoma.

# 3) Ponavljajte korake, dokler ne nastane n potomcev. Potomci so ustvarjeni, kot je prikazano spodaj.

• Iz populacije izberite par kromosomov.
• Križanje para z verjetnostjo p_coblikovati potomce.
• Mutacija križanca z verjetnostjo p_m.

# 4) Prvotno populacijo zamenjajte z novo in pojdite na 2. korak.

Oglejmo si korake, ki so bili uporabljeni v tem postopku ponovitve. Ustvari se začetna populacija kromosomov. Začetna populacija mora vsebovati dovolj genov, da se lahko ustvari kakršna koli rešitev. Prvi nabor prebivalstva se ustvari naključno.

• Izbira: Najboljši nabor genov je izbran glede na fitnes funkcijo. Izbrana je vrvica z najboljšo fitnes funkcijo.
• Razmnoževanje: Novi potomci nastanejo z rekombinacijo in mutacijo.
• Vrednotenje: Ustvarjeni novi kromosomi so ovrednoteni glede njihove kondicije.
• Zamenjava: V tem koraku se staro prebivalstvo nadomesti z novo ustvarjenim prebivalstvom.

Način izbire kolesa za ruleto

Izbira kolesa rulete je metoda izbire, ki se pogosto uporablja.

Izbirni postopek je kratek, kot je prikazano spodaj:

Pri tej metodi se linearno išče skozi kolo rulete. Reže na kolesu se stehtajo glede na posamezno vrednost kondicije. Ciljna vrednost se nastavi naključno glede na delež vsote telesne pripravljenosti v populaciji.

Nato se populacija išče, dokler ni dosežena ciljna vrednost. Ta metoda ne zagotavlja najbolj sposobnih posameznikov, vendar ima verjetnost, da bodo najbolj sposobni.

Oglejmo si korake pri izbiri kolesa rulete.

Pričakovana vrednost posameznika = Individualna kondicija / kondicija prebivalstva. Reže za kolesa so dodeljene posameznikom glede na njihovo telesno pripravljenost. Kolo se zavrti N-krat, pri čemer je N skupno število posameznikov v populaciji. Ko je ena rotacija končana, je izbrani posameznik postavljen v bazen staršev.

1. Naj bo skupna pričakovana vrednost števila posameznikov v populaciji S.
2. Korake ponovite 3-5 n krat.
3. Izberite celo število s med 0 in S.
4. Preglejte posameznike v populaciji, seštevajte pričakovane vrednosti, dokler vsota ne preseže s.
5. Izbran je posameznik, katerega pričakovana vrednost vsoto preseže mejo s.

Pomanjkljivosti izbire kolesa za ruleto:

1. Če se kondicija zelo razlikuje, bo obseg kolesa rulete največji kromosom s funkcijo kondicije zajel največ, zato imajo drugi zelo malo možnosti, da jih izberejo.
2. Hrupno je.
3. Razvoj je odvisen od razlike v kondiciji prebivalstva.

Druge izbirne metode

Obstajajo številne druge metode izbire, uporabljene v “Izbor” korak genetskega algoritma.

Razpravljali bomo o dveh drugih pogosto uporabljenih metodah:

# 1) Izbira ranga: Pri tej metodi dobi vsak kromosom kondicijsko vrednost iz razvrstitve. Najslabša sposobnost je 1 in najboljša sposobnost N. To je metoda počasne konvergence. Pri tej metodi se ohranja raznolikost, ki vodi do uspešnega iskanja.

Izberejo se potencialni starši, nato pa se izvede turnir, na katerem se odloči, kateri od posameznikov bo starš.

# 2) Izbor turnirja: Pri tej metodi se za populacijo uporablja strategija selektivnega pritiska. Najboljši posameznik je tisti z najvišjo kondicijo. Ta posameznik je zmagovalec turnirskega tekmovanja med Nu posamezniki v populaciji.

Turniška populacija skupaj z zmagovalcem se ponovno doda v bazen, da ustvari nove potomce. Razlika v kondicijskih vrednostih zmagovalca in posameznikov v parilnem bazenu zagotavlja selektivni pritisk za optimalne rezultate.

Crossover

Gre za postopek odvzema dveh oseb in rojevanja otroka od njih. Razmnoževalni postopek po izbiri naredi klone dobrih pikov. Operator križanja je uporabljen nad strunami, da ustvari boljše potomce.

Izvedba operaterja križanja je naslednja:

1. Dva prebivalca sta naključno izbrana med prebivalstvom, da bi ustvarila potomce.
2. Naključno je izbrano križišče po dolžini niza.
3. Vrednosti na spletnem mestu se zamenjajo.

Izvedeni križanec je lahko križišče z eno točko, križanje z dvema točkama, križanje z več točkami itd. Križanec z eno točko ima eno mesto križanja, dvotirno križišče pa ima dve mesti, kjer se vrednosti zamenjajo.

To lahko vidimo v spodnjem primeru:

Enotočkovni križanec

Dvotočkovni križanec

Verjetnost križanja

P_c, verjetnost križanja je izraz, ki opisuje, kako pogosto bo izveden križanje. Verjetnost 0% pomeni, da bodo novi kromosomi natančna kopija starih kromosomov, medtem ko 100% verjetnost pomeni, da so vsi novi kromosomi narejeni s križanjem.

Mutacija

Mutacija se opravi po križanju. Medtem ko se križanec osredotoča samo na trenutno rešitev, operacija mutacije išče po celotnem iskalnem prostoru. Ta metoda je obnovitev izgubljenih genetskih informacij in distribucija genetskih informacij.

Ta izvajalec pomaga ohranjati gensko raznolikost populacije. Pomaga preprečevati lokalne minimume in preprečuje ustvarjanje neuporabnih rešitev iz katere koli populacije.

Mutacija se izvaja na več načinov, na primer z majhno verjetnostjo obrne vrednost vsakega gena ali izvede mutacijo le, če izboljša kakovost raztopine.

Nekateri načini mutacije so:

• Prelistavanje: Spreminjanje od 0 do 1 ali 1 do 0.
• Izmenjava: Izbereta se dva naključna položaja in vrednosti se zamenjajo.
• Vzvratno: Izbere se naključni položaj in biti ob njem se obrnejo.

Oglejmo si nekaj primerov vsakega:

Prelistavanje

Izmenjava

Vzvratno

Verjetnost mutacije

P_m, verjetnost mutacije je izraz, ki določa, kako pogosto bodo mutirani kromosomi. Če je verjetnost mutacije 100%, to pomeni, da se spremeni celoten kromosom. Če mutacija ni izvedena, se takoj po križanju ustvari novo potomstvo.

Primer splošnega genetskega algoritma Verjetnost mutacije: P_m, verjetnost mutacije je izraz, ki določa, kako pogosto bodo mutirani kromosomi. Če je verjetnost mutacije 100%, to pomeni, da se spremeni celoten kromosom.

Če mutacija ni izvedena, se novo potomstvo ustvari takoj po križanju. Začetna populacija kromosomov je podana kot A, B, C, D. Velikost populacije je 4.

Kondicijska funkcija se šteje kot število 1 v nizu.

Vsota telesne pripravljenosti je 12, kar pomeni, da bi bila povprečna fitnes funkcija ~ 12/4 = 3

Verjetnost križanja = 0,7

Verjetnost mutacije = 0,001

# 1) Če sta izbrani B in C, križanja ni izveden, saj je kondicijska vrednost C pod povprečno kondicijo.

#two) B je mutiran => B: 11101110 -> B^': 01101110 za ohranitev raznolikosti prebivalstva

# 3) Izbrani sta B in D, izvede se križanje.

B: 11101110 E: 10110100 -> D: 00110100 F: 01101110

# 4) Če je E mutiran, potem

E: 10110100 -> E^': 10110000

Ustrezni kromosomi so prikazani v spodnji tabeli. Naročilo je naključno.

Čeprav se najbolj sposoben posameznik s kondicijsko vrednostjo 6 izgubi, se povprečna telesna pripravljenost prebivalstva poveča in bi znašala: 14/4 = 3,5

Kdaj ustaviti genetski algoritem

Genetski algoritem se ustavi, ko so izpolnjeni nekateri spodaj navedeni pogoji:

# 1) Najboljša individualna konvergenca: Ko najnižja raven telesne pripravljenosti pade pod vrednost konvergence, se algoritem ustavi. To vodi do hitrejše konvergence.

# 2) Najslabša individualna konvergenca: Ko posamezniki z najmanj telesno sposobnostjo v populaciji dosežejo najmanjšo vrednost kondicije pod konvergenco, se algoritem ustavi. Pri tej metodi se v populaciji vzdržuje minimalni fitnes standard. To pomeni, da najboljši posameznik ni zagotovljen, vendar bodo prisotni posamezniki z minimalno vrednostjo kondicije.

# 3) Vsota telesne pripravljenosti: Če je v tej metodi vsota telesne pripravljenosti manjša ali enaka konvergenčni vrednosti, se iskanje ustavi. Zagotavlja, da je vsa populacija v dosegu kondicije.

# 4) Mediana kondicije: Pri tej metodi bo vsaj polovica posameznikov v populaciji boljša ali enaka konvergenčni vrednosti.

Nekateri konvergenčni kriterij ali pogoj za zaustavitev so lahko:

• Ko se je razvilo določeno število generacij.
• Ko je izpolnjen določen čas za zagon algoritma.
• Ko se kondicijska vrednost populacije s ponovitvami ne spreminja več.

Prednosti in slabosti genetskega algoritma

Prednosti genetskega algoritma so:

1. Ima širši prostor rešitve.
2. Lažje je odkriti globalni optimum.
3. Vzporednost: Več GA-jev lahko deluje skupaj z istim CPU, ne da bi pri tem posegali med seboj. Vzporedno tečejo ločeno.

Omejitve GA:

1. Opredelitev funkcije fitnesa je omejitev.
2. Konvergenca algoritmov je lahko prehitra ali prepočasna.
3. Obstaja omejitev izbire parametrov, kot so križanje, verjetnost mutacije, velikost populacije itd.

Aplikacije genetskih algoritmov

GA je učinkovit za reševanje visoko dimenzijskih problemov. GA se učinkovito uporablja, kadar je prostor za iskanje zelo velik, ni na voljo matematičnih tehnik za reševanje problemov in drugi tradicionalni algoritmi iskanja ne delujejo.

Nekatere aplikacije, v katerih se uporablja GA:

• Optimizacijski problem: Eden najboljših primerov optimizacijskih problemov je problem prodajalca potovanj, ki uporablja GA. Druge težave z optimizacijo, kot so razporejanje delovnih mest, optimizacija kakovosti zvoka, se pogosto uporabljajo.
• Model imunskega sistema: GA se uporabljajo za modeliranje različnih vidikov imunskega sistema za posamezne genske in multigene gene v evolucijskem času.
• Strojno učenje: GA so bili uporabljeni za reševanje problemov, povezanih s klasifikacijo, predvidevanjem, ustvarjanjem pravil za učenje in razvrščanje .

Zaključek

Genetski algoritmi temeljijo na metodi naravnega razvoja. Ti algoritmi se razlikujejo od ostalih algoritmov za razvrščanje, saj uporabljajo kodirane parametre (0 ali 1), v populaciji je več posameznikov in za konvergenco uporabljajo verjetnostno metodo.

S postopkom križanja in mutacije se GA konvergirajo v naslednjih generacijah. Izvedba algoritma GA ne zagotavlja uspešne rešitve vedno. Genetski algoritmi so zelo učinkoviti pri optimizaciji - razporejanju problemov.

Upam, da bi ta vadnica obogatila vaše znanje o konceptu genetskih algoritmov !!

=> Obiščite tukaj za ekskluzivno serijo strojnega učenja

Priporočeno branje

• Modelno preskušanje z uporabo genetskega algoritma
• Data Mining Vs Machine Learning Vs Umetna inteligenca Vs Poglobljeno učenje
• Vadnica za strojno učenje: Uvod v ML in njegove aplikacije
• Vrste strojnega učenja: nadzorovano in nenadzorovano učenje
• Popoln vodnik po umetni nevronski mreži v strojnem učenju
• 11 Najbolj priljubljenih orodij za strojno učenje v letu 2021
• 13 najboljših podjetij za strojno učenje (posodobljen seznam 2021)
• Kaj je podporni vektorski stroj (SVM) pri strojnem učenju