本記事の内容は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でこの速度が出るパッケージは他にはないのではないでしょうか(あるでしょ)。巡回セールスマン問題(並び替え問題)用に完璧にチューニングされています。