16

実行ごとに異なる結果を生成するいくつかの異なる最適化アルゴリズムがあります。たとえば、最適化の目標は、関数の最小値を見つけることです。ここで、0 はグローバル最小値です。最適化を実行すると、次のようなデータが返されます。

[0.1, 0.1321, 0.0921, 0.012, 0.4]

これは大域的最小値に非常に近いため、これで問題ありません。私たちの最初のアプローチは、しきい値を選択するだけで、高すぎる結果が発生した場合に単体テストを失敗させることでした。残念ながら、これはまったく機能しません。結果はガウス分布のように見えるため、可能性は低いですが、アルゴリズムがまだ問題なく、運が悪かっただけでも、テストが失敗することがあります。

では、どうすればこれを適切にテストできますか? ここではかなりの統計が必要だと思います。また、テストが依然として高速であることも重要です。テストを数 100 回実行して平均を取るだけでは遅すぎます。

ここにいくつかのさらなる説明があります：

  • たとえば、円を一連の点に合わせるアルゴリズムがあります。非常に高速ですが、常に同じ結果が得られるとは限りません。ほとんどの場合、それで十分であることを保証する単体テストを作成したいと思います。

  • 残念ながら、アルゴリズムが以前とまったく同じ結果を生成するかどうかをテストしたくないため、乱数ジェネレーターに固定シードを選択することはできませんが、「90% の確実性で 0.1 またはより良い"。

4

7 に答える 7

15

オプティマイザには 2 種類のテストが必要なようです。

  1. アルゴリズムの全体的な有効性のテスト
  2. アルゴリズムの実装の完全性をテストする

アルゴリズムはランダム化を伴うため、(1) は単体テストが困難です。ランダム プロセスのテストは、ある程度の割合で失敗します。失敗する頻度を理解するには、いくつかの統計を知る必要があります。テストの厳密さと失敗の頻度をトレードオフする方法があります。

ただし、(2) の単体テストを作成する方法はいくつかあります。たとえば、単体テストを実行する前に、シードを特定の値にリセットできます。その後、出力は決定論的です。これでは、アルゴリズムの平均的な有効性を評価することはできませんが、それは (1) のためのものです。このようなテストは、トリップ ワイヤーとして機能します。メンテナンス中に誰かがコードにバグを導入した場合、決定論的な単体テストがバグをキャッチする可能性があります。

単体テストできるものは他にもあるかもしれません。たとえば、ランダム化された部分で何が起こっても、アルゴリズムが特定の範囲の値を返すことが保証されている場合があります。たぶん、いくつかの値は常に正でなければなりません。

更新: この問題については、Beautiful Testing という本に章を書きました。第 10 章:乱数ジェネレーターのテストを参照してください。

于 2009-01-14T14:19:05.310 に答える
7

あなたのアルゴリズムにはおそらくランダムな要素があります。制御下に置きます。

次のいずれかを実行できます

  1. 呼び出し元が乱数ジェネレーターのシードを選択できるようにします。次に、テストでハードコーディングされたシードを使用します。
  2. 呼び出し元に乱数ジェネレーターを提供してもらいます。次に、テストで偽の乱数ジェネレーターを使用します。

アルゴリズムの正しい結果が何であるかを簡単に推論できるため、2 番目のオプションがおそらく最適です。

アルゴリズムの単体テストを行う場合、検証する必要があるのは、アルゴリズムが正しく実装されていることです。アルゴリズムが本来の機能を実行するかどうかではありません。単体テストでは、テスト対象のコードをブラック ボックスとして扱うべきではありません。

さまざまなアルゴリズムがどのように機能するか (および実際に機能するかどうか) を比較するために、個別の「パフォーマンス」テストが必要になる場合がありますが、単体テストは実際にはアルゴリズムの実装をテストするためのものです。

