Introduktion till genetiska algoritmer i maskininlärning

introduction genetic algorithms machine learning

bästa ssh-klienten för Windows 10

Denna genetiska algoritmhandledning Förklarar vad som är genetiska algoritmer och deras roll i maskininlärning i detalj :

I Föregående handledning , vi lärde oss om artificiella neurala nätverksmodeller - Multilayer Perceptron, Backpropagation, Radial Bias & Kohonen Self Organizing Maps inklusive deras arkitektur.

Vi kommer att fokusera på genetiska algoritmer som kom tidigare än Neural Networks, men nu har GA tagits över av NN. Även om GA fortfarande har applikationer i verkliga livet som optimeringsproblem som schemaläggning, spel, robotik, hårdvarudesign, problem med resande säljare etc.

Genetiska algoritmer är algoritmer som bygger på den evolutionära idén om naturligt urval och genetik. GA är adaptiva heuristiska sökalgoritmer, dvs. algoritmerna följer ett iterativt mönster som förändras med tiden. Det är en typ av förstärkningslärande där återkopplingen är nödvändig utan att säga rätt väg att följa. Återkopplingen kan antingen vara positiv eller negativ.

=> Läs igenom hela serien för maskininlärning

Vad du kommer att lära dig:

• Varför använda genetiska algoritmer
  • Biologisk bakgrund av genetiska algoritmer
• Vad är genetiska algoritmer
  • Korrelation mellan en kromosom och GA
  • Viktig terminologi i GA
  • En enkel genetisk algoritm
  • Metod för val av roulettehjul
  • Andra urvalsmetoder
  • Crossover
  • Mutation
  • När ska genetisk algoritm stoppas
• Fördelar och nackdelar med genetisk algoritm
• Tillämpningar av genetiska algoritmer
• Slutsats
  • Rekommenderad läsning

Varför använda genetiska algoritmer

GA är mer robusta algoritmer som kan användas för olika optimeringsproblem. Dessa algoritmer avviker inte lätt i närvaro av brus, till skillnad från andra AI-algoritmer. GA kan användas för att söka efter stort utrymme eller multimodalt utrymme.

Biologisk bakgrund av genetiska algoritmer

Genetik härrör från det grekiska ordet ”genesis” som betyder att växa. Genetiken bestämmer ärftfaktorer, likheter och skillnader mellan avkommorna i utvecklingsprocessen. Genetiska algoritmer härrör också från naturlig utveckling.

Några terminologier i en biologisk kromosom

• Kromosomer: All genetisk information om en art är lagrade kromosomer.
• Gener: Kromosomerna är uppdelade i flera delar som kallas gener.
• Alleler: Generna identifierar egenskaperna hos en individ. Möjligheten att en kombination av gener bildar egendom kallas Alleles. En gen kan ha olika alleler.
• Genpool: Alla möjliga kombinationer av gener som är alleler i en populationspool kallas genpool.
• Genom: Uppsättningen av gener av en art kallas ett genom.
• Ställe: Varje gen har en position i ett genom som kallas locus.
• Genotyp: En fullständig kombination av gener i en individ kallas genotypen.
• Fenotyp: En uppsättning genotyper i avkodad form kallas fenotypen.

Vad är genetiska algoritmer

De genetiska algoritmerna stimulerar processen som i naturliga system för evolution. Charles Darwin förklarade evolutionsteorin att biologiska varelser i naturlig utveckling utvecklas enligt principen om 'de starkastas överlevnad'. GA-sökningen är utformad för att uppmuntra teorin om 'de starkastas överlevnad'.

GA: erna utför en slumpmässig sökning för att lösa optimeringsproblem. GA använder tekniker som använder den tidigare historiska informationen för att rikta sin sökning mot optimering i det nya sökutrymmet.

Korrelation mellan en kromosom och GA

Människokroppen har kromosomer som är gjorda av gener. En uppsättning av alla gener av en specifik art kallas genomet. Hos levande varelser lagras genomerna i olika kromosomer medan i GA lagras alla gener i samma kromosom.

Jämförelse mellan naturlig evolution och genetisk algoritmterminologi

Viktig terminologi i GA

