En genetisk algoritm är en adaptiv heuristisk sökalgoritm inspirerad av 'Darwins evolutionsteori i naturen .' Det används för att lösa optimeringsproblem inom maskininlärning. Det är en av de viktiga algoritmerna eftersom det hjälper till att lösa komplexa problem som skulle ta lång tid att lösa.

Genetiska algoritmer används i stor utsträckning i olika verkliga tillämpningar, till exempel, Design av elektroniska kretsar, kodbrytning, bildbehandling och konstgjord kreativitet.

I det här ämnet kommer vi att förklara genetisk algoritm i detalj, inklusive grundläggande terminologier som används i genetisk algoritm, hur det fungerar, fördelar och begränsningar med genetisk algoritm, etc.

Vad är en genetisk algoritm?

Innan vi förstår den genetiska algoritmen, låt oss först förstå grundläggande terminologier för att bättre förstå denna algoritm:

Befolkning:Population är delmängden av alla möjliga eller troliga lösningar, som kan lösa det givna problemet.Kromosomer:En kromosom är en av lösningarna i befolkningen för det givna problemet, och samlingen av gen genererar en kromosom.Gen:En kromosom är uppdelad i en annan gen, eller så är den en del av kromosomen.Alleler:Allel är det värde som ges till genen inom en viss kromosom.Fitnessfunktion:Fitnessfunktionen används för att bestämma individens konditionsnivå i befolkningen. Det betyder en individs förmåga att konkurrera med andra individer. I varje iteration utvärderas individer utifrån deras konditionsfunktion.Genetiska operatörer:I en genetisk algoritm, den bästa individuella paret för att regenerera avkomma bättre än föräldrar. Här spelar genetiska operatörer en roll för att förändra nästa generations genetiska sammansättning.Urval

Efter att ha beräknat lämpligheten för alla existerande i populationen, används en urvalsprocess för att bestämma vilka av individerna i populationen som kommer att få reproducera sig och producera det frö som kommer att bilda den kommande generationen.

Typer av urvalsstilar tillgängliga

Val av roulettehjul Val av evenemang Rangbaserat urval

Så nu kan vi definiera en genetisk algoritm som en heuristisk sökalgoritm för att lösa optimeringsproblem. Det är en delmängd av evolutionära algoritmer som används i datoranvändning. En genetisk algoritm använder genetiska och naturliga urvalskoncept för att lösa optimeringsproblem.

Hur fungerar genetisk algoritm?

Den genetiska algoritmen arbetar på den evolutionära generationscykeln för att generera högkvalitativa lösningar. Dessa algoritmer använder olika operationer som antingen förbättrar eller ersätter populationen för att ge en förbättrad passformslösning.

Det involverar i princip fem faser för att lösa de komplexa optimeringsproblemen, som ges enligt nedan:

Initialisering Fitnessuppdrag Urval Fortplantning Uppsägning

1. Initiering

Processen med en genetisk algoritm börjar med att generera uppsättningen individer, som kallas population. Här är varje individ lösningen på det givna problemet. En individ innehåller eller kännetecknas av en uppsättning parametrar som kallas gener. Gener kombineras till en sträng och genererar kromosomer, vilket är lösningen på problemet. En av de mest populära teknikerna för initiering är användningen av slumpmässiga binära strängar.

2. Fitnessuppdrag

Fitnessfunktionen används för att avgöra hur vältränad en individ är? Det betyder en individs förmåga att konkurrera med andra individer. I varje iteration utvärderas individer utifrån deras konditionsfunktion. Fitnessfunktionen ger varje individ ett konditionspoäng. Denna poäng avgör ytterligare sannolikheten att bli utvald för reproduktion. Ju hög konditionspoäng, desto större chans att bli utvald för reproduktion.

när börjar q2

3. Urval

Urvalsfasen innebär urval av individer för reproduktion av avkommor. Alla de utvalda individerna arrangeras sedan i ett par av två för att öka reproduktionen. Sedan överför dessa individer sina gener till nästa generation.

Det finns tre typer av urvalsmetoder tillgängliga, som är:

