12/9(月) 応用科学学会シンポジウムで自動運転に関する講演を担当します☆彡

8-4. 遺伝的アルゴリズム(vcopt)で巡回セールスマン問題を解く(50都市編)

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

やること

50都市のルート最適化ができれば、都道府県やアメリカの州にも対応できます。

実行環境

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

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

(必須)評価関数。これまでと同じです。

#巡回セールスマン問題の評価関数
def tsp_score(para):
    
    #スコアの計算(今回は直接returnする)
    
    return np.sum(((town_x[para][:-1] - town_x[para][1:])**2 + (town_y[para][:-1] - town_y[para][1:])**2)**0.5)

(任意)2-opt法で使用する、ひとつのパラメータ群を可視化する関数。8-2で作ったものです。

#paraの可視化
def tsp_show_para(para, **info):
    
    #2-opt処理中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    step_num = info['step_num']
    score = info['score']
    
    #プロット(および保存)
    plt.figure(figsize=(6, 6))
    plt.plot(town_x[para], town_y[para], 'ok-')
    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()

(任意)GAで使用する、すべてのパラメータ群を可視化する関数。8-3で作ったものです。

#巡回セールスマン問題の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']
    
    #プロット(および保存)
    plt.figure(figsize=(6, 6))
    #poolを100個まで薄い黒でプロット
    for para in pool[:100]:
        plt.plot(town_x[para], town_y[para], 'ok-', alpha=(2.0/len(pool[:100])))
    #エリートは赤でプロット     
    plt.plot(town_x[pool[best_index]], town_y[pool[best_index]], 'or-')
    #タイトルをつけて表示
    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()

2-opt法で最適化

50都市で、乱数シードは固定せずに何度か実行してみます。

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

#適当に道順を作成
para = np.arange(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=None)                     #seed=None

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

実行結果

[38 49 19  6  4 42 47 12 28 30 26 18 35 23 41 20 37 46 32 29 13 24 21 40 25 34 11 36 15 43 39  1  9 16 31  8 17 33 45  7 10  0 48 22  3 44 27  2 14  5]
6.011240602968318

[42  3 45  7 22 10  0 48  5 14  2 27 44  4 38 28 30 26 18 35 12 49  6 19 47  8 31 16  9 23 41 20 37 46 32 29  1 39 43 15 17 33 34 11 36 13 24 25 21 40]
5.646911649322136

[35 18 26 30 28 12 19  6 42 47  8 31 16  9 39  1 23 41 20 37 46 32 29 43 13 24 21 40 25 34 11 36 15 17 33 45  3 22  7 10  0 48  5 14  2 27 44  4 49 38]
5.59226224782831

これでも十分に効率的なルートに見えますが、どうでしょうか。

GAで最適化

こちらも問題を作成し、GAを実行します。

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

#パラメータ範囲
para_range = np.arange(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)

実行結果

[40 21 25 24 13 43 39  1 29 32 46 37 20 41 23  9 16 31  8 17 15 36 11 34 33 45  3 22  7 10  0 48  5 14  2 27 44  4 42 47 19  6 49 38 12 28 30 26 18 35]
5.362977427811835

GAは10分弱かかりましたが、圧倒的な勝利です。50都市のGAでこの速度が出るパッケージは他にはないのではないでしょうか(あるでしょ)。巡回セールスマン問題(並び替え問題)用に完璧にチューニングされています。

タイトルとURLをコピーしました