At the forefront of Artificial Intelligence
  Home Articles Reviews Interviews JDK Glossary Features Discussion Search
Home » Articles » Genetic Algorithms » Beginner

Genetic Algorithm Example (Japanese Translation)

By Manabu Ishii (Translator)

English Version

このサンプルを読む前に 遺伝的アルゴリズム のエッセイを読んでいるものとします。また、サンプルで提供されるクラスとコードを利用できるC++ と オブジェクト指向プログラムの知識が必要です。

遺伝的アルゴリズムサンプル

diophantine (整数解だけの) 方程式: a+2b+3c+4d=30 について考えてみましょう。 a,b,c,d は正の整数です。遺伝的アルゴリズムを使い、必要なことは解(a,b,c,d)に達するまでの少しの時間です。もちろん、あなたは、ブルートフォース法を使ってもいいです。 (こつこつ、無理に、1 =< a,b,c,d =< 30 をすべて試していく方法です) GAシステムの構造は、"よりよい"解はより生き残り子供を作るチャンスがあるので、より早く達する可能性があります。反対に、ランダムに解を投げ出し、どれが働くのか見ます。

では最初からはじめましょう。はじめに私たちは、強制的に1 =< a,b,c,d =< 30から５つのランダムな初期解の集合を選びます。 (私たちはb,c,dに対してより小さい束縛を選ぶことができます、しかし単純にするために 30 を使います)

Chromosome
(a,b,c,d)
1
(1,28,15,3)
2
(14,9,2,4)
3
(13,5,7,3)
4
(23,8,16,19)
5
(9,13,5,2)

Table 1: 1st Generation Chromosomes and Their Contents

適合度を計算するために、すべての解の集合を式a+2b+3c+4dに代入します。そして、どの式も３０との差の絶対値を求めます、これが適合度になります。

Chromosome
Fitness Value
1
|114-30|=84
2
|54-30|=24
3
|56-30|=26
4
|163-30|=133
5
|58-30|=28

Table 2: Fitness Values of 1st Generation Chromosomes (Solution sets)

低い値は、望む答え(30)に近いので、これらの値はより望まれるものです。この場合、高い適合度は望まれず、低いものが望まれます。より望ましい適合度をもつ染色体が両親として選ばれるシステムを作るために私たちはまず、すべての染色体の選ばれるための比率を計算しなければなりません。 1つの解決策は、すべての適合度の値の逆数の合計をとり(0.135266)、そこから比率を計算する方法です。 (注：すべてのシミュレーションは乱数発生によって作られました)

Chromosome
Likelihood
1
(1/84)/0.135266 = 8.80%
2
(1/24)/0.135266 = 30.8%
3
(1/26)/0.135266 = 28.4%
4
(1/133)/0.135266 = 5.56%
5
(1/28)/0.135266 = 26.4%

Table 3: Parent Selection by Percentages

５つの両親(どの両親も１人の子供を持ちます、ですから全体で５つの新しい解集合ができます)を選び出すために１００００面のサイコロを想像します。８８０面に、染色体１と表示されます３０８０面に、染色体２と表示されます２６４０面に、染色体３と表示されます５５６面に、染色体４と表示されます２６４０面に、染色体５と表示されます最初の両親を選ぶために、サイコロを２回転がします。そしてそれらの染色体を、私たちのはじめの両親とします。これを続けると次のような両親ができました:

Father Chromosome
Mother Chromosome
3
1
5
2
3
5
2
5
5
3

Table 4: Simulated Selection of Parents

これらの両親から生れたどの子孫も、両親の遺伝的情報を含んでいます。この決定の方法は非常に恣意的です。しかしながらこの場合、私たちは"交叉"と呼ばれるものを使いました。母親が次のような解集合をもっていました、a1,b1,c1,d1, 父親は次のような解集合をもっていました、a2,b2,c2,d2, そして、そこには６種類の交叉の可能性があります ( | = は分割線です):

Father Chromosome
Mother Chromosome
Offspring Chromosome
a1 | b1,c1,d1
a2 | b2,c2,d2
a1,b2,c2,d2 or a2,b1,c1,d1
a1,b1 | c1,d1
a2,b2 | c2,d2
a1,b1,c2,d2 or a2,b2,c1,d1
a1,b1,c1 | d1
a2,b2,c2 | d2
a1,b1,c1,d2 or a2,b2,c2,d1

