GENETISKA ALGORITMER - TECHCODEVIEW.COM - IT-PROBLEM OCH LÖSNINGAR

Genetiska algoritmer (GA) är adaptiva heuristiska sökalgoritmer som tillhör större delen av evolutionära algoritmer. Genetiska algoritmer är baserade på idéerna om naturligt urval och genetik. Dessa är intelligent utnyttjande av slumpmässiga sökningar försedda med historiska data för att rikta sökningen in i regionen med bättre prestanda i lösningsutrymmet. De används ofta för att generera högkvalitativa lösningar för optimeringsproblem och sökproblem.

Genetiska algoritmer simulerar processen för naturligt urval vilket innebär att de arter som kan anpassa sig till förändringar i sin miljö kan överleva och föröka sig och gå till nästa generation. Med enkla ord, de simulerar överlevnad av de starkaste bland individer av på varandra följande generationer för att lösa ett problem. Varje generation består av en population av individer och varje individ representerar en punkt i sökutrymmet och möjlig lösning. Varje individ representeras som en sträng av tecken/heltal/float/bitar. Denna sträng är analog med kromosomen.

Grunden för genetiska algoritmer

Genetiska algoritmer är baserade på en analogi med den genetiska strukturen och beteendet hos kromosomerna i befolkningen. Följande är grunden för GA baserat på denna analogi -

Individer i befolkningen tävlar om resurser och parar sig
De individer som är framgångsrika (passast) parar sig sedan för att skapa fler avkommor än andra
Gener från den starkaste föräldern sprider sig genom generationen, det vill säga ibland skapar föräldrar avkomma som är bättre än någon av föräldrarna.
Således är varje generation efter varandra mer lämpad för sin miljö.

Sök utrymme

Populationen av individer hålls inom sökutrymmet. Varje individ representerar en lösning i sökutrymmet för ett givet problem. Varje individ är kodad som en vektor med ändlig längd (analog med kromosom) av komponenter. Dessa variabla komponenter är analoga med gener. Således är en kromosom (individ) sammansatt av flera gener (variabla komponenter).

Konditionsresultat

Ett fitnessresultat ges till varje individ som visar en individs förmåga att tävla . Individen som har optimal konditionspoäng (eller nära optimal) eftersträvas.

GA:erna upprätthåller populationen av n individer (kromosom/lösningar) tillsammans med deras konditionspoäng. De individer som har bättre konditionspoäng får större chans att reproducera sig än andra. Individerna med bättre konditionspoäng väljs ut som parar sig och producerar bättre avkomma genom att kombinera föräldrars kromosomer. Befolkningsstorleken är statisk så lokalen måste skapas för nyanlända. Så, vissa individer dör och blir ersatta av nyanlända som så småningom skapar en ny generation när alla parningsmöjligheter för den gamla befolkningen är uttömda. Förhoppningen är att bättre lösningar under successiva generationer kommer att komma fram medan minst fit dör.

Varje ny generation har i genomsnitt fler bättre gener än individen (lösningen) från tidigare generationer. Således har varje ny generation bättre dellösningar än tidigare generationer. När väl den avkomma som produceras inte har någon signifikant skillnad från avkomma som producerats av tidigare populationer, konvergeras populationen. Algoritmen sägs vara konvergerad till en uppsättning lösningar för problemet.

Operatörer av genetiska algoritmer

När den första generationen har skapats utvecklar algoritmen generationen med hjälp av följande operatorer -
1) Urvalsoperatör: Tanken är att ge företräde åt individer med bra konditionspoäng och låta dem överföra sina gener till successiva generationer.
2) Crossover-operatör: Detta representerar parning mellan individer. Två individer väljs ut med hjälp av urvalsoperatorn och korsningsplatser väljs slumpmässigt. Sedan byts generna vid dessa korsningsställen ut och skapar därmed en helt ny individ (avkomma). Till exempel -

3) Mutationsoperatör: Nyckelidén är att infoga slumpmässiga gener i avkomman för att upprätthålla mångfalden i populationen för att undvika för tidig konvergens. Till exempel -

15 av 100,00

