Генетичні алгоритми (GA) — адаптивні евристичні алгоритми пошуку, які належать до більшої частини еволюційних алгоритмів. Генетичні алгоритми базуються на ідеях природного відбору та генетики. Це інтелектуальне використання випадкових пошуків із історичними даними, щоб спрямувати пошук у область кращої продуктивності в просторі рішень. Вони зазвичай використовуються для створення високоякісних рішень для проблем оптимізації та пошуку.
Генетичні алгоритми імітують процес природного відбору це означає, що ті види, які можуть адаптуватися до змін у навколишньому середовищі, можуть вижити, розмножуватися та переходити до наступного покоління. Простими словами, вони імітують виживання найпристосованіших серед індивідів послідовних поколінь для вирішення проблеми. Кожне покоління складається з популяції особин і кожна особистість представляє точку в просторі пошуку та можливе рішення. Кожна особа представлена у вигляді рядка символів/цілих чисел/плаваючої величини/біт. Цей рядок є аналогом хромосоми.
Основи генетичних алгоритмів
Генетичні алгоритми засновані на аналогії з генетичною структурою і поведінкою хромосом популяції. Нижче наведено основу GA, засновану на цій аналогії –
- Особи в популяції конкурують за ресурси та партнерство
- Ті особини, які є успішними (найбільш пристосованими), потім спаровуються, щоб створити більше потомства, ніж інші
- Гени від найбільш пристосованого батька поширюються протягом покоління, тобто іноді батьки створюють нащадків, які є кращими за будь-якого з батьків.
- Таким чином, кожне наступне покоління більше підходить для свого середовища.
Пошук простору
Популяція особин підтримується в просторі пошуку. Кожен індивід представляє рішення в просторі пошуку для даної проблеми. Кожна особина кодується як вектор кінцевої довжини (аналогічний хромосомі) компонентів. Ці змінні компоненти аналогічні генам. Таким чином, хромосома (індивід) складається з кількох генів (змінних компонентів).
Фітнес-оцінка
Фітнес-оцінка надається кожній особі, яка показує здатність індивіда до конкуренції . Розшукується особа з оптимальним показником фізичної підготовки (або близьким до оптимального).
GA зберігає популяцію з n особин (хромосоми/розчини) разом із їхніми оцінками фізичної підготовки. Особи, які мають кращі показники фізичної підготовки, отримують більше шансів для відтворення, ніж інші. Відбираються особини з кращими показниками фітнесу, які спаровуються та дають плоди краще потомство шляхом поєднання хромосом батьків. Чисельність населення є статичною, тому потрібно створити кімнату для нових прибулих. Таким чином, деякі особини вмирають і їх замінюють новими прибульцями, що зрештою створює нове покоління, коли всі можливості спаровування старої популяції вичерпано. Є надія, що протягом наступних поколінь кращі рішення з’являться, а найменш придатні вмирають.
Кожне нове покоління має в середньому більше кращих генів, ніж особина (розчин) попередніх поколінь. Таким чином, кожне нове покоління стає кращим часткові розв'язки ніж попередні покоління. Після того, як отримане потомство не має значних відмінностей від потомства, створеного попередніми популяціями, популяція конвергується. Алгоритм називається зведеним до набору розв’язків задачі.
Оператори генетичних алгоритмів
Після створення початкової генерації алгоритм розвиває генерацію за допомогою таких операторів:
1) Оператор вибору: Ідея полягає в тому, щоб надати перевагу особам із хорошими результатами фізичної підготовки та дозволити їм передавати свої гени наступним поколінням.
2) Оператор кросовера: Це означає спаровування між особинами. Дві особини вибираються за допомогою оператора відбору, а сайти кроссовера вибираються випадковим чином. Потім гени в цих місцях кросинговеру обмінюються таким чином, створюючи абсолютно нову особину (потомство). Наприклад -
3) Оператор мутації: Ключова ідея полягає в тому, щоб вставити випадкові гени в нащадків, щоб зберегти різноманітність популяції та уникнути передчасної конвергенції. Наприклад -
союз проти союзу всіх
Весь алгоритм можна коротко описати так:
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>
Приклад задачі та рішення з використанням генетичних алгоритмів
За наявності цільового рядка метою є створення цільового рядка, починаючи з випадкового рядка такої ж довжини. У наступній реалізації зроблено наступні аналогії –
- Символи A-Z, a-z, 0-9 та інші спеціальні символи вважаються генами
- Рядок, створений цими символами, вважається хромосомою/розчином/індивідуумом
Фітнес оцінка це кількість символів, які відрізняються від символів цільового рядка за певним індексом. Таким чином, людині з нижчим рівнем фізичної підготовки надається більша перевага.
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->хромосома = хромосома; фітнес = cal_fitness(); }; // Виконати спарювання та створити нове потомство Individual Individual::mate(Individual par2) { // хромосома для потомства string child_chromosome = ''; int len = chromosome.size(); for(int i = 0;i { // випадкова ймовірність float p = random_num(0, 100)/100; // якщо prob менше 0,45, вставити ген // із батьківського 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
git status -s
порівняти з рядками в java
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
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).Сума(); } // Здійснити спаровування та створити нове потомство 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 |
>
>
Вихід:
що таке робочий стіл ini
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> Примітка: Щоразу алгоритм починається з випадкових рядків, тому результат може відрізнятися
Як ми бачимо з виведених даних, наш алгоритм іноді застрягає на локальному оптимальному рішенні, це можна додатково покращити, оновивши алгоритм обчислення оцінки придатності або налаштувавши оператори мутації та кросинговеру.
Навіщо використовувати генетичні алгоритми
- Вони надійні
- Забезпечте оптимізацію у великому просторі.
- На відміну від традиційного штучного інтелекту, вони не ламаються при незначній зміні вхідного сигналу або наявності шуму
Застосування генетичних алгоритмів
Генетичні алгоритми мають багато застосувань, деякі з них:
- Рекурентна нейронна мережа
- Тестування на мутації
- Злом коду
- Фільтрація та обробка сигналів
- Вивчення бази нечітких правил тощо