アカウント名:
パスワード:
にもかかわらずGEQOを使うのは、大量のJOINを伴うようなプランの取りうる組み合わせが爆発した場合に時間がかかりすぎるからなのです。最適なプランを導くのが理論的に可能だとしても、それによって得られる恩恵以上に計算量が増えてしまえばなんの意味もないです。
そういう意味ではそれなりの計算量である程度の効果が見込めるGAは有効になり得ます。まあ、最適値がみつかるかというと評価関数のばらつきとかがあるだろうから難しいんでしょうが・・・
殆どのケースで最適解への収束が行われるでしょう
そういうのは「保証」って言わないんですよ。
DBの問い合わせプランの最適化って、大抵は、最適解じゃなくて、近似解だと思うのですけど。
最適化には二種類あって、コンパイラとかタスクスケジューラの最適化って、基本的に最適解を求めないってのが大半で、それでも最適化っていってる気がします。そういう場合は、最適解への収束をそも
DBの問い合わせプランの最適化って、大抵は、最適解じゃなくて、
もちろん評価関数の問題で、それが現実には最適解じゃない可能性もありますが:D
はっきり言っておくと、DBの問い合わせプランは順列組み合わせ問題に近く、テーブルのJOINやインデックスの選択肢が少ない殆どのケースでプラン数が数個~数十個しかなく、通常全件調査してもコスト場問題ない、と書けば満足ですか?
あなたがPostgreSQLに詳しいのは分かりましたから。
遺伝的アルゴリズムは、mutationがあるのでどんな問題でも 必ず最適解に収束しますよ。
残念。突然変異は局所最適からの脱出を可能にさせるだけで、大域的最適解への到達を保証するものではありません。もちろん、繰り返しを増やせばその確率は高まりますが、それは「理論
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
あと、僕は馬鹿なことをするのは嫌いですよ (わざとやるとき以外は)。-- Larry Wall
収束性 (スコア:0)
本当に?最適解への収束性が理論的に保証できるようなやさしい問題なら、そもそもGAなんてくだらない方法は使わない方がいいのに。
保証できないような問題に使うからこそGAやニューラルネットワークのような黒魔術の存在価値があるわけで。
まあ単にタレコミ人が無知なだけだろうけど、と思ったら書きおろしかよ…
Re:収束性 (スコア:3, 興味深い)
にもかかわらずGEQOを使うのは、大量のJOINを伴うようなプランの取りうる組み合わせが爆発した場合に時間がかかりすぎるからなのです。最適なプランを導くのが理論的に可能だとしても、それによって得られる恩恵以上に計算量が増えてしまえばなんの意味もないです。
そういう意味ではそれなりの計算量である程度の効果が見込めるGAは有効になり得ます。まあ、最適値がみつかるかというと評価関数のばらつきとかがあるだろうから難しいんでしょうが・・・
Re:収束性 (スコア:0, フレームのもと)
Re:収束性 (スコア:1)
Re:収束性 (スコア:1, すばらしい洞察)
いや、だからそこが問題なんだって指摘されてるんですけど、わかりませんか?
ここで問題になってるのは「理論的に最適解への収束を保証できる問題にGAを適用することの意味」です。そこへいきなりあなたが「理論的な最適解への収束保証」のない事例を持ち出してきたから、的がはずれてるのです。他の人も指摘してますが、あなたが出してきた例では、GAによって得られるのはあくまで近似解(最適解の保証なし)で、もちろん最適解への収束保証もありません。
理論的な最適解への収束保証ができない場合にGAを使うことについて、馬鹿らしいなどと言ってる人は誰もいませんよ。そう言ってる人間がいるとあなたが思い込んでるだけで。もうちょっと落ち着いて、他の人のコメントを読むようにしたらいいと思います。
それから、最適解と近似解の違いや、収束保証の意味も勉強された方がいいですね。基本がまるで理解できていないようですから。
Re:収束性 (スコア:0)
>きる問題にGAを適用することの意味」です。
へー、カーネルチューニングの問題は理論的に最適解への収束を
保証できるんだ。へー。
Re:収束性 (スコア:0)
DBの問い合わせプランの最適化って、大抵は、最適解じゃなくて、近似解だと思うのですけど。
最適化には二種類あって、コンパイラとかタスクスケジューラの最適化って、基本的に最適解を求めないってのが大半で、それでも最適化っていってる気がします。そういう場合は、最適解への収束をそも
Re:収束性 (スコア:1)
もちろん評価関数の問題で、それが現実には最適解じゃない可能性もありますが:D
Re:収束性 (スコア:0)
あなたがPostgreSQLに詳しいのは分かりましたから。
Re:収束性 (スコア:1)
はっきり言っておくと、DBの問い合わせプランは順列組み合わせ問題に近く、テーブルのJOINやインデックスの選択肢が少ない殆どのケースでプラン数が数個~数十個しかなく、通常全件調査してもコスト場問題ない、と書けば満足ですか?
Re:収束性 (スコア:1)
>
>本当に?
"無限世代"or"無限の個体"とか極限での話なのかな?
GA がどういう条件で巧くいくのか知らないので、
詳しい人に聞いてみたい部分です。
#そんなにやるなら、(連続問題でない限り)全探索と
#同じだと思いますが。
> ニューラルネットワークのような黒魔術
そんなに、黒魔術ですかね?
結構有名なニューラルネットの 多層パーセプトロン [google.com]
の有名な学習方法バックプロパゲーション [google.com]も
勾配法で二乗誤差を最小化してるだけだと思いますが。。。
# もっとも"ニューラルネットワーク"じゃ何を指してるか分からない
# ぐらい多種多様な"ニューラルネットワーク"があるわけですが
Re:収束性 (スコア:1)
・全探索すれば必ず最適なパラメータが見つかる問題である。
・計算量の問題があって全探索できない。
てな場合です。
突然変異があるので無限時間走らせれば全探索になります。
実用的には突然変異の確率をだんだん下げていくし、交配やら突然変異やらによる解の改善があんまりなくなっちゃった所で止めてパラメータ固定しちゃうわけですが。
まあ実用的な時間で「そこそこ近い」パラメータを出したい時に使う解法です。
完全な最適解以外でも十分役に立つような場合にはぴったり。
でも全探索できるような問題に使うのはただのムダですね。
Re:収束性 (スコア:0)
Re:収束性 (スコア:1)
NP困難 (NP-hard) というキーワードもつけておきます。
GAは多項式オーダー(時間)で解けない問題の近似解を求めるのに
よく使われます。
Re:収束性 (スコア:2)
ただ実際問題として,スケジューリングなど多くの問題では
最適解でなくとも最適に近い解が得られればそれで十分なので
GAのようなアルゴリズムが利用できるわけです.
Re:収束性 (スコア:0)
> NP困難 (NP-hard) というキーワードもつけておきます。
間違えてるのはあなたでは?
そもそもこの「カーネルのパラメータの最適化」という問題がNP困難だということは示されているのでしょうか?さらに、NP困難かどうかは解法には依存しません
Re:収束性 (スコア:0)
必ず最適解に収束しますよ。
もちろん、現実的な時間で最適解にたどり着くかどうか
は別問題ですが。
Re:収束性 (スコア:0)
なさそうですよね。
Re:収束性 (スコア:0)
残念。突然変異は局所最適からの脱出を可能にさせるだけで、大域的最適解への到達を保証するものではありません。もちろん、繰り返しを増やせばその確率は高まりますが、それは「理論
Re:収束性 (スコア:0)
大域的に必ず収束します。確率1ですよ。
大学の教養で習った「収束」の定義を思い出してみましょう。
ただ、現実的なことを考えると収束しても意味はないんですが。