En genetisk algoritme er en adaptiv heuristisk søkealgoritme inspirert av 'Darwins evolusjonsteori i naturen .' Det brukes til å løse optimaliseringsproblemer i maskinlæring. Det er en av de viktige algoritmene ettersom den hjelper til med å løse komplekse problemer som vil ta lang tid å løse.

Genetiske algoritmer blir mye brukt i forskjellige virkelige applikasjoner, for eksempel, Design av elektroniske kretser, kodebryting, bildebehandling og kunstig kreativitet.

I dette emnet vil vi forklare genetisk algoritme i detalj, inkludert grunnleggende terminologier som brukes i genetisk algoritme, hvordan det fungerer, fordeler og begrensninger ved genetisk algoritme, etc.

tojson java

Hva er en genetisk algoritme?

Før vi forstår den genetiske algoritmen, la oss først forstå grunnleggende terminologier for bedre å forstå denne algoritmen:

Befolkning:Populasjon er delmengden av alle mulige eller sannsynlige løsninger, som kan løse det gitte problemet.Kromosomer:Et kromosom er en av løsningene i befolkningen for det gitte problemet, og samlingen av gen genererer et kromosom.Gen:Et kromosom er delt inn i et annet gen, eller det er et element i kromosomet.Alleler:Allel er verdien gitt til genet i et bestemt kromosom.Treningsfunksjon:Fitness-funksjonen brukes til å bestemme individets kondisjonsnivå i befolkningen. Det betyr et individs evne til å konkurrere med andre individer. I hver iterasjon blir individer evaluert basert på deres kondisjonsfunksjon.Genetiske operatører:I en genetisk algoritme er den beste individuelle paret til å regenerere avkom bedre enn foreldre. Her spiller genetiske operatører en rolle i å endre den genetiske sammensetningen til neste generasjon.Utvalg

Etter å ha beregnet egnetheten til alle eksisterende i populasjonen, brukes en seleksjonsprosess for å bestemme hvilke av individualitetene i populasjonen som skal få reprodusere og produsere frøet som vil danne den kommende generasjonen.

Typer utvalg stiler tilgjengelig

Valg av ruletthjul Eventvalg Rangeringsbasert utvalg

Så nå kan vi definere en genetisk algoritme som en heuristisk søkealgoritme for å løse optimaliseringsproblemer. Det er en undergruppe av evolusjonære algoritmer, som brukes i databehandling. En genetisk algoritme bruker genetiske og naturlige seleksjonskonsepter for å løse optimaliseringsproblemer.

Hvordan fungerer genetisk algoritme?

Den genetiske algoritmen arbeider på den evolusjonære generasjonssyklusen for å generere løsninger av høy kvalitet. Disse algoritmene bruker forskjellige operasjoner som enten forbedrer eller erstatter populasjonen for å gi en forbedret tilpasningsløsning.

Det involverer i utgangspunktet fem faser for å løse de komplekse optimaliseringsproblemene, som er gitt som nedenfor:

Initialisering Treningsoppgave Utvalg Reproduksjon Avslutning

1. Initialisering

Prosessen med en genetisk algoritme starter med å generere settet med individer, som kalles populasjon. Her er hver enkelt løsningen på det gitte problemet. Et individ inneholder eller er preget av et sett med parametere kalt gener. Gener kombineres til en streng og genererer kromosomer, som er løsningen på problemet. En av de mest populære teknikkene for initialisering er bruken av tilfeldige binære strenger.

2. Fitness Oppdrag

Fitness-funksjonen brukes til å bestemme hvor godt et individ er? Det betyr et individs evne til å konkurrere med andre individer. I hver iterasjon blir individer evaluert basert på deres kondisjonsfunksjon. Fitnessfunksjonen gir en kondisjonspoeng til hver enkelt. Denne poengsummen bestemmer videre sannsynligheten for å bli valgt for reproduksjon. Jo høy kondisjonspoeng er, jo større sjanse er det for å bli valgt for reproduksjon.

3. Utvalg

Seleksjonsfasen innebærer utvelgelse av individer for reproduksjon av avkom. Alle de utvalgte individene blir deretter arrangert i et par på to for å øke reproduksjonen. Deretter overfører disse individene sine gener til neste generasjon.

Det er tre typer utvalgsmetoder tilgjengelig, som er:

