introduction genetic algorithms machine learning
beste ssh-klient for Windows 10
Denne opplæringen om genetisk algoritme forklarer hva som er genetiske algoritmer og deres rolle i maskinlæring i detalj :
I Forrige veiledning , lærte vi om kunstige nevrale nettverksmodeller - flerlagsperceptron, backpropagation, radial bias og Kohonen selvorganiserende kart inkludert deres arkitektur.
Vi vil fokusere på genetiske algoritmer som kom tidligere enn Neural Networks, men nå er GA overtatt av NN. Selv om GA fremdeles har applikasjoner i det virkelige liv som optimaliseringsproblemer som planlegging, spill, robotikk, maskinvaredesign, reisende selgerproblemer, etc.
Genetiske algoritmer er algoritmer som er basert på den evolusjonære ideen om naturlig seleksjon og genetikk. GA er adaptive heuristiske søkealgoritmer, dvs. algoritmene følger et iterativt mønster som endrer seg med tiden. Det er en type forsterkningslæring der tilbakemeldingen er nødvendig uten å fortelle riktig vei å følge. Tilbakemeldingene kan enten være positive eller negative.
=> Les gjennom hele serien for maskinlæring
Hva du vil lære:
- Hvorfor bruke genetiske algoritmer
- Hva er genetiske algoritmer
- Fordeler og ulemper ved genetisk algoritme
- Anvendelser av genetiske algoritmer
- Konklusjon
Hvorfor bruke genetiske algoritmer
GA er mer robuste algoritmer som kan brukes til ulike optimaliseringsproblemer. Disse algoritmene avviker ikke lett i nærvær av støy, i motsetning til andre AI-algoritmer. GA kan brukes i jakten på stort eller multimodalt rom.
Biologisk bakgrunn av genetiske algoritmer
Genetikk er avledet av det greske ordet 'genesis' som betyr å vokse. Genetikken bestemmer arvelighetsfaktorene, likhetene og forskjellene mellom avkommene i evolusjonsprosessen. Genetiske algoritmer er også avledet av naturlig evolusjon.
Noen terminologier i et biologisk kromosom
- Kromosomer: All genetisk informasjon om en art er lagrede kromosomer.
- Gener: Kromosomene er delt inn i flere deler som kalles gener.
- Alleler: Genene identifiserer karakteristikken til et individ. Muligheten for en kombinasjon av gener for å danne eiendom kalles Alleles. Et gen kan ha forskjellige alleler.
- Genbasseng: Alle mulige kombinasjoner av gener som er alleler i en populasjonsgruppe kalles genpool.
- Genom: Settet med gener av en art kalles et genom.
- Locus: Hvert gen har en posisjon i et genom som kalles locus.
- Genotype: En full kombinasjon av gener i et individ kalles genotypen.
- Fenotype: Et sett med genotyper i dekodet form kalles fenotypen.
Hva er genetiske algoritmer
De genetiske algoritmene stimulerer prosessen som i naturlige systemer for evolusjon. Charles Darwin uttalte evolusjonsteorien om at i naturlig evolusjon utvikler biologiske vesener seg etter prinsippet om 'overlevelse av de sterkeste'. GA-søket er designet for å oppmuntre teorien om 'de sterkestes overlevelse'.
GA-ene utfører et tilfeldig søk for å løse optimaliseringsproblemer. GA bruker teknikker som bruker tidligere historisk informasjon for å lede søket mot optimalisering i det nye søkeområdet.
Korrelasjon av et kromosom med GA
Menneskekroppen har kromosomer som er laget av gener. Et sett med alle gener av en bestemt art kalles genomet. Hos levende vesener er genomene lagret i forskjellige kromosomer mens i GA er alle gener lagret i samme kromosom.
Sammenligning mellom naturlig evolusjon og genetisk algoritmterminologi
| Naturlig evolusjon | Genetisk algoritme |
|---|---|
| Kromosom | String |
| Gen | Trekk |
| Allel | Funksjonsverdi |
| Genotype | Kodet streng |
| Fenotype | Dekodet struktur |
Viktig terminologi i GA
- Befolkning: Det er en gruppe individer. Befolkningen inkluderer antall individer som blir testet, informasjon om søkeområdet og fenotype-parametrene. Generelt initialiseres befolkningen tilfeldig.
- Enkeltpersoner: Enkeltpersoner er en enkelt løsning i befolkningen. Et individ har et sett med parametere som kalles gener. Gener kombinert for å danne kromosomer.
- Gener: Gener er byggesteiner for genetiske algoritmer. Et kromosom består av gener. Genene kan bestemme løsningen på problemet. De er representert med en bit (0 eller 1) streng av tilfeldig lengde.
- Fitness: Treningen forteller verdien av problemets fenotype. Treningsfunksjonen forteller hvor nær løsningen er den optimale løsningen. Treningsfunksjon bestemmes på mange måter, for eksempel summen av alle parametere relatert til problemet - euklidisk avstand, etc. Det er ingen regel for å evaluere treningsfunksjon.
En enkel genetisk algoritme
En enkel GA har en populasjon av individuelle kromosomer. Disse kromosomene representerer mulige løsninger. Reproduksjonsoperatorer brukes over disse settene av kromosomer for å utføre mutasjoner og rekombinasjon. Derfor er det viktig å finne passende reproduksjonsoperatører ettersom GAs oppførsel er avhengig av det.
En enkel genetisk algoritme er som følger:
#1) Start med befolkningen opprettet tilfeldig.
#to) Beregn treningsfunksjonen til hvert kromosom.
# 3) Gjenta trinnene til n avkom er opprettet. Avkomene er skapt som vist nedenfor.
- Velg et par kromosomer fra befolkningen.
- Kryss paret med sannsynlighet scå danne avkom.
- Mutere crossover med sannsynlighet sm.
# 4) Erstatt den opprinnelige befolkningen med den nye befolkningen og gå til trinn 2.
La oss se trinnene som følges i denne iterasjonsprosessen. Den opprinnelige populasjonen av kromosomer genereres. Den opprinnelige populasjonen bør inneholde nok gener slik at enhver løsning kan genereres. Den første befolkningsgruppen genereres tilfeldig.
- Utvalg: Det beste settet med gener velges avhengig av treningsfunksjonen. Strengen med den beste treningsfunksjonen er valgt.
- Reproduksjon: Nye avkom genereres ved rekombinasjon og mutasjon.
- Evaluering: De nye genererte kromosomene blir evaluert for deres egnethet.
- Erstatning: I dette trinnet erstattes den gamle befolkningen med den nylig genererte befolkningen.
Metode for valg av roulettehjul
Valg av roulettehjul er seleksjonsmetoden som brukes mye.
Valgprosessen er kort som vist nedenfor:
I denne metoden foretas et lineært søk gjennom roulettehjulet. Sporene i hjulet veies i henhold til den individuelle treningsverdien. Målverdien settes tilfeldig i henhold til andelen av summen av kondisjonen i befolkningen.
Populasjonen blir så søkt til målverdien er nådd. Denne metoden garanterer ikke de sterkeste av individene, men har sannsynligheten for å være den sterkeste.
La oss se trinnene som er involvert i valget av roulettehjul.
Den forventede verdien til et individ = Individuell egnethet / egnethet i befolkningen. Hjulsporene tildeles enkeltpersoner ut fra deres egnethet. Hjulet roteres N ganger der N er det totale antallet individer i befolkningen. Når en rotasjon er over, blir den valgte personen satt i et foreldrebasseng.
- La den totale forventede verdien av et antall individer i befolkningen være S.
- Gjenta trinn 3-5 n ganger.
- Velg et helt tall s mellom 0 og S.
- Sløyfe gjennom individer i befolkningen, summer de forventede verdiene til summen er større enn s.
- Den personen hvis forventede verdi setter summen over grensen s velges.
Ulemper ved valg av roulettehjul:
- Hvis egnetheten skiller seg veldig ut, vil omkretsen av roulettehjulet bli maksimalt tatt av det høyeste treningsfunksjonskromosomet, så de andre har veldig liten sjanse til å bli valgt.
- Det er støyende.
- Utviklingen avhenger av avviket i egnetheten til befolkningen.
Andre valgmetoder
Det er mange andre valgmetoder som brukes i “Utvalg” trinn i den genetiske algoritmen.
Vi vil diskutere de to andre mye brukte metodene:
# 1) Rangvalg: I denne metoden får hvert kromosom en treningsverdi fra rangering. Den verste kondisjonen er 1 og den beste kondisjonen er N. Det er en langsom konvergensmetode. I denne metoden bevares mangfold som fører til et vellykket søk.
Potensielle foreldre velges og deretter avholdes en turnering for å avgjøre hvem av individene som skal være foreldre.
# 2) Turneringsvalg: I denne metoden brukes en selektiv trykkstrategi på befolkningen. Den beste personen er den med høyest kondisjon. Denne personen er vinneren av turneringskonkurransen blant Nu-individer i befolkningen.
Turneringspopulasjonen sammen med vinneren blir igjen lagt til i bassenget for å generere nye avkom. Forskjellen i kondisjonsverdiene til vinneren og enkeltpersoner i parringsbassenget gir et selektivt press for optimale resultater.
Crossover
Det er en prosess med å ta to personer og produsere et barn fra dem. Reproduksjonsprosessen etter utvalg gjør kloner av de gode broddene. Crossover-operatøren påføres over strengene for å gi et bedre avkom.
Implementeringen av crossover-operatøren er som følger:
- To individer velges tilfeldig fra befolkningen for å produsere avkom.
- Et krysssted er valgt tilfeldig langs lengden på strengen.
- Verdiene på stedet byttes ut.
Crossoveren som utføres kan være en enkeltpunktsovergang, topunktsovergang, flerpunktsovergang osv. Enkeltpunktsovergangen har et overgangssted mens et to-punkts overgangssted har to steder hvor verdiene byttes ut.
Vi kan se dette i eksemplet nedenfor:
Enkeltpunktsovergang
To-punkts crossover
Krysssannsynlighet
Pc, crossover-sannsynlighet er begrepet som beskriver hvor ofte crossover vil bli utført. 0% sannsynlighet betyr at de nye kromosomene vil være en eksakt kopi av de gamle kromosomene mens 100% sannsynlighet betyr at alle nye kromosomer er laget ved kryssovergang.
Mutasjon
Mutasjon gjøres etter Crossover. Mens crossover bare fokuserer på den nåværende løsningen, søker mutasjonsoperasjonen i hele søkeområdet. Denne metoden er å gjenopprette den tapte genetiske informasjonen og distribuere den genetiske informasjonen.
Denne operatøren hjelper til med å opprettholde genetisk mangfold i befolkningen. Det hjelper med å forhindre lokale minima og forhindrer generering av ubrukelige løsninger fra enhver befolkning.
Mutasjonen utføres på mange måter, for eksempel å invertere verdien av hvert gen med liten sannsynlighet eller utføre mutasjon bare hvis det forbedrer kvaliteten på løsningen.
Noen av måtene for mutasjon er:
- Vend: Endres fra 0 til 1 eller 1 til 0.
- Utveksling: To tilfeldige posisjoner velges, og verdiene blir ombyttet.
- Reversering: Tilfeldig posisjon velges og bitene ved siden av blir reversert.
La oss se noen eksempler på hver:
Vend
Utveksling
Bakover
Mutasjons sannsynlighet
Pm, mutasjonssannsynlighet er et begrep som bestemmer hvor ofte kromosomene vil bli mutert. Hvis mutasjonssannsynligheten er 100%, betyr det at hele kromosomet endres. Hvis det ikke utføres en mutasjon, blir nye avkom generert direkte etter crossover.
Et eksempel på en generell genetisk algoritme Mutasjons sannsynlighet: Pm, mutasjonssannsynlighet er et begrep som bestemmer hvor ofte kromosomene vil bli mutert. Hvis mutasjonssannsynligheten er 100%, betyr det at hele kromosomet endres.
Hvis det ikke utføres en mutasjon, blir det nye avkommet generert direkte etter crossover. Den opprinnelige populasjonen av kromosomer er gitt som A, B, C, D. Befolkningsstørrelsen er 4.
Treningsfunksjonen tas som et antall 1’er i strengen.
| Kromosom | Fitness |
|---|---|
| Til: 00000110 | to |
| B: 11101110 | 6 |
| C: 00100000 | 1 |
| D: 00110100 | 3 |
Summen av kondisjon er 12, noe som antyder at den gjennomsnittlige treningsfunksjonen vil være ~ 12/4 = 3
Krysssannsynlighet = 0,7
Mutasjons sannsynlighet = 0,001
#1) Hvis B og C er valgt, blir ikke delefilter utført da kondisjonsverdien til C er under gjennomsnittlig kondisjon.
#to) B er mutert => B: 11101110 -> B': 01101110 for å bevare mangfoldet i befolkningen
# 3) B og D er valgt, blir crossover utført.
B: 11101110 E: 10110100 -> D: 00110100 F: 01101110
# 4) Hvis E er mutert, da
E: 10110100 -> E': 10110000
Tilsvarende kromosomer er vist i tabellen nedenfor. Bestillingen legges tilfeldig.
| Kromosom | Fitness |
|---|---|
| A: 01101110 | 5 |
| B: 00100000 | 1 |
| C: 10110000 | 3 |
| D: 01101110 | 5 |
Selv om den sterkeste personen med kondisjonsverdi på 6 er tapt, øker befolkningens samlede gjennomsnittlige kondisjon og vil være: 14/4 = 3,5
Når skal man stoppe genetisk algoritme
En genetisk algoritme stoppes når noen av vilkårene nedenfor er oppfylt:
# 1) Beste individuelle konvergens: Når minimumsnivået for kondisjon faller under konvergensverdien, stoppes algoritmen. Det fører til raskere konvergens.
# 2) Verste individuelle konvergens: Når de minst egnede individene i befolkningen oppnår minimumsverdi under konvergensen, stoppes algoritmen. I denne metoden opprettholdes den minste treningsstandarden i befolkningen. Det betyr at det beste individet ikke garanteres, men minimumsverdiverdier enkeltpersoner vil være til stede.
# 3) Summen av kondisjon: I denne metoden, hvis summen av kondisjon er mindre enn eller lik konvergensverdi, stoppes søket. Det garanterer at hele befolkningen er innenfor treningsområdet.
# 4) Median Fitness: I denne metoden vil minst halvparten av individene i befolkningen være bedre enn eller lik konvergensverdi.
Noen konvergenskriterier eller stopptilstander kan være:
- Når et spesifikt antall generasjoner har utviklet seg.
- Når den angitte tiden for å kjøre algoritmen er oppfylt.
- Når treningsverdien til befolkningen ikke endres ytterligere med iterasjoner.
Fordeler og ulemper ved genetisk algoritme
Fordelene med en genetisk algoritme er:
- Den har et bredere løsningsrom.
- Det er lettere å oppdage det globale optimale.
- Parallellisme: Flere GA-er kan kjøre sammen med samme CPU uten å forstyrre hverandre. De løper parallelt i isolasjon.
Begrensninger i GA:
- Treningsfunksjonens identifikasjon er en begrensning.
- Konvergensen av algoritmene kan være for rask eller for langsom.
- Det er en begrensning å velge parametere som kryssovergang, mutasjons sannsynlighet, populasjonsstørrelse etc.
Anvendelser av genetiske algoritmer
GA er effektiv for å løse høydimensjonale problemer. En GA brukes effektivt når søkeområdet er veldig stort, det er ingen matematiske problemløsningsteknikker tilgjengelig, og andre tradisjonelle søkealgoritmer fungerer ikke.
Noen applikasjoner der GA brukes:
- Optimaliseringsproblem: Et av de beste eksemplene på optimaliseringsproblemene er reiseselgerproblemet som bruker GA. Andre optimaliseringsproblemer som jobbplanlegging, GAs for optimalisering av lydkvalitet er mye brukt.
- Immunsystemmodell: GA brukes til å modellere ulike aspekter av immunsystemet for individuelle gen- og flergenfamilier i løpet av evolusjonstid.
- Maskinlæring: GA-er har blitt brukt til å løse problemrelatert til klassifisering, prediksjon, lage regler for læring og klassifisering .
Konklusjon
Genetiske algoritmer er basert på metoden for naturlig evolusjon. Disse algoritmene er forskjellige fra de andre klassifiseringsalgoritmene da de bruker kodede parametere (0 eller 1), det er flere antall individer i en populasjon, og de bruker den sannsynlige metoden for konvergens.
Med prosessen med crossover og mutasjon, konvergerer GA-ene i suksessive generasjoner. Utførelsen av en GA-algoritme garanterer ikke alltid en vellykket løsning. De genetiske algoritmene er svært effektive i optimalisering - jobbplanleggingsproblemer.
Håper denne opplæringen ville ha beriket din kunnskap om begrepet genetiske algoritmer!
=> Besøk her for den eksklusive maskinlæringsserien
Anbefalt lesing
- Modellbasert testing ved hjelp av genetisk algoritme
- Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning
- Machine Learning Tutorial: Introduksjon til ML og dets applikasjoner
- Typer maskinlæring: Overvåket vs Uovervåket læring
- En komplett guide til kunstig nevralt nettverk innen maskinlæring
- De 11 mest populære maskinlæringsverktøyene i 2021
- Topp 13 BESTE maskinlæringsselskaper (Oppdatert 2021-liste)
- Hva er Support Vector Machine (SVM) i maskinlæring