31

進化的プログラミングは、多くの最適化問題を解決する優れた方法のようです。アイデアは非常に簡単で、実装に問題はありません。

ruby/python スクリプト (または他の言語) でプログラムを進化的に作成する方法があるかどうか疑問に思っていました。

アイデアは簡単です：

  1. プログラムの母集団を作成する
  2. 遺伝子操作 (ルーレット ホイールの選択またはその他の選択) を実行したり、最高のプログラムから継承した新しいプログラムを作成したりします。
  3. 条件を満たすプログラムが見つかるまでポイント 2 をループします。

しかし、まだいくつかの問題があります。

  1. 染色体はどのように表されますか? たとえば、染色体の 1 つのセルを 1 行のコードにする必要がありますか?
  2. 染色体はどのように生成されますか? それらがコード行である場合、それらが構文的に正しいことを保証するためにどのように生成しますか?

生成できるプログラムの例:

N 個の数値を入力として取り、それらの平均を出力として返すスクリプトを作成します。

そのようなアルゴリズムを作成しようとする試みがあった場合は、リンク/ソースを見て喜んでいます.

4

8 に答える 8

23

これをやりたいと確信しているなら、遺伝的アルゴリズムではなく遺伝的プログラミングが必要です。GP を使用すると、ツリー構造のプログラムを進化させることができます。あなたがすることは、一連のプリミティブ操作 (while($register)、read($register)、increment($register)、decrement($register)、divide($result $numerator $denominator)、print) を与えることです。 、progn2（これはGPが「2つのコマンドを順番に実行する」という意味です））。

次のようなものを生成できます。

progn2(
  progn2(
    read($1)
    while($1
      progn2(
        while($1
          progn2( #add the input to the total
            increment($2)
            decrement($1)
          )
        )
        progn2( #increment number of values entered, read again
          increment($3)
          read($1)
        )
      )
    )
  )
  progn2( #calculate result
    divide($1 $2 $3)
    print($1)
  )
)

フィットネス関数として、実際の解にどれだけ近いかを使用します。そしてそこに問題があり、とにかく伝統的にそれを計算しなければなりません*。そして、それを (選択した言語で) コードに変換するものを用意します。無限ループの可能性があるため、しばらくすると実行を中断する必要があり (停止の問題を回避する方法はありません)、おそらく機能しないことに注意してください。シャック。また、提供されたコードはゼロで割ろうとすることに注意してください。

*これを回避する方法はありますが、一般的にはそれほど遠くありません。

于 2011-04-20T22:28:52.147 に答える
15

実行できますが、ほとんどの種類のアプリケーションではうまく機能しません。

遺伝的アルゴリズムは、適合度関数が連続している場合にのみ機能します。つまり、現在の母集団のどの候補が他の候補よりも解に近いかを判断できます。その場合にのみ、ある世代から次の世代に改善が得られるからです。これは、フィットネス関数に強く重み付けされた非連続コンポーネントを 1 つ持つ遺伝的アルゴリズムを使用したときに、難しい方法で学びました。それは他のすべてを支配し、非継続的であるため、より高い適合性への漸進的な進歩はありませんでした.

残念ながら、プログラムの正しさはまったく不連続です。行 A のエラー X で停止するプログラムは、行 B のエラー Y で停止するプログラムよりも優れていますか? あなたのプログラムは正しいから 1 文字離れていて、それでもエラーで中止される可能性がありますが、一定のハードコーディングされた結果を返すプログラムは、少なくとも1 つのテストに合格することができます。

そして、それはコード自体が変更の下で非連続的であるという問題にも触れていません...

于 2011-04-20T16:05:21.423 に答える
9

さて、これは非常に可能であり、@ Jivlainは彼の（素晴らしい）答えの中で、遺伝的プログラミングがあなたが探しているものである（そして単純な遺伝的アルゴリズムではない）ことを正しく指摘しています。

遺伝的プログラミングは、@ MichaelBorgwardtが彼の回答で示しているいくつかの複雑さのために、まだ幅広い聴衆に届いていない分野です。しかし、それらは単なる合併症であり、これが不可能であることは事実ではありません。このトピックに関する研究は20年以上続いています。

アンドレ・コザはこれに関する主要な研究者の1人であり（1992年の研究をご覧ください）、1996年には、遺伝的プログラミングがいくつかの古典的な計算問題（セルオートマトン同期の進化するプログラムなど）でナイーブGAよりも優れている場合があることを示しました。 ）。

これは、 2003年のKozaとPoliによる優れた遺伝的プログラミングのチュートリアルです。

最近の参考資料として、遺伝子プログラミングのフィールドガイド（2008）を参照してください。

于 2011-04-25T14:29:55.157 に答える
1

言語は問題ではありません。言語に関係なく、より高いレベルの突然変異を定義する必要があります。そうしないと、学習に永遠に時間がかかります。

たとえば、どの Ruby 言語もテキスト文字列で定義できるため、テキスト文字列をランダムに生成して最適化することができます。正当な Ruby プログラムのみを生成する方がよいでしょう。ただし、永遠にかかることもあります。

並べ替えプログラムを作成しようとしていて、「スワップ」、「移動」などの高レベルの操作がある場合は、成功する可能性がはるかに高くなります。

理論的には、サルの群れがタイプライターを無限に叩くと、シェイクスピアのすべての作品が出力されます。実際には、文学を書くための実用的な方法ではありません。遺伝的アルゴリズムが最適化問題を解決できるからといって、それが簡単であるとか、必ずしも良い方法であるとは限りません。

于 2011-04-20T16:03:40.183 に答える
0

