枝組み立て交叉法(Edge Assembly Crossover)の解説

はじめに

枝組み立て交叉法(EAX)とは、巡回セールスマン問題(TSP)を遺伝的アルゴリズムで解く際の交叉手法の一つです。

手順1

親Aと親Bの辺を交互にたどって、閉路を作成します。この閉路をABサイクルと呼びます。

なお、このABサイクルへの分割は一意ではありません。

手順2

一つ以上のABサイクルを選択し、それらの辺の集合(E-Set)を作成します。

これを親Aに適用します。
具体的な手順は以下の通りです。

1. E-Set内の親A由来の辺を削除する
2. E-Set内の親B由来の辺を追加する

この操作によって、一つ以上の部分巡回路からなる中間個体が作成されます。

手順3

中間個体の部分巡回路を、二つの辺をつなぎ変えることで結合し、一つにまとめます。

このとき、つなぎ変えでの経路長の増加量が、最小となる辺の組み合わせでつなぎ変えます。

そうすることで、TSPの制約を満たした個体が作成できます。