高次元多峰性目的関数の数値最適化アルゴリズム

質問

高次元多峰性目的関数の数値最適化アルゴリズム

高次元で多峰性のある微分不可能な目的関数を
ある制約条件の下で最大化するためのアルゴリズムを
調べていますが、たくさんあり過ぎて、結局どれが
もっとも有効な手法なのかがわからないままです。
学会でのコンセンサスがどうなっているのか教えて
頂けないでしょうか？

※以下、補足的な内容です。

ちなみに、アルゴリズムとしては

Artificial Bee Colony (ABC) Algorithm
Bacterial Foraging Optimization (BFO)
Differential Evolution (DE) Method 微分進化法
Downhill Simplex Method 滑降シンプレックス法
Genetic Alogorithm (GA) 遺伝的アルゴリズム
Particle Swarm Optimization (PSO) 粒子群最適化
Simulated Anneling 焼なめし法

などがあるようです。ABCアルゴリズムの開発者の論文

Karaboga and Basturk (2007) ``A powerful and efficient
algorithm for numerical function optimization: artificial
bee colony (ABC) algorithm,'' J. Global Optimization 39, pp. 459-471.
http://sci2s.ugr.es/EAMHCO/pdfs/ABC-algorithm-numerical-function-2007.pdf

によると、ABCはGA、PSOよりも優れているという結果を
得ています（といってもGAとPSOのパラメータの設定等に
恣意性があるのでなんとも言えません）。ただ、自分で
書いた、Karaboga and Basturk (2007)が扱ったのよりも
もっと複雑なGAでも同じように高次元になってくると
早熟収束が簡単に起きてしまうのでGAは信頼してません。

まだまだ発展分野というか何でも有りの研究分野っぽいので
次から次へと新しいアルゴリズムが提案されてすべてを
カバーするのは不可能に近いと思います。既に認知されている
物の中でも高次元多峰性関数の最適化に適していると
考えられているアルゴリズムは一体どれなのでしょうか。
専門外の人間でただ数値最適化を行いたいだけなので、
あまりサーベイに時間をかけていられなくて、みなさんの
お力をお借りしたいと思っています。
どうぞよろしくお願いします！

回答No.1

ur2c

主に simulated annealing を使った者で、専門家ではありません。

> どれがもっとも有効な手法なのか
> 学会でのコンセンサスがどうなっているのか

「まだ決定打はない」が共通認識と思います。

「特効薬のある病気なら、誰がやっても同じ治療法になる。いろんな対処法があるということは、何を試してもなかなかうまく行かないということだ。」と先生から聞きました。高次元多峰の最適化法にいろんな流派があるのは、それと同じでしょう。論文を比較しても、あまり参考になりません。舞台裏で問題に合わせた調整をさんざんやって、最高の性能がうまく出た例だけを紹介してますので。

だから手法を選択するには「有効性」の評価に番外の基準を用いるべきと思います。たとえば説明や実装が簡単とか、調整が楽とか。

お礼

ご回答ありがとうございます。

その方の仰ってることは鋭いですね。
確かに、そういうことなんでしょうね。
問題に合わせて試行錯誤するしかないと。
あまり最適化に時間を掛けたくない者としては
嬉しくないですが・・・

アルゴリズムの比較について。
いろいろと調べているとわかったのですが、
アルゴリズムの評価の際に使われる関数は
大体決まっているようですね。
http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO_files/Page364.htm
ただ、多峰性関数にもいろいろあるので、
その中でどれを使うか、というのに恣意性があるようです。

個人的には、その恣意性をなくして、すべての
関数でテストするというルールを作るべきではないかと。
多峰性関数でも特徴Ａを持つ関数にはこのアルゴリズムが、
特徴Ｂを持つ関数にはあのアルゴリズムが、という
議論ができると思うので。
あと、比較として用いられるアルゴリズムの
ベンチマークを学会で決めるとか。例えば、ＧＡと
比較するなら、このＧＡを使わないといけない、とか。

ur2cさんが仰られる「有効性」（実装が簡単か否か等）も
もちろん大切だと思います。ただ、いくら簡単でも
結局解けなければ意味がないというのがあるので、
まずは上記に書いたように恣意性を無くしてほしいです。