アルゴリズム

C言語で実装する遺伝的アルゴリズムについて解説：選択・交叉・突然変異を用いた最適化手法

2025-01-17更新日: 2025-01-17

本記事はC言語で遺伝的アルゴリズムを実装する方法を解説します。

選択、交叉、突然変異の各工程を用いて、最適化問題に取り組むプログラムの作り方を説明します。

実例を通してアルゴリズムの流れやコードの工夫を紹介し、 $, P (mutation)$ などの数式を用いてポイントを明確に解説します。

目次から探す

遺伝的アルゴリズムの基本
- 遺伝的アルゴリズムの概要
- 選択・交叉・突然変異の役割
C言語での実装環境と設計方針
- 開発環境と必要なライブラリ
- データ構造とパラメータ設定
選択 (Selection) の実装
- 選択アルゴリズムの考え方
- 実装例と注意点
交叉 (Crossover) の実装
- 交叉方式の種類と特徴
- C言語での実装例
突然変異 (Mutation) の実装
- 突然変異の基本原理
- 実装方法とサンプルコード
統合実装例と動作検証
- アルゴリズム全体の流れ
- 主要関数の解説
まとめ

遺伝的アルゴリズムの基本

遺伝的アルゴリズムの概要

遺伝的アルゴリズムは、生物の進化の仕組みを参考に、候補解の集団から最適解を探索する手法です。

個体と呼ばれる複数の候補解が、交叉や突然変異などの操作を受けながら進化し、問題に対する解を改善していきます。

ランダムな初期集団からスタートするため、広い探索範囲に対応しやすいという特長があります。

選択・交叉・突然変異の役割

遺伝的アルゴリズムにおいて、各操作は以下のような役割を果たします。

選択：評価値の高い個体を次世代に受け継ぐため、個体群から優れた候補解を選び出します。
交叉：複数の親個体から情報を組み合わせることで、新たな遺伝子構成を持つ子個体を作り出します。
突然変異：個体の遺伝子にランダムな変化を加え、探索の多様性を保ち、局所解に陥るリスクを低減します。

C言語での実装環境と設計方針

開発環境と必要なライブラリ

C言語で実装する場合、標準ライブラリであるstdio.h、stdlib.h、time.hを利用します。

これらのライブラリは、入出力処理、乱数生成、メモリ管理などの基本機能を提供します。

gccなどの一般的なコンパイラや、任意のテキストエディタが整った環境であれば実装が可能です。

データ構造とパラメータ設定

遺伝的アルゴリズムでは、各個体の遺伝子情報や評価値を保持するために構造体を使用します。

例えば、以下のように個体を表す構造体を定義し、個体数、遺伝子長、交叉率、突然変異率などのパラメータを設定します。

個体の構造体例

・gene：遺伝情報を格納する配列

・fitness：適応度を表す値

各パラメータは、扱う問題に合わせて調整する必要があります。

特に、交叉率や突然変異率は、解の多様性と収束のバランスを保つ上で重要な役割を果たします。

選択 (Selection) の実装

選択アルゴリズムの考え方

選択では、個体群から評価値の高い個体を残すための仕組みを実装します。

代表例としてトーナメント選択があります。

トーナメント選択では、ランダムに選んだ複数の個体の中から、最も評価値が高い個体を選出します。

これにより、全体の中から優れた解を効率的に絞り込むことができます。

実装例と注意点

以下は、トーナメント選択による個体選択のサンプルコードです。

個体の初期化や評価関数も簡略化して実装していますので、実装時の参考にしてください。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define POPULATION_SIZE 10
#define TOURNAMENT_SIZE 3
// 個体の構造体
typedef struct {
    int gene;       // 遺伝子(簡略化)
    double fitness; // 評価値
} Individual;
// 評価関数：ここでは単純にgeneの値をfitnessとして返す
double evaluate(Individual ind) {
    return (double)ind.gene;
}
// トーナメント選択を行う関数
Individual tournament_selection(Individual population[]) {
    int best = rand() % POPULATION_SIZE;
    for (int i = 1; i < TOURNAMENT_SIZE; i++) {
        int idx = rand() % POPULATION_SIZE;
        if (population[idx].fitness > population[best].fitness) {
            best = idx;
        }
    }
    return population[best];
}
int main(void) {
    srand((unsigned int)time(NULL));
    Individual population[POPULATION_SIZE];
    // 初期化処理
    for (int i = 0; i < POPULATION_SIZE; i++) {
        population[i].gene = rand() % 100;  // geneを0～99に設定
        population[i].fitness = evaluate(population[i]);
        printf("Individual %d: gene = %d, fitness = %.2f\n", i, population[i].gene, population[i].fitness);
    }
    // トーナメント選択のデモ
    Individual selected = tournament_selection(population);
    printf("Selected individual: gene = %d, fitness = %.2f\n", selected.gene, selected.fitness);
    return 0;
}

