遺伝的アルゴリズムの代表的な選択方式の紹介およびそれらの性質について

# はじめに
遺伝的アルゴリズムにおける **選択(Selection)** とは、ある世代の**個体群から次世代の親となる個体を選び出す操作**を指します。
本稿では、遺伝的アルゴリズムに関心のある方に向けて、代表的な選択方式とその特徴について紹介します。

アルゴリズム全体の仕組みについては既知であることを前提とし、概略の説明にとどめます。

# 遺伝的アルゴリズムとは
**遺伝的アルゴリズム(genetic algorithm)** とはJohn Henry Hollandによって、生物の進化を参考に考案されたアルゴリズムです。処理は以下の通りに進みます。

1. あらかじめ決めた個体数($N$)の個体が含まれる**個体群**を用意する。個体群中の個体はそれぞれランダムに初期化された染色体(を模した値)を持つ
1. すべての個体に対して**評価**を行い、それぞれがどのくらい環境に適応しているかをスコアリングする
1. 終了条件を満たした個体がいなければ、個体群から次世代の親となる個体を2体**選択**する
1. 両親は遺伝子の一部分を交換する**交叉**を行う。交換後の染色体を次世代の個体の染色体とする
1. 次世代の個体は低い確率で**突然変異**を起こす。突然変異が起きた個体は、遺伝子の一部をランダムに変更する
1. 2~5を繰り返す

```mermaid
%%{init:{'theme':'forest'}}%%
flowchart LR
    A([初期個体群の生成]) --> B[評価]
    B --> C{終了条件を満たすか？}
    C -- Yes --> G([終了])
    C -- No --> D[選択]
    D --> E[交叉]
    E --> F[突然変異]
    F --> B
```

環境に適応している個体ほどスコアが高くなり、スコアが高い個体の遺伝子を次世代に引き継ぎます。そうすることで、世代を重ねるにつれて次第に最適解(スコアの極大点)に近づいていきます。
そのため、選択の際には **スコアが高い順で<font color="red">選ばれやすくなる</font>** ような方法が必要です。

<font color="red">「選ばれやすくなる」</font>と書いたのは、選択は遺伝子の多様性を確保する目的で、確率的に行われるためです。
多様性の少ない遺伝子プールを持つ個体群では、親世代と子世代の特徴がほとんど同じになってしまい、新たな探索を突然変異のみに頼ることになってしまいます。

# ルーレット選択
## ルーレット選択の概要
最初期に考案された選択方式で、**スコアに応じて**親に選ばれる確率を決定します。
親世代の個体数が$N$で個体$i$のスコアが$f_i$の時、個体$i$が選ばれる確率$P(i)$は下記の式で決まります。

$$
P(i) = \frac{f_i}{\sum_{j=1}^{N} f_j}
$$

例えば、個体A~Eのスコアが下記の円グラフの凡例の通りだった場合、次世代の親としてそれぞれの個体が選ばれる確率は円グラフのラベルのようになります。

```mermaid
pie
    "個体A：スコア = 8" : 8
    "個体B：スコア = 4" : 4
    "個体C：スコア = 2" : 2
    "個体D：スコア = 1" : 1
    "個体E：スコア = 1" : 1
```

## ルーレット選択の問題点

### 1. スコアに負の数が含まれるとうまくいかない
式からも分かるように、スコアに負の数が含まれるようなスコアリング方法だと$P(i)$を正しく計算できません。
簡単にこの問題を回避するには、選択の前に下記の処理を実装するのが一般的なようです。

1. 全個体のスコアの内から`最小のスコア`を探す
1. 全個体のスコアそれぞれに`最小のスコア+1`を足す

`最小のスコア`ではなく`最小のスコア+1`を足しているのは、スコアが最小の個体にも親に選ばれる可能性を残すことで、群全体の遺伝子プールの広さを確保するためです。

### 2. 遺伝子プールの多様性が残しにくい
親世代でスコアの格差が激しい場合（スコアの低い個体にも親になる可能性が残されているとはいえ）スコアの低い個体が親に選ばれる確率はかなり低くなり、子世代では遺伝子プールの多様性が失われやすいです。
このため、後述する他の方法と比べて、大域的な最適解へ到達せず局所的な最適解にトラップされやすいです。

