染色体（進化アルゴリズム）

古典的な形式では、遺伝的アルゴリズムはビット列を使用し、最適化する決定変数をそれらにマッピングします。値の範囲が次の 1 つのブール値と 3 つの整数決定変数の例${\displaystyle 0\leq D_{1}\leq 60}$、$28 ≤ D2 ≤ 30$そして${\displaystyle -12\leq D_{3}\leq 14}$これは次のような例で説明できるかもしれません。

ここで負の数は2の補数で表されていることに注意してください。この単純な表現では、5ビットを使用して3つの値を表します。${\displaystyle D_{2}}$ただし、2ビットで十分です。これはかなりの冗長性です。遺伝子型と表現型のマッピングのために28ビットを追加する改良案は次のようになります。

と${\displaystyle D_{2}=28+D'_{2}=29}$。

実数値または混合整数決定変数を持つタスクの処理には、進化戦略^{[ 15 ]}や実数符号化 GA ^{[ 16 ] [ 17 ] [ 18 ]}などの EAが適しています。混合整数値の場合、丸めがよく使用されますが、これは冗長性の要件に違反します。実数値の必要な精度を合理的に狭めることができる場合は、整数符号化 GA を使用することでこの違反を解消できます。^{[ 19 ] [ 20 ]}この目的のために、実数値の有効な桁は、適切な係数を乗算することによって整数にマッピングされます。たとえば、12.380 は 1000 を乗算することで整数 12380 になります。これはもちろん、評価と結果の表示のための遺伝子型-表現型マッピングで考慮する必要があります。一般的な形式は、整数または実数値のリストまたは配列で構成される染色体です。

組み合わせ問題は主に、一連の基本要素の最適な順序を見つけることに関係しています。例として、最短ルートで指定された数の都市をちょうど一度ずつ訪問したい巡回セールスマンの問題を考えてみましょう。染色体への最も単純で明白なマッピングは、都市に連続して番号を付け、結果として得られるシーケンスを順列として解釈し、それを染色体に直接格納することです。ここで、1つの遺伝子は都市の順序番号に対応します。^{[ 21 ]}しかし、この場合、変異演算子は遺伝子の順序のみを変更でき、遺伝子を削除したり複製したりすることはできません。^{[ 22 ]}したがって、染色体には都市への可能なツアーの経路が含まれます。例として、シーケンス${\displaystyle 3,5,7,1,4,2,9,6,8}$9つの都市のうち、以下の染色体が対応する都市が該当する可能性があります。

パス表現と呼ばれるこのエンコーディングに加えて、順列を表現する他の方法もいくつかあります。たとえば、順序表現や行列表現などです。^{[ 22 ] [ 23 ]}

遺伝的表現が、決定変数に加えて、進化や遺伝子型から表現型へのマッピングに影響を与え、かつそれ自体が進化の対象となる追加情報を含む場合、これは共進化と呼ばれます。典型的な例は、各染色体に1つ以上の突然変異ステップサイズを戦略パラメータとして含む進化戦略（ES）です。^{[ 15 ]}別の例としては、スケジューリングタスクにおけるリソース割り当ての選択ヒューリスティックを制御する追加遺伝子があります。^{[ 24 ]}

このアプローチは、優れた解決策は、戦略パラメータの適切な選択、あるいは遺伝子型と表現型のマッピングに影響を与える制御遺伝子に基づいているという仮定に基づいている。ESの成功は、この仮定を裏付ける証拠となる。

上に示した染色体は、連続最適化、混合整数最適化、純整数最適化、または組み合わせ最適化の処理タスクに適しています。一方、これらの最適化領域の組み合わせでは、タスクに応じて、単純な値の文字列にマッピングすることがますます困難になります。この目的のために、EA GLEAM (General Learning Evolutionary Algorithm and Method) では、遺伝子の概念の次の拡張が提案されています。^{[ 25 ]}遺伝子は、表現型の要素または基本特性の説明とみなされ、複数のパラメータを持つ場合があります。この目的のために、表現型の特定の要素を記述するために必要な数の適切なデータ型のパラメータを含む遺伝子型が定義されます。染色体は、遺伝子型のデータオブジェクトとしての遺伝子で構成され、アプリケーションに応じて、各遺伝子型は遺伝子として正確に 1 回出現するか、染色体に任意の回数含まれる可能性があります。後者は、一部の問題で必要とされるように、動的な長さの染色体につながります。^{[ 26 ] [ 27 ]}遺伝子型定義には、染色体生成中および対応する突然変異時に観察される遺伝子パラメータの許容値範囲に関する情報も含まれており、致死突然変異を引き起こすことはありません。組み合わせ部分を持つタスクには、遺伝子全体、つまりパラメータごと移動または再配置できる適切な遺伝子演算子があります。

スケジューリングタスクを例として使用します。このタスクでは、異なる数の異種リソースを必要とするワークフローをスケジュールする必要があります。ワークフローは、どのワーク ステップを並列処理できるか、どのワーク ステップを順番に実行する必要があるかを指定します。この文脈では、異種リソースとは、異なる処理能力に加えて、異なるコストで異なる処理時間を意味します。^{[ 24 ]}したがって、各スケジューリング操作には、リソースの選択を決定する 1 つ以上のパラメータが必要であり、パラメータの値の範囲は、各ワーク ステップで使用可能な代替リソースの数に依存します。適切な染色体は、ワーク ステップごとに 1 つの遺伝子タイプを提供し、この場合、必要なリソースごとに 1 つのパラメータを持つ対応する遺伝子が 1 つあります。遺伝子の順序は、スケジューリング操作の順序、したがって、割り当ての競合が発生した場合の優先順位を決定します。リソースが 2 つあり、それぞれに 4 つと 7 つの代替リソースがあるワーク ステップ 15 の遺伝子タイプの定義の例は、左の画像に示すようになります。パラメータは、それぞれの作業ステップで使用可能なリソースのリストにおけるインデックスを表すため、その値の範囲は0から始まります。右の画像は、リスト表現における遺伝子型に属する染色体の3つの遺伝子の例を示しています。

染色体におけるツリー表現は、コンピュータプログラムや回路を生成するEAの一種である遺伝的プログラミングで使用されます。^{[ 10 ]}これらのツリーは、コンパイラがコンピュータプログラムを翻訳する際に内部表現として生成する構文ツリーに対応します。隣の図は、例として数式の構文ツリーを示しています。突然変異演算子は、表現された構文構造に応じて、サブツリーを再配置、変更、または削除することができます。組み換えは、適切なサブツリーを交換することによって実行されます。^{[ 28 ]}