【Excel VBAで遺伝的アルゴリズムを実装】

遺伝的アルゴリズムとは

遺伝的アルゴリズムは、進化的計算の一種であり、生物の進化の仕組みを模倣したアルゴリズムです。生物が進化する過程で、自然選択や突然変異などの要素が働き、適応度の高い個体が生き残り、次世代に遺伝子を伝えます。遺伝的アルゴリズムも同様に、個体集団内で適応度の高い個体が選択され、交叉や突然変異によって新しい個体を生成し、次世代に遺伝子を伝えることで最適解を求めます。

遺伝的アルゴリズムの実装

遺伝的アルゴリズムは、次の手順で実装することができます。

1. 遺伝子表現の定義：最適化対象の問題によって、遺伝子表現を定義します。たとえば、整数の配列、実数の配列、ビットの配列など、適切な表現を選択する必要があります。
2. 初期個体群の生成：ランダムに初期値を生成することにより、個体群を初期化します。
3. 適応度関数の定義：目的関数を適応度関数として定義します。各個体に対して、適応度を計算し、その値が高いほど適応度が高いとされます。
4. 選択：適応度が高い個体を次世代に残すために、選択を行います。選択には、ルーレット選択、トーナメント選択、ランキング選択などの方法があります。
5. 交叉：選択された個体を用いて、交叉を行います。交叉は、2つの親個体を組み合わせ、新しい子孫個体を生成することで行われます。一般的な交叉方法には、一点交叉、二点交叉、一様交叉などがあります。
6. 突然変異：個体の多様性を維持するために、突然変異を行います。突然変異は、ランダムな箇所で遺伝子を変化させることで、新たな個体を生成する方法です。
7. 次世代の生成：選択、交叉、突然変異を行った結果から、次世代の個体群を生成します。
8. 終了判定：一定の世代数や、目的達成のための十分な進捗がある場合は、アルゴリズムを終了します。そうでなければ、3-7の手順を繰り返し行います。
9. 結果の出力：最終的に求められた最適解、あるいは近似解を出力します。

このように、遺伝的アルゴリズムは、初期化、適応度評価、選択、交叉、突然変異、世代交代のサイクルを繰り返すことで、最適化問題を解決します。

遺伝的アルゴリズムの実装例

さて、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くらいになりました。近似解を得られる方法としてはそこそこ有益ではと思います。