OptaPlannerOptaPlannerで百名山最短経路で制覇を妄想するこんにちは。年末になり、今年は仕事でもプライベートでもチャレンジングな事があまり無くて、ぱっとしない一年だったなぁと振り返り中のレッドハット長谷川です。はてさて、仕事はさておき、プライベートでチャレンジングな事があまり無かった理由の1つは、去年から始めたばかりのチャレンジングな山登りに、今年はたった4回しか行けなかったからだと勝手に考えています。いうことで、今年の山行回数に物足りなさを感じる私は、仕事中の得意技である妄想を発動して、このvoidを埋めようとしています。先日、「あーあ、1年くらい休みとって、百名山制覇とか、やってみたいわー」と妄想していると、ふと、1つの疑問が。「1年で百名山制覇となると、最短経路で百名山を移動しないとなぁ、でも、最短経路ってどんなんだい?」はい、後付け的前振りは、ここまで。2018の25日目の記事です。OptaPlannerOptaPlannerとは、私の理解で言い表すと、「膨大な組み合わせの中から最適解を見つける為に、良さ気な組み合わせを沢山自動で作って、その組み合わせを自分の好きな様に評価して、最適解を導出する」Javaソフトウェアです。Managerにバンドルさてれいます。求めたい場合、考えられる経路(=組み合わせ)の数は、100の階乗となり、とてつもない桁の数になってしまい、このような膨大な組み合わせの中から1つ1つの組み合わせを調べて最適解を見つけるのは、とてつもない時間がかかってしまう。そこで、ちょっと工夫して何とか良さ気な最適解をより短時間で見つけよう、というのが、OptaPlannerの実現する価値となります。経路探索だけではなく、OptaPlannerでは、シフト表作成、ジョブスケジューリング等、組み合わせ数が膨大になる問題を解決出来ちゃうようになります。Searchの説明をしたいと思います。Searchは、日本語訳では局所探索法となり、1つのたたき台となる組み合わせ(=初期解)をベースに、異なる組み合わせを生成、評価し、良さ気な組み合わせを見つける。この良さ気な組み合わせを新たな初期解として、このサイクルを繰り返すことにより、最適解を効率良く見つけようとする手法です。場合を例に、私の脳内イメージをダンプしてみます。最初に、何かたたき台となる初期解経路を用意します。Heuristicsを使用することにより求めることが出来ますが、説明していると25日中に記事をpublish出来ないので、後日紹介したいと思います。今すぐ知りたいという方は、OptaPlannerのドキュメントをご参照下さい。その初期解経路を元に、異なる組み合わせを生成します。→C→Dという初期解経路があったとすると、AをCの後にMove(移動)させてみたり、AとCをSwap(入れ替え)してみたりすることで、異なる経路をOptaPlannerの機能により自動生成します。次に、生成された経路を評価します。評価は、経路をスコアとして数値化することで行います。Languageで自由に実装出来るので、好きな制約を適応することが可能です。場合、私は、2つの制約条件をスコア化することにしました。山と山の間の移動距離が最小であること最後に訪れる山が、家から一番近いこと(とっとと帰宅したいので)今回、私の妄想に使用したスコア計算Javaコードは以下になります。やっていることのイメージだけ把握して頂ければと思うので、細かい説明は省きますが、やっていることは、山の位置情報(Location)を緯度経度で持たせておき、そのLocation情報からOptaPlannerが生成した経路の各山間の距離の和をdistanceに格納し、HardSoftLongScoreというスコアを格納するオブジェクトにマイナスのdistance値を設定しています。マイナスのdistance値にするのは、距離が長くなるほど、悪いスコアとする為です。1000を乗じているのは、緯度経度の精度を小数点第3位まで考慮する為です。地球の丸みとか、そんなところに道はねーよ、とかは、私の妄想では考慮外なので、あしからず。1000));}生成された経路にスコア付けが完了したら、次に、スコアをベースに良さそうな経路を選定アルゴリズムが決定し、この経路を新しい初期解経路とします。Searchの最初に戻って、最適解探索を繰り返し実行していきます。Acceptance等の選定アルゴリズムが使用可能です。Optimumに嵌ってしまう問題を回避することです。はい、私の嫌いな小難しい用語です。私の理解で言い表すと、「井の中の蛙問題を回避する」ってところでしょうか。私の脳内イメージは、以下です。Searchは、その名前が示すように近傍(=Local)を探索する方式ですので、近傍により良いスコアを持つ解が見つからない場合、その近傍ばかりをグルグル探索して結局、上図の左側のわーいと言っている人の様に、今のベストスコアの解に戻ってしまう可能性があります。これ、井の中の蛙になっている可能性もあり、より視野を広げて遠方を探索すれば、より良いスコアの解が見つかる可能性もあります。OptaPlannerでは、より視野を広げて遠方を探索する為に、これらの選定アルゴリズムを用いており、ちゃんとより良い解を求める工夫がなされています。Searchの基本イメージを説明しました。1つのたたき台となる組み合わせ(=初期解)をベースに、異なる組み合わせを生成、評価し、良さ気な組み合わせを見つける。この良さ気な組み合わせを新たな初期解として、このサイクルを繰り返すことにより、最適解を見つけようとする手法というのが、イメージ出来てもらえるとありがたいです。Hatにご相談下さいませー。Hatのルールのお兄さんかセーラームーンが対応してくれる筈!!で、妄想結果は?本当は、もっともっと説明したいことがあるのですが、今回は、結果だけ。ついでに、OptaPlannerが出力した経路を、LeafletとOpenStreetMapを使用して可視化してみました。東京恵比寿からスタートするキレイな時計回りの経路が得られてますね、パット見、最短っぽいです。}次回の予定(あるのか?)次回は、今回作ったソースコードを公開して、どのように経路をJavaでモデリングしているかの話をしたいと思っています。ミドルウェアのサポートをしている三浦です。ついてJBossのサポートエンジニアをしている三浦です。HatでOpenShiftのサポートをしているid:nekopです。各記事は著者の見解によるものでありその所属組織を代表する公式なものではありません。その内容については非公式見解を含みます。スターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。