多様性を確保するためには突然変異率を高めに設定するか、個体数を増やすことが有効です。
ただし、個体数を増やすと計算量が増えてしまうため、個人的には**突然変異率で調整するのがおすすめ**です。

:::note
下記の条件で実験を行い、適切な突然変異率の設定がルーレット選択を採用した遺伝的アルゴリズムの性能を向上させることを確かめてみます。
:::

|  | 実験の条件 |
|:-:|:-:|
| 各個体の初期条件 | A~Zのランダムな文字を1~30文字のランダムな長さ繋げた文字列 |
| 終了条件 | `ABCDEFGH`となる個体が誕生すること |
| 交叉方式 | 一様交叉 |
| 最大文字数 | 30文字 |
| 最小文字数 | 1文字 |

<details><summary><font color="red">実験に使ったコードはこちら（長いので折り畳んでいます）</font></summary>

```ga.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>

#define POP_SIZE 100
#define MAX_LEN 30
#define MIN_LEN 1
#define GENERATIONS 10000
#define TRIALS 100
#define CHARS "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

typedef struct {
    // null終端文字列として扱うためにMAX_LEN + 1
    char genes[MAX_LEN + 1];
    int length;
} Individual;

char random_char() {
    // rand関数は0～RAND_MAXまでの整数の乱数を生成
    return CHARS[rand() % ((int)sizeof(CHARS) - 1)];
}

/**
 * @brief 個体のランダムな初期化
 * @param  ind: 対象の個体
 * @return なし
 */
void random_individual(Individual* ind) {
    ind->length = MIN_LEN + rand() % (MAX_LEN - MIN_LEN + 1);

    for (int i = 0; i < ind->length; ++i) {
        ind->genes[i] = random_char();
    }
    ind->genes[ind->length] = '\0';
}

int score(const Individual* ind, const char* target) {
    int score = 0;
    int target_len = strlen(target);
    for (int i = 0; i < ind->length && i < target_len; ++i) {
        if (ind->genes[i] == target[i]) {
            score++;
        }
    }
    score *= 10;
    score -= abs(ind->length - target_len);
    return score;
}

/**
 * @brief 一様交叉
 */
void crossover(const Individual* p1, const Individual* p2, Individual* child) {
    int next_len = (rand() % 2) ? p1->length : p2->length;
    child->length = next_len;
    for (int i = 0; i < next_len; ++i) {
        if (i < p1->length && i < p2->length)
            child->genes[i] = (rand() % 2) ? p1->genes[i] : p2->genes[i];
        else if (i < p1->length)
            child->genes[i] = p1->genes[i];
        else if (i < p2->length)
            child->genes[i] = p2->genes[i];
    }
    child->genes[next_len] = '\0';
}

void mutate(Individual* ind, double mutation_rate) {
    // 文字の置換
    for (int i = 0; i < ind->length; ++i) {
        if ((double)rand() / RAND_MAX < mutation_rate) {
            ind->genes[i] = random_char();
        }
    }

    // 長さの突然変異（追加 or 削除）
    if ((double)rand() / RAND_MAX < mutation_rate) {
        if (rand() % 2 && ind->length < MAX_LEN) {
            // 追加
            ind->genes[ind->length++] = random_char();
            ind->genes[ind->length] = '\0';
        } else if (ind->length > MIN_LEN) {
            // 削除
            ind->length--;
            ind->genes[ind->length] = '\0';
        }
    }
}

/**
 * @brief ルーレット選択
 * @param population: 群れ
 * @param  scores: 個体ごとのスコア
 * @return 選ばれた個体
 */
const Individual* roulette_selection(Individual population[], int scores[]) {
    int total_score = 0;
    for (int i = 0; i < POP_SIZE; ++i) {
        total_score += scores[i];
    }

    if (total_score == 0) {
        return &population[rand() % POP_SIZE];
    }

    int pick = rand() % total_score;
    int current = 0;
    for (int i = 0; i < POP_SIZE; ++i) {
        current += scores[i];
        if (current > pick) {
            return &population[i];
        }
    }
    return &population[0];
}

double calc_mean(const int data[], size_t size) {
    double sum = 0.0;
    for (size_t i = 0; i < size; ++i) {
        sum += data[i];
    }
    return sum / size;
}

double calc_stddev(const int data[], size_t size) {
    if (size < 2) return 0.0;  // 標準偏差は2つ以上のデータが必要

    double mean = calc_mean(data, size);
    double sum_sq_diff = 0.0;
    for (size_t i = 0; i < size; ++i) {
        double diff = data[i] - mean;
        sum_sq_diff += diff * diff;
    }
    // 標準偏差
    return sqrt(sum_sq_diff / size);
}

/**
 * @brief 遺伝的アルゴリズム
 * @param target: ターゲット
 * @param mutation_rate: 突然変異率
 * 
 * @return 目標に到達するまでの世代数
 */
int ga(const char* target, double mutation_rate, double* mean_stddev) {
    Individual population[POP_SIZE];
    Individual new_population[POP_SIZE];
    int scores[POP_SIZE];
    double temperature = 25.0;

    // 初期化
    for (int i = 0; i < POP_SIZE; ++i) {
        random_individual(&population[i]);
    }

    for (int generation = 0; generation < GENERATIONS; ++generation) {
        int best_index = 0;
        int best_score = 0;

        // スコア評価
        for (int i = 0; i < POP_SIZE; ++i) {
            scores[i] = score(&population[i], target);
            if (scores[i] > best_score) {
                best_score = scores[i];
                best_index = i;
            }
        }

        // 最小のスコアを探す
        int min_score = scores[0];
        for (int i = 1; i < POP_SIZE; ++i) {
            if (scores[i] < min_score) {
                min_score = scores[i];
            }
        }

        // すべてのスコアをシフトして非負に（+1 はゼロ回避のため）
        for (int i = 0; i < POP_SIZE; ++i) {
            scores[i] = scores[i] - min_score + 1;
        }

        mean_stddev[generation] += calc_stddev(scores, POP_SIZE);

        if (strcmp(population[best_index].genes, target) == 0) {
            return generation;
        }

        // 次世代の作成
        for (int i = 0; i < POP_SIZE; ++i) {
            const Individual* parent1;
            const Individual* parent2;

            parent1 = roulette_selection(population, scores);
            parent2 = roulette_selection(population, scores);

            crossover(parent1, parent2, &new_population[i]);
            mutate(&new_population[i], mutation_rate);
        }

        // 世代交代
        memcpy(population, new_population, sizeof(population));
    }

    return 0;
}

int main() {
    srand((unsigned int)time(NULL));

    double mutation_rates[] = {
        0.001,
        0.05,
        0.1,
        0.15
    };

    int mutation_rates_count = sizeof(mutation_rates) / sizeof(mutation_rates[0]);

    double mean_stddev[mutation_rates_count][GENERATIONS];
    for (int i = 0; i < mutation_rates_count; ++i) {
        for (int k = 0; k < GENERATIONS; ++k) {
            mean_stddev[i][k] = 0.0;
        }
    }

    for (int mutation_index = 0; mutation_index < mutation_rates_count; ++mutation_index) {
        double mean_generation = 0.0;
        for (int try = 0; try < TRIALS; ++try) {
            int generation = ga("ABCDEFGH", mutation_rates[mutation_index], mean_stddev[mutation_index]);
            if (generation == 0) {
                printf("fail");
            } else {
                mean_generation += generation;
            }
        }
        printf("avg = %.2f\n", mean_generation / TRIALS);
    }

    printf("====================================\n");

    for (int i = 0; i < mutation_rates_count; ++i) {
        for (int k = 0; k < GENERATIONS; ++k) {
            if (mean_stddev[i][k + 1] != 0) {
                printf("%.2f, ", mean_stddev[i][k] / TRIALS);
            } else {
                printf("%.2f", mean_stddev[i][k] / TRIALS);
                break;
            }
        }
        printf("\n");
    }

    return 0;
}
```