Hela algoritmen kan sammanfattas som -

1) Randomly initialize populations p 2) Determine fitness of population 3) Until convergence repeat:  a) Select parents from population  b) Crossover and generate new population  c) Perform mutation on new population  d) Calculate fitness for new population>

Exempel på problem och lösning med hjälp av genetiska algoritmer

Givet en målsträng är målet att producera målsträng med utgångspunkt från en slumpmässig sträng av samma längd. I följande implementering görs följande analogier -

Tecken A-Z, a-z, 0-9 och andra specialsymboler betraktas som gener
En sträng som genereras av dessa tecken anses vara kromosom/lösning/individ

Konditionspoäng är antalet tecken som skiljer sig från tecken i målsträngen vid ett visst index. Så individer med lägre konditionsvärde ges mer företräde.

C++

// C++ program to create target string, starting from> // random string using Genetic Algorithm> > #include> using> namespace> std;> > // Number of individuals in each generation> #define POPULATION_SIZE 100> > // Valid Genes> const> string GENES =>'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP'>> 'QRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'>;> > // Target string to be generated> const> string TARGET =>'I love techcodeview.com'>;> > // Function to generate random numbers in given range> int> random_num(>int> start,>int> end)> {> >int> range = (end-start)+1;> >int> random_int = start+(>rand>()%range);> >return> random_int;> }> > // Create random genes for mutation> char> mutated_genes()> {> >int> len = GENES.size();> >int> r = random_num(0, len-1);> >return> GENES[r];> }> > // create chromosome or string of genes> string create_gnome()> {> >int> len = TARGET.size();> >string gnome =>''>;> >for>(>int>

i = 0;i  gnome += mutated_genes();   return gnome;  }    // Class representing individual in population  class Individual  {  public:   string chromosome;   int fitness;   Individual(string chromosome);   Individual mate(Individual parent2);   int cal_fitness();  };    Individual::Individual(string chromosome)  {   this->kromosom = kromosom;   fitness = cal_fitness();  };    // Utför parning och producera ny avkomma Individual Individual::mate(Individual par2) { // kromosom för avkomma sträng child_kromosom = '';     int len = kromosom.storlek();   for(int i = 0;i { // slumpmässig sannolikhet float p = random_num(0, 100)/100; // om sannolikheten är mindre än 0,45, infoga gen // från förälder 1 if(p<0.45)   child_chromosome += chromosome[i];     // if prob is between 0.45 and 0.90, insert   // gene from parent 2   else if(p <0.90)   child_chromosome += par2.chromosome[i];     // otherwise insert random gene(mutate),   // for maintaining diversity   else  child_chromosome += mutated_genes();   }     // create new Individual(offspring) using   // generated chromosome for offspring   return Individual(child_chromosome);  };      // Calculate fitness score, it is the number of  // characters in string which differ from target  // string.  int Individual::cal_fitness()  {   int len = TARGET.size();   int fitness = 0;   for(int i = 0;i  {   if(chromosome[i] != TARGET[i])   fitness++;   }   return fitness;  };    // Overloading  bool operator<(const Individual &ind1, const Individual &ind2)  {   return ind1.fitness  }    // Driver code  int main()  {   srand((unsigned)(time(0)));     // current generation   int generation = 0;     vector population;   bool found = false;     // create initial population   for(int i = 0;i  {   string gnome = create_gnome();   population.push_back(Individual(gnome));   }     while(! found)   {   // sort the population in increasing order of fitness score   sort(population.begin(), population.end());     // if the individual having lowest fitness score ie.   // 0 then we know that we have reached to the target   // and break the loop   if(population[0].fitness <= 0)   {   found = true;   break;   }     // Otherwise generate new offsprings for new generation   vector new_generation;     // Perform Elitism, that mean 10% of fittest population   // goes to the next generation   int s = (10*POPULATION_SIZE)/100;   for(int i = 0;i  new_generation.push_back(population[i]);     // From 50% of fittest population, Individuals   // will mate to produce offspring   s = (90*POPULATION_SIZE)/100;   for(int i = 0;i  {   int len = population.size();   int r = random_num(0, 50);   Individual parent1 = population[r];   r = random_num(0, 50);   Individual parent2 = population[r];   Individual offspring = parent1.mate(parent2);   new_generation.push_back(offspring);   }   population = new_generation;   cout<< 'Generation: ' << generation << '	';   cout<< 'String: '<< population[0].chromosome <<'	';   cout<< 'Fitness: '<< population[0].fitness << '
';     generation++;   }   cout<< 'Generation: ' << generation << '	';   cout<< 'String: '<< population[0].chromosome <<'	';   cout<< 'Fitness: '<< population[0].fitness << '
';  }>

