2017年8月10日木曜日

学術的「問い」とは

ある書類で、「学術的「問い」」について記述する項目が新設されていた。
今までにないタイプの質問ではあるけど、非常にいい項目ではないかと思う。

いい機会なので、「学術」について改めて調べてみると
https://kotobank.jp/word/%E5%AD%A6%E8%A1%93-460349
によると
#####
①学問。専門性の高いものをいうことが多い。 「 -論文」
②学問と芸術。また、学問と技術。学芸。
#####
とのこと。

あと、こういったものは「リサーチクエスチョン」とも呼ばれていて、それ自体に関する研究もたくさんある。

2017年8月3日木曜日

デスティニー

最近、研究をしていると
「あぁ、この研究をしているのって、デスティニーだよね」
と思うことがしばしばある。

もちろん、destiny であって、よく似た単語の density ではない。

不思議なもので、何年もかかって自分のところに研究内容が来ていたりして、
「あぁ、これがご縁ってやつか」
とか
「あぁ、これを研究するために今まで勉強してたのか」
とか思ったりする。

なんとも不思議なものだ。

2017年8月1日火曜日

Julia が便利すぎる

今回計算しようと思ったのは、
「1辺が長さ1の正方形の中に n 個の点をランダムに置いた場合に、それらの巡回セールスマン問題の距離の平均はいくつ?」
ということ。

巡回セールスマン問題は NP-完全な問題なので厳密解を計算しようとしたら大変なので、モンテカルロシミュレーションを採用してヒューリスティクスを使って求めた場合の平均でいいことにした。ただ、巡回セールスマン問題のヒューリスティクスを実装したものが C や Python だと思ったほか見つからない(正確にいうと、かなりソースコードに自分で手を入れないといけない)。

ということで、Julia で探してみたら、巡回セールスマン問題のヒューリスティクスを実装してあるパッケージが既にあった。しかも、20行ぐらいを自分で書けば当面の目標は達成できる。

結局自分で書いたソースは以下のような感じで、Julia のパッケージを見つけてから10分ぐらいでコーディング完了。

##### ここから ####
using Distances
using TravelingSalesmanHeuristics

n_max = 20
for n = 1:n_max
    T = 10000
    sum0 = 0
    time1 = @elapsed begin
        for i=1:T
            pts = rand(2,n)
            distmat = pairwise(Euclidean(), pts)
            path, pathcost = solve_tsp(distmat)
            sum0 = sum0 + pathcost
        end
    end
    println("n = $n, average = $(sum0/T), time = $time1")
end
##### ここまで #####

で、実行結果は以下のような出力。
n = 1, average = 0.0, time = 0.135839147
n = 2, average = 1.0450777563744278, time = 0.182987882
n = 3, average = 1.5717746211246175, time = 0.240622039
n = 4, average = 1.8913379727886972, time = 0.309000624
n = 5, average = 2.125071816087441, time = 0.376932182
n = 6, average = 2.3193293493322282, time = 0.455320865
n = 7, average = 2.4779204158273442, time = 0.546624336
n = 8, average = 2.6150744388172296, time = 0.690397053
n = 9, average = 2.7494941691386257, time = 1.037431405
n = 10, average = 2.878494437536675, time = 1.229969995
n = 11, average = 2.984631760238664, time = 1.092407702
n = 12, average = 3.0957685529387713, time = 1.467921928
n = 13, average = 3.2022714958643905, time = 1.920219731
n = 14, average = 3.2997237925066214, time = 2.21402169
n = 15, average = 3.3949127954683385, time = 2.097072679
n = 16, average = 3.491072331414203, time = 2.212287591
n = 17, average = 3.5848683927044824, time = 2.481302509
n = 18, average = 3.6700061119169214, time = 2.758670548
n = 19, average = 3.757282880734828, time = 3.06751467
n = 20, average = 3.8405201350048874, time = 3.414271655

思っていた以上に Julia が便利。


2017年7月31日月曜日

平均が簡単なようでいて難しい

簡単に計算できるかな、というか解析的に求まるのかな、と思っていた平均が実はそれほど簡単でもなかった、というのがあって、以下のような問題が思っていた以上に難しい。


問題:「一辺が長さ 1 の正方形にランダムに2点を置いた場合の2点間の距離の平均はいくらか?」