</details>

実行速度優先で`C言語`での実装です。

突然変異率を`0.01, 0.05, 0.1, 0.15`と変化させ、それぞれの変異率で100回試行しました。
世代ごとに、スコアの標準偏差の平均をそれぞれの突然変異率でプロットしてみると、突然変異率が大きいほどスコアの標準偏差も大きい（多様性が大きい）事が分かります。

![スクリーンショット 2025-06-10 22.16.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2885419/9d2bce22-359d-47e7-bdb5-b587367af085.png)


突然変異率と、終了条件を満たすまでに要した平均世代数の関係は下記の表の通りになりました。

| 突然変異率 | 終了条件を満たすまでに要した平均世代数 |
|:-:|:-:|
| 0.001 | 315.80 |
| 0.05 | 29.16 |
| 0.1 | 35.58 |
| 0.15 | 120.11 |

突然変異率が低すぎる`0.001`の場合、丁度良い突然変異率`0.05`の場合と比べて収束までに約10倍の世代数を要しています。これは、個体群の遺伝子プールの多様性が低いため、なかなか環境に適した個体が生まれないためだと考えています。

また、突然変異率が高すぎる場合もやはり平均世代数が増える結果になりました。
これは、親世代で良い性質を持った個体が生まれても、高すぎる突然変異率によってその性質がうまく子世代に引き継がれなかったためだと考えます。