Java

ternär operatör java

sträng till tecken java

import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> import> java.util.Random;> > public> class> GeneticAlgorithm {> >// Number of individuals in each generation> >private> static> final> int> POPULATION_SIZE =>100>;> > >// Valid Genes> >private> static> final> String GENES =>'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'>;> > >// Target string to be generated> >private> static> final> String TARGET =>'I love techcodeview.com'>;> > >// Function to generate random numbers in given range> >private> static> int> randomNum(>int> start,>int> end) {> >Random rand =>new> Random();> >return> rand.nextInt(end - start +>1>) + start;> >}> > >// Create random genes for mutation> >private> static> char> mutatedGenes() {> >int> len = GENES.length();> >int> r = randomNum(>0>, len ->1>);> >return> GENES.charAt(r);> >}> > >// Create chromosome or string of genes> >private> static> String createGnome() {> >int> len = TARGET.length();> >StringBuilder gnome =>new> StringBuilder();> >for> (>int> i =>0>

; i   gnome.append(mutatedGenes());   return gnome.toString();   }     // Class representing individual in population   private static class Individual implements Comparable {   String chromosome;   int fitness;     Individual(String chromosome) {   this.chromosome = chromosome;   fitness = calFitness();   }     // Perform mating and produce new offspring   Individual mate(Individual par2) {   StringBuilder childChromosome = new StringBuilder();     int len = chromosome.length();   for (int i = 0; i   // random probability   float p = randomNum(0, 100) / 100f;     // if prob is less than 0.45, insert gene from parent 1   if (p <0.45)   childChromosome.append(chromosome.charAt(i));     // if prob is between 0.45 and 0.90, insert gene from parent 2   else if (p <0.90)   childChromosome.append(par2.chromosome.charAt(i));     // otherwise insert random gene(mutate), for maintaining diversity   else  childChromosome.append(mutatedGenes());   }     // create new Individual(offspring) using generated chromosome for offspring   return new Individual(childChromosome.toString());   }     // Calculate fitness score, it is the number of characters in string which differ from target string   private int calFitness() {   int len = TARGET.length();   int fitness = 0;   for (int i = 0; i   if (chromosome.charAt(i) != TARGET.charAt(i))   fitness++;   }   return fitness;   }     @Override  public int compareTo(Individual o) {   return Integer.compare(this.fitness, o.fitness);   }   }     // Driver code   public static void main(String[] args) {   // current generation   int generation = 0;     List population = new ArrayList();   boolean found = false;     // create initial population   for (int i = 0; i   String gnome = createGnome();   population.add(new Individual(gnome));   }     while (!found) {   // sort the population in increasing order of fitness score   Collections.sort(population);     // if the individual having lowest fitness score i.e. 0 then we know that we have reached to the target   // and break the loop   if (population.get(0).fitness <= 0) {   found = true;   break;   }     // Otherwise generate new offsprings for new generation   List newGeneration = new ArrayList();     // Perform Elitism, that mean 10% of fittest population goes to the next generation   int s = (10 * POPULATION_SIZE) / 100;   for (int i = 0; i   newGeneration.add(population.get(i));     // From 50% of fittest population, Individuals will mate to produce offspring   s = (90 * POPULATION_SIZE) / 100;   for (int i = 0; i   int len = population.size();   int r = randomNum(0, 50);   Individual parent1 = population.get(r);   r = randomNum(0, 50);   Individual parent2 = population.get(r);   Individual offspring = parent1.mate(parent2);   newGeneration.add(offspring);   }   population = newGeneration;   System.out.print('Generation: ' + generation + '	');   System.out.print('String: ' + population.get(0).chromosome + '	');   System.out.println('Fitness: ' + population.get(0).fitness);     generation++;   }   System.out.print('Generation: ' + generation + '	');   System.out.print('String: ' + population.get(0).chromosome + '	');   System.out.println('Fitness: ' + population.get(0).fitness);   }  }>

