C#と遺伝的アルゴリズムで遊んでみる
遺伝的アルゴリズムといえば あれ を思い浮かべる人も多いとおもいますが、あーいう天才の遊びではなくよくある問題を試してみるだけです
機械学習ネタといえば 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回くらいでそこそこいい感じの答えが出せたってことでしょうか
ソースはこちら
おしまい
Azure Table Storage で NaN をどうにかしたい
何の話かというと NaN の話です。おしまい
おまけ
数年前まで Table Storage を扱う際には WindowsAzure.Storage パッケージを入れて参照させていました。ほとんどの人がそうでしょう、多分
そんなライブラリも現在ではご覧の通りの非推奨です
代替パッケージも教えてくれていますし、サクッと更新でしょう。普通は
現在は Azure.Data.Tables が正式リリースされましたし、こっちを使っているかもしれませんね
変更点
WindowsAzure.Storage とそれ以降のライブラリでは非常に大きな、無視できない違いがあります
WindowsAzure.Storage ではdouble.NaN
, double.PositiveInfinity
, double.NegativeInfinity
などが保存・読み込みできたのですがこれらが扱えなくなっています
GitHub でも Issue が2年近く前に上がっているんですが全くCloseされていません
たしか JSON に NaN が定義されていない気がしたのでその辺が影響しているんですかね
私はいままで double.NaN を当たり前に使っていたので 既存データのいたるところに NaN が入っているし、保存時にも無効値として NaN をバンバン使っているのでどこで何が起こるかわからない状態です
試してみる
まずは WindowsAzure.Storage
で NaN ありデータを突っ込みます
なんとなくわかるような感じに抜粋 (完全ソースは最後にリンク貼っておきます)
public static async Task WindowsAzureStorage.TestTableService.SetTestData(string connectionString){ await table.ExecuteAsync(TableOperation.InsertOrReplace(new TestTableEntity { PartitionKey = "Test1", RowKey = "NormalValue", Value = 1.23 })); await table.ExecuteAsync(TableOperation.InsertOrReplace(new TestTableEntity { PartitionKey = "Test2", RowKey = "NaN", Value = double.NaN })); await table.ExecuteAsync(TableOperation.InsertOrReplace(new TestTableEntity { PartitionKey = "Test3", RowKey = "PositiveInfinity", Value = double.PositiveInfinity })); await table.ExecuteAsync(TableOperation.InsertOrReplace(new TestTableEntity { PartitionKey = "Test4", RowKey = "NegativeInfinity", Value = double.NegativeInfinity })); }
これを Azure.Data.Tables
で順番に読み込んでみます
public static async Task AzureDataTables.TestTableService.GetTestData(string connectionString) { var tableClient = new TableClient(connectionString, "AzureTestTable"); var queryResults = tableClient.QueryAsync<TestTableEntity>("", 1); await foreach (var entity in queryResults) { Console.WriteLine($"{entity.PartitionKey} , {entity.RowKey} , {entity.Value}"); } } await WindowsAzureStorage.TestTableService.SetTestData(configuration.GetConnectionString("StorageConnection")); try { await AzureDataTables.TestTableService.GetTestData(configuration.GetConnectionString("StorageConnection")); } catch (Exception e) { Console.WriteLine($"{e.Message}"); }
結果は
Test1 , NormalValue , 1.23 Object of type 'System.String' cannot be converted to type 'System.Double'.
2行目の double.NaN を取得するところで「文字列は変換できねーよ」と怒られて終了します
読めるようにしてみる
読み込む前にごにょごにょします
public static void AzureDataTables.TestTableService.GonyoGonyo() { var libAssembly = Assembly.GetAssembly(typeof(global::Azure.Data.Tables.TableClient)); var type = libAssembly.GetType("Azure.Data.Tables.DictionaryTableExtensions"); var typeActions = type.GetField("typeActions", BindingFlags.Static | BindingFlags.NonPublic); ((Dictionary<Type, Action<PropertyInfo, object, object>>)typeActions.GetValue(null))[typeof(double)] = SetDouble; } private static void SetDouble(PropertyInfo property, object propertyValue, object result) { if (propertyValue is string s) { if (s == double.NaN.ToString(CultureInfo.InvariantCulture)) property.SetValue(result, double.NaN); if (s == double.PositiveInfinity.ToString(CultureInfo.InvariantCulture)) property.SetValue(result, double.PositiveInfinity); if (s == double.NegativeInfinity.ToString(CultureInfo.InvariantCulture)) property.SetValue(result, double.NegativeInfinity); } else { property.SetValue(result, propertyValue); } } try { AzureDataTables.TestTableService.GonyoGonyo(); await AzureDataTables.TestTableService.GetTestData(configuration.GetConnectionString("StorageConnection")); } catch (Exception e) { Console.WriteLine($"{e.Message}"); }
Test1 , NormalValue , 1.23 Test2 , NaN , NaN Test3 , PositiveInfinity , ∞ Test4 , NegativeInfinity , -∞
読めました!
ちょっとだけ解説
Azure.Data.Tables
では値の設定時に型毎の変換処理テーブル(?)をDicrionaryで持っているのでそこのdouble型を書き換えてあげれば読めます。double?やfloatなんかも書き換えれば一応読み込みはできるんじゃないんですかね。現バージョンなら
同様に書き込み側もできるかと思ったのですが、書き込みはswitch文でがっつり書かれているので私にはどうにもなりませんでした
まとめ
リフレクションでどうにかするのはあまり良くないですよね。元の実装が変わったらそれまでですし
やはりプルリクを投げてみるのがいいのかもしれませんが、この問題はそれなりにはまっている人がいると思うのですがIssueもプルリクも全くないところをみると NaN はあまり使われていないんですかねぇ (世界的には忌避されているレベルとかだといやだな~
ダメ元でプルリク投げるかどうかは・・・びみょう
おしまい
ソースはこちら
Azure App Service のスケールアウトに失敗していた件
App Service 上で公開しているページが遅い (タイムアウトする) ということで見たらこんな感じでした
completed 失敗 とはいったい...
現象
- メモリ使用量がほぼ100%
- Auto Scale Out の設定はCPU使用率だけだったのでメモリ使用量も追加した、けどインスタンス数増えず
- 手動でスケールアウトしようとしたけど失敗
- ショーガナイのでスケールアップしようと思ったらこちらも失敗
スケールアウトの実行履歴を見たら上のスクショのような状態だったのでギブアップ、サポートお願いしました
回答
サポートに投げる前から向こうでも現象に気づいていたのか即答っぽいかんじ
長いので抜粋すると
- 使っているスケールユニットのインスタンスが不足している (スケールユニットはリージョン内でみんなで使っているやつ?
- スケールユニットも使用量に応じてオートスケールするはずなんだけど、今使っているスケールユニットはこの機能が正常に動いていない
- マルチテナントなので他の誰かがインスタンスを解放してくれた時だけその分スケールアウトできる
- スケールユニットの復旧はサービス一時停止してインフラ側で再構築しないとだめらしい
復旧方法
- 待つ
そのために、もし正常に動作するように復旧される場合でも、対応までに非常に時間を要し、難航が予想されます。
待つことはやめました
- リソースグループを新規に作ってそこに新しい App Service プランを作る
リソースグループを作り直さないとだめらしいですが、これで別のスケールユニットが使われる(可能性が高い)らしいです
リソースグループと App Service プランを作ったらそれをサポートに連絡すれば、問題のあったスケールユニットじゃないかどうかを確認してくれるらしいので、伝統に従い HogeHoge2(HogeHoge=旧リソースグループ名) という名前のリソースグループを作って現在確認中です
まとめ
今回の現象は西日本リージョンで発生しました。マルチテナントですから同じスケールユニットを使っている人がほかにもいるはずで、その人は同じ現象にあっていることでしょう(サポートから連絡が行くと思うけど)
こんなこともあるんですねぇ
追記 2021/06/17
弊社で調査させていただきました結果、(略)、障害が発生していたスケール ユニットとは異なるスケール ユニットに配置されているのを確認いたしました。 また、これ以降同じリソース グループ内で、Japan West リージョンに作成した App Service プランでホストされる App Service においても、この度 「Web App」が配置されたのと同じスケール ユニットが選ばれ、障害が発生していたスケール ユニットとは異なるユニットに配置されます
「Web App」は新しく作ったサービスプランの名前です
リソースグループで使うスケールユニットが決まったらそれ以降そのリソースグループで作る App Service プランは同じスケールユニット使うんですね