55

私はかなりの数の遺伝的アルゴリズムを作成しました。それらは機能します (合理的な解決策をすばやく見つけます)。しかし、私は今TDDを発見しました。遺伝的アルゴリズム(乱数に大きく依存している)をTDDの方法で書く方法はありますか?

より一般的に質問を投げかけるには、非決定論的なメソッド/関数をどのようにテストしますか。これが私が考えたことです:

  1. 特定のシードを使用します。そもそもコードを間違えた場合は役に立ちませんが、リファクタリング時にバグを見つけるのに役立ちます。

  2. 番号の既知のリストを使用します。上記と同様ですが、コードを手でたどることができます (これは非常に面倒です)。

  3. 定数を使用します。少なくとも私は何を期待すべきか知っています。RandomFloat(0,1) が常に 1 を返す場合、サイコロの目が常に 6 になるようにするとよいでしょう。

  4. 非決定論的なコードをできるだけ GA から移動するようにしてください。それがその目的の核心であるため、これはばかげているようです。

テストに関する非常に優れた書籍へのリンクも歓迎します。

4

10 に答える 10

14

その一貫したロジックをテストする唯一の方法は、一貫した入力を適用することです...または、各反復を、その反復の前後に状態がテストされる単一のオートマトンとして扱い、非決定論的システム全体を決定論に基づくテスト可能なコンポーネントに変えます。反復値。

反復におけるバリエーション/育種/属性の継承については、各反復の境界でこれらの値をテストし、成功した反復サブテストからの既知の入力/出力に基づいて、すべての反復のグローバル出力をテストします...

アルゴリズムは反復的であるため、テストで帰納法を使用して、1 回の反復で機能することを確認できます。n+1 回の反復で、特定の入力範囲/ドメインと可能な値の制約に対して (データ決定論に関係なく) 正しい結果が生成されることを証明できます。入力で。

編集いくつかの洞察を提供する可能性のある非決定論的システムをテストするためのこの戦略を見つけました。TDD/開発プロセスがロジックが適切であることを証明したら、ライブ結果の統計分析に役立つ場合があります。

于 2009-06-24T15:33:01.947 に答える
4

ランダム関数を何度もテストし、戻り値の分布が統計的期待を満たしているかどうかを分析することで、ランダム関数をテストします (これには統計的知識が必要です)。

于 2009-06-24T15:48:03.413 に答える
2

TDDについて話している場合は、定数を選択し、そこからテストスイートを拡張することから始めます。私はいくつかの非常に数学的な問題についてTDDを実行しました。それは、あなたが知っていて、最初から実行するために手作業で解決したいくつかの一定のケースを持つのに役立ちます。

4番目のポイントであるW/R / Tでは、非決定論的なコードをGAから移動します。これは、おそらく検討する価値のあるアプローチだと思います。アルゴリズムを分解して非決定論的な懸念を分離できれば、決定論的な部分のテストが簡単になるはずです。名前の付け方に注意している限り、ここで多くの犠牲を払っているとは思いません。私があなたを誤解しない限り、GAは引き続きこのコードに委任しますが、それは別の場所にあります。

私のお気に入りの(開発者)テストに関する非常に優れた本へのリンクは次のとおりです。

于 2009-06-24T17:07:55.770 に答える
2

GA アルゴリズムの非決定論的関数の単体テストのために私が行う 1 つの方法は、その乱数を使用するロジック 1 の別の関数に乱数の選択を配置することです。

たとえば、遺伝子 (何かのベクトル) を受け取り、遺伝子の 2 つのランダムなポイントを取得して何か (突然変異など) を行う関数がある場合、乱数の生成を関数に入れることができます。次に、それらを遺伝子とともに、その数値が与えられたロジックを含む別の関数に渡します。

このようにして、ロジック関数を使用して TDD を実行し、特定の遺伝子と特定の数値を渡すことができます。その数値が与えられた遺伝子に対してロジックが何をすべきかを正確に把握し、変更された遺伝子にアサートを書き込むことができます。

乱数の生成をテストする別の方法は、その生成を別のクラスに外部化し、コンテキストを介してアクセスしたり、構成値からロードしたりして、テストの実行に別のクラスを使用することです。そのクラスには 2 つの実装があります。1 つは実際の乱数を生成する本番用で、もう 1 つはテスト用で、後で生成される数値を受け入れる方法があります。次に、テストで、クラスがテスト対象のコードに提供する特定の数値を指定できます。

