遺伝的アルゴリズム・巡回セールスマン問題

Image from Gyazo

ノートブックの作成

Google Colaboratory を起動し,新規にノートブックを作成してください. ノートブックのタイトルは AI-11 とします. ノートブックの作成方法は第1回の資料を参照してください.

最初に Simple AINetworkX をインストールします. NetworkXはネットワーク分析のためのライブラリです. セルで下記のコマンドを実行してください.

!pip install simpleai
!pip install network

巡回セールスマン問題

今回は 巡回セールスマン問題(Traveling Salesman Problem) を取り上げましょう.

巡回セールスマン問題

$A,B,C,D,E,F,G,H,I,J$で表される10の都市がある. 各都市の座標は次の表で与えられる.

都市ABCDEFGHIJ
X17973263578310012355
Y7281597604826624977
セールスマンは,全ての都市を1回だけ訪れて,出発した都市に戻る. この条件を満たす巡回路において,経路コスト(ユークリッド距離)が最小のものを求めよ. 例えば,次の経路は条件を満たす巡回路である. この経路コストは約$558$である. $$ A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F \rightarrow G \rightarrow H \rightarrow I \rightarrow J \rightarrow A $$ 10都市を巡る巡回路の組み合わせは$1814400$通り存在する(逆の順番で巡る経路が存在するため2で割る). $$ \frac{10!}{2} = 1814400 $$ Image from Gyazo

都市ネットワーク

10都市を巡る巡回路を,NetworkXライブラリを利用して,ネットワーク(グラフ)として表現します. 都市はnodes,経路はrouteで表します. このとき,都市の座標は辞書型の pos に設定します. また,経路は2都市間のタプル("A","B")を繋げて表現します.

import networkx as nx
import numpy as np
import random
import copy
from simpleai.search import SearchProblem
from simpleai.search.local import genetic
# グラフの初期化
graph = nx.Graph()

# ノード
nodes = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]

# ノードの位置
pos ={
  "A": (17, 72),
  "B": (97, 8),
  "C": (32, 15),
  "D": (63, 97),
  "E": (57, 60),
  "F": (83, 48),
  "G": (100, 26),
  "H": (12, 62),
  "I": (3, 49),
  "J": (55, 77)
}

# 経路
route = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "E"), ("E", "F"), ("F", "G"), ("G", "H"), ("H", "I"), ("I", "J"), ("J", "A")]
graph.add_edges_from(route)

# 描画
nx.draw(graph, pos=pos, with_labels=True)

Image from Gyazo

遺伝的アルゴリズム

前回に引き続き,巡回セールスマン問題を 遺伝的アルゴリズム(Genetic Algorithm) で解くことに挑戦します. まずは,巡回セールスマン問題における遺伝的アルゴリズムの個体(遺伝子)の定義を考えます.

都市を回る順番をそのまま個体として表現することを考えます. 例えば,$A,B,\cdots,E$の5つの都市の巡回路において,$1,2, \cdots, 5$の数字を割り当て, この数字の列を個体とする方法です.

$$ A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow A $$

$$ I_1 = (1, 2, 3, 4, 5) $$

$$ A \rightarrow D \rightarrow E \rightarrow B \rightarrow C \rightarrow A $$

$$ I_2 = (1, 4, 5, 2, 3) $$

この方法では,$I_1$と$I_2$に交叉を適用したとき,巡回路の条件を満たさない解が得られることがあります(致死解). 例えば,上記の$I_1$と$I_2$の3番目の遺伝子から交叉する場合を考えます. 同じ都市を2回訪れる経路や,全ての都市を巡らない経路が生成されることがわかります.

$$ A \rightarrow B \rightarrow E \rightarrow B \rightarrow C \rightarrow A $$

$$ I_{1}^{’} = (1, 2, 5, 2, 3) $$

$$ A \rightarrow D \rightarrow C \rightarrow D \rightarrow E \rightarrow A $$

$$ I_{2}^{’} = (1, 4, 3, 4, 5) $$

そこで,次のように個体を表現することにします. この方法では,訪れる都市が,$A, B, C, D, E$の何番目にあるかを表します. 例えば,最初に訪れる都市が$A$であれば,$A$は$A, B, C, D, E$の0番目にあるため,遺伝子は0とします. 次に訪れる都市が$D$であれば,$D$は$B, C, D, E$の2番目にあるため,遺伝子は2とします. この方法では致死解は生じません.

