Gli algoritmi genetici (GA) sono algoritmi di ricerca euristica adattiva che appartengono alla maggior parte degli algoritmi evolutivi. Gli algoritmi genetici si basano sui concetti di selezione naturale e genetica. Si tratta di uno sfruttamento intelligente di ricerche casuali fornite di dati storici per indirizzare la ricerca nella regione con prestazioni migliori nello spazio delle soluzioni. Sono comunemente utilizzati per generare soluzioni di alta qualità per problemi di ottimizzazione e problemi di ricerca.
Gli algoritmi genetici simulano il processo di selezione naturale il che significa che quelle specie che possono adattarsi ai cambiamenti nel loro ambiente possono sopravvivere, riprodursi e passare alla generazione successiva. In parole semplici, simulano la sopravvivenza del più adatto tra gli individui di generazioni consecutive per risolvere un problema. Ogni generazione è costituita da una popolazione di individui e ogni individuo rappresenta un punto nello spazio di ricerca e di possibile soluzione. Ogni individuo è rappresentato come una stringa di caratteri/interi/virgola mobile/bit. Questa stringa è analoga al cromosoma.
Fondamento degli algoritmi genetici
Gli algoritmi genetici si basano su un'analogia con la struttura genetica e il comportamento dei cromosomi della popolazione. Di seguito è riportata la fondazione dei GA basata su questa analogia:
- Gli individui della popolazione competono per le risorse e per il compagno
- Quegli individui che hanno successo (più adatti) si accoppiano per creare più prole di altri
- I geni del genitore più adatto si propagano attraverso la generazione, cioè a volte i genitori creano una prole che è migliore di entrambi i genitori.
- Pertanto ogni generazione successiva è più adatta al proprio ambiente.
Spazio di ricerca
La popolazione di individui viene mantenuta all'interno dello spazio di ricerca. Ogni individuo rappresenta una soluzione nello spazio di ricerca per un dato problema. Ogni individuo è codificato come un vettore di componenti di lunghezza finita (analogo al cromosoma). Questi componenti variabili sono analoghi ai geni. Quindi un cromosoma (individuo) è composto da diversi geni (componenti variabili).
Punteggio di forma fisica
A ciascun individuo viene assegnato un punteggio di fitness mostra la capacità di un individuo di competere . Viene ricercato l'individuo con un punteggio di fitness ottimale (o quasi ottimale).
I GA mantengono la popolazione di n individui (cromosomi/soluzioni) insieme ai loro punteggi di fitness. Gli individui con punteggi di fitness migliori hanno maggiori possibilità di riprodursi rispetto ad altri. Vengono selezionati gli individui con punteggi di fitness migliori che si accoppiano e producono prole migliore combinando i cromosomi dei genitori. La dimensione della popolazione è statica quindi è necessario creare spazio per i nuovi arrivati. Quindi, alcuni individui muoiono e vengono sostituiti da nuovi arrivati che alla fine creano una nuova generazione quando tutte le opportunità di accoppiamento della vecchia popolazione sono esaurite. Si spera che nel corso delle generazioni successive arrivino soluzioni migliori mentre i meno idonei muoiono.
Ogni nuova generazione ha in media più geni migliori rispetto all'individuo (soluzione) delle generazioni precedenti. Così ogni nuova generazione ha di meglio soluzioni parziali rispetto alle generazioni precedenti. Una volta che la prole prodotta non presenta differenze significative rispetto alla prole prodotta dalle popolazioni precedenti, la popolazione converge. Si dice che l'algoritmo converge in un insieme di soluzioni per il problema.
Operatori di algoritmi genetici
Una volta creata la generazione iniziale, l'algoritmo evolve la generazione utilizzando i seguenti operatori:
1) Operatore di selezione: L'idea è quella di dare la preferenza agli individui con buoni punteggi di fitness e consentire loro di trasmettere i propri geni alle generazioni successive.
2) Operatore crossover: Questo rappresenta l'accoppiamento tra individui. Due individui vengono selezionati utilizzando l'operatore di selezione e i siti di crossover vengono scelti in modo casuale. Quindi i geni in questi siti di crossover vengono scambiati creando così un individuo completamente nuovo (prole). Per esempio -
3) Operatore di mutazione: L’idea chiave è quella di inserire geni casuali nella prole per mantenere la diversità nella popolazione ed evitare una convergenza prematura. Per esempio -
software di sistema
L’intero algoritmo può essere riassunto come:
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>
Esempio di problema e soluzione utilizzando algoritmi genetici
Data una stringa obiettivo, l'obiettivo è produrre la stringa obiettivo partendo da una stringa casuale della stessa lunghezza. Nella seguente implementazione, vengono fatte le seguenti analogie:
- I caratteri A-Z, a-z, 0-9 e altri simboli speciali sono considerati geni
- Una stringa generata da questi caratteri viene considerata come cromosoma/soluzione/Individuo
Punteggio di forma fisica è il numero di caratteri che differiscono dai caratteri nella stringa di destinazione in un particolare indice. Pertanto viene data maggiore preferenza agli individui con un valore di fitness inferiore.
C++
aggiornamento in SQL con join
// 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->cromosoma = cromosoma; forma fisica = cal_forma fisica(); }; // Esegue l'accoppiamento e produce nuova prole Individuale Individuale::mate(Individuale par2) { // cromosoma per la prole string child_chromosome = ''; int len = cromosoma.dimensione(); for(int i = 0;i { // probabilità casuale float p = random_num(0, 100)/100; // se prob è inferiore a 0,45, inserisci il gene // dal genitore 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 << '
'; }> |
>
>
Giava
ereditarietà in c++
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 per il ciclo
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) =>un == b? 0 : 1).Somma(); } // Esegue l'accoppiamento e produce nuova prole 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
f film
// 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 |
>Produzione: 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>Nota: L'algoritmo ogni volta inizia con stringhe casuali, quindi l'output potrebbe differire
Come possiamo vedere dall'output, il nostro algoritmo a volte si blocca su una soluzione ottimale locale, questa può essere ulteriormente migliorata aggiornando l'algoritmo di calcolo del punteggio di fitness o modificando gli operatori di mutazione e crossover.
Perché utilizzare gli algoritmi genetici
- Sono robusti
- Fornire l'ottimizzazione su uno stato di spazio di grandi dimensioni.
- A differenza dell'intelligenza artificiale tradizionale, non si rompono in caso di lievi cambiamenti nell'input o in presenza di rumore
Applicazione di algoritmi genetici
Gli algoritmi genetici hanno molte applicazioni, alcune di esse sono:
- Rete neurale ricorrente
- Test di mutazione
- Violazione del codice
- Filtraggio ed elaborazione del segnale
- Apprendimento della base di regole fuzzy, ecc