Genetic Algorithmの勉強と巡回セールスマン問題

Last updated Dec 10, 2022

# Genetic Algorithm

Genetic Algorithm(GA, 遺伝的アルゴリズム)は、問題に対する解を個体とし、選択・交叉・突然変異の操作によって個体の集合からなる世代を更新し、最適解を導くヒューリスティックアルゴリズムです。

AtCoderの巡回セールスマン問題のジャッジを通せたので、手法を書き残しておきます。ジャッジ結果

各個体には「染色体」と呼ばれる、解を持つ情報の列を持たせます。今回は訪れる頂点番号の順番をそのまま順列として保持しました。

Genetic Algorithm中では、二つの染色体を混ぜて新しい染色体を作り出す「交叉」という操作を行います。この操作では二つの解の特徴を残しながら繋ぐ必要があります。今回は順序交叉を用いました。

順序交叉は片方の親から一部の順列をそのまま引き継ぎ、残りの部分についてはもう一つの親での相対的な順序で補完するというものです。

1
2
3
4
5
6
p1 = (1 2 3 | 4 5 6 7 | 8 9)
p2 = (4 5 2 | 1 8 7 6 | 9 3)

p2'= (9 3 2 1 8)

ch = (2 1 8 | 4 5 6 7 | 9 3)

解が確率で新しい解を見つけるように、突然変異という操作を行います。今回は、確率で2点swapを行うことにしました。

Algorithmの中で、どの個体を交叉させるかを選ぶ必要があり、これを「選択」と呼びます。今回は、個体が持つ解の距離から重みを計算し、その重みによって個体を2つ選んで交叉を行いました。

優秀な個体は次世代にそのままコピーして引き継ぐ手法があり、これをElitismといいます。今回はこれも採用しました。

ここまでの手法で、2WAまで減らすことができますが、これを無くすためにはGenetic Algorithm自体を改善する必要があります。

各世代で選択を行う前に、全ての個体について局所探索を行い、解をあらかじめある程度よくしておくという手法「Genetic Local Search(遺伝的局所探索)」が存在し、巡回セールスマンに有効であるという研究があります。これを採用することでACすることができました。