$$ A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow A $$

$$ I_{1}^{’} = (0, 0, 0, 0, 0) $$

訪問する都市 都市の順番 遺伝子
A ABCDE 0
B BCDE 0
C CDE 0
D DE 0
E E 0

$$ A \rightarrow D \rightarrow E \rightarrow B \rightarrow C \rightarrow A $$

$$ I_2 = (0, 2, 2, 0, 0) $$

訪問する都市 都市の順番 遺伝子
A ABCDE 0
D BCDE 2
E BCE 2
B BC 0
C C 0

上記の方法に従って,経路から個体(遺伝子)を生成するtoGene()を定義します. 初期経路の個体が$(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)$となっていることがわかります.

# 経路から個体(遺伝子)へ
def toGene(route):

  destinations = list(copy.deepcopy(graph.nodes))
  gene = []

  for edge in route:
    index = destinations.index(edge[0])
    destinations.pop(index)
    gene.append(index)

  return gene

gene = toGene(route)
print(gene)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

逆に個体(遺伝子)から経路を生成するtoRoute()を定義します. 個体に対応する経路が下記であることがわかります.

$$ A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F \rightarrow G \rightarrow H \rightarrow I \rightarrow J \rightarrow A $$

# 個体(遺伝子)から経路へ
def toRoute(gene):
  destinations = list(copy.deepcopy(graph.nodes))
  nodes = []

  for index in gene:
    node = destinations[index]
    destinations.pop(index)
    nodes.append(node)

  route = []

  for i, node in enumerate(nodes):
    edge = ((nodes[i], nodes[(i+1) % len(nodes)]))
    route.append(edge)

  return route

