以下の関数の最大値を求めるような最適化アルゴリズムを探しています。


Y = f(X_1, X_2, ..., X_n)
各X_kは1からaまでの整数値
パラメータnは50~250程度、パラメータaは5~20程度の整数値

(特徴)
・Xの値にスカラー的な意味は無い、X∈{x1, x2, ..., xn}のような意味合い ← 数学家ではないので厳密な意味ではないかもしれない
・任意のX_pとX_q(X_p≠X_q)を入れ替えた場合、かなり高い割合(~90%程度)でf()は等しい値となる
・特異点?は無し、どの変数Xを変えてもf()は緩やかに変化する。

現在は遺伝的アルゴリズムを使って実装していますが、もっと効率の良い方法はないでしょうか?
適用方法含めご教授お願いします。

回答の条件
  • 1人2回まで
  • 登録:2007/07/10 22:50:51
  • 終了:2007/07/17 22:55:03

回答(3件)

id:minkpa No.1

minkpa回答回数4178ベストアンサー獲得回数552007/07/12 06:25:31

id:jeak

遺伝的アルゴリズムはヒューリスティクスの一種だと思いますが・・

できれば具体的な方法が欲しいです。

2007/07/12 20:13:27
id:fumi95 No.3

fumi95回答回数1ベストアンサー獲得回数02007/07/14 01:49:16

ポイント26pt

Simulated Annealing(焼きなまし法)は如何でしょうか?

焼きなまし法 - Wikipedia


とはいえ,ご質問で提示されている情報からどのような方法が良いかは,

私にはわかりかねますので,以下,参考になるかもしれないことを書いてみます.


まず,GAが上手く働くためには,ビルディングブロック仮説が成り立つ必要があります.

ものすごくおおざっぱに言うと,「優秀な部分解が組み合わさって良い解が生成される」という性質を満たしていなければなりません.

今回の例で言うと,例えば,{X_1=2, X_2=4}という部分解を含む解が良い評価値を持つ傾向があり,かつ{X_3=9, X_4=16}という部分解を含む解が良い評価値を持つ場合に,

{X_1=2, X_2=4, X_3=9, X_4=16}という部分解を含む解がやはり良い評価値を持つかどうか,ということです.

この性質を満たさない場合には,交叉オペレーションが効いてきませんので,GAは有効には働かないはずです.


また,GAとSA(例えば)のどっちが良いかという問題もあるのですが,

それ以前に近傍の定義も重要な問題です.

例えば,「任意のX_pとX_q(X_p≠X_q)を入れ替えた場合、かなり高い割合(~90%程度)でf()は等しい値となる」

と文中にありますので,「X_pとX_qを入れ替える」というオペレーションで近傍を生成するのは,明らかに無駄です.

また,「Xの値にスカラー的な意味は無い」とありますので,

「Xの値を1だけ加えるか減ずる」というオペレーションで近傍を生成するのも根拠がなく,

この場合は「Xの値をY(≠X, 1<=Y<=a)に変更する」とするべきでしょう.


以上,ご参考になれば.

id:jeak

結局のところ、X→X+ΔXとしてΔXをどう与えてやるか、という問題に帰結するんでしょうね。

ありがとうございます。

2007/07/14 14:52:59

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません