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;
}
習作やるかなーやらない気がするが
コメント