アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

遺伝的アルゴリズムとは

遺伝的アルゴリズム（Genetic Algorithm:GA）とは、近似解を探索するためのアルゴリズムの一つです。データを個体(遺伝子)のように見立て、淘汰や交叉、突然変異など、生命の進化を模した処理を行いながら、適応度の高い(最適解に近い値)を探し出します。

用語

まずは簡単に用語を整理しておきます。

• 個体

  遺伝子を持つデータ。

• 個体群

  それぞれに固有の遺伝子(データ)を持つ個体の集団。世代を重ねるごとに、優秀な個体が残るようになります。

• 遺伝子

  個体の性質を表す情報のことです。ビット列で表すことがあります。

• 適応度

  各個体の評価値です。個体がどの程度優秀か(環境に適応しているか)を示す指標です。適応度関数によって求められます。

• 選択(淘汰)

  現世代個体から適応度の高い個体が生き残り、次世代にその遺伝子を残す過程の処理です。適応度の低い個体は淘汰されていくので、次世代の個体群は現世代より優秀な個体が残るようになります。

• 交叉

  親となる個体から、子孫を生成する処理を指します。遺伝的操作の一つで非常に重要な処理です。

• 突然変異

  個体に対しての遺伝的操作で、生物に見られる遺伝子の突然変異をモデル化したものです。個体の遺伝子の一部が一定確率で変化します。これにより局所的な最適解に陥ることが防がれますが、突然変異の確率が高すぎると、収束しにくくなります。

アルゴリズム

まずはアルゴリズムの手順を示します。

1. 現世代個体群と次世代個体群を表すリスト(N個分)を用意します。
2. ランダムな初期個体群を生成し、現世代とします。
3. ある確率で次のいずれかの処理を行い、次世代個体群に追加します。
   • 親となる個体を2つ選び、交叉して子となる個体を作成します。
   • 現世代から1個体を選択し、そのまま複製します。
   • 1個体選択し、遺伝子の一部を突然変異させます。
4. 3. の処理を繰り返し、次世代個体N個を作成し、現世代に移行します。
5. 最大世代数になるまで繰り返し、最終世代で最も適応度の高い個体を「解」とします。

難しいイメージを持つかもしれませんが、GAは比較的実装が容易なのですぐに試すことができます。ただし、遺伝的操作(選択・交叉・突然変異)の処理にはいくつかの種類があり、どのような種類を選択するかによってうまくいったりいかなかったりします。

選択

現世代の個体群の中から優秀な個体を選択し、次世代にその遺伝子を残す必要がありますが、問題はどのように個体を選択するかという点にあります。単純に最も適応度の高い個体だけを選択すると、解の多様性が失われて局所解しか得られなくなってしまいます。

以下の適用度を持つ個体群から2個体選択するとします。その場合の代表的な選択方法とその例を示します。

個体名	適応度
個体A	100
個体B	50
個体C	25
個体D	25

エリート選択

これは単純に最も適応度の高い個体を確実に選択する方法です。選ばれた個体を次世代に残すことで確実に現世代よりも適応度が同等以上の個体を維持てきます。ただしエリートの遺伝子が広がりすぎることで解の多様性が失われる可能性もあります。

例：

常に適応度の高い個体、「個体A」「個体B」が選択されます。

ルーレット選択

個体Aの選択される確率を、全個体の適応度の総和を分母、個体Aの適応度を分子として求めた値とします。個体間の適応度の差が選択される確率に反映される方法です。したがって適応度の差が極端に大きいと、選択確率にも大きく影響します。

例：

各個体を以下の確率で選択します。

個体名	適応度	選択確率
個体A	100	50%
個体B	50	25%
個体C	25	12.5%
個体D	25	12.5%
個体全体	200	100%

ランキング選択

各個体に対し適応度での順位付けを行います。順位ごとにあらかじめ決められた確率を決めておき、その確率で選択を行います。例えば、「1位 50%, 2位 25%, 3位 15%, 4位 10% ...」といった具合です。この方法は適応度の差の大きさが確立影響しない点でルーレット選択と異なります。どれだけ差があろうと、順位ごとに確率は決められた値を用います。逆にほとんど差のない適応度であったとしても、明順位の差により選択確率への影響が大きくります。

例：

各個体を以下の確率で選択します。順位ごとの選択確立はあらかじめ「1位 50%, 2位 25%, 3位 15%, 4位 10%」と決めておきます。

個体名	適応度	選択確率
個体A	100	50%
個体B	50	25%
個体C	25	15%
個体D	25	10%
個体全体	200	100%

トーナメント選択

あらかじめトーナメントサイズを決めておき、個体群からランダムにサイズ分取り出し、その中から最も適応度の高い個体を選択する方法です。トーナメントサイズにより淘汰の具合を調整できます。

例：

トーナメントサイズを3として、個体B,C,D が選択されたとすると、適応度高い2個体(個体B, 個体C)が選択されます。

交叉

親として選択された2個体の遺伝子を掛け合わせ、子となる個体を生成する処理です。

一点交叉

親となる個体のデータの交叉点(分割点)をランダムに決定します。交叉点で遺伝子データを分割し、後半部分を入れ替えることで遺伝子を子に引き継ぎます。具体的には以下のようになります。

親1

0

0

0

0

0

親2

1

1

1

1

1

↓

子1

0

0

0

1

1

子2

1

1

1

0

0

一般に効率な方法ではないとされ、今ではあまり利用されません。

二点交叉

親となる個体のデータの交叉点(分割点)をランダムに２点決定します。交叉点で遺伝子データを３分割し、真ん中部分を入れ替えることで遺伝子を子に引き継ぎます。具体的には以下のようになります。

