大学の授業で遺伝的アルゴリズムの話題が出たので、C#を使って遺伝的アルゴリズムを実装してみました。といっても、実装するのは初めてで原理もよくわかっていなかったので、こちらのサイトにあるソースコードを参考に作ってみました。
遺伝的アルゴリズムはいくつか種類がありますが、これはルーレット選択 + 一点交叉 + 突然変異を組み合わせたものです。 流れとしてはこのようになっています。
- 適当な遺伝子配列をつくる
- その遺伝子配列の評価を行う
- ルーレット選択によって値を決める
- 一点交叉で遺伝子配列の一部を入れ替える
- 突然変異で遺伝子配列の一部を変更
- 評価を行い、以前の評価値より高い遺伝子配列を残す
- 3 ~ 6 を繰り返し、指定した世代まで行う
ソースコード
元のサイトではナップザック問題を解いていますが、私が作ったのは「決められた金額と個数で、購入金額の合計を最大にする商品の組合せを探し出す」ものです。変数名に関しては元のサイトのものを一部変更しています。
class Program { // おこづかい（所持金） static readonly int MaxPrice = 1000; // 商品1つあたりの最大価格 static readonly int MaxItemPrice = 100; // お店にある商品の数 static readonly int ItemCount = 20; // 持っていけるお菓子の数 (遺伝子列) static readonly int GeneData = 10; // 1世代あたりの個体数 static readonly int GeneCount = 8; // GAを終了する世代 static readonly int EndGenCount = 16; // 何世代ごとに点数を書き出すか static readonly int ShowGen = 1; // 交叉率 static readonly double CrosRate = 0.9; // 突然変異が起こる確率 static readonly double MutaRate = 0.1; static void Main(string[] args) { Random rand = new Random(); int geneCounter; int[] price = new int[ItemCount]; int[,] gene = new int[GeneCount, GeneData]; int[,] tempGene = new int[GeneCount, GeneData]; double total, ruletValue, ruletCf; int ruletNum = 0; int pos; int temp; double dRet; double[] results = new double[GeneCount]; double topResults; int eliteNum; int[] elite = new int[GeneData]; //各商品の価格を決める for (int i = 0; i < ItemCount; i++) { price[i] = rand.Next(10, MaxItemPrice); } //第1世代目（適当な遺伝子を与える） for (int i = 0; i < GeneCount; i++) { for (int j = 0; j < GeneData; j++) { gene[i, j] = rand.Next(0, ItemCount); } } //ここから進化開始（世代交代数初期化） geneCounter = 0; while (true) { //その世代の個体の成績を総和 for (int i = 0; i < GeneCount; i++) { //その個体の成績初期化 results[i] = 0.0; for (int j = 0; j < GeneData; j++) { results[i] += price[gene[i, j]]; } // 所持金を超えたら0点 if (results[i] > MaxPrice) { results[i] = 0.0; } } //優秀な個体番号を0番目と仮定 eliteNum = 0; //その個体のもつ成績を保持 topResults = results[eliteNum]; //初期の優秀な個体を超える個体を見つける for (int i = 1; i < GeneCount; i++) { if (topResults < results[i]) { eliteNum = i; topResults = results[i]; } } //優秀な個体の遺伝子情報を保持 for (int i = 0; i < GeneData; i++) { elite[i] = gene[eliteNum, i]; } //その世代の個体の成績総和 total = 0.0; for (int i = 0; i < GeneCount; i++) { total += results[i]; } //0～1 の値に成績の総和を掛ける for (int i = 0; i < GeneCount; i++) { ruletCf = rand.NextDouble() * total; ruletValue = 0.0; for (int j = 0; j < GeneCount; j++) { ruletValue += results[j]; if (ruletValue > ruletCf) { ruletNum = j; break; } } // 仮の個体群配列に選択された個体を入れる for (int j = 0; j < GeneData; j++) { tempGene[i, j] = gene[ruletNum, j]; } } for (int i = 0; i < GeneCount; i++) { for (int j = 0; j < GeneData; j++) { gene[i, j] = tempGene[i, j]; } } //交叉開始 for (int i = 0; i < GeneCount; i += 2) { //交叉確率の選定 dRet = rand.NextDouble(); //交叉率よりも値が低い場合のみ交叉 if (dRet < CrosRate) { pos = rand.Next(0, GeneData); //遺伝子の入れ替え for (int j = pos; j < GeneData; j++) { temp = gene[i, j]; gene[i, j] = gene[i + 1, j]; gene[i + 1, j] = temp; } } } //突然変異開始 for (int i = 0; i < GeneCount; i++) { for (int j = 0; j < GeneData; j++) { dRet = rand.NextDouble(); if (dRet < MutaRate) { gene[i, j] = rand.Next(ItemCount); } } } // 進化終了 // 待機している前世代の優秀個体の番号を個体として戻す for (int i = 0; i < GeneData; i++) { gene[0, i] = elite[i]; } geneCounter++; //現段階での状態を出力 if (geneCounter % ShowGen == 0) { if (geneCounter == 1) { Console.WriteLine($"世代\t評価点\t選んだ商品の価格(遺伝子情報)"); } Console.Write($"{geneCounter}\t{topResults}\t"); for (int i = 0; i < GeneData; i++) { Console.Write($"{price[gene[0, i]]}({gene[0, i]})\t"); } Console.WriteLine(); } //ファイル書き込み string filePath = @"C:\Users\hoge\Desktop\GeneData.csv"; using (StreamWriter writer = new StreamWriter(filePath, true, Encoding.UTF8)) { if (geneCounter == 1) { writer.WriteLine($"世代数, 評価点（合計金額）, 遺伝子配列(商品の価格)"); } writer.Write($"{geneCounter}, {topResults},"); for (int i = 0; i < GeneData; i++) { writer.Write($"{gene[0, i]}({price[gene[0, i]]}),"); } writer.WriteLine(); } if (geneCounter == EndGenCount) { break; } } } }
実行結果
とりあえず 16世代までやってみました。商品の数や金額などはソースコードの定義部分にあります。
世代 評価点 選んだ商品の価格(遺伝子番号) 1 656 98(6) 16(19) 90(1) 68(12) 92(15) 32(3) 71(9) 51(16) 51(16) 87(2) 2 709 35(5) 87(2) 35(5) 48(13) 95(7) 95(7) 98(6) 84(8) 35(4) 97(0) 3 773 98(6) 16(19) 90(1) 68(12) 92(15) 95(7) 98(6) 84(8) 35(4) 97(0) 4 799 98(6) 16(19) 90(1) 68(12) 92(15) 95(7) 98(6) 84(8) 71(9) 87(2) 5 799 98(6) 16(19) 90(1) 68(12) 92(15) 95(7) 98(6) 84(8) 71(9) 87(2) 6 811 98(6) 84(8) 90(1) 68(12) 48(13) 95(7) 98(6) 98(6) 35(4) 97(0) 7 818 98(6) 16(19) 90(1) 87(2) 92(15) 95(7) 98(6) 84(8) 71(9) 87(2) 8 869 98(6) 92(15) 90(1) 87(2) 92(15) 95(7) 98(6) 92(15) 35(4) 90(1) 9 869 98(6) 92(15) 90(1) 87(2) 92(15) 95(7) 98(6) 92(15) 35(4) 90(1) 10 919 98(6) 92(15) 97(0) 87(2) 92(15) 95(7) 97(0) 84(8) 90(1) 87(2) 11 924 98(6) 92(15) 90(1) 87(2) 92(15) 95(7) 92(15) 92(15) 96(18) 90(1) 12 924 98(6) 92(15) 90(1) 87(2) 92(15) 95(7) 92(15) 92(15) 96(18) 90(1) 13 924 98(6) 92(15) 90(1) 87(2) 92(15) 95(7) 92(15) 92(15) 96(18) 90(1) 14 924 98(6) 92(15) 90(1) 87(2) 92(15) 95(7) 92(15) 92(15) 96(18) 90(1) 15 924 98(6) 92(15) 90(1) 87(2) 92(15) 95(7) 92(15) 92(15) 96(18) 90(1) 16 929 98(6) 92(15) 96(18) 87(2) 92(15) 92(15) 92(15) 92(15) 96(18) 92(15)
世代が進むにつれて評価点（合計金額）が 1000 に近くなっています。また、CSV にも書き出しているので記録としても残しておけます。（重複ありになっています。）
ちなみに、32世代までまわすと
世代 評価点 選んだ商品の価格(遺伝子番号) 1 550 31(11) 72(17) 46(15) 36(13) 47(0) 96(12) 50(6) 31(11) 55(8) 86(16) 2 579 86(16) 24(4) 96(12) 47(0) 56(3) 54(7) 86(16) 55(8) 28(14) 47(0) 3 579 86(16) 24(4) 96(12) 47(0) 56(3) 54(7) 86(16) 55(8) 28(14) 47(0) 4 582 86(16) 24(4) 96(12) 47(0) 56(3) 54(7) 86(16) 55(8) 28(14) 50(6) 5 608 86(16) 24(4) 96(12) 47(0) 56(3) 54(7) 86(16) 31(11) 42(18) 86(16) 6 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 7 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 8 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 9 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 10 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 11 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 12 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 13 677 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 42(18) 86(16) 14 691 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 56(3) 86(16) 15 691 86(16) 62(10) 96(12) 46(1) 56(3) 86(16) 86(16) 31(11) 56(3) 86(16) 16 700 86(16) 62(10) 96(12) 46(1) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 17 700 86(16) 62(10) 96(12) 46(1) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 18 700 86(16) 62(10) 96(12) 46(1) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 19 700 86(16) 62(10) 96(12) 46(1) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 20 700 86(16) 62(10) 96(12) 46(1) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 21 700 86(16) 62(10) 96(12) 46(1) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 22 707 86(16) 62(10) 96(12) 46(1) 56(3) 62(10) 96(12) 86(16) 31(11) 86(16) 23 707 86(16) 62(10) 96(12) 46(1) 56(3) 62(10) 96(12) 86(16) 31(11) 86(16) 24 707 86(16) 62(10) 96(12) 46(1) 56(3) 62(10) 96(12) 86(16) 31(11) 86(16) 25 707 86(16) 62(10) 96(12) 46(1) 56(3) 62(10) 96(12) 86(16) 31(11) 86(16) 26 719 86(16) 72(17) 55(8) 96(12) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 27 719 86(16) 72(17) 55(8) 96(12) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 28 743 86(16) 96(12) 55(8) 96(12) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 29 743 86(16) 96(12) 55(8) 96(12) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 30 743 86(16) 96(12) 55(8) 96(12) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16) 31 746 86(16) 96(12) 50(6) 96(12) 56(3) 54(7) 86(16) 86(16) 50(6) 86(16) 32 750 86(16) 72(17) 86(16) 96(12) 56(3) 54(7) 86(16) 86(16) 42(18) 86(16)
こんな感じになります。突然変異や交叉率、個体差などをいじったりしていると面白いです。
