私には機能があり、
P(x0, x1, ..., xn)
入力として100個の整数を取り、出力として整数を与えます。P は評価するのに時間がかかる関数です (30 秒から数分の範囲になる場合があります)。
P から得られる値を最大化するポイントの値を知る必要があります。
これを達成するためにどのようなテクニックを使用できますか? 一般に、人々はこれに遺伝的アルゴリズムを使用することを知っていますが、人口が少なく世代が少ない場合でも (たとえば、人口 = 50、世代 = 50)、P はそうです。遅いと、計算に 40 時間以上かかります。
安く済ませる方法はありますか？多分反復プロセス？本当に最適である必要はありませんが、それがどのように動作するかについてのアイデアはありません（線形/二次/指数関数を試しましたが、良い値が得られないようです.Pが返されることはわかっています私が得ている値よりも少なくとも5〜10倍優れています）。
より簡単に実装できるものにする必要があります (つまり、自分で実装する必要があります)。
ありがとう
編集: P は確率過程です。
マルコフ連鎖モンテカルロ (MCMC)と密接に関連するシミュレーテッド アニーリング。おそらく必要なバリアントはMetropolis-Hastingsです。コツをつかめば、なかなかいいものです。入力と結果はすべて整数であるため、最適化する方法がいくつかある可能性があります。計算量が多く、多少の調整が必要になる場合がありますが、非常に堅牢であり、他の方法でこれ以上うまくいくかどうかはわかりません.
これを行うための脳死のコードを次に示します。
const int n = 100; // length of vector to optimize
int a[n]; // the vector to optimize
double P(a){..} // Get the probability of vector a.
// This is the function to optimize.
// for a large number of a samples
for (i = 0; i < large_number; i++){
// get P(a)
double p = P(a);
// for each element of vector a
for (j = 0; j < n; j++){
// get an amount by which to change it. This choice has to be symmetric.
// this is called the Proposal Distribution
int step = uniform_random_choice_from(-2, -1, 1, 2);
// make the change to a[j], and get p1, the new value of p
a[j] += step;
double p1 = P(a);
bool bKeepTheStep = true;
// if p1 is better than p, keep the step
// if p1 is worse than p, then keep the step p1/p of the time
if (p1 < p){
bKeepTheStep = (unif(0,1) < p1/p);
}
if (bKeepTheStep) p = p1;
else a[j] -= step;
}
// now a is a sample, and p is its value
// record a and p
}
// what you have now is a large random sampling of vectors from distribution P
// now you can choose the best one, the average, the variance,
// any statistic you like
それを微調整する方法は、提案の分布を広げたり狭めたりすることです。そのため、ステップを大きくしたり小さくしたりできます。または、最初に大きなステップを実行してから小さなステップを実行することもできます。探しているのは、高すぎず低すぎずに保持されている歩数のパーセンテージです。モードの領域を探している間に、破棄する最初の 1k 程度のサンプルの「焼き込み」フェーズが必要になる場合があります。
そしてぜひ、プロファイル P を。できるだけ高速にする必要があります。これが私のお気に入りの方法です。
ここにリストされているさまざまな確率的最適化手法を見てください。シミュレーテッド・アニーリングをお勧めします。
別の完全に深刻な答えではありませんが、検討の余地があります。
この問題は非常に大きいように見えるので、当然のことながら、それを解決するには SETI@Home のような取り組みが必要です。数千台のコンピューターが、この種の作業を適度に軽くします。しかし、何千人ものコンピュータ ユーザーに彼らのコンピュータを使用してもらうためにどのように手を差し伸べるかはわかりません。
実際、そうです。そのすべての合法性を無視することで、しばらくの間ご容赦ください.
かつての鉄のカーテンの背後に隠れている何人かの人々によって実行されているボットネットがあります。最近、ボットネットを 24 時間 70 ドルでレンタルするというオファーを見ました。考えてみてください。数千台の所有 PC があなたの入札に応じる準備ができています! 彼らに DDOS インターネット サイトを用意する代わりに、彼らに問題をかき回してもらうことができます。:)
ただし、これに関する最後の 2 つのアドバイス:
幸運を！
大域的最大値を見つけることができるよく知られた大域的最適化アルゴリズム (シミュレーテッド アニーリング、確率的トンネリングなど) はたくさんありますが、その形状についての仮定を行わずに合理的な時間内にそれを見つけることが保証されているものはありません。関数。
100 次元の自明ではない関数を最適化するための高速で簡単な方法を見つけることはできません。多くの処理能力と時間が必要になります。（質問に基づいて）自分で最適化コードを書きたくない場合は、優れた数学ソフトウェア（Mathematica など）も必要になります。
おそらく、アルゴリズムのかなりの部分が並列化可能ですか? もしそうなら、コードの並列化を検討しましたか?
このタイプの問題の最初のアルゴリズムとして、シミュレーテッドアニーリングをお勧めします。SAは、開始点と実行時間を明確に制御できるため、最初の選択肢として最適です。
100次元空間の構造について何か知っている場合は、SAを使用すると、適切な開始点を選択でき、結果の品質に大きな影響を与える可能性があります。また、SAを使用すると、実行時間と結果の品質の両方に影響を与える「冷却速度」を制御できます。当然、反対方向になります。私は通常、最初に比較的速い冷却速度で実行して適切な開始ベクトルを探し、その後の実行で冷却速度を遅くして結果を改善します。自動化できる一種のメタSA技術。
私はSAを使用して、過去に中性子陽子相互作用のモデル化に使用された非常に高次元の関数を最大化することに成功しました。
また、可能であれば、P（）を次元的に減らすことを検討します。特定の問題については、100個の変数すべてが必要ですか？それらの1/2を修正できれば、オプティマイザーを高速化し、より良い結果を得ることができます。
（そしてSAは簡単に実装できます。）
仮定:
まず、変数は整数でなければなりません。
2 番目 - 目的関数 P() は非線形です。
観察：
一般に、非線形整数計画法は解くのが非常に困難です。実際には、上で推奨されているように、整数制限を緩和して解を丸めることが役立つ場合があります。
利用可能な一般的な制約のない最適化手法があります。実験計画法に由来する 1 つのアプローチは、「応答曲面法」と呼ばれるものです。実験のコストが大きい場合に非常に役立ちます。このアプローチは、1 つのポイントから始めて、各入力を一定の増分だけずらして、一連の実験を実行することです。次に、各入力の勾配を計算し、それぞれについてその方向に一歩進み、繰り返します。Fletcher - Practical Methods of Optimization と Box Hunter & Hunter Statistics for Experimenters を参照してください。
Microsoft ソリューションがオプションである場合は、Solver Foundationを確認してください。Scott Hanselman のポッドキャスト ( #191 )で聞いたことがあります。
ニューラル ネットワーク:D またはテイラー級数?
matlab にアクセスできる場合は、コードを非常に高速かつ簡単に並列化できます。parfor ループと並列に単純な線形 for ループを作成することもできます