遺伝的アルゴリズム

遺伝的アルゴリズム (GA) は、進化的アルゴリズムの大部分に属する適応ヒューリスティック検索アルゴリズムです。遺伝的アルゴリズムは、自然選択と遺伝学の考えに基づいています。これらは、履歴データとともに提供されるランダム検索をインテリジェントに活用して、ソリューション空間でパフォーマンスが向上する領域に検索を誘導します。 これらは一般に、最適化問題や検索問題に対する高品質のソリューションを生成するために使用されます。

遺伝的アルゴリズムは自然選択のプロセスをシミュレートします これは、環境の変化に適応できる種は生き残り、繁殖し、次の世代に進むことができることを意味します。簡単に言うと、問題を解決するために、連続した世代の個人の間で適者生存をシミュレートします。 各世代は個人の集団で構成されています そして各個人は探索空間内の点と考えられる解決策を表します。各個体は、文字/整数/浮動小数点/ビットの文字列として表されます。この文字列は染色体に似ています。

遺伝的アルゴリズムの基礎

遺伝的アルゴリズムは、集団の遺伝的構造と染色体の挙動との類似性に基づいています。以下は、このアナロジーに基づく GA の基礎です。

集団内の個体は資源や交尾を求めて競争する
成功した（適者）個体は交配して他の個体よりも多くの子孫を残します。
最も適した親からの遺伝子は世代を通して伝播します。つまり、両親がどちらの親よりも優れた子孫を生み出すことがあります。
したがって、世代が続くごとに、その環境により適したものになります。

サーチスペース

個人の集団は探索空間内で維持されます。各個人は、特定の問題に対する検索空間内の解決策を表します。各個人は、コンポーネントの有限長ベクトル (染色体に類似) としてコード化されます。これらの可変コンポーネントは遺伝子に似ています。このように、染色体（個人）は複数の遺伝子（可変成分）から構成されています。

フィットネススコア

フィットネススコアは各個人に与えられます。 個人の競争能力を示す 。最適なフィットネススコア (または最適に近い) を持つ個人が検索されます。

GA は、n 個の個体 (染色体/溶液) の母集団をその適応度スコアとともに維持します。より良い適応度スコアを持つ個体には、他の個体よりも多くの繁殖機会が与えられます。より良い適応度スコアを持つ個体が交配して生産される個体として選択されます。 より良い子孫 両親の染色体を組み合わせることによって。人口の規模は静的であるため、新しい到着者のために部屋を作成する必要があります。そのため、古い個体群の交配の機会がすべて使い果たされると、一部の個体は死亡し、新しい到着個体に取って代わられ、最終的には新しい世代を生み出します。世代を重ねるごとに、最も適さないソリューションが消滅する一方で、より優れたソリューションが登場することが期待されています。

新しい世代はそれぞれ、平均して前の世代の個体 (ソリューション) よりも優れた遺伝子を持っています。したがって、新しい世代はそれぞれより良いものを持っています 部分的な解決策 前の世代よりも。生産された子孫が以前の集団によって生産された子孫と有意な差がなくなると、その集団は収束します。このアルゴリズムは、問題に対する一連の解決策に収束するといわれています。

遺伝的アルゴリズムの演算子

最初の世代が作成されると、アルゴリズムは次の演算子を使用して世代を進化させます。
1) 選択演算子: その考えは、優れた適応度スコアを持つ個体を優先し、その遺伝子を後続の世代に受け継がせることを可能にすることです。
2) クロスオーバーオペレーター: これは個体間の交配を表します。選択演算子を使用して 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; // 確率が 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  < < '
';  }>

ジャワ

