遗传算法求解路径规划

"""遗传算法求解路径规划（旅行商问题 TSP）—— 站内原创示例代码

用途：给定若干地点的二维坐标，用遗传算法搜索一条访问所有地点一次并回到起点、
      且总距离尽量短的路线。常见于「基于遗传算法的路径规划」类课程设计。
依赖：仅 Python 标准库（random / math）。
运行：python ga-path-planning.py
许可：MIT（开源拾遗原创，可自由使用与修改）
"""

import math
import random

# 十个地点的坐标（可换成你自己的地图数据）
POINTS = [
    (2, 3), (5, 9), (8, 4), (12, 8), (15, 2),
    (18, 11), (21, 6), (24, 14), (27, 3), (30, 9),
]

POPULATION_SIZE = 80
GENERATIONS = 300
MUTATION_RATE = 0.2
ELITE = 4
SEED = 42


def distance(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])


def route_length(route):
    """一条路线的总长度（首尾相连）。"""
    total = 0.0
    for i in range(len(route)):
        total += distance(POINTS[route[i]], POINTS[route[(i + 1) % len(route)]])
    return total


def random_route():
    route = list(range(len(POINTS)))
    random.shuffle(route)
    return route


def ordered_crossover(parent_a, parent_b):
    """顺序交叉（OX）：保留一段连续基因，其余按另一父代的相对顺序填充。"""
    n = len(parent_a)
    start, end = sorted(random.sample(range(n), 2))
    child = [None] * n
    child[start:end + 1] = parent_a[start:end + 1]
    fill = [gene for gene in parent_b if gene not in child]
    index = 0
    for i in range(n):
        if child[i] is None:
            child[i] = fill[index]
            index += 1
    return child


def mutate(route):
    """交换变异：随机交换两个位置。"""
    if random.random() < MUTATION_RATE:
        i, j = random.sample(range(len(route)), 2)
        route[i], route[j] = route[j], route[i]
    return route


def tournament_select(population, k=3):
    contenders = random.sample(population, k)
    return min(contenders, key=route_length)


def solve():
    population = [random_route() for _ in range(POPULATION_SIZE)]
    best = min(population, key=route_length)

    for _ in range(GENERATIONS):
        population.sort(key=route_length)
        next_generation = population[:ELITE]  # 精英保留，保证不退化
        while len(next_generation) < POPULATION_SIZE:
            child = ordered_crossover(tournament_select(population), tournament_select(population))
            next_generation.append(mutate(child))
        population = next_generation
        best = min(best, min(population, key=route_length), key=route_length)

    return best


if __name__ == "__main__":
    random.seed(SEED)  # 固定随机种子，结果可复现
    baseline = route_length(list(range(len(POINTS))))
    best_route = solve()
    best_length = route_length(best_route)

    print("地点数量:", len(POINTS))
    print("初始顺序长度: %.2f" % baseline)
    print("优化后长度:   %.2f" % best_length)
    print("最优路线:", " -> ".join(str(i) for i in best_route))

    # 自检：必须访问每个地点且只访问一次；结果应优于初始顺序
    assert sorted(best_route) == list(range(len(POINTS)))
    assert best_length < baseline, (best_length, baseline)
    print("断言通过")