Geneettiset algoritmit (GA:t) ovat mukautuvia heuristisia hakualgoritmeja, jotka kuuluvat suurempaan osaan evoluutioalgoritmeja. Geneettiset algoritmit perustuvat luonnonvalinnan ja genetiikan ideoihin. Nämä ovat satunnaisten hakujen älykästä hyödyntämistä historiallisilla tiedoilla ohjaamaan haun paremman suorituskyvyn alueelle ratkaisuavaruudessa. Niitä käytetään yleisesti luomaan korkealaatuisia ratkaisuja optimointiongelmiin ja hakuongelmiin.
Geneettiset algoritmit simuloivat luonnollisen valinnan prosessia mikä tarkoittaa, että ne lajit, jotka voivat sopeutua ympäristönsä muutoksiin, voivat selviytyä ja lisääntyä ja siirtyä seuraavaan sukupolveen. Yksinkertaisesti sanottuna ne simuloivat parhaiten selviytymistä peräkkäisten sukupolvien yksilöiden keskuudessa ratkaisemaan ongelman. Jokainen sukupolvi koostuu yksilöiden populaatiosta ja jokainen yksilö edustaa pistettä hakuavaruudessa ja mahdollista ratkaisua. Jokainen yksilö esitetään merkkijonona/kokonaislukuna/float/bittinä. Tämä merkkijono on analoginen kromosomin kanssa.
Geneettisten algoritmien perusta
Geneettiset algoritmit perustuvat analogiaan populaation kromosomien geneettisen rakenteen ja käyttäytymisen kanssa. Seuraava on tähän analogiaan perustuva GA:n perusta -
- Väestön yksilöt kilpailevat resursseista ja pariutuvat
- Ne yksilöt, jotka menestyvät (kunnossa), parittelevat luodakseen enemmän jälkeläisiä kuin muut
- Sopivimman vanhemman geenit leviävät koko sukupolven ajan, toisin sanoen vanhemmat luovat jälkeläisiä, jotka ovat parempia kuin kumpikaan vanhempi.
- Siten jokainen peräkkäinen sukupolvi sopii paremmin ympäristöönsä.
Etsi tilaa
Yksilöiden populaatio säilytetään hakutilassa. Jokainen yksilö edustaa ratkaisua tietyn ongelman hakutilassa. Jokainen yksilö on koodattu komponenttien äärellisen pituiseksi vektoriksi (analogisesti kromosomien kanssa). Nämä muuttuvat komponentit ovat analogisia geenien kanssa. Siten kromosomi (yksilö) koostuu useista geeneistä (muuttuvista komponenteista).
Kuntopisteet
Kuntopisteet annetaan jokaiselle henkilölle, joka osoittaa yksilön kyvyn kilpailla . Etsitään henkilöä, jolla on optimaalinen kuntopiste (tai lähellä optimaalista).
GA:t ylläpitävät n yksilön populaatiota (kromosomi/liuokset) sekä heidän kuntopisteensä. Paremmat kuntopisteet omaaville henkilöille annetaan enemmän mahdollisuuksia lisääntyä kuin muille. Paremmat kuntopisteet omaavat yksilöt valitaan, jotka parittelevat ja tuottavat parempia jälkeläisiä yhdistämällä vanhempien kromosomeja. Väestön koko on staattinen, joten huone on luotava uusille tulokkaille. Joten jotkut yksilöt kuolevat ja korvataan uusilla tulokkailla, jotka lopulta luovat uuden sukupolven, kun kaikki vanhan populaation pariutumismahdollisuudet on käytetty. Toivotaan, että peräkkäisten sukupolvien aikana saadaan parempia ratkaisuja, kun vähiten istuva kuolee.
Jokaisessa uudessa sukupolvessa on keskimäärin enemmän parempia geenejä kuin aiempien sukupolvien yksilöllä (ratkaisulla). Näin ollen jokaisella uusilla sukupolvilla on parempia osittaisia ratkaisuja kuin aikaisemmat sukupolvet. Kun syntyneillä jälkeläisillä ei ole merkittävää eroa aikaisempien populaatioiden tuottamiin jälkeläisiin, populaatio konvergoi. Algoritmin sanotaan konvergoivan joukkoon ratkaisuja ongelmaan.
Geneettisten algoritmien operaattorit
Kun ensimmäinen sukupolvi on luotu, algoritmi kehittää sukupolven käyttämällä seuraavia operaattoreita -
1) Operaattorin valinta: Ajatuksena on antaa etusija henkilöille, joilla on hyvä kunto ja antaa heidän siirtää geeninsä peräkkäisille sukupolville.
2) Crossover-operaattori: Tämä edustaa yksilöiden välistä parittelua. Kaksi henkilöä valitaan valintaoperaattorin avulla ja crossover-sivustot valitaan satunnaisesti. Sitten näiden risteytyskohtien geenit vaihdetaan, jolloin syntyy täysin uusi yksilö (jälkeläinen). Esimerkiksi -
3) Mutaatiooperaattori: Keskeisenä ajatuksena on lisätä satunnaisia geenejä jälkeläisiin populaation monimuotoisuuden säilyttämiseksi ennenaikaisen lähentymisen välttämiseksi. Esimerkiksi -
härkä vs härkä
Koko algoritmi voidaan tiivistää seuraavasti:
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>
Esimerkki ongelmasta ja ratkaisusta geneettisten algoritmien avulla
Kun kohdejono on annettu, tavoitteena on tuottaa kohdejono alkaen samanpituisesta satunnaisesta merkkijonosta. Seuraavassa toteutuksessa tehdään seuraavat analogiat -
- Merkit A-Z, a-z, 0-9 ja muut erikoissymbolit katsotaan geeneiksi
- Näiden merkkien luomaa merkkijonoa pidetään kromosomi/ratkaisu/yksilönä
Kuntopisteet on niiden merkkien määrä, jotka eroavat tietyn indeksin kohdemerkkijonon merkeistä. Joten henkilö, jolla on alhaisempi kunto-arvo, saa enemmän etusijaa.
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->kromosomi = kromosomi; kunto = cal_fitness(); }; // Suorita parittelu ja synnytä uusia jälkeläisiä Yksilö Individual::mate(Individual par2) { // kromosomi jälkeläisille merkkijono child_chromosome = ''; int len = kromosomi.koko(); for(int i = 0;i { // satunnaisen todennäköisyyden float p = random_num(0, 100)/100; // jos todennäköisyys on pienempi kuin 0,45, lisää geeni // emosta 1 if(p<0.45) child_chromosome += chromosome[i]; // if prob is between 0.45 and 0.90, insert // gene from parent 2 else if(p <0.90) child_chromosome += par2.chromosome[i]; // otherwise insert random gene(mutate), // for maintaining diversity else child_chromosome += mutated_genes(); } // create new Individual(offspring) using // generated chromosome for offspring return Individual(child_chromosome); }; // Calculate fitness score, it is the number of // characters in string which differ from target // string. int Individual::cal_fitness() { int len = TARGET.size(); int fitness = 0; for(int i = 0;i { if(chromosome[i] != TARGET[i]) fitness++; } return fitness; }; // Overloading bool operator<(const Individual &ind1, const Individual &ind2) { return ind1.fitness } // Driver code int main() { srand((unsigned)(time(0))); // current generation int generation = 0; vector population; bool found = false; // create initial population for(int i = 0;i { string gnome = create_gnome(); population.push_back(Individual(gnome)); } while(! found) { // sort the population in increasing order of fitness score sort(population.begin(), population.end()); // if the individual having lowest fitness score ie. // 0 then we know that we have reached to the target // and break the loop if(population[0].fitness <= 0) { found = true; break; } // Otherwise generate new offsprings for new generation vector new_generation; // Perform Elitism, that mean 10% of fittest population // goes to the next generation int s = (10*POPULATION_SIZE)/100; for(int i = 0;i new_generation.push_back(population[i]); // From 50% of fittest population, Individuals // will mate to produce offspring s = (90*POPULATION_SIZE)/100; for(int i = 0;i { int len = population.size(); int r = random_num(0, 50); Individual parent1 = population[r]; r = random_num(0, 50); Individual parent2 = population[r]; Individual offspring = parent1.mate(parent2); new_generation.push_back(offspring); } population = new_generation; cout<< 'Generation: ' << generation << ' '; cout<< 'String: '<< population[0].chromosome <<' '; cout<< 'Fitness: '<< population[0].fitness << '
'; generation++; } cout<< 'Generation: ' << generation << ' '; cout<< 'String: '<< population[0].chromosome <<' '; cout<< 'Fitness: '<< population[0].fitness << '
'; }> |
>
java poikkeusten käsittely
>
Java
vaihda väri gimpissä
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); } }> |
>
>
Python 3
# 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).Sum(); } // Suorita parittelu ja synnytä uusia jälkeläisiä public Individual Mate(Individual parent2) { char[] childChromosome = new char[kromosomi.Pituus]; 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
java-kokoelmat java
// 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 |
suorita komentosarjan kuori
>Lähtö: 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>Huomautus: Joka kerta algoritmi alkaa satunnaisilla merkkijonoilla, joten tulos voi vaihdella
Kuten tuloksesta näkyy, algoritmimme on joskus juuttunut paikalliseen optimiratkaisuun, jota voidaan parantaa edelleen päivittämällä kuntopisteiden laskentaalgoritmia tai säätämällä mutaatio- ja crossover-operaattoreita.
Miksi käyttää geneettisiä algoritmeja
- Ne ovat kestäviä
- Tarjoa optimointi suuren tilan tilassa.
- Toisin kuin perinteinen tekoäly, ne eivät katkea pienestä muutoksesta tulossa tai kohinan esiintyessä
Geneettisten algoritmien soveltaminen
Geneettisillä algoritmeilla on monia sovelluksia, joista osa on
- Toistuva hermoverkko
- Mutaatiotestaus
- Koodin rikkominen
- Suodatus ja signaalinkäsittely
- Sumean sääntöpohjan oppiminen jne