genetic-programming - 遺伝子発現プログラミングとデカルト遺伝的プログラミングの違い

Question

進化的計算でかなり厄介なのは、わずかに異なり、重複する概念が劇的に異なる名前を選択する傾向があることです。このための私の最近の混乱は、遺伝子発現プログラミングがデカルト遺伝的プログラミングと非常に似ているように見えることです。

1. （どのように）これらの根本的に異なる概念ですか？
2. GP命令の間接エンコーディングが効果的な手法であることを読みました（GEPとCGPの両方がそれを行います）。間接エンコーディングには時代遅れの古典的なツリーベースGPがあるというある種のコンセンサスに達しましたか？

Answer 1

まあ、遺伝子発現プログラミング（GEP）とデカルト遺伝的プログラミング（CGPまたは私が古典的な遺伝的プログラミングと見なしているもの）の間にはいくつかの違いがあるようですが、違いは実際にあるべきよりも誇大宣伝されているかもしれません。私はGEPを使用したことがないので、コメントはすべてCGPでの経験に基づいていることに注意してください。

CGPでは、遺伝子型と表現型の区別はありません。言い換えると、CGPの「遺伝子」を見ている場合は、それらの発現も見ています。ここにはエンコーディングはありません。つまり、式ツリーは遺伝子そのものです。

GEPでは、遺伝子型が表現型に表現されるため、遺伝子を見ていると、その表現がどのようになるかはすぐにはわかりません。GPの「発明者」であるCândidaFerreiraは、非常に優れた論文を執筆しており、概念全体の概要を簡潔に説明しようとする他のリソースがいくつかあります。

フェリエラは、メリットは「明らか」だと言っていますが、GEPをCGPよりも優れたものにするようなものは実際には見当たりません。どうやらGEPは多遺伝子性であり、これは複数の遺伝子が形質（すなわち発現ツリー）の発現に関与していることを意味します。いずれにせよ、適応度は表現されたツリーで計算されるため、GEPが適応度を上げるために何かをしているようには見えません。著者が主張しているのは、GEPはフィットネスに到達する速度を上げる（つまり、世代数が少ない）ということですが、率直に言って、異なる選択アルゴリズム、異なるトーナメント構造を持ち、分割するだけで、CGPから劇的なパフォーマンスの変化を見ることができます。個体群を部族に移し、標本を部族間で移動させます。これには、適応度への多様性などが含まれます。

選択：

• ランダム
• ルーレット盤
• top-n
• 半分を取る
• 等

トーナメントの頻度：

• エポックごとに1回
• データインスタンスごとに1回
• 世代ごとに1回。

トーナメントの構造：

• 3を取り、1を殺し、他の2つの子と交換します。
• トーナメントのすべての個人をフィットネスで並べ替え、下半分を殺して上半分の子孫に置き換えます（下半分はフィットネスが悪く、上半分はフィットネスが良い）。
• トーナメントからランダムに個体を選び、余分な個体を交配させて殺します。

部族
集団は、互いに独立して進化する部族に分割できます。

• 移行-定期的に、部族からの個人は別の部族に移動されます
• 部族は論理的に分離されているため、別々の環境で実行されている独自の別々の集団のようになります。

ダイバーシティフィットネスダイバーシティ
をフィットネスに組み込みます。ここでは、同じフィットネス値を持つ個人の数を数え（したがって、同じ表現型を持つ可能性があります）、比例した値でフィットネスにペナルティを課します。同じフィットネス値を持つ個人が多いほど、それらの個人に対するペナルティ。このようにして、独特の表現型を持つ標本が奨励されるため、個体群の停滞がはるかに少なくなります。

これらは、CGPのパフォーマンスに大きな影響を与える可能性のあるもののほんの一部であり、私が大きく言うとき、それはフェリエラのパフォーマンスと同じかそれ以上であることを意味します。したがって、フェリエラがこれらのアイデアをあまりいじくり回さなかった場合、CGPのパフォーマンスが大幅に低下する可能性があります...特に停滞と戦うために何もしなかった場合はそうです。したがって、GEPのパフォーマンス統計を読むときは注意が必要です。なぜなら、そこにあるすべての「最適化」を説明できない場合があるからです。

Answer 2

これらの回答には、明確にする必要のある混乱があるようです。デカルトGPは、従来のGP（別名ツリーベースのGP）およびGEPとは異なります。それらは多くの概念を共有し、同じ生物学的メカニズムからインスピレーションを得ていますが、個人の表現（解決策）は異なります。

CGPでは、表現（遺伝子型と表現型の間のマッピング）は間接的です。つまり、CGPゲノムのすべての遺伝子がフェノームで発現されるわけではありません（GEPや他の多くの概念にも見られます）。遺伝子型はノードのグリッドまたは配列にコード化でき、結果のプログラムグラフはアクティブノードのみの表現です。

GEPでは、表現も間接的であり、同様にすべての遺伝子が表現型で発現されるわけではありません。この場合の表現はtreeGPやCGPとは大きく異なりますが、遺伝子型もプログラムツリーに表現されます。私の意見では、GEPはよりエレガントな表現であり、実装が簡単ですが、次のようないくつかの欠点もあります。問題固有の適切な尾と頭のサイズを見つける必要があります。 、そして最後にそれはあまりにも多くの膨満感を持っています。

特定の問題ドメインでどの表現が他の表現よりも優れているかとは関係なく、それらは汎用であり、エンコードできる限り、どのドメインにも適用できます。

Answer 3

一般的に、GEPはGPよりも単純です。プログラムで次のノードを許可するとします。定数、変数、+、-、*、/、if、... GPを使用するこのようなノードごとに、次の操作を作成する必要があります。おそらく他の遺伝子演算子も

このようなノードごとにGEPで実装する必要があるのは、1つの操作のみです。deserializeは、数値の配列（CやJavaのdoubleなど）を受け取り、ノードを返します。これは、JavaやPythonなどの言語でのオブジェクトの逆シリアル化に似ています（違いは、プログラミング言語での逆シリアル化ではバイト配列が使用されることです。ここでは、数値の配列があります）。この「逆シリアル化」操作でさえ、プログラマーが実装する必要はありません。JavaまたはPythonの逆シリアル化で行われるのと同じように、一般的なアルゴリズムで実装できます。

ある観点からはこの単純さにより、最良のソリューションの検索は成功しなくなる可能性がありますが、別の側面では、プログラマーの作業が少なくて済み、アルゴリズムの実行が速くなる可能性があります（最適化が容易で、コードとデータがCPUキャッシュに収まるなど）。 。したがって、GEPの方が少し優れていると言えますが、もちろん明確な答えは問題によって異なり、多くの問題ではその逆が当てはまる可能性があります。