BRST_algorithm
Boender-Rinnooy-Stougie-Timmerアルゴリズム（BRST）を見つけるための適切な最適化アルゴリズムであるグローバル最適のブラックボックス機能を。彼らの論文では、Boender etal。 は、それらの方法を、サンプリング、クラスタリング、および局所探索の組み合わせを含む確率論的方法として説明し、グローバル最小値の信頼区間の範囲で終了します。
Boenderらのアルゴリズム。Timmerによって変更されました。 Timmerは、いくつかのクラスタリング手法を検討しました。実験に基づいて、「マルチレベルシングルリンケージ」という名前の方法が最も正確であると見なされました。
Csendesのアルゴリズムは、[Boender etal。] そして、パブリックドメインソフトウェア製品GLOBALを生み出しました。使用されるローカルアルゴリズムは、ランダム方向、Törnでも使用される線形探索アルゴリズム、および関数の導関数を使用しない準ニュートンアルゴリズムです。結果は、使用された補助ローカルアルゴリズムへの結果の依存性を示しています。
バックグラウンド
関数のクラスを拡張してマルチモーダル関数を含めると、一般に大域的最適化問題を解決できなくなります。解けるようにするためには、連続性に加えて関数の滑らかさの条件を知る必要が
いくつかの極小値の存在と一般に解けないことは、大域的最適化の重要な特徴です。ここでの解けないということは、有限のステップ数で解を保証できないことを意味します。解決不可能な問題に対処するには2つの方法がまず、fとAに「アプリオリ」条件が設定され、問題が解決可能なものに変わるか、少なくとも解決策が見つかったことを確認できます。これにより、考慮される関数クラスが制限されます。より大きなクラスの目的関数を検討できるようにする2番目のアプローチは、可解性の要件を放棄し、グローバル最小値の推定値を取得しようとすることです。この「確率的」アプローチでは、得られた推定値の良さについていくつかの結果を取得することも望ましいでしょう。保証されたソリューションに必要なステップ数が非常に多い可能性があるため、解決可能な問題の一部はこのクラスに分類される可能性が
可解性の要件を緩和する場合、手順を永久に継続できる場合は、解が得られる確率が1に近づくことを要求するのが合理的と思われます。明らかな確率的グローバル検索手順は、最適化領域全体に分散されたいくつかのポイントから開始するローカルアルゴリズムを使用することです。この手順は「マルチスタート」と呼ばれます。マルチスタートは確かに使用された最も初期のグローバル手順の1つです。得られた解の信頼性を高めるために、局所最適化でも使用されています。マルチスタートの欠点の1つは、多くの開始点が使用されると、同じ最小値が最終的に数回決定されることです。マルチスタートの効率を改善するために、これは避けるべきです。
クラスタリング手法は、極小値のこの繰り返しの決定を回避するために使用されます。これは、繰り返し使用できる3つのステップで実現されます。3つのステップは次のとおりです。（a）対象領域のサンプルポイント。（b）サンプルを変換して、極小値の周りにグループ化されたポイントを取得します。（c）クラスタリング手法を使用して、これらのグループ（つまり、極小値の近傍）を認識します。
これらの手順を使用する手順が成功した場合、各クラスターから単一のローカル最適化を開始すると、ローカル最小値が決定され、グローバル最小値も決定されます。このアプローチを使用する利点は、各最小値を1回だけ計算することで節約できる作業を、（a）と（b）の計算に費やすことができることです。これにより、グローバル最小値が見つかる可能性が高くなります。
ビーイングクラスタリング手法、その有効性は低次元の問題の方が高いと数百の変数を持つ問題にはあまり有効となります。
参考文献
^ Boender、CGE; AHG Rinnooy Kan; L. Strougie; GTティマー（1982）。「大域的最適化のための確率論的方法」 （PDF）。数理計画法。22：125〜140。土井：10.1007 / BF01581033。S2CID 545万。
^ Timmer、GT（1984）。「大域的最適化：確率論的アプローチ」（博士論文）。エラスムス大学ロッテルダム。
^ Csendes、T。（1988）。「大域的最適化による非線形パラメータ推定—効率と信頼性」。ActaCybernetica。8（4）：361–370。
外部リンク
http://www.abo.fi/~atorn/Globopt.html作者の許可を得て、テキストは逐語的にコピーされています。
Jankaは、BRSTが優れたパフォーマンスを示すさまざまな大域的最適化アルゴリズムを比較します。
Jankaは、Dixon-Szegöのテストセットで実行された関数評価の数を示します。MCSアルゴリズム、BRSTは、評価の最も小さい番号が必要です。