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

#GAで巡回セールスマン問題を解く
##はじめに
遺伝的アルゴリズム（GA）はメタヒューリスティックな最適化アルゴリズムと言われています。
様々な問題に対して適用可能であり、僕自信も建築分野に応用できないかと模索しています。
巡回セールスマン問題（TSP）自体は以前にpythonで記述したことがありましたが、今回はGAの理解を試すためにゼロから自力で実装してみました。（問題点があるかもしれませんが悪しからず。）

###実装結果：

![TSP.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/400162/808b2ca2-600b-e46d-af5a-a51d302f026f.gif)


##GAについて
GAのアルゴリズムの流れは以下の通りです。

1. 初期個体生成
2. 評価
3. 選択
4. 交叉、突然変異

指定したループ回数、または既定値になるまで2~4のプロセスを繰り返す。

##巡回セールスマン問題について
巡回セールスマン問題はn個の地点すべてを巡回する最短距離を求める問題です。
総当たりで探索しようとすると取りうる組み合わせがn!となり、気が遠くなるほどの時間を要してしまいます。


##実装内容
初期個体生成　ー＞　generator() 
評価　　　　　ー＞　evaluate()
選択　　　　　ー＞　selection()
交叉　　　　　ー＞　crossover()
突然変異　　　ー＞　mutation()

描画　　　　　ー＞　show_route()

上記の６つの関数を作成し組み合わせて利用することでTSPを解いています。

###generator()
引数はnumが地点の数。pop_numが個体数です。
初期に地点をランダムに作成し、keyを地点番号、座標値をvalueとして辞書を作成しています。
今回は地点番号の並び順を遺伝子配列としてみなし、アルゴリズムを構築していきます。
はじめの巡回経路はランダムに作成しています。

```python:
def generator(num, pop_num):
    """ 都市を初期生成 """

    # 範囲指定
    x_range = 200
    y_range = 200

    x_coordinate = [rnd.randint(0, x_range) for _ in range(num)]
    y_coordinate = [rnd.randint(0, y_range) for _ in range(num)]

    coordinate = [[x_coordinate[i], y_coordinate[i]] for i in range(num)]

    # keyが都市の番号、valueが座標値の辞書作成。
    position_info = {}
    for i in range(num):
        position_info[i] = coordinate[i]

    # 初期の巡回順序生成
    select_num = [i for i in range(num)]
    all_route = [rnd.sample(select_num, num) for _ in range(pop_num)]

    return position_info, all_route
```

###evaluate()
ここでは各座標のユークリッド距離の総和を評価値として評価関数を設計しています。
show_route()で現世代における最良個体を描画しています。

```python:
def evaluate(position_info, all_route, loop=0):
    """ ユークリッド距離の総和を計算し評価値とする。 """

    evaluate_value = []
    for i in range(len(all_route)):
        temp_evaluate_value = []
        x_coordinate = [position_info[all_route[i][x]][0] for x in range(len(all_route[i]))]
        y_coordinate = [position_info[all_route[i][y]][1] for y in range(len(all_route[i]))]
        for j in range(len(all_route[i])):
            if j == len(all_route[i]) - 1:
                distance = math.sqrt(
                    pow((x_coordinate[j] - x_coordinate[0]), 2) + pow((y_coordinate[j] - y_coordinate[0]), 2))
            else:
                distance = math.sqrt(
                    pow((x_coordinate[j] - x_coordinate[j + 1]), 2) + pow((y_coordinate[j] - y_coordinate[j + 1]), 2))
            temp_evaluate_value.append(distance)
        evaluate_value.append(sum(temp_evaluate_value))

    # 一番優秀な個体をmatplotで描画
    excellent_evaluate_value = min(evaluate_value)
    draw_pop_index = evaluate_value.index(excellent_evaluate_value)

    show_route(position_info, all_route[draw_pop_index],int(excellent_evaluate_value), loop=loop + 1)

    return evaluate_value

```

###selection()
今回は選択として、トーナメント選択、エリート主義を導入しています。
トーナメント選択は指定したサイズのトーナメントを作成し、その中で指定数の優良個体を選択します。
エリート主義は指定した上位個体を問答無用で次世代に残す手法です。

```python:
def selection(all_route, evaluate_value, tournament_select_num, tournament_size, elite_select_num, ascending=False):
    """ トーナメント選択とエリート保存を行う"""

    select_pop = []
    elite_pop = []
    # トーナメント選択
    while True:
        select = rnd.sample(evaluate_value, tournament_size)
        select.sort(reverse=ascending)
        for i in range(tournament_select_num):
            value = select[i]
            index = evaluate_value.index(value)
            select_pop.append(all_route[index])

        # 個体数の半数個選択するまで実行
        if len(select_pop) >= len(all_route) / 2:
            break

    # エリート保存
    sort_evaluate_value = copy.deepcopy(evaluate_value)
    sort_evaluate_value.sort(reverse=ascending)
    for i in range(elite_select_num):
        value = sort_evaluate_value[i]
        index = evaluate_value.index(value)
        elite_pop.append(all_route[index])

    return select_pop, elite_pop

```

###crossover()
指定した確率によって交叉を実行します。
ここでは順序交叉と呼ばれる交叉手法を使用しています。

```python:
def crossover(select_pop, crossover_prob):
    ''' 確率的に順序交叉を実行する '''

    cross_pop = rnd.sample(select_pop, 2)
    pop_1 = cross_pop[0]
    pop_2 = cross_pop[1]

    check_prob = rnd.randint(0, 100)
    if check_prob <= crossover_prob:

        # 順序交叉
        new_pop_1 = []
        cut_index = rnd.randint(1, len(pop_1) - 2)
        new_pop_1.extend(pop_1[:cut_index])
        for i in range(len(pop_1)):
            if pop_2[i] not in new_pop_1:
                new_pop_1.append(pop_2[i])

        new_pop_2 = []
        new_pop_2.extend(pop_1[cut_index:])
        for i in range(len(pop_1)):
            if pop_2[i] not in new_pop_2:
                new_pop_2.append(pop_2[i])

        return new_pop_1, new_pop_2

    else:
        return pop_1, pop_2
```

###mutation()
指定した確率で突然変異が起こるようにしています。
今回は地点番号を入れ替える操作を突然変位としています。

```python:
def mutation(pop, mutation_prob):
    """ 循環経路の順番をランダムで入れ替える """

    check_prob = rnd.randint(0, 100)

    if check_prob <= mutation_prob:
        select_num = [i for i in range(num)]
        select_index = rnd.sample(select_num, 2)

        a = pop[select_index[0]]
        b = pop[select_index[1]]
        pop[select_index[1]] = a
        pop[select_index[0]] = b

    return pop
```


###show_route()
matplotlibを使用して経路を描画する関数です。
plt.savefig()は描画したグラフをpngとして保存するためのものです。

```python:

def show_route(position_info, route, excellent_evaluate_value,  loop=0):
    """ matplotlibで循環経路を描画 """

    x_coordinate = [position_info[route[i]][0] for i in range(len(route))]
    y_coordinate = [position_info[route[i]][1] for i in range(len(route))]
    x_coordinate.append(position_info[route[0]][0])
    y_coordinate.append(position_info[route[0]][1])

    plt.scatter(x_coordinate, y_coordinate)
    plt.plot(x_coordinate, y_coordinate, label=excellent_evaluate_value)
    plt.title("Generation: {}".format(loop))
    plt.legend()

    plt.savefig("img/tsp{}".format(loop))  # pngとして保存。カレントディレクトリにimgフォルダを置く必要あり。
    plt.show()
```

##全ソースコード
以下のパラメータをチューニングすることで結果が異なってきます。
現状指定している値は目安なので自由にいじってみてください。

num = 30  # 地点の数
pop_num = 200  # 個体数
generation_num = 200  # 世代数
tournament_size = 10  # トーナメントサイズ
tournament_select_num = 2  # トーナメントサイズで選択する個体数
elite_select_num = 1  # エリート主義で選択する個体数
crossover_prob = 50  # 交叉確率
mutation_prob = 3  # 交叉確率

```python:

# coding:utf-8

import random as rnd
import matplotlib.pyplot as plt
import math
import copy


def generator(num, pop_num):
    """ 都市を初期生成 """

    # 範囲指定
    x_range = 200
    y_range = 200

    x_coordinate = [rnd.randint(0, x_range) for _ in range(num)]
    y_coordinate = [rnd.randint(0, y_range) for _ in range(num)]

    coordinate = [[x_coordinate[i], y_coordinate[i]] for i in range(num)]

    # keyが都市の番号、valueが座標値の辞書作成。
    position_info = {}
    for i in range(num):
        position_info[i] = coordinate[i]

    # 初期の巡回順序生成
    select_num = [i for i in range(num)]
    all_route = [rnd.sample(select_num, num) for _ in range(pop_num)]

    return position_info, all_route


def evaluate(position_info, all_route, loop=0):
    """ ユークリッド距離の総和を計算し評価値とする。 """

    evaluate_value = []
    for i in range(len(all_route)):
        temp_evaluate_value = []
        x_coordinate = [position_info[all_route[i][x]][0] for x in range(len(all_route[i]))]
        y_coordinate = [position_info[all_route[i][y]][1] for y in range(len(all_route[i]))]
        for j in range(len(all_route[i])):
            if j == len(all_route[i]) - 1:
                distance = math.sqrt(
                    pow((x_coordinate[j] - x_coordinate[0]), 2) + pow((y_coordinate[j] - y_coordinate[0]), 2))
            else:
                distance = math.sqrt(
                    pow((x_coordinate[j] - x_coordinate[j + 1]), 2) + pow((y_coordinate[j] - y_coordinate[j + 1]), 2))
            temp_evaluate_value.append(distance)
        evaluate_value.append(sum(temp_evaluate_value))

    # 一番優秀な個体をmatplotで描画
    excellent_evaluate_value = min(evaluate_value)
    draw_pop_index = evaluate_value.index(excellent_evaluate_value)

    show_route(position_info, all_route[draw_pop_index],int(excellent_evaluate_value), loop=loop + 1)

    return evaluate_value


def selection(all_route, evaluate_value, tournament_select_num, tournament_size, elite_select_num, ascending=False):
    """ トーナメント選択とエリート保存を行う"""

    select_pop = []
    elite_pop = []
    # トーナメント選択
    while True:
        select = rnd.sample(evaluate_value, tournament_size)
        select.sort(reverse=ascending)
        for i in range(tournament_select_num):
            value = select[i]
            index = evaluate_value.index(value)
            select_pop.append(all_route[index])

        # 個体数の半数個選択するまで実行
        if len(select_pop) >= len(all_route) / 2:
            break

    # エリート保存
    sort_evaluate_value = copy.deepcopy(evaluate_value)
    sort_evaluate_value.sort(reverse=ascending)
    for i in range(elite_select_num):
        value = sort_evaluate_value[i]
        index = evaluate_value.index(value)
        elite_pop.append(all_route[index])

    return select_pop, elite_pop


def crossover(select_pop, crossover_prob):
    ''' 確率的に順序交叉を実行する '''

    cross_pop = rnd.sample(select_pop, 2)
    pop_1 = cross_pop[0]
    pop_2 = cross_pop[1]

    check_prob = rnd.randint(0, 100)
    if check_prob <= crossover_prob:

        # 順序交叉
        new_pop_1 = []
        cut_index = rnd.randint(1, len(pop_1) - 2)
        new_pop_1.extend(pop_1[:cut_index])
        for i in range(len(pop_1)):
            if pop_2[i] not in new_pop_1:
                new_pop_1.append(pop_2[i])

        new_pop_2 = []
        new_pop_2.extend(pop_1[cut_index:])
        for i in range(len(pop_1)):
            if pop_2[i] not in new_pop_2:
                new_pop_2.append(pop_2[i])

        return new_pop_1, new_pop_2

    else:
        return pop_1, pop_2


def mutation(pop, mutation_prob):
    """ 循環経路の順番をランダムで入れ替える """

    check_prob = rnd.randint(0, 100)

    if check_prob <= mutation_prob:
        select_num = [i for i in range(num)]
        select_index = rnd.sample(select_num, 2)

        a = pop[select_index[0]]
        b = pop[select_index[1]]
        pop[select_index[1]] = a
        pop[select_index[0]] = b

    return pop


def show_route(position_info, route, excellent_evaluate_value,  loop=0):
    """ matplotlibで循環経路を描画 """

    x_coordinate = [position_info[route[i]][0] for i in range(len(route))]
    y_coordinate = [position_info[route[i]][1] for i in range(len(route))]
    x_coordinate.append(position_info[route[0]][0])
    y_coordinate.append(position_info[route[0]][1])

    plt.scatter(x_coordinate, y_coordinate)
    plt.plot(x_coordinate, y_coordinate, label=excellent_evaluate_value)
    plt.title("Generation: {}".format(loop))
    plt.legend()

    plt.savefig("img/tsp{}".format(loop))  # pngとして保存。カレントディレクトリにimgフォルダを置く必要あり。
    plt.show()


# 初期生成時のパラメータ
num = 30  # 都市の数
pop_num = 200  # 個体数
generation_num = 200  # 世代数

# 選択のパラメータ
tournament_size = 10
tournament_select_num = 2
elite_select_num = 1

# 交叉の確率
crossover_prob = 50

# 突然変異の確率
mutation_prob = 3


# 初期生成
position_info, all_route = generator(num, pop_num)

# 評価
evaluate_value = evaluate(position_info, all_route)

for loop in range(generation_num):
    # 選択
    select_pop, elite_pop = selection(
        all_route, evaluate_value, tournament_select_num, tournament_size, elite_select_num, ascending=False)

    # 選択した個体の中から2個体選択し交叉や突然変異を適用する。
    next_pop = []
    while True:
        # 交叉
        pop_1, pop_2 = crossover(select_pop, crossover_prob)
        # 突然変異
        pop_1 = mutation(pop_1, mutation_prob)
        pop_2 = mutation(pop_2, mutation_prob)

        next_pop.append(pop_1)
        next_pop.append(pop_2)

        if len(next_pop) >= pop_num - elite_select_num:
            break

    # エリート主義。優良個体を次世代へ継承。
    next_pop.extend(elite_pop)

    # 評価
    evaluate_value = evaluate(position_info, next_pop, loop=loop + 1)

    # 更新
    all_route = next_pop

```