En genetisk algoritme er en adaptiv heuristisk søgealgoritme inspireret af 'Darwins evolutionsteori i naturen .' Det bruges til at løse optimeringsproblemer i maskinlæring. Det er en af ​​de vigtige algoritmer, da det hjælper med at løse komplekse problemer, der ville tage lang tid at løse.

Genetiske algoritmer bliver meget brugt i forskellige virkelige applikationer, f.eks. Design af elektroniske kredsløb, kodebrydning, billedbehandling og kunstig kreativitet.

I dette emne vil vi forklare genetisk algoritme i detaljer, herunder grundlæggende terminologier brugt i genetisk algoritme, hvordan det virker, fordele og begrænsninger ved genetisk algoritme osv.

powershell mindre end eller lig med

Hvad er en genetisk algoritme?

Før vi forstår den genetiske algoritme, lad os først forstå grundlæggende terminologier for bedre at forstå denne algoritme:

Befolkning:Population er delmængden af ​​alle mulige eller sandsynlige løsninger, som kan løse det givne problem.Kromosomer:Et kromosom er en af ​​løsningerne i befolkningen til det givne problem, og gensamlingen genererer et kromosom.Gen:Et kromosom er opdelt i et andet gen, eller det er et element i kromosomet.Alleler:Allel er den værdi, der gives til genet i et bestemt kromosom.Fitness funktion:Fitnessfunktionen bruges til at bestemme individets konditionsniveau i befolkningen. Det betyder et individs evne til at konkurrere med andre individer. I hver iteration bliver individer evalueret ud fra deres fitnessfunktion.Genetiske operatører:I en genetisk algoritme er den bedste individuelle parring til at regenerere afkom bedre end forældre. Her spiller genetiske operatører en rolle i at ændre den næste generations genetiske sammensætning.Udvælgelse

Efter at have beregnet egnetheden af ​​alle eksisterende i befolkningen, bruges en udvælgelsesproces til at bestemme, hvilke af individualiteterne i befolkningen, der vil komme til at reproducere og producere frøet, der vil danne den kommende generation.

Typer af valgstile tilgængelige

Valg af roulettehjul Valg af begivenhed Rangbaseret udvælgelse

Så nu kan vi definere en genetisk algoritme som en heuristisk søgealgoritme til at løse optimeringsproblemer. Det er en undergruppe af evolutionære algoritmer, som bruges i databehandling. En genetisk algoritme bruger genetiske og naturlige selektionskoncepter til at løse optimeringsproblemer.

Hvordan virker genetisk algoritme?

Den genetiske algoritme arbejder på den evolutionære generationscyklus for at generere løsninger af høj kvalitet. Disse algoritmer bruger forskellige operationer, der enten forbedrer eller erstatter populationen for at give en forbedret tilpasningsløsning.

Det involverer grundlæggende fem faser til at løse de komplekse optimeringsproblemer, som er givet som nedenfor:

Initialisering Fitness opgave Udvælgelse Reproduktion Afslutning

1. Initialisering

Processen med en genetisk algoritme starter med at generere det sæt af individer, som kaldes population. Her er hver enkelt løsningen på det givne problem. Et individ indeholder eller er karakteriseret ved et sæt parametre kaldet gener. Gener kombineres til en streng og genererer kromosomer, som er løsningen på problemet. En af de mest populære teknikker til initialisering er brugen af ​​tilfældige binære strenge.

2. Fitness Opgave

Fitness-funktionen bruges til at bestemme, hvor fit en person er? Det betyder et individs evne til at konkurrere med andre individer. I hver iteration bliver individer evalueret ud fra deres fitnessfunktion. Fitnessfunktionen giver en fitnessscore til hver enkelt. Denne score bestemmer yderligere sandsynligheden for at blive udvalgt til reproduktion. Jo høj fitnessscore, jo større chance for at blive udvalgt til reproduktion.

3. Udvælgelse

Udvælgelsesfasen involverer udvælgelse af individer til reproduktion af afkom. Alle de udvalgte individer arrangeres derefter i et par af to for at øge reproduktionen. Så overfører disse individer deres gener til næste generation.

Der er tre typer udvælgelsesmetoder tilgængelige, som er:

