Oversikt over genetisk algoritme
Optimaliseringsteknikker er teknikkene som brukes for å finne den beste løsningen av alle mulige løsninger tilgjengelig under begrensningene som er til stede. Så den genetiske algoritmen er en slik optimaliseringsalgoritme som er bygd på basis av den naturlige evolusjonsprosessen av vår natur. Ideen om naturlig seleksjon og genetisk arv brukes her. Den bruker guidet tilfeldig søk, i motsetning til andre algoritmer, dvs. å finne den optimale løsningen ved å starte med en tilfeldig initial kostnadsfunksjon og deretter bare søke i det rommet som hadde minst kostnad (i veiledet retning). Passer når du jobber med enorme og komplekse datasett.
Hva er en genetisk algoritme?
Den genetiske algoritmen er basert på den genetiske strukturen og atferden til kromosomet i befolkningen. Følgende ting er grunnlaget for genetiske algoritmer.
- Hvert kromosom indikerer en mulig løsning. Dermed er populasjonen en samling kromosomer.
- Hvert individ i befolkningen er preget av en kondisjonsfunksjon. Større kondisjon bedre er løsningen.
- Av de tilgjengelige individene i befolkningen brukes de beste individene til reproduksjon av neste generasjons avkom.
- Avkommet som produseres vil ha trekk hos begge foreldrene og er et resultat av mutasjon. En mutasjon er en liten endring i genstrukturen.
Faser av genetisk algoritme
Nedenfor er de forskjellige fasene av den genetiske algoritmen:
1. Initialisering av befolkning (koding)
- Hvert gen representerer en parameter (variabler) i løsningen. Denne samlingen av parametere som danner løsningen er kromosomet. Befolkningen er en samling av kromosomer.
- Gener av rekkefølge på kromosomet betyr noe.
- Det meste av tiden er kromosomer avbildet i binær som 0-er og 1-er, men det er også andre kodinger som er mulig.
2. Treningsfunksjon
- Av de tilgjengelige kromosomene må vi velge de beste for reproduksjon av avkom, slik at hvert kromosom får en egnethetsverdi.
- Treningspoengene hjelper deg med å velge individer som skal brukes til reproduksjon.
3. Valg
- Hovedmålet med denne fasen er å finne regionen der sjansene for å få den beste løsningen er mer.
- Inspirasjon til dette er fra de mest overlevende.
- Det skal være en balanse mellom leting og utnyttelse av søkeområdet.
- GA prøver å flytte genotypen til høyere egnethet på søkeområdet.
- For sterk valg av skjevhetsutvikling kan føre til suboptimale løsninger.
- For lite valg av fitness skjevhet resulterer i ufokusert søk.
- Dermed blir Fitness proporsjonalt utvalg brukt, som også er kjent som ruletthjulvalg, en genetisk operatør som brukes i genetiske algoritmer for å velge potensielt nyttige løsninger for rekombinasjon.
4. Reproduksjon
Generasjon av avkom skjer på to måter:
- crossover
- mutasjon
a) Crossover
Crossover er det mest vitale stadiet i den genetiske algoritmen. Under crossover velges et tilfeldig punkt mens paring av et par foreldre for å generere avkom.
Det er tre hovedtyper av crossover.
- Enkeltpunktsovergang: Et punkt på begge foreldrenes kromosomer plukkes tilfeldig og betegnes som et 'overkryssingspunkt'. Biter til høyre for dette punktet blir utvekslet mellom de to foreldre-kromosomene.
- To-punkts crossover: To crossover-punkter plukkes tilfeldig fra foreldrekromosomene. Bitene mellom de to punktene byttes mellom foreldreorganismer.
- Uniform crossover: I en enhetlig crossover, velges typisk hver bit fra begge foreldrene med lik sannsynlighet.
De nye avkomene blir lagt til befolkningen.
b) Mutasjon
I noen få nye avkom dannet, kan noen av genene deres bli utsatt for en mutasjon med lav tilfeldig sannsynlighet. Dette indikerer at noen av bitene i bitkromosomet kan vendes. Mutasjon skjer for å ta vare på mangfoldet blant befolkningen og stoppe for tidlig konvergens.
5. Konvergens (når du skal stoppe)
Få regler som følges som forteller når du skal stoppe er som følger:
- Når det ikke er noen forbedring i løsningskvaliteten etter å ha fullført et visst antall generasjoner som er satt på forhånd.
- Når et hardt og raskt spekter av generasjoner og tid er nådd.
- Inntil en akseptabel løsning er oppnådd.
Anvendelse av genetisk algoritme
I dette avsnittet vil vi diskutere noen av områdene der den genetiske algoritmen ofte brukes.
1. Reiser og forsendelsesruting
Reisende selgerproblem er en av de viktigste anvendelsene av den genetiske algoritmen. For eksempel når en turplanlegger blir bedt om å planlegge en tur, ville han ta hjelp av en genetisk algoritme som ikke bare bidrar til å redusere de totale kostnadene for turen, men også til å redusere tiden.GE brukes også til å planlegge leveringen av produkter fra sted til sted på den mest effektive måten.
2. Robotikk
Den genetiske algoritmen er mye brukt innen robotikk. Roboter skiller seg fra hverandre etter formålet de er bygget for. For eksempel er det få som er bygd for en matlagingsoppgave, få er bygd for undervisningsoppgaver osv.
- Valg av viktige funksjoner i det gitte datasettet.
- I den tradisjonelle metoden velges de viktige funksjonene i datasettet ved hjelp av følgende metode. dvs. at du ser på viktigheten av den modellen, vil deretter sette en terskelverdi for funksjonene, og hvis funksjonen har viktighetsverdi mer enn en terskel, blir den vurdert.
- Men her bruker vi en metode som kalles en ryggsekkproblem.
- Vi vil igjen starte med bestanden av et kromosom, der hvert kromosom vil være binær streng. 1 vil betegne "inkludering" av funksjonen i modellen og 0 vil betegne "ekskludering" av funksjonen i modellen.
- Treningsfunksjonen her vil være vår nøyaktighetsmetrik for konkurransen. Jo mer nøyaktig vårt sett med kromosomer når det gjelder å forutsi verdi, jo mer passform vil det være.
- Det er mange andre anvendelser av genetiske algoritmer som DNA-analyse, planleggingsapplikasjoner, Ingeniørdesign.
Konklusjon
I det nåværende scenariet brukes GE i store produksjonsselskaper som fly osv. For å optimalisere bruken av tid og ressurser. Ytterligere forskere jobber med å finne nye måter å kombinere genetiske algoritmer med andre optimaliseringsteknikker.
Anbefalte artikler
Dette er en guide til Hva er genetisk algoritme? Her diskuterer vi introduksjon, faser og anvendelser av genetisk algoritme. Du kan også gå gjennom andre foreslåtte artikler -
- Ruteringsalgoritmer
- Typer av algoritmer
- Nevrale nettverksalgoritmer
- Data mining algoritmer
- guide til C ++ algoritmeeksempler