C++用遺伝的アルゴリズムライブラリ GAlib の使い方
この前はpyevolveを使いましたが、今回はC++用の遺伝的アルゴリズムライブラリであるGAlibというものを使ってみたいと思います。
GAlib: Matthew's Genetic Algorithms Library
予め言っておくと、pyevolveの使い方とGAlibは似てます。GAlibのソースにも多数のexampleが付属しているので、それが参考になります。
例
まぁ説明するより普通にソース見た方が早いと思うのでPyevolveと同じように
・要素数20の配列xがあるとき、以下の関数f(x)が最大となるxを求めよ
を解きたいと思います。
まずは個体を評価する評価関数を作成します。この評価関数の事をGAlibのドキュメントではObjective Functionとしています。
float Objective(GAGenome &g){ GA1DArrayGenome<int>& genome = (GA1DArrayGenome<int>&)g; float value=0.0; for(int i=0; i<genome.length(); i++) if (genome.gene(i) == 0) value += 1.0; return value; }
GAGenome というのは仮想クラスで、全てのゲノム(つまりデータ構造)はこれを継承します。評価関数を作る際には中で適当なクラスにキャストして評価をします。評価関数の戻り値はfloatであると決められています。今回はゲノムとしてGA1DArrayGenome
また、GA1DArrayGenomeを使う場合は、初期化関数を定義する必要があるので、これも定義しておきます。
// 初期化関数 void Initializer(GAGenome& g) { GA1DArrayGenome<int>& genome = (GA1DArrayGenome<int>&)g; for(int i = 0;i < genome.length();i++){ genome.gene(i, GARandomInt(-100,100)); // -100〜100までのランダムな値に } }
さて、それではmain関数の中になります。
GA1DArrayGenome<int> genome(20,Objective); genome.crossover(GA1DArrayGenome<int>::UniformCrossover); genome.initializer(::Initializer);
まずはgenomeを作ります。GA1DArrayGenomeコンストラクタの第一引数は要素数、第二引数は評価関数です。また、genome.crossover()、genome.initialize()で交叉関数と初期化関数を定義しています。
GASimpleGA ga(genome); ga.populationSize(100); // 集団数 ga.nGenerations(200); // 世代数 ga.pMutation(0.01); // 突然変異率 ga.pCrossover(0.9); // 交叉率
GASimpleGAで実際に評価をおこなうインスタンスを生成、そしてそれに設定を追加していきます。ちなみにnGenerationsのnはnumber,pMutationとpCrossoverのpはprobabilityの略です。
ところで、このGASimpleGAという名前ですが、これは遺伝的アルゴリズムで有名なDavid E. Goldberg氏が書いた本(これ)に由来するもので、世代によって集団数が変わらないもののことをいうようです。
ここまで来たら、後は実行するだけです。
// 評価開始 ga.evolve(); // 最も評価の高い個体を表示 std::cout << ga.statistics().bestIndividual() << "\n";
全体のコードはこんな感じです。
#include <ga/GASimpleGA.h> #include <ga/GA1DArrayGenome.h> #include <iostream> // 評価関数 float Objective(GAGenome &g){ GA1DArrayGenome<int>& genome = (GA1DArrayGenome<int>&)g; float value=0.0; for(int i=0; i<genome.length(); i++) if (genome.gene(i) == 0) value += 1.0; return value; } // 初期化関数 void Initializer(GAGenome& g) { GA1DArrayGenome<int>& genome = (GA1DArrayGenome<int>&)g; for(int i = 0;i < genome.length();i++){ genome.gene(i, GARandomInt(-100,100)); } } int main(int argc, char const* argv[]) { // ゲノムのインスタンスを生成 GA1DArrayGenome<int> genome(20,Objective); genome.crossover(GA1DArrayGenome<int>::UniformCrossover); genome.initializer(::Initializer); GASimpleGA ga(genome); ga.populationSize(100); ga.nGenerations(200); ga.pMutation(0.01); ga.pCrossover(0.9); // 評価開始 ga.evolve(); // 最も評価の高い個体を表示 std::cout << ga.statistics().bestIndividual() << "\n"; return 0; }
こんな感じでだいたいの流れは把握できると思います。Pyevolveと同様に、多くの設定にはデフォルトの値があります。一部を以下に示します。
#define name full name short name default value gaNminimaxi minimaxi mm int gaDefMiniMaxi = 1 //適応度を最大化しようとする(最小化する場合は -1) gaNnGenerations number_of_generations ngen int gaDefNumGen = 250 //世代数 gaNpConvergence convergence_percentage pconv float gaDefPConv = 0.99 //収束% laNnConvergence generations_to_convergence nconv int gaDefNConv = 20 //世代就職% gaNpCrossover crossover_probability pcross float gaDefPCross = 0.9 //交叉確率 gaNpMutation mutation_probability pmut float gaDefPMut = 0.01 //突然変異率 gaNpopulationSize population_size popsize int gaDefPopSize = 30 //集団数(個体数) gaNnPopulations number_of_populations npop int gaDefNPop = 10 //集団そのものの数(GADemeGaで使う) gaNpReplacement replacement_percentage prepl float gaDefPRepl = 0.25 //交換率(GASteadyStateGAで使う) gaNnReplacement replacement_number nrepl int gaDefNRepl = 5 //交換数(上と同じ) gaNnBestGenomes number_of_best nbest int gaDefNumBestGenomes = 1 //最善として選ぶゲノムの数 gaNscoreFrequency score_frequency sfreq int gaDefScoreFrequency1 = 1 //記録する頻度 gaNflushFrequency flush_frequency ffreq int gaDefFlushFrequency = 0 //書き込み頻度 gaNscoreFilename score_filename sfile char* gaDefScoreFilename = "generations.dat" //統計を保存するファイル名 gaNselectScores select_scores sscores int gaDefSelectScores = GAStatistics::Maximum //どのスコアを保存するか gaNelitism elitism el GABoolean gaDefElitism = gaTrue //各世代における最も優秀なゲノムを引き継ぐかどうか
(しまった崩れたorz … ドキュメントみてください…)
使用できるゲノムの種類
・ 1D binary string genome
・ 2D binary string genome
・ 3D binary string genome
・ binary-to-decimal genome
・ 1D array genome
・ 1D array genome with alleles
・ 2D array genome
・ 2D array genome with alleles
・ 3D array genome
・ 3D array genome with alleles
・ string genome
・ real number genome
・ list genome
・ tree genome
まぁ名前のとおりです。遺伝子の値の範囲を決めるには、GAAlleleSetを使う必要があります。alleleの設定方法はいろいろとありますが、基本的な流れとしては、alleleのインスタンスを作成、それにalleleを登録し、ゲノムのコンストラクタにそれを渡します。
GAAllelSetの使い方例(ex21.cより)
//それぞれの遺伝子は-10,0.1,1.0,10,100のいずれかの値を取る
GARealAlleleSet alleles1;
alleles1.add(-10);
alleles1.add(0.1);
alleles1.add(1.0);
alleles1.add(10);
alleles1.add(100);
GARealGenome genome1(length, alleles1, Objective1);
//遺伝子は0.0以上、10より小さい0.5刻みの数 (0とか0.5とか1.5とか)
GARealAlleleSet alleles3(0,10,0.5,GAAllele::INCLUSIVE,GAAllele::EXCLUSIVE);
GARealGenome genome3(length, alleles3, Objective3);
//一番目の遺伝子は0以上10以下の実数、二番目の遺伝子は50以上100以下の実数…
GARealAlleleSetArray alleles4;
alleles4.add(0,10);
alleles4.add(50,100);
alleles4.add(-10,-5);
alleles4.add(-0.01,-0.0001);
alleles4.add(10000,11000);
GARealGenome genome4(alleles4, Objective4);
//遺伝子の値は-1,0,1のいずれか
int aset[] = {-1,0,1};
GAAlleleSet<int> alleles(3, aset);
GA2DArrayAlleleGenome<int> genome(20, 20, alleles, objective);
使用できるアルゴリズム
・ GA with overlapping populations (steady-state)
・ GA with non-overlapping populations (simple)
・ GA with 1 or 2 children per generation (incremental)
・ GA with parallel, migrating populations (deme)
いろいろとあるんですが…自分はまだ2つ目のGASimpleGAしか使ってないというか分かってないです^^;
選択方法の決め方
GAlibでは選択方法はそれぞれクラスとして用意されているので、それのインスタンスをGAに登録します。
GASimpleGA ga(genome); GATournamentSelector selector; ga.selector(selector);
デフォルトで用意されている選択方法は以下のとおりです。
・ GARankSelector
・ GARouletteWheelSelector (多分デフォルト)
・ GATournamentSelector
・ GADSSSelector
・ GASRSSelector
・ GAUniformSelector
ヘッダファイルについて
GAlibを使用する場合には適当なヘッダをインクルードする必要がある訳ですが、基本的に名前は (使いたいもの).h です。例えば、ga/GASimpleGA.h とか ga/GA1DArray.h です。
ただこれだと面倒なので、 ga/ga.h をインクルードすると中で全ての 遺伝的アルゴリズムのヘッダとゲノムのヘッダをインクルードしてくます。
…ということでおおざっぱにGAlibの使い方を見てきました。いろいろと機能があるんですが、いかんせん自分の知識不足のため表面的なことしか説明できません(汗)。やはり一番参考になるのは付属のexampleだと思うので、使い方知りたい人はそれを読んでみてください。Pyevolveはかなり手軽な感じでしたが、こちらも手軽に利用できるんじゃないでしょうか。何より実行速度が早いです。
それではまたいつか…
