Ģenētiskie algoritmi (GA) ir adaptīvi heiristiski meklēšanas algoritmi, kas pieder lielākajai daļai evolūcijas algoritmu. Ģenētiskie algoritmi ir balstīti uz dabiskās atlases un ģenētikas idejām. Tā ir saprātīga nejaušu meklējumu izmantošana, kas nodrošināti ar vēsturiskiem datiem, lai virzītu meklēšanu uz labākas veiktspējas reģionu risinājumu telpā. Tos parasti izmanto, lai radītu augstas kvalitātes risinājumus optimizācijas un meklēšanas problēmām.
Ģenētiskie algoritmi simulē dabiskās atlases procesu kas nozīmē, ka tās sugas, kas spēj pielāgoties izmaiņām savā vidē, var izdzīvot un vairoties un pāriet uz nākamo paaudzi. Vienkāršiem vārdiem sakot, tie simulē to cilvēku izdzīvošanu, kuri ir piemērotākie, lai atrisinātu problēmu. Katra paaudze sastāv no indivīdu populācijas un katrs indivīds pārstāv kādu punktu meklēšanas telpā un iespējamo risinājumu. Katrs indivīds tiek attēlots kā rakstzīmju/veselu skaitļu/pludināto/bitu virkne. Šī virkne ir analoga hromosomai.
Ģenētisko algoritmu pamats
Ģenētiskie algoritmi ir balstīti uz analoģiju ar populācijas hromosomu ģenētisko struktūru un uzvedību. Tālāk ir sniegts GA pamats, pamatojoties uz šo analoģiju -
- Indivīdi populācijā sacenšas par resursiem un pārojas
- Tie indivīdi, kuri ir sekmīgi (fittest), tad pārojas, lai radītu vairāk pēcnācēju nekā citi
- Gēni no spēcīgākajiem vecākiem izplatās visas paaudzes garumā, tas ir, dažreiz vecāki rada pēcnācējus, kas ir labāki nekā jebkurš no vecākiem.
- Tādējādi katra nākamā paaudze ir vairāk piemērota savai videi.
Meklēt vietu
Indivīdu populācija tiek uzturēta meklēšanas telpā. Katrs indivīds ir konkrētas problēmas risinājums meklēšanas telpā. Katrs indivīds tiek kodēts kā komponentu ierobežota garuma vektors (analogs hromosomai). Šie mainīgie komponenti ir līdzīgi gēniem. Tādējādi hromosoma (indivīds) sastāv no vairākiem gēniem (mainīgiem komponentiem).
Fitnesa rādītājs
Fitnesa rezultāts tiek piešķirts katram indivīdam, kurš parāda indivīda spēju konkurēt . Tiek meklēta persona, kurai ir optimāls fiziskās sagatavotības rādītājs (vai tuvu optimālajam).
GA uztur n indivīdu populāciju (hromosomu/šķīdumu) kopā ar viņu piemērotības rādītājiem. Personām, kurām ir labāki fitnesa rādītāji, tiek dota lielāka iespēja vairoties nekā citiem. Tiek atlasīti indivīdi ar labākiem fiziskās sagatavotības rādītājiem, kuri pārojas un ražo labāki pēcnācēji apvienojot vecāku hromosomas. Iedzīvotāju skaits ir statisks, tāpēc telpa ir jāizveido jaunpienācējiem. Tātad daži indivīdi mirst un tiek aizstāti ar jaunpienācējiem, kas galu galā rada jaunu paaudzi, kad visas vecās populācijas pārošanās iespējas ir izsmeltas. Cerams, ka turpmākajās paaudzēs tiks iegūti labāki risinājumi, bet vismazāk piemērotie mirs.
Katrai jaunajai paaudzei ir vidēji vairāk labāku gēnu nekā iepriekšējo paaudžu indivīdam (risinājumam). Tādējādi katrai jaunajai paaudzei ir labāk daļēji risinājumi nekā iepriekšējās paaudzes. Tiklīdz iegūtajiem pēcnācējiem nav būtiskas atšķirības no iepriekšējo populāciju radītajiem pēcnācējiem, populācija tiek konverģēta. Tiek uzskatīts, ka algoritms ir apvienots ar problēmas risinājumu kopumu.
Ģenētisko algoritmu operatori
Kad sākotnējā paaudze ir izveidota, algoritms attīsta paaudzi, izmantojot šādus operatorus:
1) Operatora atlase: Ideja ir dot priekšroku personām ar labiem fitnesa rādītājiem un ļaut viņiem nodot savus gēnus nākamajām paaudzēm.
2) Crossover operators: Tas apzīmē indivīdu pārošanos. Divas personas tiek atlasītas, izmantojot atlases operatoru, un krustošanas vietnes tiek izvēlētas nejauši. Tad gēni šajās krustošanās vietās tiek apmainīti, tādējādi radot pilnīgi jaunu indivīdu (pēcnācēju). Piemēram -
3) Mutācijas operators: Galvenā ideja ir pēcnācējos ievietot nejaušus gēnus, lai saglabātu populācijas daudzveidību un izvairītos no priekšlaicīgas konverģences. Piemēram -
pievienoties mysql atjauninājumam
Visu algoritmu var apkopot šādi:
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>
Problēmas un risinājuma piemērs, izmantojot ģenētiskos algoritmus
Ņemot vērā mērķa virkni, mērķis ir izveidot mērķa virkni, sākot no nejaušas tāda paša garuma virknes. Sekojošā realizācijā tiek veiktas šādas analoģijas:
- Rakstzīmes A–Z, a–z, 0–9 un citi īpašie simboli tiek uzskatīti par gēniem
- Šo rakstzīmju ģenerētā virkne tiek uzskatīta par hromosomu/šķīdumu/individuālu
Fitnesa rādītājs ir rakstzīmju skaits, kas atšķiras no rakstzīmēm mērķa virknē noteiktā indeksā. Tāpēc priekšroka tiek dota indivīdam ar zemāku fitnesa vērtību.
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->hromosoma = hromosoma; fitness = cal_fitness(); }; // Veikt pārošanos un radīt jaunus pēcnācējus Individual Individual::mate(Individual par2) { // hromosoma pēcnācēja virknei child_chromosoma = ''; int len = hromosoma.izmērs(); for(int i = 0;i { // nejaušības varbūtības pludiņš p = random_num(0, 100)/100; // ja varbūtība ir mazāka par 0,45, ievietojiet gēnu // no 1. cilvēka 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 << '
'; }> |
>
spēle balodis android
>
Java
Ubuntu būvēšanas pamatprincipi
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#
android process acore turpina apstāties
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).Summa(); } // Veikt pārošanos un radīt jaunus pēcnācējus public Individual Mate(Individual parent2) { char[] childHromosoma = new char[Hromosoma.Length]; for (int i = 0; i { double p = nejaušs.NextDouble(); if (p<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 |
smtp interneta protokols
>Izvade: 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>Piezīme: Katru reizi algoritms sākas ar nejaušām virknēm, tāpēc izvade var atšķirties
Kā redzam no izvades, mūsu algoritms dažkārt ir iestrēdzis pie lokālā optimālā risinājuma, to var vēl vairāk uzlabot, atjauninot fitnesa rezultāta aprēķināšanas algoritmu vai pielāgojot mutāciju un krustošanas operatorus.
Kāpēc izmantot ģenētiskos algoritmus
- Viņi ir izturīgi
- Nodrošiniet optimizāciju lielas telpas stāvoklī.
- Atšķirībā no tradicionālā mākslīgā intelekta, tie nesabojājas, mainoties nelielām ievades izmaiņām vai trokšņa klātbūtnei
Ģenētisko algoritmu pielietošana
Ģenētiskajiem algoritmiem ir daudz lietojumu, daži no tiem ir -
- Atkārtots neironu tīkls
- Mutāciju pārbaude
- Koda laušana
- Filtrēšana un signālu apstrāde
- Izplūdušo noteikumu bāzes apguve utt