• Befolkning: Det är en grupp individer. Befolkningen inkluderar antalet individer som testas, sökutrymmesinformation och fenotypparametrarna. Generellt initialiseras befolkningen slumpmässigt.
• Individer: Individer är en enda lösning i befolkningen. En individ har en uppsättning parametrar som kallas gener. Gener kombinerade för att bilda kromosomer.
• Gener: Gener är byggstenar för genetiska algoritmer. En kromosom består av gener. Generna kan avgöra lösningen på problemet. De representeras av en bitsträng (0 eller 1) av slumpmässig längd.
• Kondition: Fitness visar värdet av problemets fenotyp. Fitnessfunktionen berättar hur nära lösningen är till den optimala lösningen. Fitnessfunktionen bestäms på många sätt, såsom summan av alla parametrar relaterade till problemet - euklidiskt avstånd etc. Det finns ingen regel för att utvärdera fitnessfunktionen.

En enkel genetisk algoritm

En enkel GA har en population av individuella kromosomer. Dessa kromosomer representerar möjliga lösningar. Reproduktionsoperatorer appliceras över dessa uppsättningar kromosomer för att utföra mutationer och rekombination. Det är därför viktigt att hitta lämpliga reproduktionsoperatörer eftersom GA: s beteende är beroende av det.

En enkel genetisk algoritm är som följer:

# 1) Börja med den befolkning som skapats slumpmässigt.

#två) Beräkna konditionsfunktionen för varje kromosom.

# 3) Upprepa stegen tills n avkommor skapas. Avkommorna skapas enligt nedan.

• Välj ett par kromosomer från befolkningen.
• Korsa paret med sannolikhet s_catt bilda avkommor.
• Mutera crossover med sannolikhet s_m.

# 4) Ersätt den ursprungliga befolkningen med den nya befolkningen och gå till steg 2.

Låt oss se stegen som följs i denna iterationsprocess. Den ursprungliga populationen av kromosomer genereras. Den ursprungliga populationen bör innehålla tillräckligt med gener så att valfri lösning kan genereras. Den första befolkningsgruppen genereras slumpmässigt.

• Urval: Den bästa uppsättningen gener väljs beroende på konditionsfunktionen. Strängen med bästa fitnessfunktion väljs.
• Fortplantning: Nya avkommor genereras genom rekombination och mutation.
• Utvärdering: De nya genererade kromosomerna utvärderas för deras lämplighet.
• Ersättning: I detta steg ersätts den gamla befolkningen med den nyligen genererade befolkningen.

Metod för val av roulettehjul

Roulettehjulval är valmetoden som används i stor utsträckning.

Urvalsprocessen är kort som visas nedan:

I denna metod görs en linjär sökning genom roulettehjulet. Spåren i hjulet vägs enligt det individuella konditionsvärdet. Målvärdet ställs in slumpmässigt efter andelen av summan av konditionen i befolkningen.

Befolkningen söks sedan tills målvärdet uppnås. Denna metod garanterar inte individens starkaste men har en sannolikhet att vara den starkaste.

Låt oss se stegen som är involverade i valet av roulettehjul.

Det individens förväntade värde = Befolkningens individuella kondition / kondition. Hjulplatserna tilldelas individer baserat på deras kondition. Hjulet vrids N gånger där N är det totala antalet individer i befolkningen. När en rotation är över placeras den valda individen i en pool av föräldrar.

1. Låt det totala förväntade värdet för ett antal individer i befolkningen vara S.
2. Upprepa steg 3-5 n gånger.
3. Välj ett heltal mellan 0 och S.
4. Sök igenom individer i befolkningen, summera de förväntade värdena tills summan är större än s.
5. Den person vars förväntade värde sätter summan över gränsen s väljs.

Nackdelar med val av roulettehjul:

1. Om konditionen skiljer sig väldigt mycket kommer roulettehjulets omkrets att tas maximalt av den högsta konditionsfunktionskromosomen, så de andra har mycket liten chans att väljas.
2. Det är bullrigt.
3. Utvecklingen beror på variationen i befolkningens lämplighet.

Andra urvalsmetoder

Det finns många andra urvalsmetoder som används i 'Urval' steg i den genetiska algoritmen.

Vi kommer att diskutera de två andra allmänt använda metoderna:

