1

マシンが異なれば答えも違うと思いますが、このテストは同じマシンで行われているとしましょう。

実際、私は、遺伝的アルゴリズムを私の問題の1つに実装する価値があると考えています。これは、約20の組み合わせ/順列があると思います。（！はfactoriaであり、実際には20ではなく、多かれ少なかれ可能性があります）。

数が許容範囲内である場合、GAと可能性要因（クロスオーバー、突然変異率）を設計することは容易ではないため、遺伝的アルゴリズムを使用することのブルートフォース（すべての可能性をループする）を使用します。

GAが問題のドメインに適しているかどうかをどのように判断しますか？

4

3 に答える 3

3

良い質問。正確な答えはありません。それは、いくつかの「親指のルール」と少しの論理に依存します。

私の提案：

  • 計算を行って、全数検索にかかる時間を計算します。これは比較的簡単なので、事前に見積もる価値があります。検索スペースが大きい場合（そして20！はおそらく十分に大きい場合....）、徹底的な検索は実用的ではない可能性があります。たとえば、各ソリューションの評価に1ミリ秒しかかからない場合は、20！まだ7700万年かかります。1000コアで並列検索を実行する場合でも、77000年かかります。
  • GAは通常、最適なソリューションを見つけられないことを忘れないでください。複雑な問題では、GAは「極小値」に収束することがよくあります。これがニーズに対して「十分」であるかどうかを判断する必要があります（多くの場合、そうです）。
  • 評価関数の計算コストが高い場合（たとえば、各ソリューションを評価するために小さなシミュレーションを実行する必要がある場合） 、GAは比較的優れていると考えてください。これは、高価な評価によってGAアルゴリズム自体のオーバーヘッドが基本的に無関係になるためであり、検索スペースでの膨大な数の不適合解の評価を回避できるため、価値があります。
  • ご指摘のとおり、 GAの設定と微調整には注意が必要です。特に、優れた遺伝子型表現とクロスオーバー/ミューテーション演算子を選択すると、アルゴリズムの効果に大きな違いが生じることがよくあります。また、人口の多様性をどのように維持するか、各世代をどれだけ大きくするかなどを意識する必要があります。GAをうまく実行することは、それ自体が公正なプロジェクトです。経験を積んで学ぶ。

もちろん、徹底的な検索もGAも問題に適していない可能性は十分にあります。いくつかの問題は他のアプローチによってはるかにうまく対処されます。動的計画法または分割統治法のいずれかを使用して特定の問題を解決するスマートアルゴリズムを見つけることができれば、7700万年の全数検索を実際に解決できることがわかります。ミリ秒。問題が十分に大きくなると、より優れたアルゴリズムは常に生の計算能力を上回ります。

于 2012-08-14T03:08:09.953 に答える
2

ソリューションのHadoopingまたは並列化を調査する必要があると思います。GAはそのようなアプローチに完全に適しているようです。

このように：

http://geneticalgorithms.ai-depot.com/Libraries.html

これは、元の質問を心配するよりもはるかに理にかなっています。答えは無意味です。なぜなら、あなたにとって重要な唯一の尺度は、ループがコードを含む本体をどれだけ速く処理できるかということだからです。

于 2012-08-14T02:37:15.387 に答える
1

20！かなり大きな数です。

コードの1回の反復を実行するのにどのくらい時間がかかりますか？

この整数の増分を使用して単純に計算できるループの数（時計の秒針のような粗いタイマーを使用して、間隔の最後に合計を読み取ります）。

x = 1; x！= 0 x = x+1ループの間に行う

ただし、コードはこれほど単純ではなく、各ループの処理に時間がかかり、ハードウェアのプロセッサ速度は考慮されません（これが主な懸念事項です）。duffymoが言うように、質問を無意味にする環境要因があります。

必要なものを見つけて頑張ってください。

于 2012-08-14T02:54:33.163 に答える