交叉（進化アルゴリズム）

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

進化計算における様々なアルゴリズムは、遺伝情報を格納するために異なるデータ構造を使用することがあり、それぞれの遺伝表現は異なる交叉演算子で組み換えることができます。交叉で組み換え可能な典型的なデータ構造としては、ビット配列、実数のベクトル、またはツリーなどがあります。

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

従来の遺伝的アルゴリズムでは、遺伝情報はビット配列で表される染色体に格納されます。ビット配列に対する交叉法は一般的であり、遺伝的組換えの代表的な例です。

上記で示した交叉演算子、およびビット列に対する他のほとんどの交叉演算子については、遺伝子がそれぞれ整数または実数値で構成される整数または実数値ゲノムにも同様に適用できる。個々のビットの代わりに、整数または実数値が単純に子ゲノムにコピーされる。子孫は、2つの親によって張られる超体の残りの角に位置する。${\displaystyle P_{1}=(1.5,6,8)}$そして${\displaystyle P_{2}=(7,2,1)}$添付の3次元ケースの画像に示されているように。

中間組換え

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

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

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

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

組み合わせタスクでは、通常、ある集合の順列であるゲノム用に特別に設計された順列が使用されます。基となる集合は通常、${\displaystyle \mathbb {N} }$または${\displaystyle \mathbb {N} _{0}}$整数ゲノムに対して1点交叉、n点交叉、または均一交叉を用いる場合、子ゲノムに同じ値が2回含まれたり、値が欠落したりする可能性があります。これは、遺伝子修復によって解決できます。例えば、冗長な遺伝子を位置的に忠実に、他の子ゲノムから欠落している遺伝子と置き換えるといった方法です。

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

以下では、例として2つの交叉演算子、すなわちTSPに着想を得た部分マッピング交叉（PMX）と、順序に基づく順列用に設計された順序交叉（OX1）を示す。いずれの場合も、親染色体を交換することで2番目の子孫を生成できる。

• 進化アルゴリズム
• 遺伝子表現
• フィットネス機能
• 選択（遺伝的アルゴリズム）

• ジョン・ホランド（1975）。『自然および人工システムにおける適応』、博士論文、ミシガン大学出版局、ミシガン州アナーバー。ISBN 0-262-58111-6。
• シュヴェーフェル、ハンス＝パウル（1995）。進化と最適解の探索。ニューヨーク：ジョン・ワイリー＆サンズ。ISBN 0-471-57148-2。
• デイビス、ローレンス（1991）。遺伝的アルゴリズムハンドブック。ニューヨーク：ヴァン・ノストランド・ラインホールド。ISBN 0-442-00173-8OCLC 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；ミハレヴィッチ、ズビグニエフ編（1999）。進化計算。第1巻、基本アルゴリズムと演算子。ブリストル：物理学研究所出版。ISBN 0-585-30560-9OCLC 45730387​​ 

• ニュースグループ: comp.ai.genetic FAQ - クロスオーバー（組換えとも呼ばれる）のセクションを参照してください。