Kuratani Shigeru Weblog

***
2019年6月22日

遺伝的アルゴリズムを実装してみた

はじめに

今、通勤時間に「人口知能」に関する書籍を読んでいます。
「人口知能」の教科書でも取り上げられている「遺伝的アルゴリズム」をC言語で実践してみました。当初、想定していた結果とは違っていてとても興味深かったです。

今回の実験内容

今回は以下のお題を「異伝的アルゴリズム」で解いてみました。

今回のお題

解となる0と1の値をとる16桁の数字列を生成して、それとは別にランダムに生成した同じ形式の5個の数字列を交叉しながら、解となる数字列を生成する。

今回実装した「遺伝的アルゴリズム」のアルゴリズムは以下になります。

異伝的アルゴリズム

ステップ1 初期集団を作成して、遺伝子プールに配置する。
ステップ2 遺伝子プールの全ての組み合わせを交叉して、新しい遺伝子を生成する。
ステップ3 新しく生成した遺伝子の中に解があるかを評価する。解があれば終了。
ステップ4 新しく生成した遺伝子の適応度を評価して、高順位の遺伝子を遺伝子プールに移動する。
ステップ5 ステップ2に戻る。

※注釈
通常、「突然変異」をアルゴリズムに入れるようですが、今回は簡単の為に割愛しました。

実験の結果

想定では、交叉を繰り返しながら後世代の適応度が順次上がっていって、最後に解に到達すると考えていました。
しかし、各世代の適応度は上がったり、下がったりをしながら、交叉によってたまたま解が生成されれば終了となる結果になりました。
今回の私の実装したアルゴリズムが間違っているのかもしれませんが、交叉と高適応度の遺伝子を残すということを繰り返しても、書籍で説明がされている結果を得られませんでした。
おそらく、私の設定したお題が「異伝的アルゴリズム」が有効なお題でなかったかもしれません。
もしくは、私の実装がバグっているかも???(参考にする際はお気をつけください...)

最後に

書籍で学習をしながら、自分なりにお題を設定してコンピュータに解を求めさせるのは、とても知的で楽しい作業です。
最後に今回C言語で実装したプログラムと実行結果を記載しますので、興味のある方は自分のお好みの言語で実装をしてみてください。とても興味深いですよ。

実行結果

CW-01:large_scale XXX$ clang -o genetics_algorithm genetics_algorithm.c
CW-01:large_scale XXX$ ./genetics_algorithm 
<ゴール遺伝子>
遺伝子情報 : 0111000000000001
適応度(第1世代) : 0.481250
適応度(第2世代) : 0.612500
適応度(第3世代) : 0.537500
適応度(第4世代) : 0.625000
適応度(第5世代) : 0.406250
適応度(第6世代) : 0.531250
適応度(第7世代) : 0.468750
適応度(第8世代) : 0.606250
適応度(第9世代) : 0.462500
適応度(第10世代) : 0.550000
適応度(第11世代) : 0.543750
適応度(第12世代) : 0.600000
適応度(第13世代) : 0.518750
適応度(第14世代) : 0.581250
適応度(第15世代) : 0.468750
適応度(第16世代) : 0.606250
適応度(第17世代) : 0.550000
適応度(第18世代) : 0.687500
適応度(第19世代) : 0.606250
ゴールに到達しました 

C言語での実装(genetics_algorithm.c)

/****************************************************/
/* 遺伝的アルゴリズム                                  */
/* <処理内容>                                       */
/* ランダムに生成された16桁の2進数に、解となる数字列を      */
/* ランダムに生成した遺伝子プールから交叉により生成する       */
/****************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// マクロ定義
#define GENE_SIZE 16
#define POOL_SIZE 5
#define GENERATE_SIZE 10

// 構造体定義
struct gene
{
    int gene[GENE_SIZE]; // 遺伝子
};
typedef struct gene Gene;

// グローバル変数
Gene pool[POOL_SIZE];             // 遺伝子プール
Gene generate[GENERATE_SIZE];     // 生成遺伝子配列 
int generation_index = 0;         // 世代インデックス
Gene goal;                        // ゴール遺伝子
double adaptation[GENERATE_SIZE]; // 適応度配列

// プロトタイプ宣言
void init_gene();
void generate_gene_from_pool();
void crossover_gene(Gene g1, Gene g2, int count);
int rearch_goal();
int is_goal(Gene gene);
double evaluation();
double evaluation_gene(Gene gene);
void move_high_adaptation();
Gene generate_gene();
void print_gene(Gene gene);
int random_crossover();
int random_zero_one();
void bubblesort(double data[], int n);
void swapdata(double *i, double *j);

/************************************/
/* メイン関数                         */
/************************************/
int main(int argc, char const *argv[])
{
    // 乱数シード設定
    srand((unsigned) time(NULL));

    // ゴール遺伝子生成・表示
    goal = generate_gene();
    printf("<ゴール遺伝子>\n");
    print_gene(goal);

    // 初期集団生成
    init_gene();

    // 遺伝子プールから遺伝子を生成
    generate_gene_from_pool();

    while (1)
    {
        // 生成遺伝子のゴール判定
        if (rearch_goal())
        {
            printf("ゴールに到達しました\n");
            break;
        }

        // 適応度評価
        printf("適応度(第%d世代) : %f\n", generation_index, evaluation());

        // 適応度の高い遺伝子をプールに移動
        move_high_adaptation();

        // 遺伝子プールから遺伝子を生成
        generate_gene_from_pool();
    }

    return 0;
}

