遺伝的アルゴリズムといえば あれ を思い浮かべる人も多いとおもいますが、あーいう天才の遊びではなくよくある問題を試してみるだけです
機械学習ネタといえば Python ですが私は C# が大好きなので使う言語は C# です
こんなのを見つけたのでこれを使って、サンプルを写経するような感じでやっていきます
上記リポジトリにリンクがありますが Blazor 上で動作するサンプルがあります
実際に遊んでみるなら上記ページに飛んでぽちぽちするのが早いでしょう
ちなみに以下で少し説明っぽいことを書くと思いますが、すべて 想像 で書いています。参考にする人はいないと思いますが、参考にする時はご自身で裏を取ってから使ってください
巡回セールスマン問題
お題はよくあるこいつです。Wikipedia にも説明がありますね
英語では Traveling Salesman Problem、というらしいので機械学習系で tsp って出てきたらこれのことかもしれません。以下ではTSPと略します
ざっくり説明すると、始点から n個の地点を一つずつ通って始点に戻ってくるルートのうち最短のルートを求める、といった感じでしょうか。全部の組み合わせの距離を求めて比較すれば最短ルートが求められるわけですが、全部の組み合わせがなかなか面白いことになります
n地点の時の組み合わせの合計は (n-1)!/2 になるらしいので (数学忘れた)
10地点で181440通り程度ですが、30地点になると4.420881e+30 (4.4 × 10の30乗)、100地点では4.666311e+155、って感じに組み合わせが爆発します
巡回セールスマン問題に関しては気になった方はググって正しい知識をどうぞ
ということで普通に全部の距離を求めるというのが現実的ではないので、それの解決策の一つとして遺伝的アルゴリズムを使う、ということです
遺伝的アルゴリズム
Wikipedia 参照
GeneticSharp を使う
ほとんど Blazor サンプルの写経になります
自分で用意するのは TSP 用の遺伝子(染色体？)と評価関数です。あとは標準のものを使います
実装してみる
500×500 のCanvas上にランダムにn個の点を置いてその最短のパスを求めることにします
まずは地点の定義から。Pointでもよかったのですが、一応巡回セールスマン問題なのでそれっぽく
public class City { public int X { get; set; } public int Y { get; set; } public double DistanceTo(City to) { return Math.Sqrt(Math.Pow(X - to.X, 2) + Math.Pow(Y - to.Y, 2)); } } // 使う時はこんな感じで for (var i = 0; i < PointCount.Value; i++) { Points.Add(new City { X = RandomizationProvider.Current.GetInt(0, 500), Y = RandomizationProvider.Current.GetInt(0, 500), }); }
説明不要ですね
つぎ、染色体(遺伝子?)情報
public class TspChromosome : ChromosomeBase { private readonly int[] _inputGenes; public TspChromosome(int[] inputGenes) : base(inputGenes.Length) { _inputGenes = inputGenes; // Shuffle いる？ var genes = inputGenes.Select(g => g).OrderBy(g => new Guid()).Select(x => new Gene(x)).ToArray(); ReplaceGenes(0, genes); } public override Gene GenerateGene(int geneIndex) { return new Gene(RandomizationProvider.Current.GetInt(0, _inputGenes.Length)); } public override IChromosome CreateNew() { return new TspChromosome(_inputGenes); } } // 初期値はこんな感じ new TspChromosome(1.To(_currentArray.Length - 1).ToArray());
こんな感じにするそうです。inputGenesには地点配列のインデックスが入っています。0番目が始点なので1から配列の上限まで一つずつ、初期値は順番にという感じで
最後は評価関数
public class TspFitness : IFitness { private readonly City[] _inputPoints; private readonly double _initialDistance; public TspFitness(City[] inputPoints) { _inputPoints = inputPoints; var cycle = _inputPoints.Append(_inputPoints[0]).ToArray(); _initialDistance = GetTotalDistance(cycle); } // 距離を求めるためのあれこれ double GetTotalDistance(City[] points) => points.Pairwise((x, y) => x.DistanceTo(y)).Sum(); public double GetTotalDistance(IChromosome chromosome) { return GetTotalDistance(GetPoints(chromosome)); } public City[] GetPoints(IChromosome chromosome) => chromosome.GetGenes().Select(x => (int)x.Value).Prepend(0).Append(0).Select(x => _inputPoints[x]).ToArray(); public double Evaluate(IChromosome chromosome) { return Math.Max(0, 1.0 - (GetTotalDistance(chromosome) / _initialDistance)); } }
距離の短い方が優秀って感じになっていますTpsFitness.Evaluate()
実行
準備はできたのであとは動かすだけです
// 抜粋 var ga = new GeneticAlgorithm( population, _currentTspFitness, new TournamentSelection(), new OrderedCrossover(), new ReverseSequenceMutation()); Generation.Value = 1; ga.Termination = new GenerationNumberTermination(Generation.Value); ga.Start();
こんな感じ
選択はトーナメント方式、組み換えは順序交叉(?)、突然変異は(???)よくわかりませんがそーいうことで
可視化してみる
WPFで見える化() してみます。地点数は200点で頑張れ！
- 1世代目
- 101世代目
- 1001世代目
- 10001世代目
- 20001世代目
10001と20001ではほとんど変化ないので、今回は10000回くらいでそこそこいい感じの答えが出せたってことでしょうか
ソースはこちら
おしまい