Python3

# Python3 program to create target string, starting from> # random string using Genetic Algorithm> > import> random> > # Number of individuals in each generation> POPULATION_SIZE>=> 100> > # Valid genes> GENES>=> '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP> QRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'''> > # Target string to be generated> TARGET>=> 'I love techcodeview.com'> > class> Individual(>object>):> >'''> >Class representing individual in population> >'''> >def> __init__(>self>, chromosome):> >self>.chromosome>=> chromosome> >self>.fitness>=> self>.cal_fitness()> > >@classmethod> >def> mutated_genes(>self>):> >'''> >create random genes for mutation> >'''> >global> GENES> >gene>=> random.choice(GENES)> >return> gene> > >@classmethod> >def> create_gnome(>self>):> >'''> >create chromosome or string of genes> >'''> >global> TARGET> >gnome_len>=> len>(TARGET)> >return> [>self>.mutated_genes()>for> _>in> range>(gnome_len)]> > >def> mate(>self>, par2):> >'''> >Perform mating and produce new offspring> >'''> > ># chromosome for offspring> >child_chromosome>=> []> >for> gp1, gp2>in> zip>(>self>.chromosome, par2.chromosome):> > ># random probability> >prob>=> random.random()> > ># if prob is less than 0.45, insert gene> ># from parent 1> >if> prob <>0.45>:> >child_chromosome.append(gp1)> > ># if prob is between 0.45 and 0.90, insert> ># gene from parent 2> >elif> prob <>0.90>:> >child_chromosome.append(gp2)> > ># otherwise insert random gene(mutate),> ># for maintaining diversity> >else>:> >child_chromosome.append(>self>.mutated_genes())> > ># create new Individual(offspring) using> ># generated chromosome for offspring> >return> Individual(child_chromosome)> > >def> cal_fitness(>self>):> >'''> >Calculate fitness score, it is the number of> >characters in string which differ from target> >string.> >'''> >global> TARGET> >fitness>=> 0> >for> gs, gt>in> zip>(>self>.chromosome, TARGET):> >if> gs !>=> gt: fitness>+>=> 1> >return> fitness> > # Driver code> def> main():> >global> POPULATION_SIZE> > >#current generation> >generation>=> 1> > >found>=> False> >population>=> []> > ># create initial population> >for> _>in> range>(POPULATION_SIZE):> >gnome>=> Individual.create_gnome()> >population.append(Individual(gnome))> > >while> not> found:> > ># sort the population in increasing order of fitness score> >population>=> sorted>(population, key>=> lambda> x:x.fitness)> > ># if the individual having lowest fitness score ie.> ># 0 then we know that we have reached to the target> ># and break the loop> >if> population[>0>].fitness <>=> 0>:> >found>=> True> >break> > ># Otherwise generate new offsprings for new generation> >new_generation>=> []> > ># Perform Elitism, that mean 10% of fittest population> ># goes to the next generation> >s>=> int>((>10>*>POPULATION_SIZE)>/>100>)> >new_generation.extend(population[:s])> > ># From 50% of fittest population, Individuals> ># will mate to produce offspring> >s>=> int>((>90>*>POPULATION_SIZE)>/>100>)> >for> _>in> range>(s):> >parent1>=> random.choice(population[:>50>])> >parent2>=> random.choice(population[:>50>])> >child>=> parent1.mate(parent2)> >new_generation.append(child)> > >population>=> new_generation> > >print>(>'Generation: {} String: {} Fitness: {}'>.> >format>(generation,> >''.join(population[>0>].chromosome),> >population[>0>].fitness))> > >generation>+>=> 1> > > >print>(>'Generation: {} String: {} Fitness: {}'>.> >format>(generation,> >''.join(population[>0>].chromosome),> >population[>0>].fitness))> > if> __name__>=>=> '__main__'>:> >main()>