/************************************/
/* 初期集団生成                       */
/************************************/
void init_gene()
{
    for (int i = 0; i < POOL_SIZE; ++i)
    {
        pool[i] = generate_gene();
    }
}

/************************************/
/* 遺伝子プールの遺伝子を全て交叉         */
/************************************/
void generate_gene_from_pool()
{
    int gene_index = 0;
    for (int i = 0; i < POOL_SIZE - 1; ++i)
    {
        for (int j = i + 1; j < POOL_SIZE; ++j)
        {
            crossover_gene(pool[i], pool[j], gene_index);
            gene_index++;
        }
    }
    generation_index++;
}

/************************************/
/* 遺伝子を交叉                       */
/************************************/
void crossover_gene(Gene g1, Gene g2, int count)
{
    // 交叉点
    int crossover_point = random_crossover();

    // 交叉
    Gene new1, new2;
    for (int i = 0; i < GENE_SIZE; i++)
    {
        if (i < crossover_point)
        {
            new1.gene[i] = g1.gene[i];
            new2.gene[i] = g2.gene[i];
        }
        else
        {
            new1.gene[i] = g2.gene[i];
            new2.gene[i] = g1.gene[i];
        }
    }

    // 生成遺伝子配列に追加
    generate[count * 2] = new1;
    generate[count * 2 + 1] = new2;
}

/************************************/
/* 生成遺伝子のゴール判定               */
/*    0 : ゴールを到達していない     */
/*    1 : ゴールに到達した             */
/************************************/
int rearch_goal()
{
    for (int i = 0; i < GENERATE_SIZE; ++i)
    {
        if (is_goal(generate[i]))
        {
            return 1;
        }
    }

    return 0;
}

/************************************/
/* ゴール遺伝子判定                    */
/*    0 : ゴールでない                */
/*    1 : ゴールである                */
/************************************/
int is_goal(Gene gene)
{
    for (int i = 0; i < GENE_SIZE; ++i)
    {
        if (goal.gene[i] != gene.gene[i])
        {
            return 0;
        }
    }

    return 1;
}

/************************************/
/* 生成遺伝子評価                      */
/************************************/
double evaluation()
{
    double evaluation_value = 0.0;
    for (int i = 0; i < GENERATE_SIZE; ++i)
    {
        evaluation_value += evaluation_gene(generate[i]);
    }

    return evaluation_value / GENERATE_SIZE;
}

/************************************/
/* 遺伝子適応度評価                    */
/************************************/
double evaluation_gene(Gene gene)
{
    int match_value = 0;
    for (int i = 0; i < GENE_SIZE; ++i)
    {
        if (goal.gene[i] == gene.gene[i])
        {
            match_value++;
        }
    }

    return (double) match_value / GENE_SIZE;
}

/************************************/
/* 適応度の高い遺伝子をプールに移動       */
/************************************/
void move_high_adaptation()
{
    // 適応度を評価・設定
    for (int i = 0; i < GENERATE_SIZE; ++i)
    {
        adaptation[i] = evaluation_gene(generate[i]);
    }

    // 適応度をソート
    bubblesort(adaptation, GENERATE_SIZE);

    // 遺伝子プールへ移動
    for (int i = 0; i < POOL_SIZE; ++i)
    {
        for (int j = 0; j < GENERATE_SIZE; ++j)
        {
            if (adaptation[i] == evaluation_gene(generate[j]))
            {
                pool[i] = generate[j];
            }
        }
    }

}

/************************************/
/* 遺伝子生成                         */
/************************************/
Gene generate_gene()
{
    Gene new_gene;

    for (int i = 0; i < GENE_SIZE; ++i)
    {
        new_gene.gene[i] = random_zero_one();
    }

    return new_gene;
}

/************************************/
/* 遺伝子出力                         */
/************************************/
void print_gene(Gene gene)
{
    printf("遺伝子情報 : ");
    for (int i = 0; i < GENE_SIZE; ++i)
    {
        printf("%d", gene.gene[i]);
    }
    printf("\n");
}

/************************************/
/* ランダム関数                       */
/*   一点交叉のランダムな値を生成する     */
/************************************/
int random_crossover()
{
    return rand() % GENE_SIZE;
}

/************************************/
/* ランダム関数                       */
/*   1・0のランダムな値を生成する        */
/************************************/
int random_zero_one()
{
    return rand() % 2;
}

/**************************************/
/* bubblesor関数                       */
/**************************************/
void bubblesort(double data[], int n)
{
    int i, j;

    for (i = n - 1; i >= 1; i--) {
        for (j = 0; j < i; j++) {
            if (data[j] > data[j+1]) {
                swapdata(&data[j], &data[j+1]);
            }
        }
    }
}

/**************************************/
/* swapdata関数                        */
/**************************************/
void swapdata(double *i, double *j)
{
    int temp;

    temp = *i;
    *i = *j;
    *j = temp;
}