# ランキング選択
ルーレット選択の二つの欠点

- スコアに負の数が含まれるとうまくいかない
- 遺伝子プールの多様性が残しにくい

を克服した手法が**ランキング選択**です。

ランキング選択では、親世代の全個体$N$個体をスコアに応じて順位づけします。
個体$i$の順位が$rank_i$の時、個体$i$が選ばれる確率$P(i)$は下記の式で決まります。

$$
P(i) = \frac{N+1-rank_i}{\sum_{j=1}^{N} (N+1-rank_j)} = \frac{N+1-rank_i}{\sum_{j=1}^{N} rank_j}
$$

**スコアではなく順位により比較**することで

- 負の数になることがあり得るスコアリング手法
- 上位と下位で差が大きくなりやすいスコアリング手法

を採用していても悪影響を受けにくくなります。

:::note
**分子が$N-rank_i$ ではなく $N+1-rank_i$ になっている理由**

最下位の個体$i_{tailend}$が親に選ばれる確率$P(i_{tailend})$が$0$にならないようににするためです。
例えば$N=100$の時、最下位の個体が選ばれる確率も下記のように$0$にはなりません。

$$
P(i_{tailend}) = \frac{100+1-100}{\sum_{j=1}^{N} (100+1-rank_j)} = \frac{1}{\sum_{j=1}^{N} rank_j} = \frac{1}{5050}
$$
:::

実装は、先ほど登場したコードの`roulette_selection`関数と置き換えてお使いください。

```ga.c
/**
 * @brief ランキング選択
 * @param population: 群れ
 * @param  fitnesses: 個体ごとの適応度
 * @return 選ばれた個体
 */
const Individual* ranking_selection(Individual population[], int fitnesses[]) {
    // 個体のインデックスを保持する配列（0〜POP_SIZE-1）
    int indices[POP_SIZE];
    for (int i = 0; i < POP_SIZE; ++i) {
        indices[i] = i;
    }

    // 適応度に従って昇順にソート
    for (int i = 0; i < POP_SIZE - 1; ++i) {
        for (int j = 0; j < POP_SIZE - 1 - i; ++j) {
            if (fitnesses[indices[j]] > fitnesses[indices[j + 1]]) {
                int temp = indices[j];
                indices[j] = indices[j + 1];
                indices[j + 1] = temp;
            }
        }
    }

    // ランクに比例した重みをつける（最下位:1, 最上位:POP_SIZE）
    int rank_weights[POP_SIZE];
    int total_rank = 0;
    for (int i = 0; i < POP_SIZE; ++i) {
        rank_weights[i] = i + 1;
        total_rank += rank_weights[i];
    }

    int pick = rand() % total_rank;
    int current = 0;
    for (int i = 0; i < POP_SIZE; ++i) {
        current += rank_weights[i];
        if (current > pick) {
            return &population[indices[i]];
        }
    }

    // 念のため最後の個体を返す（到達しないはず）
    return &population[indices[POP_SIZE - 1]];
}

```