• Val av roulettehjul
• Turneringsurval
• Rangbaserat urval

4. Reproduktion

Efter urvalsprocessen sker skapandet av ett barn i reproduktionssteget. I det här steget använder den genetiska algoritmen två variationsoperatorer som tillämpas på moderpopulationen. De två operatörerna som är involverade i reproduktionsfasen anges nedan:

Crossover:Korsningen spelar en mycket betydande roll i reproduktionsfasen av den genetiska algoritmen. I denna process väljs en övergångspunkt slumpmässigt inom generna. Sedan byter crossover-operatören genetisk information från två föräldrar från den nuvarande generationen för att producera en ny individ som representerar avkomman.

Föräldrarnas gener utbyts sinsemellan tills korsningspunkten uppnås. Dessa nygenererade avkommor läggs till populationen. Denna process kallas också crossover. Typer av crossover-stilar tillgängliga:
• En poängs crossover
• Tvåpunkts crossover
• Livery crossover
• Överkorsning av ärftliga algoritmer
Mutation
Mutationsoperatören infogar slumpmässiga gener i avkomman (nytt barn) för att upprätthålla mångfalden i populationen. Det kan göras genom att vända några bitar i kromosomerna.
Mutation hjälper till att lösa frågan om för tidig konvergens och förbättrar diversifieringen. Bilden nedan visar mutationsprocessen:
Typer av mutationsstilar tillgängliga,
Flip bit mutation Gaussisk mutation Exchange/Swap mutation

5. Uppsägning

Efter reproduktionsfasen tillämpas ett stoppkriterium som grund för uppsägning. Algoritmen avslutas efter att tröskelvärdeslösningen har nåtts. Den kommer att identifiera den slutliga lösningen som den bästa lösningen i befolkningen.

Allmänt arbetsflöde för en enkel genetisk algoritm

Fördelar med genetisk algoritm

• De parallella egenskaperna hos genetiska algoritmer är bäst.
• Det hjälper till att optimera olika problem såsom diskreta funktioner, problem med flera mål och kontinuerliga funktioner.
• Det ger en lösning på ett problem som förbättras med tiden.
• En genetisk algoritm behöver inte härledd information.

Begränsningar för genetiska algoritmer

• Genetiska algoritmer är inte effektiva algoritmer för att lösa enkla problem.
• Det garanterar inte kvaliteten på den slutliga lösningen på ett problem.
• Upprepade beräkningar av konditionsvärden kan generera vissa beräkningsmässiga utmaningar.

Skillnaden mellan genetiska algoritmer och traditionella algoritmer

• Ett sökutrymme är uppsättningen av alla möjliga lösningar på problemet. I den traditionella algoritmen upprätthålls endast en uppsättning lösningar, medan i en genetisk algoritm kan flera uppsättningar av lösningar i sökutrymme användas.
• Traditionella algoritmer behöver mer information för att kunna utföra en sökning, medan genetiska algoritmer bara behöver en objektiv funktion för att beräkna en individs lämplighet.
• Traditionella algoritmer kan inte fungera parallellt, medan genetiska algoritmer kan fungera parallellt (beräkna individernas lämplighet är oberoende).
• En stor skillnad i genetiska algoritmer är att i stället för att arbeta direkt på sökresultat, så arbetar ärftliga algoritmer på deras representationer (eller rendering), ofta hänvisade till som kromosomer.
• En av de stora skillnaderna mellan traditionell algoritm och genetisk algoritm är att den inte direkt verkar på kandidatlösningar.
• Traditionella algoritmer kan bara generera ett resultat i slutändan, medan genetiska algoritmer kan generera flera optimala resultat från olika generationer.
• Den traditionella algoritmen är inte mer sannolikt att generera optimala resultat, medan genetiska algoritmer inte garanterar att generera optimala globala resultat, men det finns också en stor möjlighet att få det optimala resultatet för ett problem eftersom den använder genetiska operatorer som Crossover och Mutation.
• Traditionella algoritmer är deterministiska till sin natur, medan genetiska algoritmer är probabilistiska och stokastiska till sin natur.