6

関数 f(x,y) (x と y は整数) を最小化するための提案があるかどうか疑問に思っていました。私は、BFGS やその他の GSL の手法、数値レシピの手法など、多くの最小化および最適化手法を研究してきました。これまでのところ、いくつかの異なるスキームを実装しようとしました。最初の作業は、最大の降下 f(x+1,y),f(x-1,y),f(x,y+1),f(x,y-1) の方向を選択し、その方向に従います。行の最小化で。また、ダウンヒル シンプレックス (Nelder-Mead) メソッドを使用してみました。どちらの方法も、最小値から遠く離れて行き詰まります。どちらも、放物面の最小値を見つけるなど、より単純な関数で機能するように見えますが、両方、特に前者は、x と y が実数値 (double) である関数用に設計されていると思います。もう 1 つの問題は、f(x,y) をできるだけ少ない回数呼び出す必要があることです。外部ハードウェアと通信し、呼び出しごとに数秒かかります。これについてのアイデアは大歓迎です。

エラー関数の例を次に示します。申し訳ありませんが、私は前にこれを投稿しませんでした. この関数の評価には数秒かかります。また、デバイスからクエリした情報は、目的の値を下回っている場合はエラーに追加されず、上にある場合にのみ追加されます

double Error(x,y)
{
  SetDeviceParams(x,y);
  double a = QueryParamA();
  double b = QueryParamB();
  double c = QueryParamC();
  double _fReturnable = 0;
  if(a>=A_desired)
  {
    _fReturnable+=(A_desired-a)*(A_desired-a);
  }
  if(b>=B_desired)
  {
    _fReturnable+=(B_desired-b)*(B_desired-b);
  }
  if(c>=C_desired)
  {
    _fReturnable+=(C_desired-c)*(C_desired-c);
  }
  return Math.sqrt(_fReturnable)
}
4

8 に答える 8

4

ここには非常に多くのソリューションがあります。実際、主題に基づいた完全な本や学問分野があります。私は今、優れたものを読んでいます: How to Solve It: Modern Heuristics .

正しいソリューションは 1 つではありません。機能に関する特定の知識に基づいて、ソリューションが異なれば利点も異なります。すべての最適化タスクで最高のパフォーマンスを発揮するヒューリスティックは存在しないことが証明されています。

関数が 2 次であることがわかっている場合は、Newton-Gaussを使用して 1 ステップで最小値を見つけることができます。遺伝的アルゴリズムは、優れた汎用ツールになる可能性があります。また、より単純なシミュレーテッド アニーリングを試すこともできます。

于 2009-07-24T14:46:11.987 に答える
3

遺伝的アルゴリズムを見たことがありますか？それらは、局所的な最小値/最大値を回避しながら、最小値と最大値を見つけるのが非常に得意です。

于 2009-07-24T14:39:19.813 に答える
2

f(x,y) をどのように定義しますか? 関数の複雑さによっては、最小化は難しい問題です。

遺伝的アルゴリズムは良い候補になる可能性があります。

資力：

検索、最適化、機械学習における遺伝的アルゴリズム

C# での遺伝的アルゴリズムの実装

シンプルな C# GA

于 2009-07-24T14:40:48.407 に答える
2

それが任意の関数である場合、これを行うきちんとした方法はありません。

次のように定義された関数があるとします。

f(x, y) = 0 for x==100, y==100
          100 otherwise

最小値として (100, 100) を現実的に見つけることができるアルゴリズムはありますか? 可能な値の任意の組み合わせが可能です。

テストしている機能について何か知っていますか?

于 2009-07-24T14:40:46.007 に答える
1

それでは、数学の話であなたの問題を見てみましょう。これはすべて、私があなたの問題を完全に理解していることを前提としています。間違えた場合は、遠慮なく訂正してください。

以下を最小限に抑えたい：

\ sqrt（（a-a_desired）^ 2 +（b-b_desired）^ 2 +（c-c_desired）^ 2）

または他の表記法で||Pos（x --x_desired）|| _2

ここで、x =（a、b、c）およびPos（y）= max（y、0）は、「正の部分」が必要であることを意味します（これはifステートメントを説明します）。最後に、xが整数値である解に制限したいと思います。

上記のポスターとは異なり、遺伝的アルゴリズムはあなたが望むものではないと思います。
実際、解決策ははるかに簡単だと思います（私があなたの問題を理解していると仮定します）。

1）上記の関数で最適化ルーチンを実行します。これにより、解x ^ * =（a ^ *、b ^ *、c ^ *）が得られます。この関数は変数に関して増加しているので、期待できる最良の整数解は（ceil（a ^ *）、ceil（b ^ *）、ceil（c ^ *））です。

今、あなたはあなたの関数を評価するのはおそらく難しいと言います。ヒューリスティックに基づかないこのためのツールが存在します。Derivative-FreeOptimizationという名前で行きましょう。人々はこれらのツールを使用して、シミュレーションに基づいて目的を最適化します（目的関数が作物の鳴き声の収量に基づいている場合も聞いたことがあります！）

これらの方法はそれぞれ異なる特性を持っていますが、一般に、目的だけでなく、目的関数の評価の数を最小限に抑えようとします。

于 2009-08-13T00:36:40.450 に答える
1

あなたが一般的に探しているものは、数学の最適化手法と呼ばれています。一般に、これらは実数値関数に適用されますが、多くは整数値関数に適用できます。

特に、非線形計画法と勾配降下法を調べることをお勧めします。どちらもあなたのアプリケーションに非常に適しているようです。

もう少し詳しく教えていただければ、もう少し具体的な提案ができるかもしれません。

于 2009-07-24T14:51:24.863 に答える
1

ジョンスキートの答えは正しいです。f に関する情報が本当に必要であり、 f がどこでも連続している場合でも、その導関数です。

あなたが尋ねることの難しさを理解する最も簡単な方法（整数値での f の最小化のみ）は、大きなエクスカーションを行う 1 つの変数の f: R->R (f は実数の実数値関数) について考えることです。個々の整数の間。このような関数は、実線上の極小値と整数の極小値の間に相関関係がなく、一次導関数との関係がないように簡単に作成できます。

任意の関数については、ブルートフォース以外に方法がありません。

于 2009-07-24T15:26:28.270 に答える
0

申し訳ありませんが、以前はフォーマットが非常に悪かったです。エラー関数の例を次に示します。

double Error(x,y)
{
SetDeviceParams(x,y);
double a = QueryParamA();
double b = QueryParamB();
double c = QueryParamC();
double _fReturnable = 0;
if(a>=A_desired)
{
  _fReturnable+=(A_desired-a)*(A_desired-a);
}
if(b>=B_desired)
{
 _fReturnable+=(B_desired-b)*(B_desired-b);
}
if(c>=C_desired)
{
  _fReturnable+=(C_desired-c)*(C_desired-c);
}
return Math.sqrt(_fReturnable)
}
于 2009-07-24T15:26:58.053 に答える