2

Gregory Chaitin のメタバイオロジー モデルに従って、進化のシミュレーションをハックしようとしています。

整数を返すアルゴリズムが与えられた場合、構文的に正しく、最終的に停止する別のアルゴリズムを取得しようとしてランダムに変更する必要があります。突然変異が本当にランダムである場合、取得したものが停止する有効なアルゴリズムであることを確認することは不可能です。

私の質問は次のとおりです。

  • これを行うのに最適なチューリング完全言語は何ですか?
  • この問題にすでに取り組んでいる遺伝的プログラミングの技術はありますか?

前もって感謝します

私は次のようなことを考えていました：

x <- x + 1
x <- x - 1
y <- x
if x != 0 goto label

これは完全なチューリングであり、変更は非常に簡単です。どう思いますか？

4

4 に答える 4

1

突然変異が本当にランダムである場合、取得したものが停止する有効なアルゴリズムであることを確認することは不可能です。

Robert B が指摘したように、一連のチューリング完全関数は最初の部分を満たしますが、ループの可能性を許容する問題の解決策はありません。ただし、可能性としてループを削除すると、いくつかの入力をフィードするたびに出力を提供できる式ツリーを生成できます。式ツリーのサイズは有限であり、終了が保証されています。別の言い方をすれば、実行時間が無限の式ツリーを取得するには、式ツリーに無限のノードが必要です (これには、無限の RAM またはディスクが必要です)。

問題に最小限の解決策を提供するために式ツリーを剪定する戦略があり、それらの戦略のいくつかは、ツリーのサイズをフィットネス関数の一部にすることを含みます。つまり、適合度を計算するときは、式ツリーのサイズを考慮してください。他のすべてが等しい場合 (つまり、両方の解が同じ精度を持つ場合) は、大きい解よりも小さい解が優先されます。

于 2011-12-12T21:26:11.893 に答える
0

舌足らずの発音。まあ、どんなホモイコニック言語でも。しかしLISP。Koza の本を読むhttp://www.genetic-programming.com/

于 2011-07-30T19:13:57.913 に答える
0

ここで探しているのは「Grammatical Evolution」です。これは、進化する動作するコンピューター プログラムへの遺伝的プログラミングの適用です。これは良いサイトです: http://www.grammatical-evolution.com/ . また、Google に「FPGA 遺伝的プログラミング」と入力すると、FPGA などのより基本的なコンピューティング メカニズムの進化を調べることができます。

于 2011-08-11T02:16:29.720 に答える
0

質問の最初の部分は、有効なアルゴリズムについてです。チューリング完全性を確保するために必要な数の関数を定義する場合 (たとえば、+、-、*、/、X、Y、Retval、ループ、if)、最初の部分を満たしています。何度も何度も進化し続ける特定の構造があり、最初から関数のリストに入れるだけで進化がスピードアップするため、より高いレベルの関数を使用することをお勧めします。たとえば、ループは if と goto に分解できますが、ループを使用すると、貴重な進化エネルギーを節約でき、有効性も確保できます。

ただし、2 番目の部分は、最終的に停止するアルゴリズムについてです。これには解決策がないことが知られています。1 つの代替手段は、プログラムが実行できる命令の数に制限を設定し、その制限に違反した場合にプログラムを中止して、高いペナルティを与えることです。または、プログラムが応答をロードする必要がある端末 (Retval など) がある場合は、プログラムを停止してその端末を確認することができます。

于 2011-12-08T15:06:19.577 に答える