8-6. 遺伝的アルゴリズム（vcopt）で巡回セールスマン問題を解く（閉路はどうやるの？編）

GA / vcopt

2019/03/21

本記事の内容は2019年5月13日に更新されました。

やること
実行環境
考え方
import
関数の準備
2-opt法で最適化
GAで最適化

やること

巡回というくらいですから、セールスマンは戻ってこなければいけません。もちろんvcoptでできます。

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net

Portable Scientific Python 2/3 32/64bit Distribution for Windows

vcoptの使い方についてはチュートリアルをご参照ください。

vcoptの仕様については最新の仕様書をご参照ください。本記事執筆時とは仕様が異なる場合があります。

考え方

8-3は、[0, 1, 2, … , 19]の20パラメータ（20都市を訪れる順番）を並び替える問題でした。

閉路問題とする場合、0を除いて[1, 2, … , 19]の19パラメータの並び替え問題とし、評価関数と可視化関数の中で、前後に0を付けて[0, 1, 2, … , 19, 0]として計算や表示を行います。このようにすれば、0からスタートして0に帰って来る距離を最適化できます。

import

まずは、今回使うパッケージをインポートします。

import numpy as np
import numpy.random as nr
import matplotlib.pyplot as plt
from vcopt import vcopt

関数の準備

巡回セールスマン問題の作成。これまでと同じです。

#巡回セールスマン問題の作成
def create_tsp(town_num):
    
    #町のx座標とy座標の配列を作成
    town_x = nr.rand(town_num)
    town_y = nr.rand(town_num)
    
    return town_x, town_y

（必須）評価関数。paraの前後に0を付けてpara_fullとし、距離を計算します。

#巡回セールスマン問題の評価関数
def tsp_score(para):
    
    #paraの前後に0を付ける（0からスタートし0でゴールする）
    para_full = np.hstack((0, para, 0))
    
    #スコアの計算（今回は直接returnする）
    
    return np.sum(((town_x[para_full][:-1] - town_x[para_full][1:])**2 + (town_y[para_full][:-1] - town_y[para_full][1:])**2)**0.5)

（任意）ひとつのパラメータ群を可視化する関数。これも、paraの前後に0を付けてpara_fullとし、プロットします。スタート/ゴール地点は赤丸（中が白）で上書き表示します。

#paraの可視化
def tsp_show_para(para, **info):
    
    #2-opt処理中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    step_num = info['step_num']
    score = info['score']
    
    #paraの前後に0を付ける（0からスタートし0でゴールする）
    para_full = np.hstack((0, para, 0))
    
    #プロット（および保存）
    plt.figure(figsize=(6, 6))
    plt.plot(town_x[para_full], town_y[para_full], 'ok-')
    #スタート/ゴール地点を赤丸（中が白）で上書き
    plt.plot(town_x[0], town_y[0], 'or', markerfacecolor='w')
    plt.xlabel('x'); plt.ylabel('y')
    plt.xlim([0, 1]); plt.ylim([0, 1])
    plt.title('step={}, score={}'.format(step_num, score))
    #plt.savefig('save/{}.png'.format(step_num))
    plt.show()
    print()

（任意）すべてのパラメータ群を可視化する関数。poolの前後に0列を付けてpool_fullとし、プロットします。先と同様に、スタート/ゴール地点は赤丸（中が白）で上書き表示します。

#巡回セールスマン問題のpoolの可視化
def tsp_show_pool(pool, **info):
    
    #GA中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    gen = info['gen']
    best_index = info['best_index']
    best_score = info['best_score']
    mean_score = info['mean_score']
    mean_gap = info['mean_gap']
    time = info['time']
    
    #poolの前後に0列を付ける（すべてのparaが0からスタートし0でゴールする）
    pool_full = np.hstack((np.zeros(len(pool), dtype=int).reshape(len(pool), 1), pool, (np.zeros(len(pool), dtype=int).reshape(len(pool), 1))))
    
    #プロット
    plt.figure(figsize=(6, 6))
    #pool_fullを100個まで薄い黒でプロット
    for para in pool_full[:100]:
        plt.plot(town_x[para], town_y[para], 'ok-', alpha=(2.0/len(pool[:100])))
    #エリートは赤でプロット     
    plt.plot(town_x[pool_full[best_index]], town_y[pool_full[best_index]], 'or-')
    #スタート/ゴール地点を赤丸（中白）で上書き
    plt.plot(town_x[0], town_y[0], 'or', markerfacecolor='w')
    #タイトルをつけて表示
    plt.xlabel('x'); plt.ylabel('y')
    plt.xlim([0, 1]); plt.ylim([0, 1])
    plt.title('gen={}, best={} mean={} time={}'.format(gen, best_score, mean_score, time))
    #plt.savefig('save/{}.png'.format(gen_num))
    plt.show()
    print()

具体的には、次のような処理をしています。

pool
[[18 16 1 12 17 5 11 13 3 6 8 9 10 14 7 2 19 4 15],
[ 7 4 1 9 16 3 17 5 6 14 13 15 12 8 2 10 18 11 19],
[ 9 17 16 1 8 6 5 15 7 19 2 12 13 14 18 3 4 11 10],
…
[12 1 8 11 16 4 19 15 3 5 14 2 9 17 10 13 7 6 18]]

↓

pool_full
[[0 18 16 1 12 17 5 11 13 3 6 8 9 10 14 7 2 19 4 15 0],
[ 0  7 4 1 9 16 3 17 5 6 14 13 15 12 8 2 10 18 11 19 0],
[ 0  9 17 16 1 8 6 5 15 7 19 2 12 13 14 18 3 4 11 10 0],
…
[ 0 12 1 8 11 16 4 19 15 3 5 14 2 9 17 10 13 7 6 18 0]]

2-opt法で最適化

20都市で実行してみます。適当な順路（para）を生成する際、0を含まないように注意します。

#巡回セールスマン問題の作成
nr.seed(1)
town_num = 20
town_x, town_y = create_tsp(town_num)

#適当に道順を作成（ただし0の町は含まない）
para = np.arange(1, town_num)
nr.shuffle(para)

#2-opt法で最適化
para, score = vcopt().opt2(para,                          #para
                           tsp_score,                     #score_func
                           0.0,                           #aim
                           show_para_func=tsp_show_para,  #show_para_func=None
                           seed=1)                        #seed=None

#結果の表示
print(para)
print(score)

実行結果

[17  9  1 13 11 15  8 10  7  6 18  2 14  5 12  4 19  3 16]
3.5475293979312674

The 閉路。

GAで最適化

こちらも問題を作成し、GAを実行します。こちらも同様に、並び替えるべき順路（para_range）に0を含まないように注意します。

#巡回セールスマン問題の作成
nr.seed(1)
town_num = 20
town_x, town_y = create_tsp(town_num)

#パラメータ範囲（ただし0の町は含まない）
para_range = np.arange(1, town_num)

#GAで最適化
para, score = vcopt().tspGA(para_range,                    #para_range
                            tsp_score,                     #score_func
                            0.0,                           #aim
                            show_pool_func=tsp_show_pool,  #show_pool_func=None
                            seed=1)                        #seed=None

#結果の表示
print(para)
print(score)

実行結果

[17  9  1 13 11 15  8 10  7  6 18  2 14  5 12  4 19  3 16]
3.5475293979312674

結果、閉路にしたことで、偶然に2-opt法とGAの結果が一致しました（ちょうどぐるっと一周しやすい配置だったため）。もっと複雑な配置であれば差が出ると思います。