4/14(日) 足・靴・木型研究会「第2回研究集会」を開催します☆彡

9-1. 遺伝的アルゴリズム(vcopt)で巡回セールスマン問題を解く(2人のセールスマン編)

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

やること

実は、2人のセールスマンがいる場合も最適化できます。

実行環境

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

考え方

2人のセールスマンは0の町(世界の中心)から出発するとします。

例えば、[3, 5, 2, 0, 4, 1, 2, 7, 9, 6, 8]という経路を、 評価関数の中で、0を境界にして2つの経路に分割します。[0, 2, 5, 3]と[0, 4, 1, 2, 7, 9, 6, 8]ですね。評価関数ではそれぞれの経路の距離を計算して、遠い方の距離を返すようにします。こうすれば、2人の距離ができるだけ同じくらいになるように最適化できます。

※まあ本当は1つ目の経路は逆順にする必要はないです。[3, 5, 2, 0]と[0, 4, 1, 2, 7, 9, 6, 8]で大丈夫です。

ちょっと確認

2つの経路に分割できるか試してみます。

#適当な道順を作成
para = np.array([3, 5, 2, 0, 4, 1, 2, 7, 9, 6, 8])
print(para)

#0のインデックス
print(np.where(para==0)[0][0])

#0番目の町を境界に、2つの列に分割(どちらも0はじまり)
para_1 = para[:np.where(para==0)[0][0] + 1][::-1]
para_2 = para[np.where(para==0)[0][0]:]
print(para_1)
print(para_2)
[3 5 2 0 4 1 2 7 9 6 8]
3
[0 2 5 3]
[0 4 1 2 7 9 6 8]

できていますね!np.where()は慣れないとややこしいです。para中の0が端にあっても問題なく動作します。

import

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

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

巡回セールスマン問題の作成

これまでと同様に町のx, y座標をランダムに生成しますが、0の町は(x, y)=(0.5 ,0.5)に修正してやります。

#巡回セールスマン問題の作成
def create_tsp(town_num):
    
    #町のx座標とy座標の配列を作成
    town_x = nr.rand(town_num)
    town_y = nr.rand(town_num)
    
    #0番目の町を中心に置く
    town_x[0] = 0.5
    town_y[0] = 0.5
    
    return town_x, town_y

(必須)評価関数

先ほどの経路分割テクニックを使って、評価関数を書きました。スコアは2人分計算して、大きい方を返します。

#巡回セールスマン問題の評価関数
def tsp_score(para):
    
    #0番目の町を境界に、2つの列に分解(どちらも0はじまり)    
    para_1 = para[:np.where(para==0)[0][0] + 1][::-1]
    para_2 = para[np.where(para==0)[0][0]:]

    #スコアの計算
    score_1 = np.sum(((town_x[para_1][:-1] - town_x[para_1][1:])**2 + (town_y[para_1][:-1] - town_y[para_1][1:])**2)**0.5)
    score_2 = np.sum(((town_x[para_2][:-1] - town_x[para_2][1:])**2 + (town_y[para_2][:-1] - town_y[para_2][1:])**2)**0.5)

    return max(score_1, score_2)

paraの中で0が端にある場合は分割した経路の一方が[0]となりますが、1つの町だけで距離の計算はできるのでしょうか。Pythonのスライスでは、[-1]は後ろから1番目を指します。すなわち、town_x[para_1][1:]もtown_x[para_1][:-1]も同じ0の町を指すため、その間の距離は0と計算されます。スライスの神秘。

(任意)ひとつのパラメータ群を可視化する関数

可視化の際、経路を分割する必要はありません。経路をプロットした後に、スタート地点を赤丸(中が白)で上書きしてやれば、見た目としては十分です。

#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.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の可視化
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_fullを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.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()

2-opt法で最適化

40都市で実行してみます。

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

#適当に道順を作成
para = np.arange(town_num)

#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)

実行結果

[37 21 25 29 11 39  1 36 33  6 28 30 38 26 27 14  5 18 19  3 22 16  0 31 35  7  8 23 34 13 32 20 24 15 17  9 10  4 12  2]
2.855860454165001

あれ、下経路の一部が交差しています。通常、巡回セールスマン問題を2-opt法で最適化した場合、経路が交差することはありません。何が起きているのでしょうか。上下の経路の長さを表示してみると、(ソースコードなし)

2.855860454165001
2.7965735711223907

また、下経路の交差を解消した場合の距離は、

2.855860454165001
2.7275698870690332

下経路は交差を解消することで距離が短縮されました。しかし、上経路が律速でありこれがどうしても更新できないため、下経路が疎かのままに探索が終了してしまいました。言い換えれば、下経路には余力があるため、もう少し下のセールスマンに配分しても良いと判断できます。やはりセールスマンが2人の場合の最適化は難しいです。

GAで最適化

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

#巡回セールスマン問題の作成
nr.seed(1)
town_num = 40
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)

実行結果

[ 2  5 14 27 18 26 38 30 28  6  3 19 22 33 36  1 39 11 16  0 34 23 29 25 21 37 13 32 24 20 15 17  9 10 31 35  8  7 12  4]
2.4778823846365903

GAの勝利です。各経路の距離を見てみると、(ソースコードなし)

2.4778823846365903
2.473074265997595

ほとんど同じです。まったく見事な最適化でした。vcoptは完璧にチューニングされています。

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