• Valg av ruletthjul
• Turneringsvalg
• Rangeringsbasert utvalg

4. Reproduksjon

Etter utvelgelsesprosessen skjer opprettelsen av et barn i reproduksjonstrinnet. I dette trinnet bruker den genetiske algoritmen to variasjonsoperatorer som brukes på foreldrepopulasjonen. De to operatørene som er involvert i reproduksjonsfasen er gitt nedenfor:

vindu.åpne

Crossover:Crossoveren spiller en svært viktig rolle i reproduksjonsfasen av den genetiske algoritmen. I denne prosessen velges et krysspunkt tilfeldig innenfor genene. Deretter bytter crossover-operatøren ut genetisk informasjon til to foreldre fra den nåværende generasjonen for å produsere et nytt individ som representerer avkommet.

Genene til foreldrene utveksles seg imellom inntil overgangspunktet er nådd. Disse nygenererte avkommet legges til populasjonen. Denne prosessen kalles også crossover. Typer crossover-stiler tilgjengelig:
• Ett poengs crossover
• To-punkts crossover
• Livery crossover
• Arvelige algoritmer crossover
Mutasjon
Mutasjonsoperatøren setter inn tilfeldige gener i avkommet (nytt barn) for å opprettholde mangfoldet i populasjonen. Det kan gjøres ved å snu noen biter i kromosomene.
Mutasjon hjelper til med å løse problemet med for tidlig konvergens og øker diversifiseringen. Bildet nedenfor viser mutasjonsprosessen:
Typer mutasjonsstiler tilgjengelig,
Flip bit mutasjon Gaussisk mutasjon Bytte/bytte mutasjon

5. Oppsigelse

Etter reproduksjonsfasen brukes et stoppkriterium som grunnlag for oppsigelse. Algoritmen avsluttes etter at terskeltreningsløsningen er nådd. Den vil identifisere den endelige løsningen som den beste løsningen i befolkningen.

Generell arbeidsflyt for en enkel genetisk algoritme

Fordeler med genetisk algoritme

• De parallelle egenskapene til genetiske algoritmer er best.
• Det hjelper med å optimalisere ulike problemer som diskrete funksjoner, multi-objektive problemer og kontinuerlige funksjoner.
• Det gir en løsning på et problem som forbedres over tid.
• En genetisk algoritme trenger ikke avledet informasjon.

Begrensninger for genetiske algoritmer

• Genetiske algoritmer er ikke effektive algoritmer for å løse enkle problemer.
• Det garanterer ikke kvaliteten på den endelige løsningen på et problem.
• Gjentatte beregninger av kondisjonsverdier kan generere noen beregningsmessige utfordringer.

Forskjellen mellom genetiske algoritmer og tradisjonelle algoritmer

• Et søkerom er settet med alle mulige løsninger på problemet. I den tradisjonelle algoritmen opprettholdes bare ett sett med løsninger, mens i en genetisk algoritme kan flere sett med løsninger i søkerom brukes.
• Tradisjonelle algoritmer trenger mer informasjon for å utføre et søk, mens genetiske algoritmer trenger bare én objektiv funksjon for å beregne egnetheten til et individ.
• Tradisjonelle algoritmer kan ikke fungere parallelt, mens genetiske algoritmer kan fungere parallelt (beregning av egnetheten til individualitetene er uavhengige).
• En stor forskjell i genetiske algoritmer er at i stedet for å operere direkte på søkerresultater, opererer arvelige algoritmer på deres representasjoner (eller gjengivelse), ofte tilordnet som kromosomer.
• En av de store forskjellene mellom tradisjonell algoritme og genetisk algoritme er at den ikke direkte opererer på kandidatløsninger.
• Tradisjonelle algoritmer kan bare generere ett resultat til slutt, mens genetiske algoritmer kan generere flere optimale resultater fra forskjellige generasjoner.
• Den tradisjonelle algoritmen er ikke mer sannsynlig å generere optimale resultater, mens genetiske algoritmer ikke garanterer å generere optimale globale resultater, men det er også en stor mulighet for å få det optimale resultatet for et problem ettersom den bruker genetiske operatører som Crossover og Mutation.
• Tradisjonelle algoritmer er deterministiske i naturen, mens genetiske algoritmer er sannsynlige og stokastiske.