• Valg af roulettehjul
• Turneringsvalg
• Rang-baseret udvælgelse

4. Reproduktion

Efter udvælgelsesprocessen sker oprettelsen af ​​et barn i reproduktionstrinnet. I dette trin bruger den genetiske algoritme to variationsoperatorer, der anvendes på forældrepopulationen. De to operatører involveret i reproduktionsfasen er angivet nedenfor:

java heltal

Crossover:Crossoveren spiller en meget væsentlig rolle i reproduktionsfasen af ​​den genetiske algoritme. I denne proces vælges et krydsningspunkt tilfældigt i generne. Derefter bytter crossover-operatøren genetisk information om to forældre fra den nuværende generation for at producere et nyt individ, der repræsenterer afkommet.

Forældrenes gener udveksles indbyrdes, indtil overgangspunktet er opfyldt. Disse nygenererede afkom føjes til befolkningen. Denne proces kaldes også crossover. Tilgængelige typer crossover-stile:
• Et point crossover
• To-punkts crossover
• Livery crossover
• Arvelige algoritmer crossover
Mutation
Mutationsoperatøren indsætter tilfældige gener i afkommet (nyt barn) for at opretholde diversiteten i populationen. Det kan gøres ved at vende nogle bidder i kromosomerne.
Mutation hjælper med at løse spørgsmålet om for tidlig konvergens og øger diversificeringen. Nedenstående billede viser mutationsprocessen:
Mutationstyper tilgængelige,
Flip bit mutation Gaussisk mutation Exchange/Swap mutation

5. Opsigelse

Efter reproduktionsfasen anvendes et stopkriterium som grundlag for opsigelse. Algoritmen afsluttes, efter at tærskelfitnessløsningen er nået. Det vil identificere den endelige løsning som den bedste løsning i befolkningen.

Generel arbejdsgang for en simpel genetisk algoritme

Fordele ved genetisk algoritme

• De parallelle muligheder for genetiske algoritmer er bedst.
• Det hjælper med at optimere forskellige problemer såsom diskrete funktioner, multi-objektive problemer og kontinuerlige funktioner.
• Det giver en løsning på et problem, der forbedres over tid.
• En genetisk algoritme behøver ikke afledt information.

Begrænsninger af genetiske algoritmer

• Genetiske algoritmer er ikke effektive algoritmer til at løse simple problemer.
• Det garanterer ikke kvaliteten af ​​den endelige løsning på et problem.
• Gentagen beregning af fitnessværdier kan generere nogle beregningsmæssige udfordringer.

Forskellen mellem genetiske algoritmer og traditionelle algoritmer

• Et søgeområde er et sæt af alle mulige løsninger på problemet. I den traditionelle algoritme opretholdes kun ét sæt løsninger, hvorimod der i en genetisk algoritme kan bruges flere sæt løsninger i søgerummet.
• Traditionelle algoritmer har brug for mere information for at udføre en søgning, hvorimod genetiske algoritmer kun behøver én objektiv funktion til at beregne et individs egnethed.
• Traditionelle algoritmer kan ikke arbejde parallelt, hvorimod genetiske algoritmer kan arbejde parallelt (beregning af individualiteternes egnethed er uafhængige).
• En stor forskel i genetiske algoritmer er, at i stedet for at operere direkte på søgeresultater, opererer nedarvelige algoritmer på deres repræsentationer (eller gengivelser), der ofte betegnes som kromosomer.
• En af de store forskelle mellem traditionel algoritme og genetisk algoritme er, at den ikke direkte fungerer på kandidatløsninger.
• Traditionelle algoritmer kan kun generere ét resultat i sidste ende, hvorimod genetiske algoritmer kan generere flere optimale resultater fra forskellige generationer.
• Den traditionelle algoritme er ikke mere tilbøjelig til at generere optimale resultater, hvorimod genetiske algoritmer ikke garanterer at generere optimale globale resultater, men der er også en stor mulighed for at få det optimale resultat for et problem, da det bruger genetiske operatorer som Crossover og Mutation.
• Traditionelle algoritmer er deterministiske i naturen, hvorimod genetiske algoritmer er sandsynlige og stokastiske.