Översikt över genetisk algoritm

Optimeringstekniker är de tekniker som används för att upptäcka den bästa lösningen av alla möjliga lösningar tillgängliga under de nuvarande begränsningarna. Så den genetiska algoritmen är en sådan optimeringsalgoritm som byggs på grundval av vår naturliga evolutionära process. Idén om naturligt urval och genetisk arv används här. Den använder guidad slumpmässig sökning, till skillnad från andra algoritmer, dvs. att hitta den optimala lösningen genom att börja med en slumpmässig initialkostnadsfunktion och sedan bara söka i det utrymme som hade den lägsta kostnaden (i styrd riktning). Lämplig när du arbetar med enorma och komplexa datasätt.

Vad är en genetisk algoritm?

Den genetiska algoritmen baseras på den genetiska strukturen och beteendet hos befolkningens kromosom. Följande saker är grunden för genetiska algoritmer.

  • Varje kromosom indikerar en möjlig lösning. Således är populationen en samling kromosomer.
  • Varje individ i befolkningen kännetecknas av en fitnessfunktion. Större kondition bättre är lösningen.
  • Av de tillgängliga individerna i befolkningen används de bästa individerna för reproduktion av nästa generations avkommor.
  • Avkomman som produceras kommer att ha egenskaper hos båda föräldrarna och är ett resultat av mutation. En mutation är en liten förändring i genstrukturen.

Faser av genetisk algoritm

Nedan är de olika faserna i den genetiska algoritmen:

1. Initiering av befolkning (kodning)

  • Varje gen representerar en parameter (variabler) i lösningen. Denna samling parametrar som bildar lösningen är kromosomen. Befolkningen är en samling kromosomer.
  • Generordning på kromosomfrågor.
  • De flesta av tiden kromosomer avbildas i binär som 0 och 1, men det finns också andra kodningar möjliga.

2. Fitness-funktion

  • Av de tillgängliga kromosomerna måste vi välja de bästa för reproduktion av avkommor, så varje kromosom får ett konditionvärde.
  • Fitness poäng hjälper dig att välja individer som kommer att användas för reproduktion.

3. Val

  • Huvudmålet med denna fas är att hitta den region där chansen att få den bästa lösningen är mer.
  • Inspiration för detta är från överlevnad av de fittest.
  • Det borde vara en balans mellan utforskning och utnyttjande av sökutrymme.
  • GA försöker flytta genotypen till högre kondition på sökutrymmet.
  • För starka förmågor i fitnessval kan leda till suboptimala lösningar.
  • För lite val av träningsförmåga leder till ofokuserad sökning.
  • Således används Fitness proportionerligt val, vilket också kallas val av roulettehjul, är en genetisk operatör som används i genetiska algoritmer för att välja potentiellt användbara lösningar för rekombination.

4. Reproduktion

Generering av avkommor sker på två sätt:

  • crossover
  • Mutation

a) Crossover

Crossover är det viktigaste stadiet i den genetiska algoritmen. Under crossover väljs en slumpmässig punkt under parning av ett par föräldrar för att generera avkommor.

Det finns tre huvudtyper av crossover.

  • Single Point Crossover: En punkt på båda föräldrarnas kromosomer plockas slumpmässigt ut och benämns en "crossover point". Bitar till höger om den punkten utbyts mellan de två föräldrakromosomerna.
  • Tvåpunktsovergång: Två överkorsningspunkter plockas slumpmässigt från föräldrakromosomerna. Bitarna mellan de två punkterna byts mellan moderorganismerna.
  • Uniform crossover: I en enhetlig crossover, väljs vanligtvis varje bit från endera föräldern med lika sannolikhet.

De nya avkommorna läggs till i befolkningen.

b) Mutation

I några få nya avkommor som bildas kan några av deras gener utsättas för en mutation med låg slumpmässig sannolikhet. Detta indikerar att några av bitarna i bitkromosomen kan vändas. Mutation råkar ta hand om mångfald bland befolkningen och stoppa för tidigt konvergens.

5. Konvergens (när man ska stoppa)

Några regler som följs som säger när man ska stoppa är följande:

  • När det inte finns någon förbättring av lösningskvaliteten efter att ha slutfört ett visst antal generationer som ställts i förväg.
  • När ett hårt och snabbt antal generationer och tid nås.
  • Tills en acceptabel lösning erhålls.

Tillämpning av genetisk algoritm

I det här avsnittet kommer vi att diskutera några av de områden där den genetiska algoritmen ofta används.

1. Resor och transportering

Resande säljare problem är en av de viktigaste tillämpningarna av den genetiska algoritmen. Till exempel, när en reseplanerare ombeds att planera en resa, skulle han ta hjälp av en genetisk algoritm som inte bara hjälper till att minska resans totala kostnad utan också för att minska tiden.GE används också för att planera leveransen av produkter från plats till plats på bästa sätt.

2. Robotik

Den genetiska algoritmen används allmänt inom området robotik. Roboter skiljer sig från varandra med det syfte de är byggda för. Till exempel är få byggda för en matlagningsuppgift, några är byggda för undervisningsuppgifter etc.

  • Val av viktiga funktioner i det givna datasättet.
  • I den traditionella metoden väljs de viktiga funktionerna i datasatsen med följande metod. dvs, du tittar på vikten av den modellen, kommer då att ställa in ett tröskelvärde för funktionerna, och om funktionen har betydelsevärde mer än en tröskel, beaktas den.
  • Men här använder vi en metod som kallas en ryggsäckproblem.
  • Vi börjar igen med populationen av en kromosom, där varje kromosom kommer att vara binär sträng. 1 kommer att beteckna "inkludering" av funktionen i modellen och 0 kommer att beteckna "uteslutning" av funktionen i modellen.
  • Fitnessfunktionen här kommer att vara vår noggrannhetsstatistik för tävlingen. Ju mer exakt vår uppsättning av kromosomer förutsäger värde, desto mer passande kommer den att vara.
  • Det finns många andra tillämpningar av genetiska algoritmer som DNA-analys, schemaläggningsapplikationer, Engineering design.

Slutsats

I det aktuella scenariot används GE i stora tillverkningsföretag som flygplan etc för att optimera tids- och resursanvändningen. Ytterligare forskare arbetar med att hitta nya sätt att kombinera genetiska algoritmer med andra optimeringstekniker.

Rekommenderade artiklar

Detta är en guide till Vad är genetisk algoritm? Här diskuterar vi introduktion, faser och tillämpningar av genetisk algoritm. Du kan också gå igenom våra andra föreslagna artiklar -

  1. Routingalgoritmer
  2. Typer av algoritmer
  3. Neurala nätverksalgoritmer
  4. Data Mining Algoritms
  5. guide till C ++ algoritmexempel

Kategori:

Big Data