組合せ最適化と量子コンピュータに関する怪しい言説に研究者が間違いを指摘 42
ストーリー by nagazou
なんでもはできない、できることだけ 部門より
なんでもはできない、できることだけ 部門より
ニュースや新聞で量子コンピュータが取り上げられることが増え、量子コンピュータであればすべて解決できる的な言説が増え、危機感を感じている研究者がいるそうだ。このため、「むしゃくしゃしてやった,今は反省している日記」の記事では、この問題を指摘しておくことにしたそうだ(むしゃくしゃしてやった,今は反省している日記)。
例えば、古典コンピュータでは組合せ最適化を解けないという考えに関しては、量子じゃないと解けないわけではなく、古典コンピュータでも解くことはでき、むしろ量子アニーリングでは厳密解の意味では解いたことにならないと指摘している。このほか巡回セールスマン問題(TSP)古典コンピュータでは時間がかかるといった問題に関しても指摘を行っている。
例えば、古典コンピュータでは組合せ最適化を解けないという考えに関しては、量子じゃないと解けないわけではなく、古典コンピュータでも解くことはでき、むしろ量子アニーリングでは厳密解の意味では解いたことにならないと指摘している。このほか巡回セールスマン問題(TSP)古典コンピュータでは時間がかかるといった問題に関しても指摘を行っている。
ジョブショップスケジューリング問題 (スコア:1)
巡回セールスマン問題は、配達員では重要そうですが
私の場合、巡回セールスマン問題は仕事であまり使うことはないのですが
ジョブショップスケジュール問題はよく必要に迫られます。
ジョブショップスケジューリング問題を古典コンピュータで解かせるアルゴリズムについて
知っている方がいらしたら教えて下さい。
Re:ジョブショップスケジューリング問題 (スコア:1)
巡回セールスマン問題もジョブショップスケジューリング問題も NP 完全なので、評価関数を用意して総当たりor焼き鈍しor遺伝的アルゴリズムしかないんじゃないかな
評価関数を組めれば、実現自体は出来ると思います
なお「特定の問題に関して量子コンピュータが圧倒的に高速」なだけで、古典コンピュータで解けない問題を量子コンピュータが解けるようになるわけではないです
Re: (スコア:0)
巡回セールスマン問題はNP困難だけどNP完全ではない(NP完全問題より難しいかもしれない)のでは? (そもそも「はい」「いいえ」で答えられる問題でなければNP問題という概念が適用できないが巡回セールスマン問題は「最短経路を求めよ」という問題)
Re:このあとむちゃくちゃラクロスした (スコア:0)
日々、「効率化」と「生産性」で検証がなされている分野ですので
それに特化したアルゴリズムはありません。
今ホットなのは、量子計算の様に ばばっと定量計算をおこなって
統計的にこっちの解の方がいいね?っていう従来の古典的なやり方
からくる結果を利用した、未来判断を組み合わせたものが流行ってます
Re: (スコア:0)
何が問題なのかを自分で良く考えれば対処法は見つかるのでは?
どうしても最適解が必要だから決定論的なアルゴリズムを求めているのか?
今よりも良い解が得られるアルゴリズムを業務上必要としているのか?
競合しているライバルよりも良い解を得て競争に勝とうとしているのか?
ほんのちょっとだけ良い解が得られるアルゴリズムを自社で開発して商品の宣伝文句にしたいのか?
最適解を必要としているわけではないが現実的な解を今よりも短時間で求めたいのか?
Re:ジョブショップスケジューリング問題 (スコア:1)
質問としては、どれが一番近いかと言うと最適解を求めるアルゴリズムです。
(もし存在しているのであればお知恵を借りたくて書き込みました)
私は賢くないのでこういったアルゴリズムを自分で考えて対処できません。
以前、ソートアルゴリズムの存在を知らず自分で考えましたが(後にバブルソートだとわかる)、
後で知ったクイックソートには性能も悪いですし、アルゴリズムを知ったときは自分で考案できないなと思いました。
ジョブショップスケジュール問題の研究者でも無い私はアルゴリズム考案するほど余裕はありません。
ただ生産管理において大きな壁であります。
そういうものは先人の知恵を借りたほうが良いと思ったのです。
#4067055さんのように
特化したアルゴリズムはありません。
でもありがたい情報でした。
#4067055さんありがとうございます。
Re: (スコア:0)
> 質問としては、どれが一番近いかと言うと最適解を求めるアルゴリズムです。
この問題での最適解を求めるのは(規模によるけど)現実的な時間では難しいです
ただ「それなりに最適だろう」という近似解であれば、既にある手法で可能です
(最適解出すのに1ヶ月、近似解出すのに1時間とかそのぐらいの差がある)
必要なのは評価関数(スケジューリング A とスケジューリング B のどちらが優れているかの評価)なので、これさえあれば自分で頑張るでも他者/他社にお任せするも可能です
ただどれにしても片手間でできることではないので、改善活動として社内で提言し予算や人を割いてもらうのがいいかと
Re: (スコア:0)
組み合わせ最適化問題は、深く研究するつもりがないのなら、適当なソルバーに投げ渡してしまうのが手っ取り早い。
ソルバーには、有料/無料、最適解を求める(むっちゃ時間がかかる)/そこそこ良い解を求める(速い)、など色々あるけど、
いずれにせよ、解きたい問題をソルバーが対応してる形の数式(大体は、多数の条件式と、最適化したい目的関数1つ)に落とし込んだら、後はよしなにやってくれる。
検索してとりあえず出てきた解説例だと組合せ最適化を使おう [qiita.com]とか。リンク先に組合せ最適化 - 典型問題 - ジョブショップ問題 [qiita.com]もあるね。
Re: (スコア:0)
具体例も含めてご案内ありがとうございます。
参考になります。
今回いろいろな方から参考意見を聞くことが出来てよかったと思います。
そりゃそうだ (スコア:0)
今は(と言うより今までずっと)研究費を取るのが目的で実用性なんて二の次三の次だからな。
一握りの本当に凄い研究者と、大勢の山師が混ざっている分野。
Re: (スコア:0)
データサイエンスの次はこれだね
Re: (スコア:0)
ニューロみたいに一度使えない判定された後10年ぐらい日陰暮らしはあるかもね。
Re: (スコア:0)
> 一度使えない判定された後10年ぐらい日陰暮らしはあるかもね
量子アニーリングって10年以上「使えない」って評価だぞ
Re: (スコア:0)
ニューロてなに?あなたの脳?
Re: (スコア:0)
光回線やってる会社の事?
ニューラルネットワークの事?
それとも貴方の脳細胞の事を言いたかった?
Re: (スコア:0)
一人でボケネタ網羅するのは良くない!!
欲張らず他人にも回そう!!
Re: (スコア:0)
ニューロは10年じゃきかないんじゃないかな…。冬の時代に研究続けてた人は偉い。
Re: (スコア:0)
今みたいな予算配分の仕方だと冬の時代に凍死してしまうけどな
Re: (スコア:0)
ニューラルネットワークであれば30年ほど前にブームがあったような
Re: (スコア:0)
家電製品、マイコン制御→ニューロファジー→AIと、同じことを名前を変えてるだけの様に感じられて仕方がありません。
Re: (スコア:0)
おっとシャープの悪口はそこまでだ
Re: (スコア:0)
文科省の馬鹿官僚が研究なんて何も知らないくせして
ムーンショットだかなんだか知らんが間違った予算配分するのが悪いんだろ
誰か教えてください (スコア:0)
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)
・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
Re: (スコア:0)
答え知ってて聞いてるんでしょ
Re: (スコア:0)
だいたいあってることが保証されてるのが前者。(あってると言った)
だいたいあってるつもりなのが後者。(あってるとは言ってない)
Re: (スコア:0)
書いてあるまんまだと思いますが。。。
例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、
近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。
ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
Re: (スコア:0)
ただしab→ただしa<b
Re: (スコア:0)
それって単に局所解ですよね。
ヒューリスティクスや量子アニーリングって局所解に(も)近似しちゃうの?
Re: (スコア:0)
パラメータ次第ですね
谷(局所解)から別の谷に行くためには、ポテンシャルの山を越える必要があるので、それを越えられるようなパラメータ(打切り条件)が必要です
ただこの条件が緩すぎると収束せずにずっと探索して効率悪くなる
# 遺伝的アルゴリズムだと突然変異でこれを越えるんだけど、その発想は面白いなと思ったし、自然界すげーとも思った
なお量子ゲートを使った量子コンピュータだと、量子ビットが十分なら最適解が求まるはず
Re: (スコア:0)
違います。その理解だと、「近似アルゴリズム」で最適解まで到達できちゃいませんか? aのくぼみの近くに居るならそこから単純に坂を下ればaの底に到達できるので。くぼみが無数にある場合でも、a<b<c<d<…だったら、こっちの方が小さい、を繰り返してaに到達できそうですし。
a、b、c、…と無数にくぼみがあって究極のくぼみがzだった時に、zの定数倍以内に収まるくぼみが必ず選ばれる、というような保証があるものが近似アルゴリズムです。他にも設定した以上の確率で必ずzに到達できる近似アルゴリズム、とか、保証される内容は色々です。
要は、
Re: (スコア:0)
解が有理数であればね。
Re: (スコア:0)
「求まった解はおそらく最適ではないけど、最適解より高々x%しか悪くはないことは証明できる」ってやるのが近似解。xは好きに設定できて、小さくするとより大幅に計算に時間が掛かるようになる。もちろん、x=0にすると計算量が指数オーダーを超えるか、アルゴリズムの制約上そうはできないか。
保証がない方はそのまま。どんな値が求まってるんだか分からない。近似比保証のあるアルゴリズムとか他の方法とかで求めた結果と比べてみた範囲ではそんなに悪くは無さそう、というやり方。運が悪いととんでもなく悪い解になっているかも知れないけど、その分、計算は無茶苦茶速い。
Re: (スコア:0)
これが学会で皆が戦慄するという、
「わたくしこの分野は専門外なのですが」か。
一瞬で解けるならクラウド一機でいいじゃん (スコア:0)
実際には落ち着くまで時間かかるはずでしたが。
よくわからんが (スコア:0)
量子コンピュータは量子力学で使われている数学技法を使っているだけで、
物理的な量子とは無関係、これで合ってる?
昔の知識しかないけど、行列式と微分方程式が等価、という部分を使っているのかな?
シュレディンガーとハイゼンベルクが元になってる。
Re: (スコア:0)
合ってない。
Re: (スコア:0)
Re:よくわからんが (スコア:1)
量子コンピュータに小判だな
Re: (スコア:0)
> 物理的な量子とは無関係、これで合ってる?
合ってない。
Re: (スコア:0)
量子コンピュータは量子もつれ、重ね合わせ、量子トンネリングなどを使った量子のふるまいそのものを利用する計算方法ですよ
もちろんそれをシミュレーションすることで実現しているハードもあるので、それは数学技法と言えるかもしれませんが……
Re:よくわからんが (スコア:1)
> シミュレーションすることで実現しているハードもある
量子アルゴリズムのテストには使えても量子超越性は無いのでそれは量子コンピュータでは無い
量子ゲート方式にあるよくある誤解 (スコア:0)
量子アニーリング方式と量子ゲート方式を混同させて
「あの現代の暗号システムを崩壊させる量子コンピュータが完成しただと!?よしっ!○○の株を売れ(買え)!!」
みたいな誤解もあるけど、
量子ゲート方式でよくある誤解は、「量子状態の重ね合わせを使って複数の組合せパターンを1回で計算できる」というもの。
複数のパターンを量子状態の重ね合わせで一気に計算できたとしても、観測することで取り出せる計算結果は1個だけなんで、問題を解くプログラムだけじゃなく、欲しい結果を観測できる確率が高くなるようにするアルゴリズムも必要で、それが使えるのは限定的だったはず。