親1

0

0

0

0

0

親2

1

1

1

1

1

↓

子1

0

0

1

1

0

子2

1

1

0

0

1

多点交叉

一点、二点とあれば、当然三点あるいはN点でも交叉を行えます。しかし二点交叉や一様交叉よりも良い値が出ることはないとされ、利用されることはありません。

一様交叉

親となる個体の各要素ごと独立に 1/2 の確率で交換します。

親1

0

0

0

0

0

親2

1

1

1

1

1

↓

子1

0

1

0

0

1

子2

1

0

1

1

0

突然変異

生物の突然変異をモデル化したものです。突然変異は個体の遺伝子データの一部を変化させる操作を行います。突然変異では 0.1%～1.0% 程度の確率で発生させるようにします。突然変異の確率が高すぎるとランダム探索に近くなる、つまり解が収束しにくくなってしまいます。

一般的に突然変異の遺伝子操作は、ランダムな遺伝子を対立する遺伝子に置き換えます。ビット型であれば反転させます。

変異前

0

0

0

0

0

↓

変異後

0

1

0

0

0

OneMax問題の実装

遺伝的アルゴリズムの最初の実装としては、OneMax問題を扱うのがよいでしょう。何も難しい問題ではありません。

問題はこうです。ある"0"と"1"で表された数列(ビット列)について、"1" の個数が最大となるビット列を求めるという問題です。言うまでもなく、最大となるなるのはすべて"1"のときです。

個体を8桁のビット列とすると、個体の遺伝子データを以下のようなビット列で定義します。

[0, 1, 1, 0, 0, 0, 1, 0]
  ↓
[1, 1, 1, 1, 1, 1, 1, 1] // こういうデータを求めたい

実装にはまずルール(設定)決めが必要です。そこで「遺伝子長=10」「エリート選択」「一点交差」「個体群数=4」として処理を処理を行うこととします。上位2個体をそのまま次世代に移行し、さらにその個体同士を交差した2個体の子も次世代個体とします。次世代個体には5%の確率で突然変異でランダム位置のビットを反転します。

設定の如何によって結果に差が出ます。とりあえずは裁量で決めて動かしてみるのがよいでしょう。

C#

using System;
using System.Collections.Generic;
using System.Linq;

class GA
{
    private const int GeneLength = 10;      // 遺伝子長
    private int Age;                        // 現在の世代
    private const double MutateRate = 0.05; // 突然変異の確率5%
    private Random Rnd = new Random();

    // 実行
    public void Run()
    {
        // 初期設定(適当な4個体を用意)
        Age = 1;
        var currentPopulation = CreateInitialData();

        while (true)
        {
            DebugState(Age, currentPopulation);

            // 選択
            var selected = Select(currentPopulation).ToList();

            // 交差
            var children = CrossOver(selected[0], selected[1]).ToList();

            // 突然変異
            var nextPopulation = selected.Concat(children).Select(individual =>
            {
                if (Rnd.NextDouble() < MutateRate)
                {
                    return Mutate(individual);
                }
                return individual;
            });

            // 次世代に進む
            currentPopulation = nextPopulation.ToList();

            // 終了
            if (IsConverged(currentPopulation)) break;
            Age++;
        }
        DebugState(Age, currentPopulation);
    }

    // 初期データ
    private List<bool[]> CreateInitialData()
    {
        return Enumerable.Range(0, 4).Select(_ =>
        {
            var array = new bool[GeneLength];
            for (int i = 0; i < GeneLength; i++)
            {
                array[i] = Rnd.Next(0, 2) == 1;
            }
            return array;
        }).ToList();
    }

    // 選択・淘汰
    private IEnumerable<bool[]> Select(List<bool[]> currentPopulation)
    {
        // 1の数が多い順に並べる
        var nextPopulation = currentPopulation.OrderByDescending(d => d.Count(b => b)).ToList();

        // 成績上位2個体を選択
        yield return nextPopulation[0];
        yield return nextPopulation[1];
    }

    // 交差
    private IEnumerable<bool[]> CrossOver(bool[] GeneA, bool[] GeneB)
    {
        // 個体A, Bをランダムな点で分割し A=A1B2, B=B1A2 とする
        // 分割点
        var point = Rnd.Next(1, GeneLength - 1);

        // 親を複製
        var splitedA1 = GeneA.Take(point);
        var splitedA2 = GeneA.Skip(point).Take(GeneLength - point);
        var splitedB1 = GeneB.Take(point);
        var splitedB2 = GeneB.Skip(point).Take(GeneLength - point);

        // 結合して返す
        yield return splitedA1.Concat(splitedB2).ToArray();
        yield return splitedB1.Concat(splitedA2).ToArray();
    }

    // 突然変異
    private bool[] Mutate(bool[] data)
    {
        // ランダム位置で1ビットのみ反転
        var point = Rnd.Next(0, GeneLength);
        if (point >= 0) data[point] = !data[point];
        return data;
    }

    // 収束評価(すべて1になっていれば終了)
    private bool IsConverged(List<bool[]> Population)
    {
        var top = Population.OrderByDescending(d => d.Count(b => b)).First();
        return top.Count(b => b) == top.Count();
    }

    // 状態確認用
    public void DebugState(int age, List<bool[]> Population)
    {
        Console.WriteLine($"世代数: {age}");
        foreach (var indivisual in Population.OrderByDescending(d => d.Count(b => b)))
        {
            foreach (var b in indivisual) Console.Write(b ? "1" : "0");
            Console.WriteLine($"");
        }
    }
}