遺伝的アルゴリズムで巡回セールスマン問題を解いてみる(実行結果編)

はじめに

「巡回セールスマン問題　遺伝的アルゴリズム」でググるとたくさんヒットすることを自分でもやってみました。

• 理論編
• Python コード編
• 実行結果編

実行結果

Python コード編 で作成したコードを、Google Colaboratory 上で、いくつかの点群について探索した結果です。

• time ... 実行時間
• epoch ... 世代数
• fitness ... 近似解の適応度
• length ... 近似解の経路長
• path ... 近似解の経路
• グラフ ... $p_1, p_2, \dots, p_N$ と順にたどった経路と、途中世代での最適解の経路

遺伝的アルゴリズムは乱数の要素が強いので、実行するたびに計算時間や近似解が変わります。似たような結果を再現できない場合は、何度かやり直してみてください。

格子状 25 点

import numpy as np
from GaTsp import *

loggers = (Logger_trace(level=2), Logger_leaders())
pts_m = np.array([(x+random.random()/5-2.09, y+random.random()/5-2.09) for x in range(5) for y in range(5)])
spc_m = Species(points=pts_m)  # matrix points
mdl = Model(species=spc_m)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

ランダム 30 点

ランダムに生成した点群の経路です。
初期状態は乱雑ですが、世代を追うごとに整理されていく様子がわかります。
下段は、適応度の推移、世代の個体数、生成した子個体の数、最終世代の適応度の分布、です。

import numpy as np
from GaTsp import *

loggers = (
    Logger_trace(level=2),
    Logger_leaders(),
    Logger_fitness(),
    Logger_population(),
    Logger_population(show_breeded=True),
    Logger_last_fitness_histgram(),
)
loggers = (Logger_trace(level=2), Logger_leaders())
spc_r = Species(N=30, seed=30)
mdl = Model(species=spc_r)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

ランダム 30 点：一本道

原点を始終点とした経路ではなく、$p_1, \dots, p_N$ のどれかを始点・終点とした一本道の経路を探索しました。
グラフでは、青色の線のみが探索された経路になります。
原点を始終点とした経路とは異なる経路に収束する様子がわかります。

import numpy as np
from GaTsp import *

class SpeciesPolyline(Species):
    def measure(self, path:np.ndarray, *args, **kwargs):
        length = self._distance_map[path[:-1], path[1:]].sum()
        return length

loggers = (Logger_trace(level=2), Logger_leaders())
spc_p = SpeciesPolyline(N=30, seed=30)
mdl = Model(species=spc_p)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

ランダム 30 点：一本道：ペナルティあり

上と同じく一本道の経路ですが、原点から離れるように進んだら原点からの距離の差をペナルティとして経路長に加えています。
ペナルティなしとは異なる経路に収束する様子がわかります。
また、47 世代目と95 世代目を比べると、適応度は減少していますが、経路長は逆に増加しています。ペナルティが効いているようです。

class SpeciesSpiral(SpeciesPolyline):
    def penalty(self, path:np.ndarray, *args, **kwargs):
        penalties = self._to_origin[path[1:]] - self._to_origin[path[:-1]]
        penalty = penalties[penalties > 0].sum()
        return penalty

loggers = (Logger_trace(level=2), Logger_leaders())
spc_s = SpeciesSpiral(N=30, seed=30)
mdl = Model(species=spc_s)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

おわりに

単純な実装ですが、意外と短い時間で最適解を探索できます。
しかし、点の数が増えると指数的に探索時間が増えていきます。
次は、ハイパーパラメータを調整したり、実装を工夫したりして、探索時間の削減をねらいます。