@ayafuruta QAであれSAであれ、真の最適解が求められるわけではないので、総当たりと比較するのは意味ありません
2018-03-24 00:22:55@ayafuruta ヒューリスティックスは問題ごとに違うので、問題を決めてしまわないと難しいですね。それこそ、巡回セールスマン問題とか限定しないと
2018-03-24 00:28:11@kikumaco この記事によると30 ノードの巡回セールスマン問題で比較したようですが,RTしたHideyuki Tanakaさんのツイートによると,ヒューリスティックでは大きな差は出なそうに見えます。厳密解まで得られるとは知りませんでした。 twitter.com/tanakh/status/…
2018-03-24 00:36:55まず8億年というのは、ブルートフォースでの話だろうけど、枝狩りをすればはるかに速くなるだろうし、アニーリングで求めるのは実質的には近似解だから、秒数の比較に何の意味があるのだろうとか、スパコンでも疑似焼きなましすればわずか30ノード程度なら普通に1秒でそれなりに良い解出ると思う。
2018-03-23 23:33:29@ayafuruta 巡回セールスマンに限定するなら、SA使わないほうがいいですね。SAは「遅い代わりに万能」というのが特徴だと思います
2018-03-24 00:40:26@ayafuruta Fujitsuに出ている論文では、比較対象を新し目のXeonの1コアSAとして、1ノードだけだと2倍、1024並列で約1000倍、解法の工夫で6倍Speedupで、12000倍性能向上と示されています。逐次とFPGA内並列を比較するのはちょっと不公平ですが、PCより12000倍速いが主張です。(続く)
2018-03-24 07:14:32@ayafuruta ただし、SAは最速アルゴリズムではないし、並列と逐次をくらべちゃだめでしょう。私は詳しくないですが、既知の最速アルゴリズムと比べると似たようなもの、または少し遅いくらいじゃないのでしょうか。(さらに続く)
2018-03-24 07:19:01@ayafuruta 私の理解するところでは、この論文ではアニーリングマシンでTSPをちゃんと解いて高速化した点が注目で、NIIのアニーリングマシンの限界をこえているところです。実用性はまだ謎ですが、少なくとも量子アニーリングを終わらせる糸口は見せています。
2018-03-24 07:21:59これかー 富士通の中の人はともかく、記事書いた人は分かってないのね。今どきTSP30都市って。。 -- スパコンで8億年かかる計算を1秒で解く富士通の「デジタルアニーラ」 ~量子現象に着想を得て開発した、これまでにないコンピュータ - PC Watch pc.watch.impress.co.jp/docs/news/1113… @pc_watchさんから
2018-03-24 07:34:21もちろん、解けるの定義によって何を指してるかは違うし、最適性をきっちり示すのは自明ではないけど、この記事を信じるとこれは別に最適性示してそうではないし。
2018-03-24 07:52:0130都市巡回セールスマン1秒とか遅すぎやろ……と思ったけどやっぱり突っ込まれていた。量子に着想とか、色々と問題があるプレスだなぁ。日立のイジングマシンではMax-cutでちゃんと有名な近似アルゴリズムと戦わせていたので、今回のプレスの倫理観が際立つ。
2018-03-24 11:25:51私企業のプレスに倫理を要求するのも酷であるが、余りやると炎上する(させる)のでたいがいにしていただきたい所存。本件、後一線で炎上するギリギリのラインという印象がある。
2018-03-24 11:28:57昨日も内閣府の知財ビジョン議論で投げ込んだのですが、選択と集中は進化論的には最も愚かなアプローチなので、研究や研究者の多様性を強引に担保することが必須かと思います。そもそも正のスパイラルが効きやすいところにさらに突っ込むのは何というか無策以外の何者でもないと思います。 twitter.com/norionakatsuji…
2018-03-24 16:52:56「選択と集中」政策によって、潤沢な資金を与えられた、ごく一部の研究者や研究所を除いて、少ない予算でこれまでよく頑張って来たな、というのは同意。然し乍ら、もうこれ以上は、公正で合理的な政策見直しが無いと非常に難しいと思う。 twitter.com/kaz_ataka/stat…
2018-03-24 15:14:32@tanakh というか、この間そんな話したあと気づきましたけど、アニーリングって焼きなましですよね あいつらがAIとか言ってるしOKなのでは
2018-03-24 19:31:49「デジタルアニーラ」が1秒以下で解くという32都市のTSP を Numerical Recipes にのっている SA のアルゴリズムで私のノートPC1コアで解いたところ、0.2秒で解けた。
2018-03-24 21:33:02説明資料(講義ノート) jun-makino.sakura.ne.jp/kougi/keisan_t… プログラム:jun-makino.sakura.ne.jp/kougi/keisan_t… (リンクにはPGPLOTがいります)
2018-03-24 21:46:13