たとえば、Foo-Bar-Baz Optimization Algorithm (TM) を実装するときに、誤って x:=x/3 ではなく x:=x/2 と記述した可能性があります。これは、アルゴリズムの動作が遅くなることを意味している可能性がありますが、それでも同じアルゴリズムが検出されます。このようなエラーを見つけるには、ホワイトボックス テストが必要です。

編集：

残念ながら、アルゴリズムが以前とまったく同じ結果を生成するかどうかをテストしたくないため、乱数ジェネレーターに固定シードを選択することはできませんが、「90% の確実性で 0.1 またはより良い"。

自動検証可能で確率論的なテストを作成する方法がわかりません。特に、実際のエラーと統計ノイズを区別する機会が必要な場合はそうではありません。

「90% の確率で 0.1 以上の結果が得られる」ことをテストしたい場合は、次のようにすることをお勧めします。

double expectedResult = ...;
double resultMargin = 0.1;
int successes = 0;
for(int i=0;i<100;i++){
  int randomSeed = i;
  double result = optimizer.Optimize(randomSeed);
  if(Math.Abs(result, expectedResult)<resultMargin)
    successes++; 
}
Assert.GreaterThan(90, successes);

(このテストは決定論的であることに注意してください)。

于 2009-01-14T14:12:31.503 に答える
7

単体テストの合格/不合格の状態が不明であってはなりません。同じ入力で複数回実行したときにアルゴリズムが異なる値を返す場合は、おそらくアルゴリズムで何かおかしなことをしています。

5 つの最適化アルゴリズムのそれぞれを使用してテストし、一連の入力 x が与えられたときに、毎回最適化された y の値が得られることを確認します。

編集: システムのランダムなコンポーネントに対処するには、使用する乱数ジェネレーターのシードを渡す機能を導入するか、モッキング ライブラリ (ala RhinoMocks) を利用して特定の数値を使用するように強制することができます。 RNG は乱数を要求されます。

于 2009-01-14T14:02:34.627 に答える
5

テストを実行し、いずれかが失敗した場合は、それらのテストだけを50 回再実行し、失敗した時間の割合を確認します。（もちろん、自動化された方法で。）

于 2009-01-14T13:56:23.780 に答える
1

すべての答えをありがとう、私は今これをやっています：

  1. テストを5回実行し、結果の中央値を取得します。
  2. 結果の中央値が特定のしきい値を下回っている場合、テストは成功します。
  3. しきい値が失敗した場合は、しきい値に達するまで（テストが成功するまで）、または中央値がしきい値を下回らないことを確信できるほど多くの反復（約100回）を実行するまで、再度テストします。

このように、テストが失敗するように見えるときはいつでも、実際に失敗したことがかなり確実になるまで、テストは頻繁に再計算されます。

これはうまくいくようですが、結果の中央値をテストしているだけなので、私は完全には満足していません。

于 2009-01-15T07:36:13.160 に答える
1

ガウス分布を生成するコードに対してテストを実行するのではなく、メソッドを何度も実行するモンテカルロ タイプのアルゴリズムを作成し、適切な分布モデルを使用して結果の全体的な分布をテストすることをお勧めします。たとえば、それが平均値である場合、確定しきい値に対してテストできます。より複雑な場合は、適切な分布をモデル化するコードを作成する必要があります (たとえば、値 < x が結果の y% を構成します)。

数値ジェネレーターをテストしているのではなく、値を生成するユニットをテストしていることに注意してください!

于 2009-01-14T14:27:13.500 に答える
0

jUnit と NUnit はどちらも、許容誤差/デルタ値を持つ浮動小数点データ型をアサートできます。つまり、出力が正しい値であるかどうかをテストし、小数を指定または取得します。あなたの場合、チェックしたい正しい値は 0 で、指定された出力のすべての値を渡す場合は許容値 0.5 (または許容値 +/-0.20 の場合は 0.20) です。

結果はランダムな性質を持つため、アルゴリズムの一部を単体テストして、想定どおりに機能することを確認することができます。

于 2009-01-14T14:27:58.930 に答える