遺伝的アルゴリズム(DEAP)を使ったルート最適化

1. はじめに

遺伝的アルゴリズム（GA）は、進化の過程を模倣して複雑な問題の最適解を見つける手法です。今回は、PythonのライブラリDEAPを使って、東京都内で複数の配達先を巡る最短ルートを見つける方法を学びます。また、folium ライブラリを使って、地図上で最適なルートを可視化します。

2. 遺伝的アルゴリズムとは？

遺伝的アルゴリズムは以下のステップで解を見つけます。

1. 個体生成: ランダムな解候補（個体）を作成します。
2. 評価: 各個体がどれだけ良い解か（適応度）を評価します。
3. 選択: より良い個体を選び、次世代に残します。
4. 交叉: 2つの個体を組み合わせて新しい個体を生成します。
5. 変異: 個体にランダムな変更を加え、新しい可能性を探ります。
6. 繰り返し: この手順を繰り返して最適な解を見つけます。

3. 今回の問題設定

東京都内で10箇所の配達先があると仮定し、それらの地点を最短ルートで回る配達ルートを最適化します。各配達先は、東京都内の座標に設定し、最も効率的なルートを見つけます。

4. 実装ステップ

ステップ1: 必要なライブラリをインストール

まず、Google Colabで以下のコードを実行して、DEAP と folium ライブラリをインストールします。

!pip install deap folium

ステップ2: 東京都内の配達先の位置を設定

東京都内の10箇所の配達先の座標（超テキトー（笑））を設定します。

import numpy as np

# 東京都内の配達先の位置（例として10箇所の座標）
locations = np.array([
    [35.6895, 139.6917],  # 新宿
    [35.6733, 139.7100],  # 渋谷
    [35.6586, 139.7454],  # 六本木
    [35.7295, 139.7104],  # 池袋
    [35.6993, 139.7745],  # 上野
    [35.7074, 139.7608],  # 秋葉原
    [35.6938, 139.7035],  # 四谷
    [35.6654, 139.7310],  # 恵比寿
    [35.6764, 139.6993],  # 代々木
    [35.6852, 139.7528]   # 千代田
])
print("東京都内の配達先（座標）:")
print(locations)

ステップ3: 評価関数を定義

次に、配達ルートの総距離を計算する評価関数を定義します。

def evalDeliveryRoute(individual):
    distance = 0
    for i in range(len(individual) - 1):
        start = locations[individual[i]]
        end = locations[individual[i + 1]]
        distance += np.linalg.norm(start - end)
    distance += np.linalg.norm(locations[individual[-1]] - locations[individual[0]])  # 最後の配達先から始点へ戻る距離
    return distance,

ステップ4: 遺伝的アルゴリズムの設定

次に、DEAPを使って遺伝的アルゴリズムをセットアップします。

from deap import base, creator, tools

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

toolbox = base.Toolbox()
toolbox.register("indices", np.random.permutation, len(locations))  # ランダムな順序を生成
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("mate", tools.cxOrdered)  # 順序交叉
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)  # 変異
toolbox.register("select", tools.selTournament, tournsize=3)  # トーナメント選択
toolbox.register("evaluate", evalDeliveryRoute)

ステップ5: 遺伝的アルゴリズムの実行

遺伝的アルゴリズムを実行して最適なルートを探します。

from deap import algorithms

# パラメータ設定
population_size = 100
num_generations = 200
cx_prob = 0.7  # 交叉の確率
mut_prob = 0.2  # 変異の確率

# 初期集団を生成
population = toolbox.population(n=population_size)

# 遺伝的アルゴリズムを実行
result_population, _ = algorithms.eaSimple(population, toolbox, cxpb=cx_prob, mutpb=mut_prob, ngen=num_generations, verbose=False)

ステップ6: 最適なルートの可視化（地図）

次に、folium を使って、最適なルートを地図上に可視化します。

import folium

# 最適解を取得
best_individual = tools.selBest(result_population, k=1)[0]
print(f"最適な配達ルート: {best_individual}")
print(f"総距離: {best_individual.fitness.values[0]}")

# 地図の中心を設定（ここでは東京駅を中心にする）
mymap = folium.Map(location=[35.6852, 139.7528], zoom_start=12)

# 配達先をマーカーとして地図に追加
for i, location in enumerate(locations):
    folium.Marker([location[0], location[1]], popup=f"配達先 {i+1}").add_to(mymap)

# 配達ルートを線で描画
route = [(locations[i][0], locations[i][1]) for i in best_individual]
folium.PolyLine(locations=route, color='blue').add_to(mymap)

# 地図を表示
mymap

直線じゃねーか！ていうツッコミは置いておいて、とりあえず遺伝的アルゴリズムを使った最適なルートを出すことができました。より詳細な地理情報を入力していくことで、より詳細なルート選択が可能となります。

まとめ

今回は、配達ルート最適化を遺伝的アルゴリズムを使って実装し、folium を利用して地図上に最適なルートを可視化しました。これにより、効率化に役立つ最適化技術を学ぶことができました。これらの技術はMAPだけでなく、様々な最適化問題にも応用することができます。
ぜひ、ご自身の課題に当てはめて使ってみてください！