Loading article…
線形遺伝的プログラミング(LGP) [ 1 ]は、集団内のコンピュータ プログラムが命令型プログラミング言語または機械語からのレジスタ ベースの命令のシーケンスとして表現される遺伝的プログラミングの特定の方法です。形容詞「線形」は、各 LGP プログラムが命令のシーケンスであり、命令のシーケンスが通常は順次実行されるという事実に由来します。他のプログラムと同様に、LGP のデータ フローは、レジスタ 内容の潜在的な複数使用と構造的に非効率的なコード (イントロン)の存在を視覚化するグラフとしてモデル化できます。これらは、この遺伝的表現とより一般的なツリー ベースの遺伝的プログラミング(TGP) バリアントとの 2 つの主な違いです。[ 2 ] [ 3 ] [ 4 ]
他の遺伝的プログラミング手法と同様に、線形遺伝的プログラミングでは、プログラム集団を実行するためのデータの入力が必要です。次に、プログラムの出力（その動作）は、適合度関数を使用して、何らかの目標動作と比較されます。ただし、LGP は、上述の 2 つの主な違いにより、一般的にツリー遺伝的プログラミングよりも効率的です。中間結果（レジスタに格納）を再利用できること、および、意図したデータでプログラムを実行する前に、すべての非有効なコードを削除するために実行できる単純なイントロン除去アルゴリズム[ 1 ]が存在することです。これらの 2 つの違いにより、ツリー内の高度に制約されたデータ フローや、TGP ですべてのツリー ノードを実行する一般的な方法と比較して、コンパクトなソリューションと大幅な計算コストの削減が実現されることがよくあります。さらに、LGP は、複数の出力レジスタを定義することで自然に複数の出力を持ち、制御フロー操作と容易に連携します。
線形遺伝的プログラミングは、システムモデリングやシステム制御など、多くの分野で大きな成功を収めて応用されてきた。[ 5 ] [ 6 ] [ 7 ] [ 8 ]
線形遺伝的プログラミングは、可変数の単項関数と単一の終端で構成されるプログラムであるツリー遺伝的プログラミングにおける線形ツリープログラムと混同してはならない。線形ツリーGPは、集団に長さの異なるプログラムが含まれる可能性があり、2種類以上の関数または2種類以上の終端が存在する可能性があるため、ビットストリング遺伝的アルゴリズムとは異なることに注意されたい。[ 9 ]
LGPプログラムは基本的に命令の線形シーケンスで表現されるため、ツリーベースのプログラムよりも読みやすく、操作も簡単です。例えば、3つの入力（R1、R2、R3）と1つの出力（R0）を持つブール関数問題を解くための単純なプログラムは、次のように記述できます。
R4 = R2 AND R3 R0 = R1 OR R4 R0 = R3 AND R0 R4 = R2 AND R4 # これは無効な命令ですR0 = R0 OR R2 R1、R2、R3は入力（読み取り専用）レジスタとして宣言する必要があり、R0とR4は計算（読み書き可能）レジスタとして宣言する必要があります。このプログラムはわずか5つの命令からなる非常にシンプルなものです。しかし、突然変異演算子と交叉演算子を用いることで、プログラムの長さや各命令の内容を増やすことができます。
出力レジスタ R0 に影響を与えないため、1 つの命令は無効またはイントロン (マーク付き) であることに注意してください。これらの命令の認識は、実行前にコードを分析するために使用されるイントロン除去アルゴリズムの基礎となります。技術的には、これは個体をコピーし、イントロン除去を 1 回実行することによって行われます。イントロンが除去されたコピーは、トレーニングケースの数に応じて、指定された回数だけ実行されます。注目すべきは、元の個体はそのまま残され、進化プロセスに引き続き参加することです。これらの「構造的」イントロンを除去することによって圧縮されるのは、実行されるコピーのみです。
もう一つのシンプルなプログラム、これはLGP言語で書かれています。スラッシュ/Aは、スラッシュで区切られた一連の命令のように見えます。
input/ # ユーザーから入力を受け取り、レジスタ F に保存する0 / # レジスタ I を 0 に設定する save/ # F の内容をデータベクトル D[I] に保存する (つまり D[0] := F) input/ # 別の入力を受け取り、F に保存する add/ # I が指す現在のデータを F に追加する (つまり F := F + D[0]) output/. # F の結果を出力このようなコードをバイトコード形式、つまり各バイトが異なる命令を表すバイト配列として表現することで、配列の要素を変更するだけで簡単に変更操作を行うことができる。