あなたが言うように、遺伝的アルゴリズムの最大のセールス ポイントは、非常に単純なことです。彼らは最高のパフォーマンスや数学的バックグラウンドを持っていませんが、問題を解決する方法がわからない場合でも、最適化問題として定義できる限り、GA に変えることができます。

コードは良い染色体材料ではないという理由だけで、プログラムは GA にはあまり適していません。Python の代わりに (より単純な) 機械語で似たようなことをした人を見たことがあります (ただし、それ自体は GA というよりは生態系シミュレーションでした)。それ。

一方で、GA がどれほど魅力的で、基本的には GA を見ている人なら誰でも同じ質問をすることを考えると、どこかでこれを試した人がすでにいると確信しています。

于 2011-04-20T16:06:55.967 に答える
0

頑張ってください。

確かに、プログラムを読み取り、ランダムにいくつかの文字を追加、削除、または変更する「突然変異」プログラムを作成できます。次に、結果をコンパイルして、出力が元のプログラムよりも優れているかどうかを確認できます。もちろん、99.9% の確率でコンパイル エラーが発生します。構文エラー、未定義の変数などです。残りのほとんどは、まったく正しくありません。

非常に簡単な問題をいくつか試してください。たとえば、2 つの数値を読み取り、それらを加算し、合計を出力するプログラムから始めます。目標は、3 つの数値を読み取って合計を計算するプログラムであるとしましょう。もちろん、そのようなプログラムがどれほど長く複雑になるかは、言語によって異なります。たった 1 行のコードで数値を読み書きできる非常に高水準の言語があるとします。その場合、開始プログラムはわずか 4 行です。

read x
read y
total=x+y
write total

望ましい目標を達成するための最も簡単なプログラムは、次のようなものになります

read x
read y
read z
total=x+y+z
write total

したがって、ランダムな突然変異により、「read z」と「+z」を追加する必要があり、スペースと改行を含めて合計 9 文字になります。ミューテーション プログラムを簡単に説明すると、常に正確に 9 文字のランダムな文字が挿入され、それらが正しい場所にあることが保証され、26 文字と 10 桁と 14 の特殊文字の文字セットから選択されるとしましょう = 50文字。正しい 9 文字を選択する確率は? 50^9 分の 1 = 2.0e15 分の 1。(プログラムは、「read z」と「+z」の代わりに「read w」と「+w」を挿入しても機能しますが、魔法のように正確な数の文字が挿入されると仮定して簡単にします。常に適切な場所に挿入します. したがって、この見積もりはまだ寛大だと思います.)

2.0e15 分の 1 はかなり小さな確率です。プログラムが 1 秒間に 1000 回実行され、出力をすばやくテストできたとしても、その可能性は 1 秒あたり 2.0e12 に 1 つ、1 時間あたり 5.4e8 に 1 つ、1 日あたり 2.3e7 に 1 つです。1 年間実行し続けても、成功する可能性は 62,000 分の 1 です。

ある程度有能なプログラマーでさえ、10 分でそのような変更を行うことができるはずです。

変更は、少なくとも正しい「パケット」で行われる必要があることに注意してください。つまり、ミューテーションが "reax z" を生成した場合、それは "read z" から 1 文字しか離れていませんが、それでもコンパイル エラーが発生するため、失敗します。

同様に「read z」を追加しますが、計算を「total=x+y+w」に変更してもうまくいきません。言語によっては、未定義の変数に対してエラーが発生するか、せいぜいゼロなどのデフォルト値があり、誤った結果が返されることになります。

増分ソリューションを理論化できると思います。おそらく、1 つのミューテーションが新しい read ステートメントを追加し、その後のミューテーションが計算を更新します。しかし、計算がなければ、追加の読み取りは無意味です。追加の読み取りが「正しい方向への一歩」であると判断するために、プログラムはどのように評価されますか? 私がそれを行う唯一の方法は、各突然変異の後にコードを知的な存在に読み取らせ、変更が望ましい目標に向かって進んでいるかどうかを確認することです. そして、それができるインテリジェントなデザイナーがいる場合、それは、彼が望ましい目標が何であり、それを達成する方法を知っていることを意味するに違いありません. その時点で、変更がランダムに発生するのを待つよりも、目的の変更を行う方がはるかに効率的です。

そして、これは非常に簡単な言語で書かれた非常に単純なプログラムです。ほとんどのプログラムは何百、何千もの行で構成されており、それらすべてが連携して動作する必要があります。ランダムなプロセスが動作するプログラムを作成する可能性は天文学的です。

非常に特殊なアプリケーションでは、実際にはランダムな変更を行うのではなく、ソリューションのパラメーターを段階的に変更する方法で、これに類似したことを行う方法があるかもしれません。同様に、値がわからないいくつかの定数を含む式があります。いくつかの小さな入力セットに対する正しい結果が何であるかはわかっています。そこで定数をランダムに変更し、結果が正解に近ければそこから変更し、そうでなければ元の値に戻します。しかし、それでも、ランダムな変更を行うことはめったに生産的ではないと思います. 1000 から始めて、次に 100 から 10 というように、厳密な式に従って定数を変更してみると、より役立つ可能性があります。

于 2011-04-20T17:31:27.870 に答える
0

私はあなたに提案したいだけです。あなたがどれほど成功するかはわかりませんが、遺伝子プログラミングを使ってコア ウォーボットを進化させることができるかもしれません。フィットネス機能は簡単です。ボットをゲームで競わせるだけです。よく知られているボットから始めて、おそらくいくつかのランダムなボットから始めて、何が起こるかを待ちます。

于 2011-04-21T03:12:32.367 に答える