巡回セールスマン問題（Traveling Salesman Problem, TSP）

巡回セールスマン問題（Traveling Salesman Problem, TSP）

最適化問題の一例として、「巡回セールスマン問題（Traveling Salesman Problem, TSP）」を挙げます。

TSPは、いくつかの都市を訪問する最短経路を求める問題で、非常に計算困難です。

今回は、Pythonを使ってTSPを解き、結果をグラフ化します。

巡回セールスマン問題の説明

巡回セールスマン問題は、以下のように定義されます：

• あるセールスマンが$N$個の都市を訪れ、それぞれの都市を一度だけ訪問し、出発地点に戻る必要がある。
• すべての都市間の距離が与えられている。
• セールスマンが移動する総距離を最小化する経路を見つけることが目的。

解法

TSPはNP困難問題であり、大規模な問題を厳密に解くのは現実的ではありません。
ここでは、近似解法の一つである遺伝的アルゴリズム（Genetic Algorithm）を用いて解を求めます。

実装

まず、必要なライブラリをインストールします。

pip install deap matplotlib numpy

次に、Pythonコードを以下に示します：

import numpy as np
import matplotlib.pyplot as plt
from deap import base, creator, tools, algorithms

# 都市数
num_cities = 20

# ランダムな都市の座標を生成
np.random.seed(42)
cities = np.random.rand(num_cities, 2)

# 距離行列を計算
distance_matrix = np.sqrt(((cities[:, np.newaxis] - cities)**2).sum(axis=2))

# 遺伝的アルゴリズムの設定
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", np.ndarray, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("indices", np.random.permutation, num_cities)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

def evalTSP(individual):
    distance = 0
    for i in range(num_cities):
        distance += distance_matrix[individual[i-1], individual[i]]
    return distance,

toolbox.register("mate", tools.cxOrdered)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evalTSP)

def main():
    population = toolbox.population(n=300)
    ngen = 400
    cxpb = 0.7
    mutpb = 0.2

    result, log = algorithms.eaSimple(population, toolbox, cxpb, mutpb, ngen, 
                                      stats=None, halloffame=None, verbose=False)
    
    best_ind = tools.selBest(population, 1)[0]
    return best_ind

best_route = main()

# 結果をプロット
plt.figure(figsize=(10, 5))
plt.scatter(cities[:, 0], cities[:, 1], color='red')
for i in range(num_cities):
    plt.annotate(i, (cities[i, 0], cities[i, 1]))
route = np.append(best_route, best_route[0])
plt.plot(cities[route, 0], cities[route, 1], 'b-')
plt.title('Traveling Salesman Problem - Best Route')
plt.xlabel('X Coordinate')
plt.ylabel('Y Coordinate')
plt.grid(True)
plt.show()

コードの説明

1. 都市の生成:

   • num_citiesを設定し、ランダムな都市の座標を生成します。
   • 都市間の距離行列を計算します。

2. 遺伝的アルゴリズムの設定:

   • DEAPライブラリを使用して遺伝的アルゴリズムを設定します。
   • creatorで個体（経路）とその適合度を定義します。
   • toolboxで個体の生成、交叉、突然変異、選択、および評価関数を登録します。

3. 適合度関数:

   • evalTSP関数で個体（経路）の総距離を計算します。

4. 主関数:

   • 遺伝的アルゴリズムの主要なパラメータを設定し、eaSimple関数を使用して進化を実行します。
   • 最良の経路を選択し、結果を返します。

5. 結果のプロット:

   • 最良の経路をプロットし、都市の座標と経路を視覚化します。

結果

このコードを実行すると、TSPの最良の経路がプロットされます。

[実行結果]

都市間の最短経路が青線で表示され、各都市の座標が赤点で示されます。