route = toRoute(gene)
print(route)
[('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'F'), ('F', 'G'), ('G', 'H'), ('H', 'I'), ('I', 'J'), ('J', 'A')]

ランダムに個体を生成するrandomGene()を定義します. 生成された個体と対応する経路を合わせて確認しておきます.

# ランダムに個体を生成
def randomGene():
    destinations = list(copy.deepcopy(graph.nodes))
    gene = []

    for i in range(len(destinations)):
      node = random.choice(destinations)
      index = destinations.index(node)
      destinations.pop(index)
      gene.append(index)

    return gene

gene = randomGene()
print(gene)
print(toRoute(gene))
[9, 4, 4, 6, 0, 2, 1, 2, 1, 0]
[('J', 'E'), ('E', 'F'), ('F', 'I'), ('I', 'A'), ('A', 'D'), ('D', 'C'), ('C', 'H'), ('H', 'G'), ('G', 'B'), ('B', 'J')]

巡回セールスマン問題の目的関数となる経路コストを算出するdistance()を定義します. この経路コストを 最小化 することが目的となります.

# 経路距離
def distance(route):
  d = 0

  for edge in route:
    pos_head = np.array(pos[edge[0]])
    pos_tail = np.array(pos[edge[1]])
    d += np.linalg.norm(pos_tail - pos_head)

  return d

d = distance(route)
print(f"distance={d}")
distance=557.6889363201603

実装

クラスの定義

それでは,遺伝的アルゴリズムを実装しましょう. 最初に初期状態を定義します.

START = toGene(route)

インポートしたSearchProblemクラスをオーバライドして, 巡回セールスマン問題を表す TSProblem を定義します. オーバライドするメソッドは,valuegenerate_random_statecrossovermutate の4種類です.

class TSProblem(SearchProblem):

    def value(self, state):
        ...

    def generate_random_state(self):
        ...     

    def crossover(self, state1, state2):
        ...

    def mutate(self, state):
        ...

value(self, state)

個体stateの経路コストを算出します. 巡回セールスマン問題は経路コストを最小化する必要がありますが, ここでは目的関数を負の値で表し,最大化 を目的とした問題として扱います.

def value(self, state):

  route = toRoute(state)
  value = -1 * distance(route)

  #--------------------
  # 途中経過の出力
  global max_state
  global max_value

  if max_value < value:
	max_state = state
	max_value = value
	print(f"max state: {max_state}({max_value:.3f})")
  #--------------------

  return value

generate_random_state(self)

ランダムに個体geneを生成します.

def generate_random_state(self):

  gene = randomGene()

  return gene

crossover(self, state1, state2)

個体state1と個体state2を交叉し,新しい個体を生成します. 交叉する位置は乱数で決定します.

def crossover(self, state1, state2):

  child = []

  index = np.random.randint(0, len(state1))

  for i in range(0, index):
	child.append(state1[i])

  for i in range(index, len(state2)):
	child.append(state2[i])

  return child

mutate(self, state)

個体stateを突然変異させ,新しい個体を生成します. 突然変異する位置は乱数で決定します. 位置に応じて設定する値の最大値が異なることに注意してください. 例えば,個体の最初の遺伝子は$0,1,\cdots,9$の10通りから選択しますが, 5番目の遺伝子は$0,1,\cdots,4$の5通りから選択します.

def mutate(self, state):

  child = list(copy.deepcopy(state))

  index = np.random.randint(0, len(child))
  max = len(child) - index
  child[index] = np.random.randint(0, max)

  return child

解の探索

遺伝的アルゴリズムgeneticを用いて解を探索します ここで,population_sizeは1世代の個体の数,mutation_chanceは突然変異の確率,iterations_limitは世代交代の数です. 経路コストは徐々に減少し,最終的に約$302$になりました.

max_state = START
max_value = -1000
problem = TSProblem(initial_state=START)
result = genetic(problem, population_size=300, mutation_chance=0.4, iterations_limit=100)
max state: [2, 7, 1, 0, 5, 4, 1, 0, 0, 0](-565.698)
max state: [6, 1, 6, 6, 5, 3, 0, 1, 0, 0](-540.774)
max state: [2, 1, 3, 1, 2, 4, 0, 2, 1, 0](-486.344)
max state: [2, 2, 0, 4, 5, 1, 3, 0, 1, 0](-478.315)
max state: [5, 7, 2, 3, 5, 0, 3, 1, 1, 0](-445.342)
max state: [5, 6, 6, 0, 1, 0, 2, 0, 1, 0](-405.025)
max state: [7, 7, 2, 5, 1, 4, 1, 2, 1, 0](-384.451)
max state: [3, 8, 0, 5, 1, 4, 0, 2, 1, 0](-381.537)
max state: [3, 0, 5, 5, 5, 3, 3, 0, 0, 0](-379.105)
max state: [2, 6, 0, 5, 1, 1, 3, 1, 1, 0](-372.361)
max state: [6, 1, 1, 0, 3, 3, 0, 2, 0, 0](-341.490)
max state: [2, 5, 1, 3, 2, 1, 3, 0, 0, 0](-327.178)
max state: [3, 0, 5, 5, 1, 3, 0, 1, 0, 0](-320.839)
max state: [5, 5, 1, 1, 4, 3, 0, 2, 0, 0](-309.094)
max state: [3, 0, 5, 5, 1, 0, 2, 1, 0, 0](-302.755)

得られた経路を確認すると,経路コストが最短となっていることがわかります.

$$ D \rightarrow A \rightarrow H \rightarrow I \rightarrow C \rightarrow B \rightarrow G \rightarrow F \rightarrow E \rightarrow J \rightarrow D $$

route = toRoute(result.state)
print(route)

# グラフの初期化
graph.clear()

# ノードの設定
graph.add_nodes_from(nodes)

# 経路の設定
graph.add_edges_from(route)

# 描画
nx.draw(graph, pos=pos, with_labels=True)
[('D', 'A'), ('A', 'H'), ('H', 'I'), ('I', 'C'), ('C', 'B'), ('B', 'G'), ('G', 'F'), ('F', 'E'), ('E', 'J'), ('J', 'D')]

Image from Gyazo

課題

ノード数を12まで増やして,最適な巡回路を探索してください. ノードの座標は自由に設定して構いません.

Google Colaboratoryで作成した AI-11.ipynb を保存し, ノートブック(.ipynb) をダウンロードして提出しなさい. 提出の前に必ず下記の設定を行うこと.

参考書籍

愛知県名古屋市にある椙山女学園大学 文化情報学部 向研究室の公式サイトです. 専門は情報科学であり,人工知能やデータベースなどの技術要素を指導しています. この公式サイトでは,授業で使用している教材を公開すると共に, ベールに包まれた女子大教員のミステリアスな日常を4コマ漫画でお伝えしていきます. サイトに関するご意見やご質問はFacebookまたはTwitterでお問い合わせください.