于 2012-12-23T14:18:15.353 に答える
1

C# TDD 遺伝的アルゴリズムの教訓的なアプリケーションを作成しました: http://code.google.com/p/evo-lisa-clone/

アプリケーションで最も単純なランダム結果メソッドを見てみましょう: PointGenetics.Create は、境界を指定してランダム ポイントを作成します。この方法では、5 つのテストを使用しましたが、いずれも特定のシードに依存していません。

http://code.google.com/p/evo-lisa-clone/source/browse/trunk/EvoLisaClone/EvoLisaCloneTest/PointGeneticsTest.cs

ランダム性テストは単純です。境界が大きい場合 (多くの可能性があります)、2 つの連続する生成点が等しくならないはずです。残りのテストでは、他の制約をチェックします。

于 2009-07-02T17:03:13.713 に答える
1

冗長なニューラル ネットワークを記述して、アルゴリズムの結果を分析し、予想される結果に基づいて出力をランク付けすることができます。:)

できる限り方法を分解してください。次に、ランダムな部分だけを単体テストして、値の範囲を確認することもできます。テストを数回実行して、結果が変わるかどうかを確認してください。

于 2009-06-24T15:32:45.613 に答える
1

最もテストしやすい部分はフィットネス関数です。ここにすべてのロジックが配置されます。これは場合によっては非常に複雑になる可能性があるため (入力パラメーターに基づいてあらゆる種類のシミュレーションを実行している可能性があります)、そのすべてが多数の単体テストで機能することを確認したいと考えています。

GA パラメータ (突然変異率、クロスオーバー戦略など) のテストに関しては、それを自分で実装している場合は、確かにテストできます (突然変異ロジックなどの単体テストを再度行うことができます)。 GA の「微調整」をテストできます。

つまり、GA が実際に機能するかどうかは、見つかったソリューションの良さ以外にはテストできません。

于 2011-07-05T10:49:44.170 に答える
1

すべての関数は完全に決定論的でなければなりません。これは、テストしているどの関数も、関数自体の内部で乱数を生成してはならないことを意味します。それをパラメーターとして渡したいと思うでしょう。そうすれば、プログラムが乱数に基づいて決定を下すときに、代表的な数値を渡して、その数値の期待される出力をテストできます。決定論的であってはならない唯一のものは、実際の乱数ジェネレーターです。これは、自分で作成するべきではないため、あまり心配する必要はありません。確立されたライブラリである限り、それが機能すると想定できるはずです。

これは単体テスト用です。統合テストでそれを行っている場合は、乱数の生成をモックして、生成する必要があるすべての乱数に対して 0..n から既知の数値を返すアルゴリズムに置き換えることを検討できます。

于 2009-06-24T17:31:12.527 に答える
0

単体テスト ケース ( http://en.wikipedia.org/wiki/Mock_object ) にモック オブジェクトを使用することを検討することを強くお勧めします。それらを使用して、ランダムな推測を行うオブジェクトをモックアウトして、代わりに期待される結果を得ることができます。

于 2010-03-12T00:10:37.653 に答える
0

アルゴリズムが同じ入力に対して同じ結果を与えることをテストすることは役に立ちますが、アルゴリズムの結果選択動作を変更する変更を行う場合があります。

アルゴリズムが正しい結果をもたらすことを保証するテストを行うために、私は最大限の努力をします. アルゴリズムがいくつかの静的シードとランダム値に対して正しい結果を返す場合、アルゴリズムは機能しているか、変更によって壊れていません。

TDD のもう 1 つのチャンスは、アルゴリズムを評価する可能性です。結果の良さを自動的にチェックできる場合は、変更によって結果の品質が低下したり、計算時間が不当に増加したりしていないことを示すテストを追加できます。

多くのベース シードを使用してアルゴリズムをテストする場合は、保存のたびに開始するためのクイック テストを実行する 1 つのスーツをテストして、何も壊れていないことを確認する必要があるかもしれません。その後の評価

于 2009-06-24T15:42:35.733 に答える