Individual 0: gene = 42, fitness = 42.00
Individual 1: gene = 17, fitness = 17.00
Individual 2: gene = 85, fitness = 85.00
Individual 3: gene = 63, fitness = 63.00
Individual 4: gene = 29, fitness = 29.00
Individual 5: gene = 77, fitness = 77.00
Individual 6: gene = 55, fitness = 55.00
Individual 7: gene = 94, fitness = 94.00
Individual 8: gene = 38, fitness = 38.00
Individual 9: gene = 10, fitness = 10.00
Selected individual: gene = 94, fitness = 94.00

交叉 (Crossover) の実装

交叉方式の種類と特徴

交叉は、2つの親個体から情報を引き継ぐことで新たな個体を生成する操作です。

代表的な手法として、1点交叉と2点交叉があります。

1点交叉では、ある交叉点を境に親の遺伝子を切り替え、2点交叉では2つの点で切り替えるため、より多様な組み合わせが生まれます。

問題や実装の複雑さに合わせて、適切な方法を選択することが大切です。

C言語での実装例

以下は、1点交叉のサンプルコードです。

2つの親個体の遺伝子配列をもとに、交叉点で分割して子個体を生成します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define GENE_LENGTH 10
// 2つの親の遺伝子情報から1点交叉を行い、子を生成する関数
void one_point_crossover(int parent1[], int parent2[], int child[]) {
    int crossover_point = rand() % GENE_LENGTH;
    for (int i = 0; i < GENE_LENGTH; i++) {
        if (i < crossover_point) {
            child[i] = parent1[i];
        } else {
            child[i] = parent2[i];
        }
    }
}
int main(void) {
    srand((unsigned int)time(NULL));
    int parent1[GENE_LENGTH] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1};
    int parent2[GENE_LENGTH] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
    int child[GENE_LENGTH];
    one_point_crossover(parent1, parent2, child);
    printf("Parent1: ");
    for (int i = 0; i < GENE_LENGTH; i++) {
        printf("%d ", parent1[i]);
    }
    printf("\nParent2: ");
    for (int i = 0; i < GENE_LENGTH; i++) {
        printf("%d ", parent2[i]);
    }
    printf("\nChild:   ");
    for (int i = 0; i < GENE_LENGTH; i++) {
        printf("%d ", child[i]);
    }
    printf("\n");
    return 0;
}

Parent1: 0 1 0 1 0 1 0 1 0 1
Parent2: 1 0 1 0 1 0 1 0 1 0
Child:   0 1 0 1 1 0 1 0 1 0

突然変異 (Mutation) の実装

突然変異の基本原理

突然変異は、各個体の遺伝子に対してランダムな変化を加える操作です。

突然変異により、これまで探索されなかった解の領域に触れることが可能になり、局所解から抜け出すための効果が期待できます。

一般的には、遺伝子ごとに一定の確率 $p_{m}$ で変化を起こす設定となります。

実装方法とサンプルコード

以下は、ビット表現の場合の突然変異を実装したサンプルコードです。

各ビットが一定の確率で反転するように実装しています。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define GENE_LENGTH 10
#define MUTATION_RATE 0.1  // 突然変異率 \( p_m \)
void mutation(int gene[]) {
    for (int i = 0; i < GENE_LENGTH; i++) {
        double randVal = (double)rand() / RAND_MAX;
        if (randVal < MUTATION_RATE) {
            // ビット反転
            gene[i] = (gene[i] == 0) ? 1 : 0;
        }
    }
}
int main(void) {
    srand((unsigned int)time(NULL));
    int individual[GENE_LENGTH] = {0, 0, 1, 1, 0, 1, 0, 1, 1, 0};
    printf("Before mutation: ");
    for (int i = 0; i < GENE_LENGTH; i++) {
        printf("%d ", individual[i]);
    }
    printf("\n");
    mutation(individual);
    printf("After mutation:  ");
    for (int i = 0; i < GENE_LENGTH; i++) {
        printf("%d ", individual[i]);
    }
    printf("\n");
    return 0;
}

Before mutation: 0 0 1 1 0 1 0 1 1 0
After mutation:  0 1 1 1 0 1 0 1 0 0

統合実装例と動作検証

アルゴリズム全体の流れ

統合実装例では、初期化、評価、選択、交叉、突然変異の各ステップを順に実行して、次世代の個体群を生成します。

具体的な流れは以下のとおりです。

個体群の初期化
各個体の評価値計算
選択による親個体の取得
交叉で新たな子個体の生成
突然変異で遺伝子に変化を加え、次世代個体群を完成

主要関数の解説

初期化関数

