5章は遺伝的アルゴリズムです。
ルーレット選択、一点交叉、突然変異、のsimpleGAです。最初は、目的関数最適化をめざすヒューリスティック。

/**
 * simpleGA:
 * 1 遺伝子プールの初期化
 * 2 loop{
 *  交叉(親の選択を含む)
 *  突然変異
 *  結果の出力
 * }
 * 使い方:
 *  $./simpleGA (遺伝子の桁数) (遺伝子の数) (終了条件スイッチ) (終了条件) > (出力ファイル)
 * 終了条件スイッチ:(終了条件)を指定。0->ループ回数、1->最高適応度下限
 **/

#include <iostream>
#include <string>
#include <limits>
#include <cstdlib>
#include <ctime>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

inline int randLessThan(const int &n)
{
    int answer = n;
    while(answer == n) answer = ((double)rand() / RAND_MAX) * n;
    return answer;
}

/**遺伝子プールの初期化**/
void initializePool(int **pool, const int &numGene, const int &lenGene)
{
    initRand();
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = rand() % 2;
        }
    }
}

/**!!適用データに応じて変更!!**/
/**適応度の計算**/
int evaluateFitness(const int gene[], const int &lenGene)
{
    // 配列q中の数字を足すことで、最も499に近くなる組み合わせを探す。
    // 適応度が大きくなるほど最適となるように、1000から引いている。
    // このサンプルでは遺伝子数は20でなければならない。
    int q[] = {31, 41, 59, 26, 53, 58, 97, 93, 23, 84,
        -62, -64, -33, -83, -27, -95, -2, -88, -41, -97};
    int fitness = 0;
    for(int i=0; i<lenGene; ++i){
        fitness += gene[i] * q[i];
    }

    return 1000 - abs(499 - fitness);
}

/**!!適用データに応じて変更!!**/
/**交叉のための親を選択(ルーレット選択)**/
int select(const int roulette[], const int &numGene, const int &totalFitness)
{
    int ball;        // 玉(選択位置の数値)
    int acc = 0;     // 適応度の積算値

    ball =randLessThan(totalFitness);
    for(int i=0; i<numGene; ++i){
        acc += roulette[i];
        if(acc > ball) return i;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の2遺伝子の交叉(一点交叉)**/
void crossing(const int &lenGene, const int father[],
        const int mother[], int child1[], int child2[])
{
    int crossPoint; // 交叉する点

    // 交叉点の決定
    crossPoint = randLessThan(lenGene);
    // 遺伝子の前半部分をコピー
    for(int i=0; i<crossPoint; ++i){
        child1[i] = father[i];
        child2[i] = mother[i];
    }
    // 遺伝子の後半部分をコピー
    for(int i=crossPoint; i<lenGene; ++i){
        child1[i] = mother[i];
        child2[i] = father[i];
    }
}

/**交叉**/
void mating(int **pool, const int &numGene, const int &lenGene)
{
    int roulette[numGene];           // 適応度を格納
    int totalFitness = 0;            // 適応度の合計値
    int father = 0, mother = 0;      // 親の遺伝子番号
    int nextPool[numGene][lenGene];  // 子の世代

    // ルーレットの作成
    for(int i=0; i<numGene; ++i){
        roulette[i] = evaluateFitness(pool[i], lenGene);
        totalFitness += roulette[i];
    }

    // 選択と交叉を繰り返す
    for(int i=0; i<numGene/2; ++i){
        while(father==mother){
            father = select(roulette, numGene, totalFitness);
            mother = select(roulette, numGene, totalFitness);
        }
        // 交叉
        crossing(lenGene, pool[father], pool[mother],
                nextPool[i*2], nextPool[i*2+1]);
    }

    // 次世代のプールをコピー
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = nextPool[i][j];
        }
    }
}

/**真理値の反転(突然変異に使う)**/
inline int notVal(const int &val)
{
    if(val == 1) return 0;
    else return 1;
}

/**!!適用データに応じて変更!!**/
/**突然変異(反転)**/
void mutation(int **pool, const int &numGene, const int &lenGene,
        const int &MUTATIONRATE)
{
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            if((double)randLessThan(100) / 100 <= MUTATIONRATE)
                pool[i][j] = notVal(pool[i][j]);
        }
    }
}

