-
hirokazu1020
- 27962
- 6
- 18
- 9
-
- いいね！9
chokudai(高橋 直大)@AtCoder社長
@chokudai
よくある失敗パターンその１として、確かに良い解がたくさんあるところに行けてるんだけど、ちゃんと深いところが見つけられてなくて、中途半端なところで終わっちゃうパターン。 これは焼きなまし覚えたての人にほんとによくある。 http://t.co/2spXNQwwzr
2013-12-27 01:01:55
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
これは、「温度変化でしっかり冷ましていけば、ランダムな動きでもある程度良い方向行けるでしょー」みたいな甘えが生み出すもので、最後の方はある程度やっぱり貪欲とか混ぜて、しっかり深いところまで見に行く動きを入れないとうまくいかないこともしばしば。
2013-12-27 01:03:46
chokudai(高橋 直大)@AtCoder社長
@chokudai
例えば、こんな感じで、超細くて深い解がたくさんあるケース。これは、ちゃんと一旦底まで降りてあげるような動きを積極的に入れてあげないと上手くいかないことが多い。ある程度深いところまで来たら、どれだけ緑の底を多く調べられるかの勝負みたいに http://t.co/Vf4Gv9Xgjb
2013-12-27 01:06:06
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
次！そもそも「全体を包むおっきいお椀」というのが存在しなくって、色んなところにそこそこの解があるやつ！ http://t.co/0XMSMlSQ6G
2013-12-27 01:07:35
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
これは、焼きなましで対応しようとするのが悪い。焼きなましでそんなうまいこと行かないんだし、多点スタートでどうにかしよう。短い時間である程度の解を出して、一番良いところを見つけたら潜ってく、みたいな感じでも良いし、焼きなまし一本に頼るのはやめよう！
2013-12-27 01:08:27
コルン
@colun
https://t.co/L36jUIvapr これはまだまだ焼きなまし法に向いてる方の探索空間ですねw（chokudaiさんがすごく注意して作図してるのが良くわかる
2013-12-27 01:08:34
chokudai(高橋 直大)@AtCoder社長
@chokudai
まぁ総突っ込みを受けているのが、「そもそも探索空間どうなってるのかってどうやったら解るの？」という話になって、これが解るようになると、焼きなましがいつ使えるか、どういう焼きなましをすれば良いかが解るわけですね！
2013-12-27 01:13:23
chokudai(高橋 直大)@AtCoder社長
@chokudai
という話なんだけど、どうやったら解るのかはなんか感覚でやっててよくわかんないのでここからは@colunさんに任せます！！！！
2013-12-27 01:13:49
hirosegolf
@hirose_golf
純粋な疑問として、焼きなまししたい空間って、大抵超高次元の事が多いけど、一次元の図でのアナロジーってどれくらい有効なのかなあ。
2013-12-27 01:14:46
chokudai(高橋 直大)@AtCoder社長
@chokudai
まぁ正直、焼きなまし書いてみる前にどういう感じになってそう、ってのは出来たら結構なエスパーだと思うけど、一回実装したとしたら、どういう動きしてるかを眺めることは可能なわけで、評価値と時間全部出力して１００万行くらいテキスト吐くから、その一部をてきとーに眺めれば良いと思うけどなぁ
2013-12-27 01:20:30
コルン
@colun
https://t.co/OZEtxdE6jF 変なところでボールをパスされた。。。 とりあえず座標系なら、２次元に適当に射影して、作図してみればなんとなく分かるのでは？（テキトウ） 射影は色々と変えてみて、色々な角度から見てみれば良いのでは？（テキトウ）
2013-12-27 01:18:04
コルン
@colun
それじゃあ、座標系がない場合はどうするか？ の前に、なんで座標系なら適当に射影して作図すれば良いと思っているかを説明しておきます。ここで距離と近傍の定義が出ます。「距離が近いことと、スコアの期待値にどう相関があるのか？」が、まぁ、探索空間の形なのかな、と僕は思っています。
2013-12-27 01:21:02
コルン
@colun
なのでまぁ、元が座標系じゃなくても、要は２次元ぐらいの低次元の座標系に射影できれば作図できます。つまるところ、座標系じゃなくても２点間の距離が定義できればいい。篠原武先生のSimpleMapとか、割とこの辺は万能な気がする。
2013-12-27 01:24:26
hogeover30
@hogeover30
んでコード書いてみて、現時点でのベストスコアとベストじゃないスコアがだんだん近づいていくようなら焼きなまし向きで、いつまで経ってもバラッバラだったら方針がダメなんじゃね？って思って困る
2013-12-27 01:28:33
chokudai(高橋 直大)@AtCoder社長
@chokudai
あとはまぁ根本的な話として、「評価を差分で高速に取ることが可能か？」って焼きなましにおいて超重要なところで、その前提がないとお話にならないことも多い気がする。計算時間が数十秒しかない環境、って前提だから、研究とかにおいては多分話が変わってくるけどその辺は解らん
2013-12-27 01:30:11