import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> import> java.util.Random;> > public> class> GeneticAlgorithm {> > // Number of individuals in each generation> > private> static> final> int> POPULATION_SIZE => 100> ;> > > // Valid Genes> > private> static> final> String GENES => 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'> ;> > > // Target string to be generated> > private> static> final> String TARGET => 'I love techcodeview.com'> ;> > > // Function to generate random numbers in given range> > private> static> int> randomNum(> int> start,> int> end) {> > Random rand => new> Random();> > return> rand.nextInt(end - start +> 1> ) + start;> > }> > > // Create random genes for mutation> > private> static> char> mutatedGenes() {> > int> len = GENES.length();> > int> r = randomNum(> 0> , len -> 1> );> > return> GENES.charAt(r);> > }> > > // Create chromosome or string of genes> > private> static> String createGnome() {> > int> len = TARGET.length();> > StringBuilder gnome => new> StringBuilder();> > for> (> int> i => 0>

; i   gnome.append(mutatedGenes());   return gnome.toString();   }     // Class representing individual in population   private static class Individual implements Comparable {   String chromosome;   int fitness;     Individual(String chromosome) {   this.chromosome = chromosome;   fitness = calFitness();   }     // Perform mating and produce new offspring   Individual mate(Individual par2) {   StringBuilder childChromosome = new StringBuilder();     int len = chromosome.length();   for (int i = 0; i   // random probability   float p = randomNum(0, 100) / 100f;     // if prob is less than 0.45, insert gene from parent 1   if (p  <0.45)   childChromosome.append(chromosome.charAt(i));     // if prob is between 0.45 and 0.90, insert gene from parent 2   else if (p  <0.90)   childChromosome.append(par2.chromosome.charAt(i));     // otherwise insert random gene(mutate), for maintaining diversity   else  childChromosome.append(mutatedGenes());   }     // create new Individual(offspring) using generated chromosome for offspring   return new Individual(childChromosome.toString());   }     // Calculate fitness score, it is the number of characters in string which differ from target string   private int calFitness() {   int len = TARGET.length();   int fitness = 0;   for (int i = 0; i   if (chromosome.charAt(i) != TARGET.charAt(i))   fitness++;   }   return fitness;   }     @Override  public int compareTo(Individual o) {   return Integer.compare(this.fitness, o.fitness);   }   }     // Driver code   public static void main(String[] args) {   // current generation   int generation = 0;     List population = new ArrayList();   boolean found = false;     // create initial population   for (int i = 0; i   String gnome = createGnome();   population.add(new Individual(gnome));   }     while (!found) {   // sort the population in increasing order of fitness score   Collections.sort(population);     // if the individual having lowest fitness score i.e. 0 then we know that we have reached to the target   // and break the loop   if (population.get(0).fitness  <= 0) {   found = true;   break;   }     // Otherwise generate new offsprings for new generation   List newGeneration = new ArrayList();     // Perform Elitism, that mean 10% of fittest population goes to the next generation   int s = (10 * POPULATION_SIZE) / 100;   for (int i = 0; i   newGeneration.add(population.get(i));     // From 50% of fittest population, Individuals will mate to produce offspring   s = (90 * POPULATION_SIZE) / 100;   for (int i = 0; i   int len = population.size();   int r = randomNum(0, 50);   Individual parent1 = population.get(r);   r = randomNum(0, 50);   Individual parent2 = population.get(r);   Individual offspring = parent1.mate(parent2);   newGeneration.add(offspring);   }   population = newGeneration;   System.out.print('Generation: ' + generation + '	');   System.out.print('String: ' + population.get(0).chromosome + '	');   System.out.println('Fitness: ' + population.get(0).fitness);     generation++;   }   System.out.print('Generation: ' + generation + '	');   System.out.print('String: ' + population.get(0).chromosome + '	');   System.out.println('Fitness: ' + population.get(0).fitness);   }  }>

Python3

# Python3 program to create target string, starting from> # random string using Genetic Algorithm> > import> random> > # Number of individuals in each generation> POPULATION_SIZE> => 100> > # Valid genes> GENES> => '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP> QRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'''> > # Target string to be generated> TARGET> => 'I love techcodeview.com'> > class> Individual(> object> ):> > '''> > Class representing individual in population> > '''> > def> __init__(> self> , chromosome):> > self> .chromosome> => chromosome> > self> .fitness> => self> .cal_fitness()> > > @classmethod> > def> mutated_genes(> self> ):> > '''> > create random genes for mutation> > '''> > global> GENES> > gene> => random.choice(GENES)> > return> gene> > > @classmethod> > def> create_gnome(> self> ):> > '''> > create chromosome or string of genes> > '''> > global> TARGET> > gnome_len> => len> (TARGET)> > return> [> self> .mutated_genes()> for> _> in> range> (gnome_len)]> > > def> mate(> self> , par2):> > '''> > Perform mating and produce new offspring> > '''> > > # chromosome for offspring> > child_chromosome> => []> > for> gp1, gp2> in> zip> (> self> .chromosome, par2.chromosome):> > > # random probability> > prob> => random.random()> > > # if prob is less than 0.45, insert gene> > # from parent 1> > if> prob <> 0.45> :> > child_chromosome.append(gp1)> > > # if prob is between 0.45 and 0.90, insert> > # gene from parent 2> > elif> prob <> 0.90> :> > child_chromosome.append(gp2)> > > # otherwise insert random gene(mutate),> > # for maintaining diversity> > else> :> > child_chromosome.append(> self> .mutated_genes())> > > # create new Individual(offspring) using> > # generated chromosome for offspring> > return> Individual(child_chromosome)> > > def> cal_fitness(> self> ):> > '''> > Calculate fitness score, it is the number of> > characters in string which differ from target> > string.> > '''> > global> TARGET> > fitness> => 0> > for> gs, gt> in> zip> (> self> .chromosome, TARGET):> > if> gs !> => gt: fitness> +> => 1> > return> fitness> > # Driver code> def> main():> > global> POPULATION_SIZE> > > #current generation> > generation> => 1> > > found> => False> > population> => []> > > # create initial population> > for> _> in> range> (POPULATION_SIZE):> > gnome> => Individual.create_gnome()> > population.append(Individual(gnome))> > > while> not> found:> > > # sort the population in increasing order of fitness score> > population> => sorted> (population, key> => lambda> x:x.fitness)> > > # if the individual having lowest fitness score ie.> > # 0 then we know that we have reached to the target> > # and break the loop> > if> population[> 0> ].fitness <> => 0> :> > found> => True> > break> > > # Otherwise generate new offsprings for new generation> > new_generation> => []> > > # Perform Elitism, that mean 10% of fittest population> > # goes to the next generation> > s> => int> ((> 10> *> POPULATION_SIZE)> /> 100> )> > new_generation.extend(population[:s])> > > # From 50% of fittest population, Individuals> > # will mate to produce offspring> > s> => int> ((> 90> *> POPULATION_SIZE)> /> 100> )> > for> _> in> range> (s):> > parent1> => random.choice(population[:> 50> ])> > parent2> => random.choice(population[:> 50> ])> > child> => parent1.mate(parent2)> > new_generation.append(child)> > > population> => new_generation> > > print> (> 'Generation: {} String: {} Fitness: {}'> .> > format> (generation,> > ''.join(population[> 0> ].chromosome),> > population[> 0> ].fitness))> > > generation> +> => 1> > > > print> (> 'Generation: {} String: {} Fitness: {}'> .> > format> (generation,> > ''.join(population[> 0> ].chromosome),> > population[> 0> ].fitness))> > if> __name__> => => '__main__'> :> > main()>

