私は遺伝的アルゴリズムを使ってかなりの量の仕事を成功させてきましたが、これまでのところ遺伝的プログラミングを無視しています。私の知る限り、ほとんどのプログラムはプログラマーによって書かれたままですが、遺伝的プログラミングを妨げているものを知りたいのですが。
私が考えたいくつかの可能な説明は次のとおりです。
何か案は？
これは私自身の研究で検討してきたことであり、多くの理由があると思います。
GP 分野の研究の大部分は、ほとんどのプログラマーが作成する種類のソフトウェアではなく、式の作成に焦点を当てています。この分野には多くのコンピューター科学者がいますが、期待される種類のプログラムを作成することに焦点を当てている人はほとんどいないため、その分野での進歩は遅れています.
LISP は操作が簡単な優れたツリー構造を生成できるため、LISP を使用することに過度に重点が置かれています。残念ながら、いくつかのトリッキーな問題を解決する必要があるため、命令型のプログラムは無視されてきました。GP がプログラマーによって真剣に受け止められるためには、命令型プログラムを作成する必要があります。
実際のプログラムにはループ構造が含まれていますが、GP でループを実装するには、無限ループを防ぐためのあらゆる種類の醜い制約がなければ困難です。
遺伝的プログラミングはうまくスケーリングしません。利用可能な言語が少ない小さな問題には問題ありませんが、最初のポイントで述べたように、検索スペースがすぐに大きくなりすぎます。
人間のプログラマーと比較すると、GP は非常に遅くなる可能性があります。ただし、これは非常に並列化可能であるため、より多くのプロセッサ コアが標準になるにつれて、大幅なメリットが得られる可能性があります。
もう 1 つの有効な答えは、コードが自動的に生成されたことを信頼するのは難しいということです。これは事実ですが、GP はそもそも正しい種類のプログラムを作成できないため、実際にはこれが大きな影響を与えるとは思えません。
遺伝的プログラミングの難しい部分は、優れたスコアリング関数を作成することです。
スコアリング関数は、アルゴリズムが目的のプロパティを持っているかどうかを正しく判断する必要があります。これは思ったより難しく、テスト スイートを作成するよりもはるかに困難です。アルゴリズムは、スコアリング関数の癖に適応し、最適化する場合があります。進化しようとしていstrcmpますか？代わりに、アルゴリズムは、合格/不合格のテスト ケースの長さに対する数学的パターンを発見する場合があります。
スコアリング機能は、テスト対象のアルゴリズムが部分的に機能しているかどうかを判断できる必要があります。遺伝子プログラミングは「山登り」に依存しています。小さな有益な変異は、スコアを少しずつ改善する必要があります。スコアリング関数が true/false しか出力できない場合は、遺伝的ではなくランダムに検索しています。
試してみると、遺伝的プログラミングが横方向の思考の究極であることがわかります。プログラムは、考えもしなかったあらゆる方法で問題を解決する傾向があり、そのほとんどは予想外であり、(深刻なアプリケーションの場合)おそらく使い物にならない。有名な事例の 1 つは、基本的な電子部品を使用して発振器を進化させる試みに関するものでした。回路の簡単さと出力が発振するかどうかで判断しました。それは非常に単純なことであり、研究者たちはそれが機能しないと確信していましたが、実際に機能しました。それは、環境からの電波を拾い上げて増幅することでした。
引用するために編集：
グラハム・ロウ、ダンカン。「電子スープからラジオが生まれる」New Scientist、vol.175、no.2358、p.19 (2002 年 8 月 31 日)。http://www.newscientist.com/news/news.jsp?id=ns99992732でオンラインで入手できます。
ただし、リンクは現在壊れているようです。
新しいリンクはhttp://www.newscientist.com/article/dn2732-radio-emerges-from-the-electronic-soup.htmlです
私はこのパーティーに遅れていることを知っていますが、いくつかのポイントを作りたいと思います. 私は、ジョン・コザと彼の遺伝的プログラミング 4 の本で仕事をするという信じられないほどの幸運に恵まれました。
私たちのほとんどが日常的に行っている種類のプログラミング (GUI イベントの接続、ピクセルのプッシュ、データベースなど) は、GP が構築しようとしている種類のプログラムではないことは間違いありません。
John Koza が約 100 台のマシンからなるクラスターで行っていること (私の記憶が正しければ!) は、興味深い問題 (NP 困難と考えてください) の解決策を探すことです。悲しいことに、私たちプログラマーが日々取り組んでいる問題のほとんどは、あまり面白くも難しい問題でもありません。ほとんどの場合、イライラして時間がかかるだけです。
遺伝子操作された電子発振器についてベン・ジャクソンが言ったことは、このスレッドでコザ博士とチームが実際に行っていることに最も近いものです。GPシリーズの本にはサーキットの例がたくさんありました。
トム・キャッスルが命令型プログラムについてここで述べたことは、正確には正しくありません。ジョンと会社によるこの重要な例は、アンテナ設計の実行です。これは、アンテナを設計する LOGO 描画言語のようなコマンドを備えた 3D 描画プログラムです。スタック上の行列をプッシュおよびポップするための moveto、lineto タイプのコマンドがあります。先週見たばかりの GP パッケージ jgap は、直接サポートしています。つまり、void return ステートメントを含めることができ、最後に return ステートメントを持つコンテナ型の非終端記号です。あまり詳しく見ていませんが、ローカル変数のようなものさえあると思います。
初期の GP が中心となって実行されていたオリジナルの LISP 設計は、ときどき苦痛を感じますが、それは確かに真実です。これは通過儀礼のようなもので、GP 実行の出力をより使いやすいコードに変換することに悩まされていると思います。
TL;DR: GP は実際には自動プログラミング システムではありません。自動発明システムです。
1.と3.だと思います。
特に、ポイント 3 に関しては、ほとんどの場合、適切なターゲット関数を考え出し、これが正しいまたは許容可能なソリューションにつながることを確認するよりも、実際のプログラムを作成する方が簡単であると言えます (どのようにしてそれを知ることができますか) 。遺伝的プログラミングから派生したアルゴリズムは期待どおりに機能しますか?)
ポイント 1 に関しては、検索空間の次元数は無限であると言えます。
GP は、フィットネス関数を作成する人の知識を超えた新しい問題を迅速に解決できません。したがって、現在のところ、解決方法が既にわかっている問題を解決するためにのみ使用できますが、検索スペースのために完全に解決するのは理想的ではありません. 巡回セールスマンなど。これは、GAでより迅速に解決できます。
その理由は実に単純です。新しい問題を解決するために、GP に与えるツールは、GP 検索空間が実際の遺伝学に真に類似するように、十分に単純であるか、十分に完全である必要があります。
遺伝子プログラミングは、実際の遺伝学と同様に、すべてのプラットフォーム成長システムと同じ成長パターンの影響を受けます。つまり、GP は、含まれているコア ユーティリティがプラットフォームにヒットし、横ばいになり、新しいパラダイムに出くわして新しいプラットフォームを構築するまでに長い時間がかかります。
この進化促進ビデオは、これらのプラットフォームの成長パターンを示しています。 http://www.youtube.com/watch?v=mcAq9bmCeR0 新しい手を開発するには長い時間がかかります。開発が完了すると、追加の手が新しいものになり、より多くの手の最適な例にすばやく進みます。(このビデオは GP ではなく GA を使用している可能性が最も高いことに言及する必要がありますが、遺伝学は遺伝学です)
これは、ところで、特異点理論に入るのと同じロジックです。
しかし、これが GP にとって何を意味するかというと、それはプログラム内での実用的なアプリケーションではなく、研究にのみ適しているということです。いくつかの単純な例外を除いて、要件が GA で解決できるよりもわずかに詳細です。一部のスケジューラ プログラムなど。プログラミングの検索空間が非常に小さく、それを解決するために必要なツールがよく理解されており、明確に定義されたフィットネス関数が存在できる場所。
それは、(少なくとも正しいプログラムでは) 理論的に不可能であることが証明されているからです。
検索スペースのサイズと速度の問題、およびその他の「速度」の問題を破棄する無限の計算能力があると仮定しましょう。ここで直面する問題は 2 つだけです。 - 生成されたプログラムは停止しますか? - 生成されたプログラムが希望どおりに動作することを確認するにはどうすればよいですか?
最初の問題は、計算可能性理論の中心的な問題であり 、停止問題と呼ばれます。チューリングは 1936 年に、この問題がすべてのプログラムと入力のペアに対して決定不能であることを証明しました。つまり、場合によっては可能ですが、すべてではありません。プログラムが停止するかどうかを判断できる自動化されたプロセスはありません。このため、多くのことはできません ;)
2 番目の問題は、プログラムの正確性に関するものです。遺伝的プログラミングでは、検証は通常、正しさの証明をまったく構成しない例の値によって行われます。これは単体テストに匹敵し、多くの例では問題ありませんが、一般的な証拠はありません。たとえば、素数チェッカーを作成し、3 5 7 と 11 のみでテストすると、すべての奇数に対して true を返すプログラムはテストに合格します。
さらに一歩進むと、自動証明が使用されます。アルゴリズムの正しさの自動証明は、実際には数学的自動定理証明に深く関係しています。公理化されたシステムを使用してプログラムを記述し、ステートメントの正確性を自動的に証明しようとします。ここでもまた、ゲーデルの不完全性定理である強力な理論的障壁に直面します。これらの定理は、自然数の算術演算を実行できる非常に単純な公理化されたシステムでさえ、これらの自然数に関するすべての定理を証明できるアルゴリズム (有効な手順と呼ばれる) がないことをとりわけ述べています。具体的には、単純なプログラムであっても、その正しさを証明することはできません。
正当性が証明されていなくても、サンプル テスト ケースを使用して遺伝的プログラムを検証すると、過度に特化する傾向があります。これは、機械学習におけるオーバーフィッティングとして知られる現象です。つまり、学習したプログラムは、提供されたテスト ケースでは問題なく動作しますが、他の入力に対しては完全に弾道的になる可能性があります。
三つのこと：
たぶん、ほとんどのプログラマーはプログラマーであり、コンピューター科学者ではないのでしょうか。
遺伝的プログラミングには真剣な賢さが必要です。問題を適切に分解できる必要があり、最初に適切な問題が必要です。そして、あなたは遺伝的アルゴリズムがオプションであることを知るのに十分な知識を持っている必要があります。そして、問題はまだよく知られた解決策を持っている必要はありません。
すべてが凝ったアルゴリズムを必要とするわけではありません。世界で書かれているすべてのコードの中で、「標準的な」ウェブアプリ、OS、デバイスプログラミングは本当に遺伝的アルゴリズムを必要としますか？
そして、それに関して言えば、ほとんどのプログラミング作業は、複雑なアプローチが必要とされない単純な問題の解決に費やされています。
その理由の大きな部分は、リスク管理にあると思います。我慢してください: プログラマーがプログラムを書くために座っているとき、彼らはそれがどれくらいかかるか、そして何ができるかについて少なくともある程度の考えを持っています.
代わりに、プログラマーが (遺伝的プログラミングを使用して) プログラムを生成するプログラムを作成するために座っている場合、不確実性が屋根を突き破ります: プロセスにどれくらいの時間がかかるかは不明であり、最終的なプログラムがどれほど優れているかは不明です。
後でプログラムを調整したり、バグを修正したりするのはどれほど簡単でしょうか? 生成されたコードは、デバッグがほとんど不可能な場合があります。
大学でのGP研究とその後の分野の追跡で数年後の私の個人的な見解：GPはスケーリングに失敗します。
単純な適応度関数GPで表される単純な問題は、問題なく解決できます。しかし、前述のように、strcmpや計算機、さらには単純なテキストエディターを進化させるタスクを説明する適応度関数を作成することは、従来のアプローチではほとんど不可能です。
GPフィットネス関数が完全にTDDであるという概念は好きですが、:-)いつか、シミュレートされた進化を指示するためのより良い方法を思いつくかもしれませんが、それはまだ実現していません。
私は現在いくつかの「私的研究」を行っている暗黙の適応度関数の分野でGPにいくつかの希望を持っています。どこまで到達するか見ていきます！
乾杯、ジェイ
原初のスープは疑わしく、食欲をそそらない。私のプロダクション コードでは、Intelligent Design を好みます。
GP で上記の問題に取り組んでいるプロジェクトがいくつかあります。例としては、 opencog MOSESがあります。
現在、プログラミングは機械が読み取り可能な方法で細かい仕様を定義しています。プログラムに何をしたいのか、そして結果がどのように見えるべきかを正確に伝えます。もうそれだけではありません。つまり、たとえば遺伝的プログラミングによって結果を生成したい場合でも、適合関数の形式でこの機械可読の細かい仕様を実行する必要があります。これにより、少なくとも同じ量の作業が発生する可能性があります。したがって、定義は簡単だが仕様に到達するのが難しい問題のために作成された遺伝的プログラミングにとっては、間違った分野です。
編集：ほとんどのプロジェクトでは、この細かい仕様はとにかくテストの形で行われていると言えます。遺伝的プログラミングのアプローチでは、テストはニーズを特定するのに不正確な方法だと思います。それらは例に基づいており、正式な仕様言語に基づくプログラミングとは異なります。遺伝的プログラミングはおそらく、テスト ケースに適した結果を生成し、新しい入力を使用した実際の状況では正しく動作しないでしょう。したがって、プログラミング言語の仕様と同じくらい正確なテストで仕様レベルを取得するには、すべての不測の事態に対して膨大な量のテスト ケースが必要になります。したがって、最終的には、そのようなことをプログラミングするよりもはるかに多くの作業を行うことになります.
GP と GA、または一般的な進化的アルゴリズムは趣味に近いものです。例外を除いて、実際のアプリケーションには使用されません。その理由は、これらのアルゴリズムがランダム性に基づいているためです。良い答えが得られるという確証はありません。
さらに、この分野は、他の数学的に強力な手法と比較して理解しやすく実装しやすいため、標準以下の研究作業であふれています。そのため、学生はエンジニアリングや科学のアプリケーションを最適化する目的を見つけただけで、新しい仕事、つまり出版することができます。
カンファレンスのスポンサーを、他の AI/ML/Optimization カンファレンスのスポンサーと比較してください。業界における「現在の」重要性が明らかになります。
しかし、それは研究の領域であり、それを機能させるのは私たち次第です. 現在はただの趣味です！