交差（遺伝的アルゴリズム）

遺伝的アルゴリズムと進化的計算において、交叉（組み換えとも呼ばれる）は、2 つの親の遺伝情報を組み合わせて新しい子孫を生成するために使用される遺伝演算子です。これは、既存の集団から新しいソリューションを確率的に生成する1 つの方法であり、生物学における有性生殖の際に発生する交叉に類似しています。ソリューションは、既存のソリューションを複製することによっても生成でき、これは無性生殖に類似しています。新しく生成されたソリューションは、集団に追加される前に 突然変異する可能性があります。

進化計算におけるさまざまなアルゴリズムでは、遺伝情報を格納するためにさまざまなデータ構造が使用される可能性があり、各遺伝表現はさまざまな交差演算子で再結合できます。交差で再結合できる一般的なデータ構造は、ビット配列、実数のベクトル、またはツリーです。

以下に示す演算子のリストは決して完全なものではなく、主にこの二元遺伝子演算子タイプの例示的な説明として役立ちます。より多くの演算子と詳細については、文献を参照してください。^{[1] [2] [3] [4] [5]}

従来の遺伝的アルゴリズムでは、ビット配列で表される染色体に遺伝情報を格納します。ビット配列の交差法は一般的であり、遺伝子組み換えのわかりやすい例です。

両親の染色体上の点がランダムに選択され、「交差点」と指定されます。その点の右側のビットが、2 つの親の染色体間で交換されます。その結果、両親から遺伝情報の一部を受け継いだ 2 人の子孫が生まれます。

2 点交差では、親染色体から 2 つの交差ポイントがランダムに選択されます。2 つのポイント間のビットは親生物間で交換されます。

2 点クロスオーバーは、異なるクロスオーバー ポイントを持つ 2 つの単一ポイント クロスオーバーを実行することと同じです。この戦略は、任意の正の整数 k に対して k 点クロスオーバーに一般化でき、k 個のクロスオーバー ポイントを選択します。

均一交差では、通常、各ビットはどちらの親からも同じ確率で選択されます。^[6]他の混合比が使用されることもあり、その結果、一方の親からもう一方の親よりも多くの遺伝情報を受け継いだ子孫が生まれます。均一交差では、染色体をセグメントに分割するのではなく、各遺伝子を個別に扱います。この方法では、基本的に各染色体についてコインを投げて、子孫に含めるかどうかを決定します。

上で示した交差演算子と、ビット文字列に対する他のほとんどの交差演算子については、遺伝子がそれぞれ整数または実数値で構成される整数または実数値のゲノムにも同様に適用されると考えられます。個々のビットの代わりに、整数または実数値が子ゲノムにコピーされるだけです。子孫は、3 次元の場合の添付画像に例示されているように、 2つの親とによって張られるハイパーボディの残りのコーナー上にあります。${\displaystyle P_{1}=(1.5,6,8)}$${\displaystyle P_{2}=(7,2,1)}$

ビット列の一様交差の規則が子孫の生成中に適用される場合、これは離散的組換えとも呼ばれます。^[7]

この組み換え演算子では、子ゲノムの対立遺伝子値は、2つの親ゲノムの対立遺伝子を混合することによって生成される。^[7]${\displaystyle a_{i}}$${\displaystyle a_{i,P_{1}}}$${\displaystyle a_{i,P_{2}}}$

${\displaystyle \alpha _{i}=\alpha _{i,P_{1}}\cdot \beta _{i}+\alpha _{i,P_{2}}\cdot \left(1-\beta _{i}\right)\quad {\mathsf {with}}\quad \beta _{i}\in \left[-d,1+d\right]}$遺伝子ごとにランダムに均等に分布${\displaystyle i}$

区間の選択により、親遺伝子の対立遺伝子値が張るハイパーボディの内部に加えて、子孫の値の範囲に関する特定の環境も問題になります。 の値は、そうでなければ存在する対立遺伝子値を減らす傾向に対抗するために推奨されます。^[8]${\displaystyle [-d,1+d]}$${\displaystyle 0.25}$${\displaystyle d}$${\displaystyle d=0}$

隣の図は、2次元の場合、中間組換えにおける2つの典型的な親との新しい対立遺伝子の可能な範囲を示しています。離散的組換えと子孫もプロットされています。中間組換えは、仮想アルファベット理論で要求される子ゲノムの対立遺伝子値の算術計算を満たしています。^{[9] [10]離散的組換えと中間組換えは、}進化戦略の標準として使用されます。^[11]${\displaystyle P_{1}=(3,6)}$${\displaystyle P_{2}=(9,2)}$${\displaystyle C_{1}}$${\displaystyle C_{2}}$