/**状態を出力**/
void printCondition(int **pool, const int &numGene, const int &lenGene,
                    int &elite, int &bestfit)
{
    int     fitness;
    double  totalFitness = 0;
    bestfit = 0;

    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            cout << pool[i][j];
        }
        fitness = evaluateFitness(pool[i], lenGene);
        cout << "t" << fitness << endl;
        // elite
        if(fitness > bestfit){
            bestfit = fitness;
            elite = i;
        }
        totalFitness += fitness;
    }

    // エリート解の適応度を出力
    cout << elite << "t" << bestfit << endl;
    // 平均の適応度を出力
    cout << totalFitness / numGene << endl;
}

int main(int argc,  char *argv[])
{
    // 定数
    const double MUTATIONRATE = 0.01; // 突然変異率

    // 変数
    int     lenGene, numGene;    // 遺伝子の桁数、遺伝子数
    int     iterationSwitch;     // 終了条件スイッチ
    int     numIteration = 0;    // 繰り返し回数(if iterationSwitch==0)
    double  fitnessLimit = 0.0;  // 最高適応度下限(if iterationSwitch==1)
    int     **pool = 0;          // 遺伝子プール
    int     elite;               // エリート遺伝子のインデックス
    int     bestfit = 0;         // エリート遺伝子の適応度

    // 引数のチェック
    if(argc != 5){
        cerr << "使い方 $./simpleGA "
            << "(遺伝子の桁数) (遺伝子の数) (終了条件スイッチ) (終了条件) "
            << "> (出力ファイル)" << endl;
        return -1;
    }
    if((lenGene=atoi(argv[1])) < 1){
        cerr << "遺伝子の桁数が不適切です" << endl;
        return -1;
    }
    if((numGene=atoi(argv[2])) < 1){
        cerr << "遺伝子の数が不適切です" << endl;
        return -1;
    }
    if((iterationSwitch=atoi(argv[3]))<0 || iterationSwitch>1){
        cerr << "終了条件スイッチは0か1を入力してください。" << endl
            << "0:終了条件は繰り返し回数" << endl
            << "1:終了条件は最高適応度の下限" << endl;
        return -1;
    }
    if(iterationSwitch==0){
        if((numIteration=atoi(argv[4])) < 1){
            cerr << "終了条件(繰り返し回数)が不適切です" << endl;
            return -1;
        }
    } else {
        fitnessLimit=atof(argv[4]);
    }

    // get memory
    pool = new int * [numGene];
    for(int i=0; i<numGene; ++i){
        pool[i] = new int [lenGene];
    }

    // 1. initialize pool
    initializePool(pool, numGene, lenGene);

    // 2. loop
    // 繰り返し回数が固定
    if(iterationSwitch==0){
        for(int i=0; i<numIteration; ++i){
            cout << i << "世代" << endl;
            mating(pool, numGene, lenGene);                 // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, elite, bestfit);
        }
    // 適応度の下限が指定されている
    } else if(iterationSwitch==1){
        int iteration = 0;
        while(bestfit<fitnessLimit){
            cout << iterationSwitch++ << "世代" << endl;
            mating(pool, numGene, lenGene);                 // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, elite, bestfit);
        }

    }

    // memory release
    if(pool != 0){
        for(int i=0; i<numGene; ++i) delete [] pool[i];
        delete [] pool;
    }

    return 0;
}

後半は、4章の論理式によるカテゴリ分類の組み合わせ最適化用にsimpleGAを書き換えます。

/**
 * gaml:
 * 各データの、特徴ごとの分類と含まれるカテゴリを入力データとして、
 * 最もデータを効率良く分類する特徴の組み合わせを探索する。
 * 遺伝子の桁数は、特徴数*2(否定)に分類回数をかけたものとなる。
 * 評価値は、分類率を%で表す。つまり100点満点。
 * 1 遺伝子プールの初期化
 * 2 loop{
 *  交叉(親の選択を含む)
 *  突然変異
 *  結果の出力
 * }
 * 使い方:
 *  $./simpleGA (遺伝子の数) (終了条件スイッチ) (終了条件)
 *              < (入力ファイル) > (出力ファイル)
 * 終了条件スイッチ:(終了条件)を指定。0->ループ回数、1->最高適応度下限
 * 入力ファイル(例):
 *  3        <-分類回数
 *  4        <-特徴数
 *  1 0 1 1 1   <-各特徴に対する分類と、最後にカテゴリ
 *  0 1 0 0 1
 *      :
 *      :
 **/

#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <cstdlib>
#include <ctime>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

inline int randLessThan(const int &n)
{
    int answer = n;
    while(answer == n) answer = ((double)rand() / RAND_MAX) * n;
    return answer;
}