# 1) Rangval: I denna metod ges varje kromosom ett konditionsvärde från rangordningen. Den värsta konditionen är 1 och den bästa konditionen är N. Det är en långsam konvergensmetod. I denna metod bevaras mångfald vilket leder till en lyckad sökning.

Potentiella föräldrar väljs och sedan hålls en turnering för att avgöra vilken av individerna som ska vara förälder.

# 2) Turneringsval: I denna metod tillämpas en selektiv tryckstrategi på befolkningen. Den bästa individen är den med högsta kondition. Denna person är vinnaren av turneringstävlingen bland Nu-individer i befolkningen.

Turneringspopulationen tillsammans med vinnaren läggs till i poolen för att generera nya avkommor. Skillnaden i konditionsvärden för vinnaren och individer i parningspoolen ger ett selektivt tryck för optimala resultat.

Crossover

Det är en process att ta två individer och producera ett barn från dem. Reproduktionsprocessen efter urval gör kloner av de goda stingarna. Crossover-operatören appliceras över strängarna för att producera en bättre avkomma.

Implementeringen av crossover-operatören är som följer:

1. Två individer väljs slumpmässigt från befolkningen för att producera avkommor.
2. En tvärsida väljs slumpmässigt längs strängens längd.
3. Värdena på platsen byts ut.

Den utförda korsningen kan vara en korsning med en punkt, korsning med två punkter, korsning med flera punkter, etc. Korsningen med en punkt har en delningsplats medan en tvåpunktsdelningsplats har två platser där värdena byts ut.

Vi kan se detta i exemplet nedan:

Enpunktsdelning

Tvåpunktsdelning

Övergångs sannolikhet

P_c, crossover-sannolikhet är termen som beskriver hur ofta crossover kommer att utföras. 0% sannolikhet betyder att de nya kromosomerna kommer att vara en exakt kopia av de gamla kromosomerna medan 100% sannolikhet innebär att alla nya kromosomer är gjorda genom crossover.

Mutation

Mutation görs efter Crossover. Medan crossover bara fokuserar på den aktuella lösningen, söker mutationsoperationen hela sökutrymmet. Denna metod är att återställa den förlorade genetiska informationen och att distribuera den genetiska informationen.

Denna operatör hjälper till att upprätthålla genetisk mångfald i befolkningen. Det hjälper till att förhindra lokala minima och förhindrar att det genererar värdelösa lösningar från alla befolkningar.

Mutationen utförs på många sätt, såsom att invertera värdet på varje gen med liten sannolikhet eller utföra mutation endast om det förbättrar kvaliteten på lösningen.

Några av sätten att mutera är:

• Vänd: Ändrar från 0 till 1 eller 1 till 0.
• Utbyte: Två slumpmässiga positioner väljs och värdena byts ut.
• Backning: Slumpmässig position väljs och bitarna bredvid den vänds.

Låt oss se några exempel på var och en:

Vänd

Utbyte

Backning

Mutationssannolikhet

P_m, mutationssannolikhet är en term som bestämmer hur ofta kromosomerna kommer att muteras. Om mutationssannolikheten är 100% betyder det att hela kromosomen ändras. Om en mutation inte utförs genereras nya avkommor direkt efter crossover.

Ett exempel på en generell genetisk algoritm Mutationssannolikhet: P_m, mutationssannolikhet är en term som bestämmer hur ofta kromosomerna kommer att muteras. Om mutationssannolikheten är 100% betyder det att hela kromosomen ändras.

Om en mutation inte utförs genereras den nya avkomman direkt efter crossover. Den initiala populationen av kromosomer ges som A, B, C, D. Befolkningsstorleken är 4.

Fitnessfunktionen tas som ett antal 1 i strängen.

Summan av kondition är 12 vilket innebär att den genomsnittliga konditionsfunktionen skulle vara ~ 12/4 = 3

Crossover-sannolikhet = 0,7

Mutationssannolikhet = 0,001

# 1) Om B och C väljs, utförs inte delningen eftersom konditionsvärdet för C ligger under den genomsnittliga konditionen.

#två) B är muterad => B: 11101110 -> B^'': 01101110 för att bevara mångfalden i befolkningen

# 3) B och D väljs, delningen utförs.

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

# 4) Om E är muterad, då

