Genetische Algorithmen (GAs) sind adaptive heuristische Suchalgorithmen, die zum größeren Teil der evolutionären Algorithmen gehören. Genetische Algorithmen basieren auf den Ideen der natürlichen Selektion und der Genetik. Dabei handelt es sich um eine intelligente Ausnutzung von Zufallssuchen mit historischen Daten, um die Suche in den Bereich mit der besseren Leistung im Lösungsbereich zu lenken. Sie werden häufig verwendet, um qualitativ hochwertige Lösungen für Optimierungsprobleme und Suchprobleme zu generieren.
Genetische Algorithmen simulieren den Prozess der natürlichen Selektion Das bedeutet, dass diejenigen Arten, die sich an Veränderungen in ihrer Umwelt anpassen können, überleben, sich vermehren und in die nächste Generation übergehen können. Mit einfachen Worten: Sie simulieren das Überleben des Stärksten unter Individuen aufeinanderfolgender Generationen, um ein Problem zu lösen. Jede Generation besteht aus einer Population von Individuen und jedes Individuum stellt einen Punkt im Suchraum und eine mögliche Lösung dar. Jedes Individuum wird als eine Zeichenfolge aus Zeichen/Ganzzahl/Float/Bits dargestellt. Diese Zeichenfolge ist analog zum Chromosom.
Grundlagen genetischer Algorithmen
Genetische Algorithmen basieren auf einer Analogie zur genetischen Struktur und zum Verhalten der Chromosomen der Bevölkerung. Es folgt die Grundlage von GAs, die auf dieser Analogie basieren:
- Individuen der Population konkurrieren um Ressourcen und Paarung
- Diejenigen Individuen, die erfolgreich (fitter) sind, paaren sich dann, um mehr Nachkommen als andere zu zeugen
- Gene des leistungsfähigsten Elternteils verbreiten sich über die gesamte Generation hinweg, das heißt, manchmal erzeugen Eltern Nachkommen, die besser sind als die beiden Elternteile.
- Somit ist jede nachfolgende Generation besser für ihre Umgebung geeignet.
Suchraum
Die Population der Individuen wird innerhalb des Suchraums verwaltet. Jedes Individuum repräsentiert eine Lösung im Suchraum für ein gegebenes Problem. Jedes Individuum ist als Vektor endlicher Länge (analog zum Chromosom) von Komponenten kodiert. Diese variablen Komponenten sind analog zu Genen. Somit besteht ein Chromosom (Individuum) aus mehreren Genen (variablen Bestandteilen).
Fitness-Score
Jedem Einzelnen wird ein Fitness-Score gegeben zeigt die Wettbewerbsfähigkeit einer Person . Gesucht wird die Person mit einem optimalen (oder nahezu optimalen) Fitnesswert.
Die GAs behalten die Population von n Individuen (Chromosom/Lösungen) zusammen mit ihren Fitness-Scores bei. Den Individuen mit besseren Fitness-Scores wird eine größere Chance gegeben, sich zu reproduzieren als anderen. Es werden die Individuen mit besseren Fitnesswerten ausgewählt, die sich paaren und produzieren bessere Nachkommen durch Kombination der Chromosomen der Eltern. Die Bevölkerungszahl ist statisch, daher muss Platz für Neuankömmlinge geschaffen werden. So sterben einige Individuen und werden durch Neuankömmlinge ersetzt, wodurch schließlich eine neue Generation entsteht, wenn alle Paarungsmöglichkeiten der alten Population erschöpft sind. Es besteht die Hoffnung, dass im Laufe der Generationen bessere Lösungen entstehen, während die Ungeeignetsten sterben.
Jede neue Generation verfügt im Durchschnitt über mehr bessere Gene als das Individuum (Lösung) früherer Generationen. Somit haben alle neuen Generationen bessere Ergebnisse Teillösungen als frühere Generationen. Sobald sich die Nachkommenschaft nicht wesentlich von der Nachkommenschaft früherer Populationen unterscheidet, wird die Population konvergiert. Man sagt, dass der Algorithmus zu einer Reihe von Lösungen für das Problem konvergiert.
Operatoren genetischer Algorithmen
Sobald die erste Generation erstellt wurde, entwickelt der Algorithmus die Generation mithilfe der folgenden Operatoren weiter:
1) Auswahloperator: Die Idee besteht darin, Individuen mit guten Fitnesswerten den Vorzug zu geben und ihnen die Möglichkeit zu geben, ihre Gene an nachfolgende Generationen weiterzugeben.
2) Crossover-Operator: Dies stellt die Paarung zwischen Individuen dar. Zwei Personen werden mithilfe eines Auswahloperators ausgewählt und Crossover-Standorte werden zufällig ausgewählt. Dann werden die Gene an diesen Kreuzungsstellen ausgetauscht, wodurch ein völlig neues Individuum (Nachkommen) entsteht. Zum Beispiel -
3) Mutationsoperator: Die Schlüsselidee besteht darin, zufällige Gene in die Nachkommen einzuführen, um die Vielfalt in der Population aufrechtzuerhalten und eine vorzeitige Konvergenz zu vermeiden. Zum Beispiel -
js settimeout
Der gesamte Algorithmus kann wie folgt zusammengefasst werden:
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>
Beispielproblem und Lösung mit genetischen Algorithmen
Bei gegebener Zielzeichenfolge besteht das Ziel darin, ausgehend von einer zufälligen Zeichenfolge derselben Länge eine Zielzeichenfolge zu erzeugen. In der folgenden Implementierung werden folgende Analogien vorgenommen:
- Als Gene gelten die Zeichen A-Z, a-z, 0-9 und andere Sonderzeichen
- Eine aus diesen Zeichen generierte Zeichenfolge wird als Chromosom/Lösung/Individuum betrachtet
Fitness-Score ist die Anzahl der Zeichen, die sich an einem bestimmten Index von den Zeichen in der Zielzeichenfolge unterscheiden. Personen mit geringerem Fitnesswert werden daher stärker bevorzugt.
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->Chromosom = Chromosom; fitness = cal_fitness(); }; // Paarung durchführen und neuen Nachwuchs zeugen Individual Individual::mate(Individual par2) { // Chromosom für Nachkommen string child_chromosome = ''; int len = chromosome.size(); for(int i = 0;i { // Zufallswahrscheinlichkeit float p = random_num(0, 100)/100; // wenn prob kleiner als 0,45 ist, Gen einfügen // aus Elternteil 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 << '
'; }> |
>
Frühlingsinitialisierung
>
Java
So deaktivieren Sie den Entwicklermodus
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-Utility-Datum
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(); } // Paarung durchführen und neue Nachkommen hervorbringen public Individual Mate(Individual parent2) { char[] childChromosome = new char[Chromosome.Length]; for (int i = 0; i { double p = random.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 |
Anhängen einer Zeichenfolge in Java
>Ausgabe: 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>Notiz: Jeder Algorithmus beginnt mit zufälligen Zeichenfolgen, daher kann die Ausgabe unterschiedlich sein
Wie wir der Ausgabe entnehmen können, bleibt unser Algorithmus manchmal bei einer lokalen optimalen Lösung hängen. Dies kann durch die Aktualisierung des Fitness-Score-Berechnungsalgorithmus oder durch Optimierung der Mutations- und Crossover-Operatoren weiter verbessert werden.
Warum genetische Algorithmen verwenden?
- Sie sind robust
- Bietet Optimierung für große Raumzustände.
- Im Gegensatz zu herkömmlicher KI brechen sie nicht bei geringfügigen Änderungen der Eingabe oder beim Vorhandensein von Rauschen
Anwendung genetischer Algorithmen
Genetische Algorithmen haben viele Anwendungen, einige davon sind –
- Wiederkehrendes neuronales Netzwerk
- Mutationstests
- Code knacken
- Filterung und Signalverarbeitung
- Erlernen der Fuzzy-Regelbasis usw