/**遺伝子プールの初期化**/
void initializePool(int **pool, const int &numGene, const int &lenGene)
{
    initRand();
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = rand() % 2;
        }
    }
}

/**真理値の反転(突然変異と論理式評価に使う)**/
inline int notVal(const int &val)
{
    if(val == 1) return 0;
    else return 1;
}

/**!!適用データに応じて変更!!**/
/**特定のデータに対する分類が正しいかを返す**/
int evaluate(const int gene[],
                const vector<int> &dataField,
                const int &numTerm, const int &numAttribute)
{
    int orValue, andValue, result;
    andValue = 1;
    // 論理積で項を結んだ、式全体の評価
    for(int i=0; i<numTerm; ++i){
        orValue = 0;
        // 論理和で結んだ項の評価
        for(int j=0; j<numAttribute*2; ++j){
            if((j%2) == 0) orValue += dataField[j/2] * gene[i*numAttribute*2+j];
            else orValue += notVal(dataField[j/2]) * gene[i*numAttribute*2+j];
        }
        if(orValue == 0) andValue = 0;
        else andValue += 1;
    }

    // 結果がカテゴリと不一致
    if(andValue == gene[numAttribute]) return 1;
    // 一致
    else return 0;
}

/**!!適用データに応じて変更!!**/
/**適応度の計算**/
int evaluateFitness(const int gene[],
                    const vector< vector<int> > &data,
                    const int &numTerm, const int &numAttribute)
{
    int point = 0; // 正しく分類されたデータの個数
    for(int i=0; i<data.size(); ++i){
        point += evaluate(gene, data[i], numTerm, numAttribute);
    }
    // 評価値(100点満点)を返す
    return 100*point / data.size();
}

/**!!適用データに応じて変更!!**/
/**交叉のための親を選択(ルーレット選択)**/
int select(const int roulette[], const int &numGene, const int &totalFitness)
{
    int ball;        // 玉(選択位置の数値)
    int acc = 0;     // 適応度の積算値

    ball =randLessThan(totalFitness);
    for(int i=0; i<numGene; ++i){
        acc += roulette[i];
        if(acc > ball) return i;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の2遺伝子の交叉(一点交叉)**/
void crossing(const int &lenGene, const int father[],
        const int mother[], int child1[], int child2[])
{
    int crossPoint; // 交叉する点

    // 交叉点の決定
    crossPoint = randLessThan(lenGene);
    // 遺伝子の前半部分をコピー
    for(int i=0; i<crossPoint; ++i){
        child1[i] = father[i];
        child2[i] = mother[i];
    }
    // 遺伝子の後半部分をコピー
    for(int i=crossPoint; i<lenGene; ++i){
        child1[i] = mother[i];
        child2[i] = father[i];
    }
}

/**交叉**/
void mating(int **pool, const int &numGene, const int &lenGene,
            const vector< vector<int> > &data,
            const int &numTerm, const int &numAttribute)
{
    int roulette[numGene];           // 適応度を格納
    int totalFitness = 0;            // 適応度の合計値
    int father = 0, mother = 0;      // 親の遺伝子番号
    int nextPool[numGene][lenGene];  // 子の世代

    // ルーレットの作成
    for(int i=0; i<numGene; ++i){
        roulette[i] = evaluateFitness(pool[i], data, numTerm, numAttribute);
        totalFitness += roulette[i];
    }

    // 選択と交叉を繰り返す
    for(int i=0; i<numGene/2; ++i){
        while(father==mother){
            father = select(roulette, numGene, totalFitness);
            mother = select(roulette, numGene, totalFitness);
        }
        // 交叉
        crossing(lenGene, pool[father], pool[mother],
                nextPool[i*2], nextPool[i*2+1]);
    }

    // 次世代のプールをコピー
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = nextPool[i][j];
        }
    }
}

/**!!適用データに応じて変更!!**/
/**突然変異(反転)**/
void mutation(int **pool, const int &numGene, const int &lenGene,
        const int &MUTATIONRATE)
{
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            if((double)randLessThan(100) / 100 <= MUTATIONRATE)
                pool[i][j] = notVal(pool[i][j]);
        }
    }
}

