Genetiniai algoritmai (GA) yra prisitaikantys euristinės paieškos algoritmai, priklausantys didesnei evoliucinių algoritmų daliai. Genetiniai algoritmai yra pagrįsti natūralios atrankos ir genetikos idėjomis. Tai yra protingas atsitiktinių paieškų, pateiktų su istoriniais duomenimis, išnaudojimas, siekiant nukreipti paiešką į geresnio našumo regioną sprendimų erdvėje. Jie dažniausiai naudojami kuriant aukštos kokybės optimizavimo ir paieškos problemų sprendimus.
Genetiniai algoritmai imituoja natūralios atrankos procesą o tai reiškia, kad tos rūšys, kurios gali prisitaikyti prie savo aplinkos pokyčių, gali išgyventi, daugintis ir pereiti į kitą kartą. Paprastais žodžiais tariant, jie imituoja iš eilės einančių kartų asmenų išgyvenimą, kurie yra pajėgiausi išspręsti problemą. Kiekviena karta susideda iš individų populiacijos ir kiekvienas individas reprezentuoja paieškos erdvės tašką ir galimą sprendimą. Kiekvienas asmuo vaizduojamas kaip simbolių / sveikųjų skaičių / plūduriuojančių / bitų eilutė. Ši eilutė yra analogiška chromosomai.
Genetinių algoritmų pagrindas
Genetiniai algoritmai yra pagrįsti analogija su populiacijos chromosomų genetine struktūra ir elgesiu. Toliau pateikiamas GA pagrindas, pagrįstas šia analogija -
- Asmenys populiacijoje konkuruoja dėl išteklių ir poruojasi
- Tie asmenys, kuriems sekasi (tvirčiausi), poruojasi, kad susilauktų daugiau palikuonių nei kiti
- Tinkamiausių tėvų genai plinta per visą kartą, ty kartais tėvai sukuria palikuonis, kurie yra geresni už bet kurį iš tėvų.
- Taigi kiekviena paskesnė karta yra labiau pritaikyta savo aplinkai.
Ieškoti erdvės
Asmenų populiacija išlaikoma paieškos erdvėje. Kiekvienas individas reiškia sprendimą konkrečios problemos paieškos erdvėje. Kiekvienas individas yra užkoduotas kaip baigtinio ilgio komponentų vektorius (analogiškas chromosomai). Šie kintamieji komponentai yra analogiški Genams. Taigi chromosoma (individas) susideda iš kelių genų (kintamų komponentų).
Fitneso balas
Fitneso balas suteikiamas kiekvienam asmeniui, kuris parodo individo gebėjimą konkuruoti . Ieškomas asmuo, turintis optimalų kūno rengybos balą (arba beveik optimalų).
GA palaiko n asmenų populiaciją (chromosomų / tirpalų) kartu su jų tinkamumo balais. Asmenims, kurių kūno rengybos rezultatai geresni, suteikiama daugiau galimybių daugintis nei kitiems. Atrenkami geriau pasirengę asmenys, kurie poruojasi ir gamina geresni palikuonys derinant tėvų chromosomas. Gyventojų skaičius yra statinis, todėl kambarys turi būti sukurtas naujiems atvykėliams. Taigi, kai kurie individai miršta ir juos pakeičia nauji atvykėliai, galiausiai sukuriantys naują kartą, kai išnaudojamos visos senosios populiacijos poravimosi galimybės. Tikimasi, kad per kelias kartas bus rasti geresni sprendimai, o mažiausiai tinkami mirs.
Kiekviena nauja karta turi vidutiniškai daugiau geresnių genų nei ankstesnių kartų individas (sprendimas). Taigi kiekviena nauja karta turi geriau daliniai sprendimai nei ankstesnės kartos. Kai susilaukę palikuonys reikšmingai nesiskiria nuo ankstesnių populiacijų palikuonių, populiacija suartėja. Teigiama, kad algoritmas yra suartintas su problemos sprendimų rinkiniu.
Genetinių algoritmų operatoriai
Sukūrus pradinę generaciją, algoritmas evoliucionuoja generaciją naudodamas šiuos operatorius:
1) Operatoriaus pasirinkimas: Idėja yra teikti pirmenybę asmenims, kurių kūno rengybos rezultatai yra geri, ir leisti jiems perduoti savo genus iš eilės kartoms.
2) Crossover operatorius: Tai reiškia poravimąsi tarp individų. Du asmenys atrenkami naudojant atrankos operatorių, o kryžminės svetainės parenkamos atsitiktinai. Tada genai šiose kryžminimo vietose yra keičiami taip sukuriant visiškai naują individą (palikuonį). Pavyzdžiui -
3) Mutacijos operatorius: Pagrindinė idėja yra įterpti atsitiktinius genus į palikuonis, kad būtų išlaikyta populiacijos įvairovė, kad būtų išvengta ankstyvos konvergencijos. Pavyzdžiui -
mesti išimties tvarkymą java
Visą algoritmą galima apibendrinti taip:
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>
Problemos ir sprendimo pavyzdys naudojant genetinius algoritmus
Atsižvelgiant į tikslinę eilutę, tikslas yra sukurti tikslinę eilutę, pradedant nuo atsitiktinės tokio paties ilgio eilutės. Tokiame įgyvendinime pateikiamos šios analogijos:
- Simboliai A–Z, a–z, 0–9 ir kiti specialūs simboliai laikomi genais
- Šių simbolių sugeneruota eilutė laikoma chromosoma / tirpalu / asmeniu
Fitneso balas yra simbolių, kurie skiriasi nuo simbolių tikslinėje eilutėje tam tikrame indekse, skaičius. Taigi asmeniui, turinčiam mažesnę fitneso vertę, teikiama daugiau pirmenybės.
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->chromosoma = chromosoma; fitnesas = cal_fitness(); }; // Atlikti poravimą ir susilaukti naujų palikuonių Individual Individual::mate(Individual par2) { // chromosoma palikuonių eilutei child_chromosoma = ''; int len = chromosoma.dydis(); for(int i = 0;i { // atsitiktinės tikimybės plūdimas p = random_num(0, 100)/100; // jei tikimybė mažesnė nei 0,45, įterpkite geną // iš pirminio 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 << '
'; }> |
>
>
lygiavertiškumo dėsniai
Java
kaip eilutę paversti int
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#
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).Suma(); } // Atlikti poravimąsi ir susilaukti naujų palikuonių public Individual Mate(Individual parent2) { char[] childChromosoma = new char[Chromosoma.Length]; for (int i = 0; i { double p = atsitiktinis.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); } }> |
xor java
>
>
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 |
>kas yra css selektoriaiIšvestis: 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>Pastaba: Kaskart algoritmas prasideda atsitiktinėmis eilutėmis, todėl išvestis gali skirtis
Kaip matome iš išvesties, mūsų algoritmas kartais įstrigo prie optimalaus vietinio sprendimo, tai gali būti dar labiau patobulinta atnaujinus kūno rengybos balo skaičiavimo algoritmą arba pakeitus mutacijų ir kryžminimo operatorius.
Kodėl verta naudoti genetinius algoritmus
- Jie yra tvirti
- Optimizuokite didelės erdvės būseną.
- Skirtingai nuo tradicinio AI, jie nesugenda dėl nedidelių įvesties pokyčių ar triukšmo
Genetinių algoritmų taikymas
Genetiniai algoritmai turi daug pritaikymų, kai kurie iš jų yra:
- Pasikartojantis neuroninis tinklas
- Mutacijų testavimas
- Kodo sulaužymas
- Filtravimas ir signalų apdorojimas
- Mokymasis neaiškios taisyklių bazės ir kt