ルーレット選択で行った実験と同じ条件でランキング選択を100回試行しました。終了条件を満たすまでの平均世代数で比較します。
どの突然変異率でもルーレット選択より良い結果が得られました。

| 突然変異率 | <font color="red">ランキング選択</font> | ルーレット選択 |
|:-:|:-:|:-:|
| 0.001 | 268.74 | 315.80 |
| 0.05 | 19.87 | 29.16 |
| 0.1 | 22.17 | 35.58 |
| 0.15 | 36.56 | 120.11 |

ランキング選択の性能向上が、遺伝子プールの多様性が保たれていることに由来することを確認します。突然変異率`0.05`の、場合のルーレット選択とランキング選択の世代数とスコアの標準偏差の関係を、データの縮尺を変えて始端と終端を揃えた上でプロットします。

![スクリーンショット 2025-06-11 8.46.22.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2885419/cb8d8357-41d0-4e88-ae53-c2f51dd3628a.png)

ランキング選択の方が標準偏差の変化が緩やかになっていることが分かります。

# トーナメント選択

個体群から抜き出された**ランダムな数個体の中で一番高い個体を親とする選択方法**です。
最初に群れから抜き出す個体数(トーナメントサイズ)が小さいほどランダムな選択に近くなり、大きいほど厳密なスコア順位順の親選択に近くなります。

```ga.c
/**
 * @brief トーナメント選択
 * @param population: 群れ（個体配列）
 * @param fitnesses: 個体ごとの適応度
 * @param tournament_size
 * @return 選ばれた個体へのポインタ
 */
const Individual* tournament_selection(Individual population[], int fitnesses[], int tournament_size) {
    int best_index = rand() % POP_SIZE;  // 初期化：ランダムに1個選ぶ
    int best_fitness = fitnesses[best_index];

    for (int i = 1; i < tournament_size; ++i) {
        int index = rand() % POP_SIZE;
        if (fitnesses[index] > best_fitness) {
            best_index = index;
            best_fitness = fitnesses[index];
        }
    }

    return &population[best_index];
}
```

トーナメントサイズは、これまで紹介したルーレット選択やランキング選択には無かったハイパーパラメータになります。トーナメントサイズによる性能への影響を確認します。
あまり顕著な差が出ないため、3種類の課題で、それぞれ1000回試行しています。

![スクリーンショット 2025-06-11 21.46.43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2885419/89e764c0-cad0-4f03-baca-4924b1f1e3c5.png)

最小のトーナメントサイズである`2`の時は明らかに性能が悪くなっています。
トーナメントサイズ`4~98`までは、意外なことにほとんど性能差がありません。
強いていうならトーナメントサイズ`4~10`あたりで最も性能が良さそうです。性能が変わらないのであれば計算量が少ないトーナメントサイズ`4~10`あたりを設定するのが良いでしょう。

`トーナメントサイズ=6`に設定してランキング選択やルーレット選択と同じ条件で実験をしたところ、いずれの突然変異率でもこれまでで最も良い結果が得られました。

| 突然変異率 | <font color="red">トーナメント選択</font> | ランキング選択 | ルーレット選択 |
|:-:|:-:|:-:|:-:|
| 0.001 | 239.80 | 268.74 | 315.80 |
| 0.05 | 10.81 | 19.87 | 29.16 |
| 0.1 | 9.52 | 22.17 | 35.58 |
| 0.15 | 9.63 | 36.56 | 120.11 |

# ボルツマン選択
ボルツマン選択では、**スコアを指数関数でスケーリングした値により選ばれやすさを決定**します。
個体$i$が選ばれる確率$P(i)$は、ハイパーパラメータである温度$T$を使って下記の式で表されます。