初期化関数は、個体群の遺伝子を乱数により生成し、各個体の初期の状態を作成します。

これにより、多様な解候補を投入することが可能になります。

評価関数

評価関数は、各個体の適応度を算出する役割があります。

ここでは、単純に遺伝子中の1の数を評価値とする例を用いています。

次世代生成関数

次世代生成関数は、選択、交叉、突然変異の各操作を統合し、新たな個体群を作り出す関数です。

これにより、各世代で徐々により良い個体が生まれる仕組みとなります。

以下は、遺伝的アルゴリズム全体を統合したサンプルコードです。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define POP_SIZE 10
#define GENE_LENGTH 10
#define TOURNAMENT_SIZE 3
#define CROSSOVER_RATE 0.8
#define MUTATION_RATE 0.1
#define GENERATIONS 5
// 個体の構造体
typedef struct {
    int gene[GENE_LENGTH];
    int fitness;
} Individual;
// 評価関数：遺伝子中の1の数をカウントする
int evaluate(Individual ind) {
    int count = 0;
    for (int i = 0; i < GENE_LENGTH; i++) {
        if (ind.gene[i] == 1) {
            count++;
        }
    }
    return count;
}
// 初期化関数：個体群をランダム生成する
void initialize_population(Individual pop[]) {
    for (int i = 0; i < POP_SIZE; i++) {
        for (int j = 0; j < GENE_LENGTH; j++) {
            pop[i].gene[j] = rand() % 2;
        }
        pop[i].fitness = evaluate(pop[i]);
    }
}
// トーナメント選択による個体の選択
Individual tournament_selection(Individual pop[]) {
    int best = rand() % POP_SIZE;
    for (int i = 1; i < TOURNAMENT_SIZE; i++) {
        int idx = rand() % POP_SIZE;
        if (pop[idx].fitness > pop[best].fitness) {
            best = idx;
        }
    }
    return pop[best];
}
// 1点交叉による子の生成
void one_point_crossover(int parent1[], int parent2[], int child[]) {
    int cp = rand() % GENE_LENGTH;
    for (int i = 0; i < GENE_LENGTH; i++) {
        if (i < cp) {
            child[i] = parent1[i];
        } else {
            child[i] = parent2[i];
        }
    }
}
// 突然変異処理(ビット反転)
void mutation(int gene[]) {
    for (int i = 0; i < GENE_LENGTH; i++) {
        double r = (double)rand() / RAND_MAX;
        if (r < MUTATION_RATE) {
            gene[i] = (gene[i] == 0) ? 1 : 0;
        }
    }
}
// 次世代生成関数：新しい個体群を生成する
void generate_next_population(Individual current_pop[], Individual next_pop[]) {
    for (int i = 0; i < POP_SIZE; i++) {
        // 選択
        Individual parent1 = tournament_selection(current_pop);
        Individual parent2 = tournament_selection(current_pop);
        Individual child;
        // 交叉の確率判定
        double r = (double)rand() / RAND_MAX;
        if (r < CROSSOVER_RATE) {
            one_point_crossover(parent1.gene, parent2.gene, child.gene);
        } else {
            for (int j = 0; j < GENE_LENGTH; j++) {
                child.gene[j] = parent1.gene[j];
            }
        }
        // 突然変異
        mutation(child.gene);
        // 評価
        child.fitness = evaluate(child);
        next_pop[i] = child;
    }
}
int main(void) {
    srand((unsigned int)time(NULL));
    Individual population[POP_SIZE];
    Individual next_population[POP_SIZE];
    // 初期化
    initialize_population(population);
    // 世代ごとの進化
    for (int gen = 0; gen < GENERATIONS; gen++) {
        printf("Generation %d\n", gen);
        for (int i = 0; i < POP_SIZE; i++) {
            printf("Ind %d: Fitness = %d\n", i, population[i].fitness);
        }
        printf("----------\n");
        generate_next_population(population, next_population);
        for (int i = 0; i < POP_SIZE; i++) {
            population[i] = next_population[i];
        }
    }
    return 0;
}

Generation 0
Ind 0: Fitness = 5
Ind 1: Fitness = 4
Ind 2: Fitness = 6
Ind 3: Fitness = 3
Ind 4: Fitness = 7
Ind 5: Fitness = 2
Ind 6: Fitness = 5
Ind 7: Fitness = 4
Ind 8: Fitness = 6
Ind 9: Fitness = 3
----------
Generation 1
Ind 0: Fitness = 6
Ind 1: Fitness = 5
Ind 2: Fitness = 7
Ind 3: Fitness = 4
Ind 4: Fitness = 6
Ind 5: Fitness = 5
Ind 6: Fitness = 7
Ind 7: Fitness = 4
Ind 8: Fitness = 6
Ind 9: Fitness = 5
----------
...