/**状態を出力**/
void printCondition(int **pool, const int &numGene, const int &lenGene,
                    const vector< vector<int> > &data,
                    const int &numTerm, const int &numAttribute,
                    int &elite, int &bestfit)
{
    int     fitness;
    double  totalFitness = 0;
    bestfit = 0;

    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            cout << pool[i][j];
        }
        fitness = evaluateFitness(pool[i], data, numTerm, numAttribute);
        cout << "t" << fitness << endl;
        // elite
        if(fitness > bestfit){
            bestfit = fitness;
            elite = i;
        }
        totalFitness += fitness;
    }

    // エリート解の適応度を出力
    cout << elite << "t" << bestfit << endl;
    // 平均の適応度を出力
    cout << totalFitness / numGene << endl;
}

int main(int argc,  char *argv[])
{
    // 定数
    const double MUTATIONRATE = 0.01; // 突然変異率

    // 変数
    int     lenGene, numGene;    // 遺伝子の桁数、遺伝子数
    int     iterationSwitch;     // 終了条件スイッチ
    int     numIteration = 0;    // 繰り返し回数(if iterationSwitch==0)
    double  fitnessLimit = 0.0;  // 最高適応度下限(if iterationSwitch==1)
    int     **pool = 0;          // 遺伝子プール
    int     elite;               // エリート遺伝子のインデックス
    int     bestfit = 0;         // エリート遺伝子の適応度
    int     numTerm;             // 論理式の論理和項の個数
    int     numAttribute;        // 属性値の個数
    vector< vector<int> > data;  // 入力データ

    // 引数のチェック
    if(argc != 4){
        cerr << "使い方 $./simpleGA "
            << "(遺伝子の数) (終了条件スイッチ) (終了条件) "
            << "< (入力ファイル) > (出力ファイル)" << endl;
        return -1;
    }
    if((numGene=atoi(argv[1])) < 1){
        cerr << "遺伝子の数が不適切です" << endl;
        return -1;
    }
    if((iterationSwitch=atoi(argv[2]))<0 || iterationSwitch>1){
        cerr << "終了条件スイッチは0か1を入力してください。" << endl
            << "0:終了条件は繰り返し回数" << endl
            << "1:終了条件は最高適応度の下限"   << endl;
        return -1;
    }
    if(iterationSwitch==0){
        if((numIteration=atoi(argv[3])) < 1){
            cerr << "終了条件(繰り返し回数)が不適切です" << endl;
            return -1;
        }
    } else {
        fitnessLimit=atof(argv[3]);
    }

    // データ入力
    cin >> numTerm;
    cin >> numAttribute;
    lenGene = numTerm*(numAttribute*2);
    while(true){
        // データをdataBufferに読み込む
        int dataBuffer[numAttribute+1];
        cin >> dataBuffer[0];
        if(cin.eof()) break;
        for(int i=1; i<numAttribute+1; ++i){
            cin >> dataBuffer[i];
        }
        // dataBufferをrowBufferにコピー
        vector<int> rowBuffer;
        for(int i=0; i<numAttribute+1; ++i){
            rowBuffer.push_back(dataBuffer[i]);
        }
        // rowBufferをdataに追加
        data.push_back(rowBuffer);
    }

    // get memory
    pool = new int * [numGene];
    for(int i=0; i<numGene; ++i){
        pool[i] = new int [lenGene];
    }

    // 1. initialize pool
    initializePool(pool, numGene, lenGene);

    // 2. loop
    // 繰り返し回数が固定
    if(iterationSwitch==0){
        for(int i=0; i<numIteration; ++i){
            cout << i << "世代" << endl;
            mating(pool, numGene, lenGene, data, numTerm, numAttribute); // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene,
                            data, numTerm, numAttribute, elite, bestfit);
        }
    // 適応度の下限が指定されている
    } else if(iterationSwitch==1){
        int iteration = 0;
        while(bestfit<fitnessLimit){
            cout << iterationSwitch++ << "世代" << endl;
            mating(pool, numGene, lenGene, data, numTerm, numAttribute); // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, data,
                            numTerm, numAttribute, elite, bestfit);
        }

    }

    // memory release
    if(pool != 0){
        for(int i=0; i<numGene; ++i) delete [] pool[i];
        delete [] pool;
    }

    return 0;
}

習作やるかなーやらない気がするが

関連記事

『君の名は』はキモいのか

フェイクだった時代の終焉

低解像度動画を高解像度にアプコンする精度がすごいと話題のTecoGANをwindowsで動かしてみた

5月分のBanggoodクーポン Mi Pad 4 Plusもあるよ

Kindle Cloud Readerで洋書を読む時にgoogle翻訳を使う

シグマのフルサイズ超広角Artレンズを買った

コメント

コメントを返信する

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です