遺伝的アルゴリズムとは
遺伝的アルゴリズムは、進化的計算の一種であり、生物の進化の仕組みを模倣したアルゴリズムです。生物が進化する過程で、自然選択や突然変異などの要素が働き、適応度の高い個体が生き残り、次世代に遺伝子を伝えます。遺伝的アルゴリズムも同様に、個体集団内で適応度の高い個体が選択され、交叉や突然変異によって新しい個体を生成し、次世代に遺伝子を伝えることで最適解を求めます。
遺伝的アルゴリズムの実装
遺伝的アルゴリズムは、次の手順で実装することができます。
- 遺伝子表現の定義:最適化対象の問題によって、遺伝子表現を定義します。たとえば、整数の配列、実数の配列、ビットの配列など、適切な表現を選択する必要があります。
- 初期個体群の生成:ランダムに初期値を生成することにより、個体群を初期化します。
- 適応度関数の定義:目的関数を適応度関数として定義します。各個体に対して、適応度を計算し、その値が高いほど適応度が高いとされます。
- 選択:適応度が高い個体を次世代に残すために、選択を行います。選択には、ルーレット選択、トーナメント選択、ランキング選択などの方法があります。
- 交叉:選択された個体を用いて、交叉を行います。交叉は、2つの親個体を組み合わせ、新しい子孫個体を生成することで行われます。一般的な交叉方法には、一点交叉、二点交叉、一様交叉などがあります。
- 突然変異:個体の多様性を維持するために、突然変異を行います。突然変異は、ランダムな箇所で遺伝子を変化させることで、新たな個体を生成する方法です。
- 次世代の生成:選択、交叉、突然変異を行った結果から、次世代の個体群を生成します。
- 終了判定:一定の世代数や、目的達成のための十分な進捗がある場合は、アルゴリズムを終了します。そうでなければ、3-7の手順を繰り返し行います。
- 結果の出力:最終的に求められた最適解、あるいは近似解を出力します。
このように、遺伝的アルゴリズムは、初期化、適応度評価、選択、交叉、突然変異、世代交代のサイクルを繰り返すことで、最適化問題を解決します。
遺伝的アルゴリズムの実装例
さて、ExcelVBAで実装してみます。
問題設定
問題を以下のとおり設定しました。
- “0”,”1″のデータからなる遺伝子(パラメーターで長さを変更可)を設定する。
設定例(5桁の場合):”1″,”0″,”1″,”1″,”0″ - 数列の平均値(“0″~”1”)を適応関数とし、個体の中で適用関数の値がMax値を優秀な個体とする。
- 答えはすべて”1″(平均値が”1″)とする。
関数の概要
実装にあたり、以下の関数を作成します。
- Evaluate関数
個体集団の適応度を計算します。Initialize関数は、ランダムに遺伝子型を初期化します。 - Initialize関数
ランダムに遺伝子型を初期化します。 - CalculateFitness関数
Evaluate関数を呼び出して、遺伝子型を適応度に基づいてソートします。 - SelectParent関数
ルーレット選択法を使用して、親を選択します。 - Crossover関数
2つの親の遺伝子型を交叉し、2つの子を作成します。 - Mutation関数
子の遺伝子型を突然変異させます。 - Evolve関数
SelectParent、Crossover、Mutation関数を使用して、新しい個体集団(世代)を生成させます。 - Main関数
遺伝的アルゴリズムを実行し、一番優秀(適応度関数の数値が一番高い)な個体を答えとして表示させます。
パラメーターの設定
今回は、以下のパラメーターを設定する。
- 遺伝子の長さは”20″文字
- 個体集団の数は”150″個体
- 交叉率は”0.6″
- 突然変異率は”0.01″
- 世代数は”1000″世代
関数の実装例
関数を以下のとおり実装してみました。
Evaluate関数
' 適応度関数
Private Function Evaluate(ByRef gene() As Integer, ByRef fitness() As Double)
Dim i As Integer
Dim j As Integer
Dim sum As Double
For i = 0 To PopulationSize - 1
sum = 0
For j = 0 To GeneLength - 1
sum = sum + gene(i, j)
Next j
fitness(i) = sum / GeneLength
Next i
End Function
適応度関数は、ある個体の遺伝子座(遺伝子の位置)の配列を引数として受け取り、その個体の適応度を計算して返します。
このコードでは、遺伝子座の配列gene()と、各個体の適応度を格納するための配列fitness()を引数として受け取ります。
まず、変数iとjを初期化し、各個体の遺伝子座を走査するためのループを設定します。
次に、変数sumを0で初期化し、各遺伝子座の値を合計してsumに加算します。
最後に、各個体の適応度を、各遺伝子座の合計値をその遺伝子座の数で割った値で求めます。この値は、各個体の適応度として、fitness()配列に格納されます。
つまり、この適応度関数は、各個体の遺伝子座の平均値をその個体の適応度として返します。
Initialize関数
' 初期化
Private Sub Initialize()
Dim i As Integer
Dim j As Integer
For i = 0 To PopulationSize - 1
For j = 0 To GeneLength - 1
genes(i, j) = Int(Rnd() + 0.5)
Next j
Next i
End Sub
0か1の値を持つ遺伝子をランダムに生成し、それを複数の個体にわたって初期集団として設定します。遺伝子の長さはGeneLengthで、初期集団のサイズはPopulationSizeで指定されています。
CalculateFitness関数
' 適応度の計算
Private Sub CalculateFitness()
Dim i As Integer
Dim j As Integer
Dim k As Integer
Evaluate genes(), fitness()
' 適応度に基づいて遺伝子型をソート
Dim tempGene(GeneLength) As Integer
Dim tempFitness As Double
For i = 0 To PopulationSize - 2
For j = i + 1 To PopulationSize - 1
If fitness(i) < fitness(j) Then
tempFitness = fitness(i)
fitness(i) = fitness(j)
fitness(j) = tempFitness
For k = 0 To GeneLength - 1
tempGene(k) = genes(i, k)
genes(i, k) = genes(j, k)
genes(j, k) = tempGene(k)
Next k
End If
Next j
Next i
End Sub
遺伝的アルゴリズムにおける適応度の計算と、適応度に基づく遺伝子型のソートを行います。
Evaluate
関数で、genes
配列の各個体の遺伝子型に対する適応度を計算しています。fitness
配列に、各個体の適応度を格納しています。
次に、適応度に基づいてgenes
配列をソートしています。このソートは、適応度が高い個体から順に配列を並び替えることで、探索空間の中でより良い解を探索するためのものです。ここでは、バブルソートを使用しています。2重のforループを使用して、配列の要素を比較して適応度に基づいて並び替えを行っています。適応度が高い個体が前に来るように、要素を入れ替えているだけです。
なお、このコードは遺伝子型をバイナリ表現で表しているため、Int(Rnd() + 0.5)
を使用して、0または1をランダムに生成しています。これは、各遺伝子がランダムに0または1のいずれかになるように初期化するためのものです。
SelectParent関数
' 選択演算子
Private Function SelectParent() As Integer
Dim i As Integer
Dim j As Integer
Dim totalFitness As Double
Dim fitnessSum As Double
For i = 0 To PopulationSize - 1
totalFitness = totalFitness + fitness(i)
Next i
Dim roulette(PopulationSize) As Double
roulette(0) = fitness(0) / totalFitness
For i = 1 To PopulationSize - 1
roulette(i) = roulette(i - 1) + fitness(i) / totalFitness
Next i
' ルーレット選択
Dim r As Double
r = Rnd()
For i = 0 To PopulationSize - 1
If r < roulette(i) Then
SelectParent = i
Exit Function
End If
Next i
End Function
まず、全個体の適応度を計算し、その合計値を求めます。次に、各個体の適応度を合計値で割って、ルーレットのスロットの大きさを計算します。これにより、適応度が高い個体ほど選ばれやすくなります。この処理は、roulette()
配列に格納されます。
次に、乱数を生成し、ルーレットを回して親個体を選択します。SelectParent()
関数は、生成した乱数を使ってルーレットを回し、最初に選ばれたスロットの番号を返します。この選択プロセスは、If r < roulette(i)
の条件式によって実装されます。
この選択演算子では、適応度が高い個体が選ばれやすくなるため、選択される親個体の遺伝子は、次世代に適応度が高い個体が多く含まれることになります。
Crossover関数
' 交叉演算子
Private Sub Crossover(ByVal parent1 As Integer, ByVal parent2 As Integer, ByRef child1() As Integer, ByRef child2() As Integer)
Dim i As Integer
Dim r As Double
ReDim child1(GeneLength - 1)
ReDim child2(GeneLength - 1)
For i = 0 To GeneLength - 1
r = Rnd()
If r < CrossoverRate Then
child1(i) = genes(parent1, i)
child2(i) = genes(parent2, i)
Else
child1(i) = genes(parent2, i)
child2(i) = genes(parent1, i)
End If
Next i
End Sub
2つの親遺伝子から2つの子孫遺伝子を生成します。親遺伝子は、選択演算子で選ばれた適応度の高い個体として与えられます。子孫遺伝子は、交叉率に基づいて、2つの親遺伝子からランダムに組み合わせて生成されます。
具体的には、この関数は、GeneLength個の遺伝子を持つ2つの子孫遺伝子(child1, child2)を生成します。各遺伝子に対して、交叉率に基づいてランダムな数値が生成されます。この数値が交叉率未満の場合、child1は親1の遺伝子を継承し、child2は親2の遺伝子を継承します。数値が交叉率以上の場合、child1は親2の遺伝子を継承し、child2は親1の遺伝子を継承します。
このようにして生成された子孫遺伝子は、次の世代の個体集団に加えられます。これにより、世代ごとに適応度の高い個体が生き残り、集団全体の適応度が改善されることが期待されます。
Mutation関数
' 突然変異演算子
Private Sub Mutation(ByRef gene() As Integer)
Dim i As Integer
Dim r As Double
For i = 0 To GeneLength - 1
r = Rnd()
If r < MutationRate Then
gene(i) = 1 - gene(i)
End If
Next i
End Sub
まず、各遺伝子座について、乱数を生成し、それが突然変異率以下であるかどうかを確認します。もし突然変異率以下であれば、その遺伝子座の値を反転させます(0を1に、1を0に)。
この突然変異演算子を遺伝子配列全体に対して実行することで、個体の多様性を保持し、解の探索範囲を広げることができます。ただし、突然変異率が高すぎると、解探索の進展が遅くなったり、最適解を見つけられなくなることがあるため、適切な突然変異率を設定することが重要です。
Evolve関数
' 進化
Private Sub Evolve()
Dim i As Integer
Dim j As Integer
Dim parent1 As Integer
Dim parent2 As Integer
Dim child1() As Integer
Dim child2() As Integer
' 新しい個体集団を生成
For i = 0 To PopulationSize - 1 Step 2
' 親の選択
parent1 = SelectParent()
parent2 = SelectParent()
' 交叉
Crossover parent1, parent2, child1, child2
' 突然変異
Mutation child1
Mutation child2
' 新しい個体を個体集団に追加
For j = 0 To ginesize - 1
genes(i, j) = child1(j)
genes(i + 1, j) = child2(j)
Next j
Next i
End Sub
個体集団内の個々の遺伝子に対して、選択、交叉、突然変異という3つの操作を行い、新しい子孫を生成します。
コードの最初の行で、2つの親を選択するためにSelectParent()
関数が呼び出されます。この関数は、適応度に基づく確率的な選択を実行し、親のインデックスを返します。
次に、選択された2つの親の遺伝子を交叉するためにCrossover()
関数が呼び出されます。この関数は、2つの親の遺伝子をランダムに選択し、それらを交換することによって2つの子孫を生成します。
その後、Mutation()
関数が呼び出され、子孫の遺伝子にランダムに突然変異を適用します。これにより、新しい遺伝子バリエーションが生成されます。
最後に、新しい子孫を個体集団に追加します。この操作は、新しい個体が個体集団の一部になり、古い個体が淘汰されることを意味します。このプロセスは、次の世代の個体集団を生成するために反復的に実行されます。
Main関数
Sub Main()
Dim i As Integer
Dim j As Integer
Dim k As Integer
' 初期化
Initialize
' 進化
For i = 1 To Generation
CalculateFitness
Evolve
Next i
' 結果を表示
Dim bestGene(GeneLength) As Integer
For i = 0 To GeneLength - 1
bestGene(i) = genes(0, i)
Next i
Dim bestFitness As Double
bestFitness = fitness(0)
For i = 1 To PopulationSize - 1
If fitness(i) > bestFitness Then
For j = 0 To GeneLength - 1
bestGene(j) = genes(i, j)
Next j
bestFitness = fitness(i)
End If
Next i
Debug.Print "Best Gene: ";
For i = 0 To GeneLength - 1
Debug.Print bestGene(i);
Next
Debug.Print
Debug.Print "Best Fitness: " & bestFitness
End Sub
メイン関数では、以下の処理を行っています。
- 初期化:Initialize関数を呼び出して、個体集団をランダムに生成します。
- 進化:Generationで指定された世代数分の繰り返しを行います。各繰り返しの中で、CalculateFitness関数を呼び出して、現在の個体集団の各個体の適応度を計算します。次に、Evolve関数を呼び出して、新しい個体集団を生成します。
- 結果の表示:最終世代の個体集団から、最適な遺伝子を持つ個体を選択し、その遺伝子と適応度を表示します。
まとめ
実行の結果、遺伝子長が20程度だと大体Fitnessが0.8くらいになりました。近似解を得られる方法としてはそこそこ有益ではと思います。
![](https://www.taketaka.net/wp-content/uploads/2023/04/03a8582b8fd54d394e566c59b4dec2dc-1.png)