人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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()は緩やかに変化する。

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

●質問者: jeak
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:X1 アルゴリズム スカラー パラメータ 変数
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● minkpa
●27ポイント

http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%A5%E3%83%BC%E3%83%A...

ヒューリスティクス

◎質問者からの返答

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

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


2 ● kawashima58
●27ポイント

http://www.ism.ac.jp/~tsuchiya/sympo/shukai05/pr05.txt


3 ● fumi95
●26ポイント

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)に変更する」とするべきでしょう.


以上,ご参考になれば.

◎質問者からの返答

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

ありがとうございます。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