C#

java-tecken till int

using> System;> using> System.Collections.Generic;> using> System.Linq;> > public> class> GeneticAlgorithm> {> >// Number of individuals in each generation> >private> const> int> POPULATION_SIZE = 100;> > >// Valid Genes> >private> const> string> GENES =>'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP'> +> >'QRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'>;> > >// Target string to be generated> >private> const> string> TARGET =>'I love techcodeview.com'>;> > >private> static> readonly> Random random =>new> Random();> > >// Function to generate random numbers in given range> >private> static> int> RandomNum(>int> start,>int> end)> >{> >return> random.Next(start, end + 1);> >}> > >// Create random genes for mutation> >private> static> char> MutatedGenes()> >{> >int> len = GENES.Length;> >int> r = RandomNum(0, len - 1);> >return> GENES[r];> >}> > >// Create chromosome or string of genes> >private> static> string> CreateGnome()> >{> >int> len = TARGET.Length;> >char>[] gnome =>new> char>[len];> >for> (>int>

i = 0; i   {   gnome[i] = MutatedGenes();   }   return new string(gnome);   }     // Class representing individual in population   private class Individual   {   public string Chromosome { get; }   public int Fitness { get; }     public Individual(string chromosome)   {   Chromosome = chromosome;   Fitness = CalculateFitness();   }     // Calculate fitness score, it is the number of   // characters in string which differ from target string.   private int CalculateFitness()   {   return Chromosome.Zip(TARGET, (a, b) =>a == b ? 0 : 1). Sum();   } // Utför parning och producera ny avkomma offentlig Individual Mate(Individual parent2) { char[] childChromosome = new char[Chromosom.Length];   for (int i = 0; i { double p = random.NextDouble(); if (s<0.45)   childChromosome[i] = Chromosome[i];   else if (p <0.90)   childChromosome[i] = parent2.Chromosome[i];   else  childChromosome[i] = MutatedGenes();   }   return new Individual(new string(childChromosome));   }   }     // Overloading   private class FitnessComparer : IComparer   {   public int Compare(Individual ind1, Individual ind2)   {   return ind1.Fitness.CompareTo(ind2.Fitness);   }   }     // Driver code   public static void Main()   {   // current generation   int generation = 0;     List population = new List();   bool found = false;     // create initial population   for (int i = 0; i   {   string gnome = CreateGnome();   population.Add(new Individual(gnome));   }     while (!found)   {   // sort the population in increasing order of fitness score   population.Sort(new FitnessComparer());     // if the individual having lowest fitness score ie.   // 0 then we know that we have reached the target   // and break the loop   if (population[0].Fitness == 0)   {   found = true;   break;   }     // Otherwise generate new offsprings for new generation   List newGeneration = new List();     // Perform Elitism, that means 10% of fittest population   // goes to the next generation   int s = (10 * POPULATION_SIZE) / 100;   for (int i = 0; i   newGeneration.Add(population[i]);     // From 50% of fittest population, Individuals   // will mate to produce offspring   s = (90 * POPULATION_SIZE) / 100;   for (int i = 0; i   {   int len = population.Count;   int r = RandomNum(0, 50);   Individual parent1 = population[r];   r = RandomNum(0, 50);   Individual parent2 = population[r];   Individual offspring = parent1.Mate(parent2);   newGeneration.Add(offspring);   }   population = newGeneration;   Console.WriteLine('Generation: ' + generation + '	' +   'String: ' + population[0].Chromosome + '	' +   'Fitness: ' + population[0].Fitness);     generation++;   }     Console.WriteLine('Generation: ' + generation + '	' +   'String: ' + population[0].Chromosome + '	' +   'Fitness: ' + population[0].Fitness);   }  }>

Javascript