E: 10110100 -> E^'': 10110000

Motsvarande kromosomer visas i nedanstående tabell. Ordern läggs slumpmässigt.

Även om den starkaste personen med konditionsvärde på 6 förloras, ökar befolkningens totala genomsnittliga kondition och skulle vara: 14/4 = 3,5

När ska genetisk algoritm stoppas

En genetisk algoritm stoppas när vissa villkor som anges nedan är uppfyllda:

# 1) Bästa individuella konvergens: När den lägsta konditionsnivån sjunker under konvergensvärdet stoppas algoritmen. Det leder till snabbare konvergens.

# 2) Värsta individuella konvergens: När de minst passande individerna i befolkningen uppnår ett lägsta konditionsvärde under konvergensen, stoppas algoritmen. I denna metod bibehålls den lägsta konditionsstandarden i befolkningen. Det betyder att den bästa individen inte garanteras, men det finns ett minimum av träningsvärde.

# 3) Summan av konditionen: Om den här metoden är mindre än eller lika med konvergensvärdet, stoppas sökningen. Det garanterar att hela befolkningen ligger inom träningsområdet.

# 4) Median Fitness: I denna metod kommer minst hälften av individerna i befolkningen att vara bättre än eller lika med konvergensvärde.

Vissa konvergenskriterier eller stoppvillkor kan vara:

• När ett visst antal generationer har utvecklats.
• När den angivna tiden för att köra algoritmen har uppnåtts.
• När befolkningens konditionsvärde inte förändras ytterligare med iterationer.

Fördelar och nackdelar med genetisk algoritm

Fördelarna med en genetisk algoritm är:

1. Den har ett bredare lösningsutrymme.
2. Det är lättare att upptäcka det globala optimala.
3. Parallelism: Flera GA kan köras tillsammans med samma CPU utan att störa varandra. De går parallellt isolerat.

Begränsningar av GA:

1. Konditionsfunktionens identifiering är en begränsning.
2. Konvergensen av algoritmerna kan vara för snabb eller för långsam.
3. Det finns en begränsning av att välja parametrar som crossover, mutationssannolikhet, befolkningsstorlek etc.

Tillämpningar av genetiska algoritmer

GA är effektivt för att lösa högdimensionella problem. En GA används effektivt när sökutrymmet är mycket stort, det finns inga matematiska problemlösningstekniker tillgängliga och andra traditionella sökalgoritmer fungerar inte.

Några applikationer där GA används:

• Optimeringsproblem: Ett av de bästa exemplen på optimeringsproblemen är resesäljarens problem som använder GA. Andra optimeringsproblem såsom jobbschemaläggning, ljudkvalitetsoptimerings-GA: er används ofta.
• Immunsystemmodell: GA används för att modellera olika aspekter av immunsystemet för enskilda gen- och flergenfamiljer under evolutionstiden.
• Maskininlärning: GA har använts för att lösa problem relaterade till klassificering, förutsägelse, skapa regler för inlärning och klassificering .

Slutsats

Genetiska algoritmer är baserade på metoden för naturlig utveckling. Dessa algoritmer skiljer sig från andra klassificeringsalgoritmer eftersom de använder kodade parametrar (0 eller 1), det finns flera antal individer i en population och de använder den probabilistiska metoden för konvergens.

Med processen för crossover och mutation konvergerar GA: erna på varandra följande generationer. Körningen av en GA-algoritm garanterar inte alltid en framgångsrik lösning. Genetiska algoritmer är mycket effektiva i optimering - jobbschemaläggningsproblem.

Hoppas att denna handledning skulle ha berikat din kunskap om begreppet genetiska algoritmer !!

=> Besök här för den exklusiva maskininlärningsserien

Rekommenderad läsning

• Modellbaserad testning med genetisk algoritm
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning
• Maskininlärningshandledning: Introduktion till ML och dess tillämpningar
• Typer av maskininlärning: Övervakad vs Övervakad inlärning
• En komplett guide till artificiellt neuralt nätverk inom maskininlärning
• 11 mest populära maskininlärningsverktyg 2021
• Topp 13 BÄSTA maskininlärningsföretag (uppdaterad 2021-lista)
• Vad är Support Vector Machine (SVM) i maskininlärning