C#

using> System;> using> System.Collections.Generic;> using> System.Linq;> > public> class> GeneticAlgorithm> {> > // Number of individuals in each generation> > private> const> int> POPULATION_SIZE = 100;> > > // Valid Genes> > private> const> string> GENES => 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP'> +> > 'QRSTUVWXYZ 1234567890, .-;:_!'#%&/()=?@${[]}'> ;> > > // Target string to be generated> > private> const> string> TARGET => 'I love techcodeview.com'> ;> > > private> static> readonly> Random random => new> Random();> > > // Function to generate random numbers in given range> > private> static> int> RandomNum(> int> start,> int> end)> > {> > return> random.Next(start, end + 1);> > }> > > // Create random genes for mutation> > private> static> char> MutatedGenes()> > {> > int> len = GENES.Length;> > int> r = RandomNum(0, len - 1);> > return> GENES[r];> > }> > > // Create chromosome or string of genes> > private> static> string> CreateGnome()> > {> > int> len = TARGET.Length;> > char> [] gnome => new> char> [len];> > for> (> int>

i = 0; i   {   gnome[i] = MutatedGenes();   }   return new string(gnome);   }     // Class representing individual in population   private class Individual   {   public string Chromosome { get; }   public int Fitness { get; }     public Individual(string chromosome)   {   Chromosome = chromosome;   Fitness = CalculateFitness();   }     // Calculate fitness score, it is the number of   // characters in string which differ from target string.   private int CalculateFitness()   {   return Chromosome.Zip(TARGET, (a, b) =>a == b ? 0 : 1).Sum();   } // 交配を実行し、新しい子孫を生成します public Individual Mate(Individualparent2) { 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  FitnessComparer.Compare(a, b));     // 個人の適応度スコアが最も低い場合、すなわち。   // 0 の場合、ターゲットに到達したことがわかります // そしてループを終了します if (population[0].Fitness === 0) { found = true;   壊す;   // それ以外の場合は、新しい世代の新しい子孫を生成します let newGeneration = [];     // エリート主義を実行します。つまり、適者集団の 10% が次の世代に移ります。 let s = Math.floor((10 * POPULATION_SIZE) / 100);   for (let i = 0; i newGeneration.push(population[i]); // 適者集団の 50% から、個体は // 交配して子孫を生み出します s = Math.floor((90 * POPULATION_SIZE) / 100); for (let i = 0; i let r = RandomNum(0, 50); letparent1 = 人口[r]; r = RandomNum(0, 50); letparent2 = 人口[r]; let offspring =parent1.Mate( parent2); newGeneration.push(offspring); } 人口 = newGeneration; '世代: ' + 世代 + '	' + '文字列: ' + 染色体 +  '	' + 'フィットネス: ' + 人口[0].フィットネス) } console.log('世代: ' + 世代 + '	' + '文字列: ' + ポピュレーション[0].Chromosome + '	' + 'フィットネス: ' + ポピュレーション[0].Fitness) } // メイン関数 Main() を実行します。

出力：

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

注記： 毎回アルゴリズムはランダムな文字列から始まるため、出力は異なる場合があります

出力からわかるように、アルゴリズムは局所的な最適解に固執することがありますが、これは、適応度スコア計算アルゴリズムを更新するか、突然変異および交差演算子を微調整することによってさらに改善できます。