// Number of individuals in each generation> const POPULATION_SIZE = 100;> > // Valid Genes> const GENES =>'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP'> +> >'QRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'>;> > // Target string to be generated> const TARGET =>'I love techcodeview.com'>;> > // Function to generate random numbers in given range> function> RandomNum(start, end) {> >return> Math.floor(Math.random() * (end - start + 1)) + start;> }> > // Create random genes for mutation> function> MutatedGenes() {> >let len = GENES.length;> >let r = RandomNum(0, len - 1);> >return> GENES.charAt(r);> }> > // Create chromosome or string of genes> function> CreateGnome() {> >let len = TARGET.length;> >let gnome =>''>;> >for>

(let i = 0; i   gnome += MutatedGenes();   }   return gnome;  }    // Class representing individual in population  class Individual {   constructor(chromosome) {   this.Chromosome = chromosome;   this.Fitness = this.CalculateFitness();   }     // Calculate fitness score, it is the number of   // characters in string which differ from target string.   CalculateFitness() {   let fitness = 0;   for (let i = 0; i FitnessComparer.Compare(a, b));     // om individen har lägst konditionspoäng, dvs.   // 0 då vet vi att vi har nått målet // och bryter slingan if (population[0].Fitness === 0) { found = true;   ha sönder;   } // Generera annars nya avkommor för ny generation låt newGeneration = [];     // Utför elitism, det betyder att 10 % av den starkaste befolkningen // går till nästa generation låt s = Math.floor((10 * POPULATION_SIZE) / 100);   för (låt i = 0; i newGeneration.push(population[i]); // Från 50 % av den starkaste populationen kommer individer // att para sig för att producera avkomma s = Math.floor((90 * POPULATION_SIZE) / 100); för (låt i = 0; jag låter r = Slumptal(0, 50); låt förälder1 = population[r]; r = Slumptal(0, 50); låt förälder2 = population[r]; låt avkomma = förälder1. Kompis( parent2); newGeneration.push(avkomma } population = newGeneration.log('Generation: ' + generation + '	' + 'String: ' + population[0]. '	' + 'Fitness: ' + population[0].Fitness generation++; } console.log('Generation: ' + generation + '	' + 'String: '); + population[0].Kromosom + '	' + 'Fitness: ' + population[0].Fitness);

Produktion:

faktoriell java

Generation: 1 String: tO{'-?=jH[k8=B4]Oe@} Fitness: 18 Generation: 2 String: tO{'-?=jH[k8=B4]Oe@} Fitness: 18 Generation: 3 String: .#lRWf9k_Ifslw #O$k_ Fitness: 17 Generation: 4 String: .-1Rq?9mHqk3Wo]3rek_ Fitness: 16 Generation: 5 String: .-1Rq?9mHqk3Wo]3rek_ Fitness: 16 Generation: 6 String: A#ldW) #lIkslw cVek) Fitness: 14 Generation: 7 String: A#ldW) #lIkslw cVek) Fitness: 14 Generation: 8 String: (, o x _x%Rs=, 6Peek3 Fitness: 13  .   .   .  Generation: 29 String: I lope Geeks#o, Geeks Fitness: 3 Generation: 30 String: I loMe GeeksfoBGeeks Fitness: 2 Generation: 31 String: I love Geeksfo0Geeks Fitness: 1 Generation: 32 String: I love Geeksfo0Geeks Fitness: 1 Generation: 33 String: I love Geeksfo0Geeks Fitness: 1 Generation: 34 String: I love techcodeview.com Fitness: 0>

Notera: Algoritmen varje gång börjar med slumpmässiga strängar, så utdata kan skilja sig åt

Som vi kan se från resultatet, fastnade vår algoritm ibland vid en lokal optimal lösning, detta kan förbättras ytterligare genom att uppdatera algoritmen för beräkning av fitnesspoäng eller genom att justera mutations- och korsningsoperatorer.

Varför använda genetiska algoritmer

De är robusta
Ge optimering över stort utrymme.
Till skillnad från traditionell AI går de inte sönder vid små förändringar i input eller närvaro av brus

Tillämpning av genetiska algoritmer

Genetiska algoritmer har många applikationer, några av dem är -

Återkommande neurala nätverk
Mutationstestning
Kodbrott
Filtrering och signalbehandling
Att lära sig luddig regelbas etc