Table 5: Generalization of Cross-overs Between Parents

子供を作るために、両親の遺伝的情報を色々な方法でやり取りがすることができます。交叉は一つの方法にすぎません。分割線の場所は完全に恣意的にきまります、そして両親は、分割線の左または右に提供します。これを私たちの子供に適用してみましょう:

Father Chromosome
Mother Chromosome
Offspring Chromosome
(13 | 5,7,3)
(1 | 28,15,3)
(13,28,15,3)
(9,13 | 5,2)
(14,9 | 2,4)
(9,13,2,4)
(13,5,7 | 3)
(9,13,5 | 2)
(13,5,7,2)
(14 | 9,2,4)
(9 | 13,5,2)
(14,13,5,2)
(13,5 | 7, 3)
(9,13 | 5, 2)
(13,5,5,2)

Table 6: Simulated Crossovers from Parent Chromosomes

今、新世代の子供の適合度を計算することができます。

Offspring Chromosome
Fitness Value
(13,28,15,3)
|126-30|=96
(9,13,2,4)
|57-30|=27
(13,5,7,2)
|57-30|=22
(14,13,5,2)
|63-30|=33
(13,5,5,2)
|46-30|=16

Table 7: Fitness Values of Offspring Chromosomes

子孫染色体の平均適合度は38.8になりました。一方で両親染色体の平均適合度は59.4でした。もちろん、次の世代(子孫)は突然変異することになっています。つまり例えば、私たちはどの染色体の４の倍数の値を、ランダムに 1 から 30 の間の整数に変更することが可能です。これを進めていくと、私たちの染色体は解が見つかったときに、最終的に適合度レベル０に達するでしょう。もしあなたがこれを自分自身でシミュレーションするなら、突然変異に依存して、あなたは高い平均適合度になるかもしれまんが、しかし長いことはしらせると、適合度レベルは減少します。大きな集団(5ではなく50)のシステムに対しては、適合度レベルは安定して望まれるレベル(0)に達するでしょう。

C++ Class Code

C++ のクラスに含まれるすべてのクラスは、４つの係数と答えの５つの引数をとります。上のサンプルのクラスに関しては次のように初期化します:

CDiophantine dp(1,2,3,4,30);
そして、方程式を解くために関数Solve() を呼び出します。これは、それの解集合の対立遺伝子に対するインデックスを返します。 GetGene()を呼ぶことで、a,b,c,dに対する正しい値の染色体を手に入れられます。その結果、このクラスを使った典型的なmain.cpp は次のようになります: 
#include <iostream.h>
#include "diophantine.h"


void main() {

   CDiophantine dp(1,2,3,4,30);

   int ans;
   ans = dp.Solve();

   if (ans == -1) {
      cout << "No solution found." << endl;
   } else {
      gene gn = dp.GetGene(ans);

      cout << "The solution set to a+2b+3c+4d=30 is:\n";
      cout << "a = " << gn.alleles[0] << "." << endl;
      cout << "b = " << gn.alleles[1] << "." << endl;
      cout << "c = " << gn.alleles[2] << "." << endl;
      cout << "d = " << gn.alleles[3] << "." << endl;
   }
}

Translation by Manabu Ishii.

Submitted: 11/12/1999

Article content copyright © Manabu Ishii (Translator), 1999.
 Article Toolbar
Print
BibTeX entry

Search

Latest News
- Generation5 10-year Anniversary (03/09/2008)
- New Generation5 Design! (09/04/2007)
- Happy New Year 2007 (02/01/2007)
- Where has Generation5 Gone?! (04/11/2005)
- NeuroEvolving Robotic Operatives (NERO) (25/06/2005)

What's New?
- Back-propagation using the Generation5 JDK (07/04/2008)
- Hough Transforms (02/01/2008)
- Kohonen-based Image Analysis using the Generation5 JDK (11/12/2007)
- Modelling Bacterium using the JDK (19/03/2007)
- Modelling Bacterium using the JDK (19/03/2007)


All content copyright © 1998-2007, Generation5 unless otherwise noted.
- Privacy Policy - Legal - Terms of Use -