組み合わせタスクでは、通常、それ自体が集合の順列であるゲノム用に特別に設計された順列が使用されます。基礎となる集合は通常、またはのサブセットです。このようなゲノムに 1 点または n 点交差または整数ゲノムの均一交差を使用すると、子ゲノムに一部の値が 2 回含まれ、他の値が欠落している可能性があります。これは、遺伝子修復、たとえば、冗長な遺伝子を位置忠実度に従って他の子ゲノムの欠落している遺伝子と置き換えることによって修正できます。 ${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} _{0}}$

無効な子孫の生成を避けるために、順列用の特別な交差演算子が開発されました^[12]。これは、順列用のそのような演算子の基本要件、つまり、最初の順列のすべての要素が新しい順列にも存在し、順序のみが変更されるという要件を満たします。これは、すべてのシーケンスが許容される組み合わせタスクと、許容されない部分シーケンスの形で制約があるタスクに区別できます。最初のタスクタイプのよく知られた代表例は、巡回セールスマン問題(TSP) です。これは、最短のツアーで都市のセットを 1 回だけ訪問することを目標としています。制約付きタスクタイプの例としては、複数のワークフローのスケジューリングがあります。ワークフローでは、個々の作業ステップの一部にシーケンス制約が伴います。たとえば、ワークピースに対応する穴が開けられるまで、ねじを切ることはできません。このような問題は、順序ベースの順列とも呼ばれます。

以下では、TSP をモチーフにした部分マッピング交差 (PMX) と順序ベースの順列用に設計された順序交差 (OX1) の 2 つの交差演算子を例として示します。いずれの場合も、親染色体を交換することで 2 番目の子孫を生成できます。

PMX演算子はTSPのような問題の再結合演算子として設計されました。^{[13] [14]}手順の説明は例で示されています。

^{順序交差は、その原型はデイビス[1]}に遡り、ここでは交差ポイントが 2 つ以上ある、やや一般化されたバージョンで紹介されています。これは、相対的な順序に関する情報を 2 番目の親から子孫に伝達します。まず、交差ポイントの数と位置がランダムに決定されます。次に、結果として得られる遺伝子配列は、以下のように処理されます。

とりわけ、順序交叉は、1点交叉やn点交叉と組み合わせて使用​​すると、複数のワークフローをスケジュールするのに適しています。^[15]

これまで、順列に対する交差演算子は数多く提案されてきたため、以下のリストはほんの一部に過ぎません。詳細については、文献を参照してください。^{[1] [5] [14] [12]}

1. サイクルクロスオーバー（CX）^{[16] [14]}
2. 順序ベース交差（OX2）^{[5] [17]}
3. 位置ベースクロスオーバー（POS）^{[5] [17]}
4. エッジ組み換え^{[18] [14]}
5. 投票再結合（VR）^[12]
6. 交互位置クロスオーバー（AP）^[12]
7. 最大保存クロスオーバー（MPX）^{[5] [19]}
8. マージクロスオーバー（MX）^{[5] [20]}
9. 逐次構成的交差演算子（SCX）^[21]

先に示した遺伝的アルゴリズム、あるいはより一般的には進化的アルゴリズムによってTSPのような問題を解くための通常のアプローチは、違法な子孫を修復するか、そもそも違法な子孫が発生しないように演算子を適切に調整するかのいずれかである。あるいは、リアジは違法な子孫を回避する二重染色体表現の使用を提案している。^[22]

• 進化アルゴリズム
• 遺伝的表現
• 適応度関数
• 選択（遺伝的アルゴリズム）

• ジョン・ホランド（1975年）。『自然システムと人工システムにおける適応』、博士論文、ミシガン大学出版局、ミシガン州アナーバー。ISBN 0-262-58111-6 。
• シュヴェフェル、ハンス・ポール（1995年）。進化と最適探索。ニューヨーク：ジョン・ワイリー・アンド・サンズ。ISBN 0-471-57148-2。
• デイビス、ローレンス (1991)。遺伝的アルゴリズムハンドブック。ニューヨーク: ヴァン・ノストランド・ラインホールド。ISBN 0-442-00173-8. OCLC  23081440.
• Eiben, AE; Smith, JE (2015). 進化コンピューティング入門。ナチュラルコンピューティングシリーズ。ベルリン、ハイデルベルク: Springer。doi : 10.1007 / 978-3-662-44874-8。ISBN 978-3-662-44873-1. S2CID  20912932。
• Yu, Xinjie; Gen, Mitsuo (2010). 進化アルゴリズム入門。意思決定エンジニアリング。ロンドン: Springer。doi : 10.1007 / 978-1-84996-129-5。ISBN 978-1-84996-128-8。
• Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew 編 (1999)。進化的計算。第 1 巻、基本アルゴリズムと演算子。ブリストル: Institute of Physics Pub. ISBN 0-585-30560-9. OCLC  45730387.

• ニュースグループ: comp.ai.genetic FAQ - 交差 (組み換えとも呼ばれる) に関するセクションを参照してください。