Genetic-algorithms-genotype-representation
遺伝子型の表現
遺伝的アルゴリズムを実装する際に行う最も重要な決定の1つは、ソリューションの表現に使用する表現を決定することです。 不適切な表現は、GAのパフォーマンスを低下させる可能性があることが観察されています。
したがって、適切な表現を選択し、表現型と遺伝子型の空間間のマッピングを適切に定義することは、GAの成功に不可欠です。
このセクションでは、遺伝的アルゴリズムで最も一般的に使用される表現のいくつかを紹介します。 ただし、表現は非常に問題に固有のものであり、読者は、ここで述べた別の表現または表現の組み合わせが自分の問題により適していることに気付くかもしれません。
バイナリ表現
これは、GAで最も単純で最も広く使用されている表現の1つです。 このタイプの表現では、遺伝子型はビット文字列で構成されています。
ソリューション空間がブール決定変数で構成されている一部の問題（yesまたはno）では、バイナリ表現は自然です。 たとえば、0/1ナップザック問題を取り上げます。 n個のアイテムがある場合、n個の要素のバイナリ文字列で解を表すことができます。x^ th ^要素は、アイテムxが選択されている（1）かどうか（0）を示します。
他の問題、特に数値を扱う問題については、バイナリ表現で数値を表現できます。 この種のエンコーディングの問題は、ビットごとに重要性が異なるため、突然変異演算子とクロスオーバー演算子が望ましくない結果をもたらす可能性があることです。 これは、 Gray Coding を使用することである程度解決できます。1ビットの変更はソリューションに大きな影響を与えないためです。
実価値のある表現
離散変数ではなく連続変数を使用して遺伝子を定義する問題の場合、実際の値の表現が最も自然です。 ただし、これらの実数値または浮動小数点数の精度はコンピューターに限定されます。
整数表現
離散的な価値のある遺伝子の場合、ソリューション空間を常に「はい」または「いいえ」のバイナリに制限することはできません。 たとえば、北、南、東、西の4つの距離をエンコードする場合は、 \ {0,1,2,3} としてエンコードできます。 このような場合、整数表現が望ましいです。
順列表現
多くの問題では、ソリューションは要素の順序で表されます。 このような場合、順列表現が最も適しています。
この表現の典型的な例は、巡回セールスマン問題（TSP）です。 この場合、セールスマンはすべての都市のツアーに参加し、各都市を1回だけ訪問して、出発都市に戻る必要があります。 ツアーの合計距離は最小限に抑える必要があります。 このTSPの解決策は、当然すべての都市の順序付けまたは並べ替えであるため、この問題には並べ替え表現を使用するのが理にかなっています。