$$
P(i) = \frac{e^{f(i)/T}}{\sum_{j=1}^{N} e^{f(j)/T}}
$$

ここで、$exp(\frac{x}{T})$の性質を確認しておきます。
下記のグラフから分かるように、$T$が大きい時は$x$が変化しても$y$はあまり変化せず、$T$が小さい時は$y$が大きく変化します。

![スクリーンショット 2025-06-11 22.36.40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2885419/9ec37c15-7f9f-4de4-893c-1010f7ebc493.png)

ボルツマン選択では、世代が増えるごとに$T$を少しづつ減少させます。これにより、始めのうちはよりランダムな選択になり、終わりに近づくとスコア通りの選択に近づくようにします。
アルゴリズムの初期で局所最適解にトラップされることを防ぎつつ、後半はスコア通りに選択しやすくなることで正確に収束することを目指す手法です。

温度$T$を減らす方法には色々な手法がありますが、今回は世代数$g$、初期温度$T0$と冷却率$cr$を使って$T=T_0(cr)^{g}$となるように冷やしました。
実装はこちら。

```ga.c
/**
 * @brief ボルツマン選択（Softmax選択）
 * @param population: 群れ（個体配列）
 * @param fitnesses: 個体ごとの適応度
 * @param temperature: 温度パラメータ（大きいほどランダム性↑）
 * @return 選ばれた個体へのポインタ
 */
const Individual* boltzmann_selection(Individual population[], int fitnesses[], double temperature) {
    double probs[POP_SIZE];
    double sum = 0.0;

    for (int i = 0; i < POP_SIZE; ++i) {
        probs[i] = exp((double)fitnesses[i] / temperature);
        sum += probs[i];
    }

    for (int i = 0; i < POP_SIZE; ++i) {
        probs[i] /= sum;
    }

    double r = (double)rand() / RAND_MAX;
    double accum = 0.0;
    for (int i = 0; i < POP_SIZE; ++i) {
        accum += probs[i];
        if (r < accum) {
            return &population[i];
        }
    }

    return &population[POP_SIZE - 1]; // フォールバック（合計誤差対策）
}
```

これまでと同じ課題で、突然変異率=0.05は固定し初期温度$T0$と冷却率$cr$を変化させた結果の収束までの平均世代数をヒートマップにしたものが下記の図です。

![スクリーンショット 2025-06-12 22.00.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2885419/8f58cca1-0b0d-4f26-a702-1920223da821.png)

ボルツマン選択はトーナメント選択と違いハイパーパラメータの影響を大きく受けるようです。
今回の課題だと、$T_0=5.0$、$cr=0.94$が適していることがわかったのでこの設定で他の手法と性能を比較してみます。

| 突然変異率 | <font color="red">ボルツマン選択</font> | トーナメント選択 |  ランキング選択 | ルーレット選択 |
|:-:|:-:|:-:|:-:|:-:|
| 0.001 | - | 239.80 | 268.74 | 315.80 |
| 0.05 | 14.65 | 10.81 | 19.87 | 29.16 |
| 0.1 | 11.24 | 9.52 | 22.17 | 35.58 |
| 0.15 | 11.16 | 9.63 | 36.56 | 120.11 |

突然変異率`0.001`の場合はうまく終了条件を満たすまでスコアを上げることができませんでした。
しかし、`0.05~0.15`では割と良い性能が得られました。ハイパーパラメータが二つありこれまで紹介した手法の中では一番調整が難しいです。

# おわりに
今回の課題ではトーナメント選択が最も高性能だという結果になりました。実装も4つの手法の中で一番シンプルなので、初めて遺伝的アルゴリズムを実装される方はまずはトーナメント選択を使用してみるのがおすすめです。

取り組む課題によって選択方式やそのハイパーパラメータ、また今回紹介しなかった

- 交叉方法
- スコアリング関数
- 群れのサイズ

などをアドホックに調整するのも楽しそうです。
遺伝的アルゴリズムを実装して遊びたい方の一助になれば幸いです。