遺伝子型の表現

遺伝的アルゴリズムを実装する際に行う最も重要な決定の1つは、ソリューションを表すために使用する表現を決定することです。不適切な表現はGAのパフォーマンスの低下につながる可能性があることが観察されています。

したがって、適切な表現を選択し、表現型と遺伝子型の空間間のマッピングを適切に定義することは、GAの成功に不可欠です。

このセクションでは、遺伝的アルゴリズムで最も一般的に使用される表現のいくつかを紹介します。ただし、表現は非常に問題に固有であり、読者は、ここで言及されている別の表現または表現の組み合わせが自分の問題により適していることに気付く場合があります。

バイナリ表現

これは、GAで最も単純で最も広く使用されている表現の1つです。このタイプの表現では、遺伝子型はビット文字列で構成されます。

解空間がブール決定変数で構成されている場合のいくつかの問題(はいまたはいいえ)では、バイナリ表現は自然です。たとえば、0/1ナップサック問題を考えてみましょう。n個のアイテムがある場合、n個の要素のバイナリ文字列でソリューションを表すことができます。x番目の要素は、アイテムxが選択されているか(1)、選択されていないか(0)を示します。

他の問題、特に数値を扱う問題については、2進表現で数値を表すことができます。この種のエンコーディングの問題は、ビットが異なれば重要性も異なるため、ミューテーションおよびクロスオーバー演算子が望ましくない結果をもたらす可能性があることです。これは、を使用することである程度解決できますGray Coding, 1ビットの変更は、ソリューションに大きな影響を与えないためです。

実数値表現

離散変数ではなく連続変数を使用して遺伝子を定義したい問題の場合、実際の値の表現が最も自然です。ただし、これらの実数値または浮動小数点数の精度はコンピューターに限定されます。

整数表現

離散値遺伝子の場合、解空間を常にバイナリの「yes」または「no」に制限できるとは限りません。たとえば、北、南、東、西の4つの距離をエンコードする場合は、次のようにエンコードできます。{0,1,2,3}。このような場合、整数表現が望ましいです。

順列表現

多くの問題では、解は要素の順序で表されます。このような場合、順列表現が最も適しています。

この表現の典型的な例は、巡回セールスマン問題(TSP)です。この場合、セールスマンはすべての都市のツアーに参加し、各都市を1回だけ訪問して、開始都市に戻る必要があります。ツアーの総距離を最小限に抑える必要があります。このTSPの解決策は、当然、すべての都市の順序付けまたは順列であるため、順列表現を使用することは、この問題に意味があります。