それほど厳密な解がほしいわけでもないので、サクッとモンテカルロシミュレーションを Julia で作ってみたら、だいたい 0.5214 という解になった。
この 0.5214 って数字、なんだろう?


ちなみに、作ったプログラムは
sum0 = 0.0
T = 10000*10000
for i=1:T
    x1 = rand()
    x2 = rand()
    y1 = rand()
    y2 = rand()
    dist0 = sqrt((x1-x2)^2 + (y1-y2)^2)
    sum0 = sum0 + dist0
    if rem(i, 10000000) == 0
        println("iter = $i, average = $(sum0/i)")
    end
end

で 40 秒ぐらいで計算してみている。
julia> @time include("randdist.jl")
iter = 10000000, average = 0.521513779364118
iter = 20000000, average = 0.521471850234503
iter = 30000000, average = 0.5214132474790024
iter = 40000000, average = 0.5214231135462779
iter = 50000000, average = 0.521431221770643
iter = 60000000, average = 0.5214123606643466
iter = 70000000, average = 0.5213983220702314
iter = 80000000, average = 0.521385077693363
iter = 90000000, average = 0.5213964364889536
iter = 100000000, average = 0.5213935109322017
 41.304951 seconds (600.00 M allocations: 10.431 GB, 1.90% gc time)

ちなみに、1行で計算すると4倍ぐらい速かった。

julia> @time begin T = 10000*10000; x = rand(T,4); ave = sum(sqrt((x[:,1] - x[:,2]).^2 + (x[:,3]-x[:,4]).^2))/T; println("T = $T, ave = $ave"); end
T = 100000000, ave = 0.5213702192902951
  8.407286 seconds (45 allocations: 10.431 GB, 9.60% gc time)




2017年7月26日水曜日

新しい最適化の概念

数理最適化の分野では first-order method のような手法が「大規模なデータ」を扱えるということで多くの研究がされてきたが、昨日チェックしたもう1本の論文では、「first-order method が扱えるような小さなデータではなくて、ちゃんとした規模のデータを扱いたい」という話が載っていた。

そのために、今までの数理最適化の概念とは全く異なる最適化の概念を導入していて、簡単にいうと
「最適値や最適解を求めない」
というもの。

「なるほど、そういう考え方があったか」という気分で、目から鱗がパラパラ。

2017年7月25日火曜日

Home Health Care の論文をチェック

今回は、

OR problems related to Home Health Care: A review of relevant routing and scheduling problems,
Operations Research for Health Care (2017), http://dx.doi.org/10.1016/j.orhc.2017.06.001

という論文をチェックしてみた。
簡単にいうと、「自宅療養をしているような患者さんが複数いる場合に看護師がどういう順番で患者さんを見て回ったらいいか?」というような内容で研究している論文のサーベイだった。

結構面白いテーマかと思って読んだわけだけど、それぞれの論文でケースバイケースでアルゴリズムを作っている感じだった。ある意味で行き当たりばったりなアプローチが多く、うまく行く理由がたまたまなのか、ちゃんと科学的理由があるのか、検証がなされていないようだ。

一番致命的なのは、他の研究者がデータにアクセスできない(たぶん、公開を前提としてのデータ収集が行われていないためだろうな、とは思う)ことで、論文の結果を再現できないことだと思う。

このサーベイで指摘されているように、ベンチマークのようなデータセットがあって、それで試すことで本当に有益な手法なのかが分かるようになるのかもしれない。

2017年7月21日金曜日

クロスドッキングセンターの出庫エリアにおけるシュート・ドック割り当てとその解法の提案

論文を読んでみたので、思ったあたりをメモ書きしておく。

1.問題を mixed integer linear programming (MILP) で定式化する
2.MILP が小さい場合は Gurobi で解く
3.大きくなる場合は、遺伝的アルゴリズム+局所探索で解く
4.数値実験では、MILP が小さい場合は Gurobi で解いた解と同程度の解を遺伝的アルゴリズム+局所探索で得ることができる


読んでみた限りだと、遺伝的アルゴリズムと局所探索の実装は、問題にあまり特化せずに比較的スタンダードな実装が行われているようだ。
数理最適化の視点だと、ガッチリと問題の性質を使いまくった複雑なアルゴリズムを作って、その定理とか証明したりなっちゃうかもしれないけど、実用上では厳密解を求める必要がないから、こういうアプローチはありだなぁ、と思ったりする。