import numpy as np
import matplotlib.pyplot as plt
import random
from math import sqrt
from matplotlib.collections import LineCollection


plt.rcParams['font.family'] = ['serif'] # 顯示中文問題
plt.rcParams['font.serif'] = ['SimSun'] # 顯示中文問題


# 生成隨機城市坐標(biāo)
def generate_cities(num_cities, width=1000, height=1000):
    return [(random.randint(0, width), random.randint(0, height)) for _ in range(num_cities)]


# 計算路徑總距離
def calculate_distance(path, cities):
    distance = 0
    for i in range(len(path)):
        x1, y1 = cities[path[i-1]]
        x2, y2 = cities[path[i]]
        distance += sqrt((x2 - x1)**2 + (y2 - y1)**2)
    return distance


# 初始化種群
def initialize_population(pop_size, num_cities):
    population = []
    for _ in range(pop_size):
        individual = list(range(num_cities))
        random.shuffle(individual)
        population.append(individual)
    return population


# 選擇操作 - 輪盤賭選擇
def selection(population, cities, num_parents):
    fitness_values = [1/calculate_distance(individual, cities) for individual in population]
    total_fitness = sum(fitness_values)
    probabilities = [f/total_fitness for f in fitness_values]
    
    selected_indices = np.random.choice(len(population), size=num_parents, p=probabilities, replace=False)
    return [population[i] for i in selected_indices]


# 交叉操作 - 有序交叉(OX)
def crossover(parent1, parent2):
    size = len(parent1)
    child = [-1] * size
    
    # 選擇交叉點
    start, end = sorted(random.sample(range(size), 2))
    
    # 從parent1復(fù)制片段
    child[start:end] = parent1[start:end]
    
    # 從parent2填充剩余城市
    remaining = [city for city in parent2 if city not in child]
    ptr = 0
    for i in range(size):
        if child[i] == -1:
            child[i] = remaining[ptr]
            ptr += 1
    
    return child


# 變異操作 - 交換變異
def mutate(individual, mutation_rate):
    if random.random() < mutation_rate:
        i, j = random.sample(range(len(individual)), 2)
        individual[i], individual[j] = individual[j], individual[i]
    return individual


# 遺傳算法主函數(shù)
def genetic_algorithm(cities, pop_size=100, num_generatinotallow=500, mutation_rate=0.01, elitism_ratio=0.1):
    num_cities = len(cities)
    population = initialize_population(pop_size, num_cities)
    best_distance = float('inf')
    best_path = None
    fitness_history = []
    
    num_elites = int(pop_size * elitism_ratio)
    
    for generation in range(num_generations):
        # 評估種群
        distances = [calculate_distance(individual, cities) for individual in population]
        current_best = min(distances)
        fitness_history.append(current_best)
        
        if current_best < best_distance:
            best_distance = current_best
            best_path = population[distances.index(current_best)]
        
        # 選擇精英
        elite_indices = np.argsort(distances)[:num_elites]
        elites = [population[i] for i in elite_indices]
        
        # 選擇父母
        parents = selection(population, cities, pop_size - num_elites)
        
        # 生成下一代
        next_generation = elites.copy()
        
        while len(next_generation) < pop_size:
            parent1, parent2 = random.sample(parents, 2)
            child = crossover(parent1, parent2)
            child = mutate(child, mutation_rate)
            next_generation.append(child)
        
        population = next_generation
    
    return best_path, best_distance, fitness_history


# 繪制路徑
def plot_path(cities, path, title="TSP Path"):
    path_coords = [cities[i] for i in path] + [cities[path[0]]]  # 回到起點
    x, y = zip(*path_coords)
    
    fig, ax = plt.subplots(figsize=(10, 6))
    ax.scatter(x, y, color='red')
    
    # 繪制路徑線
    lines = [[path_coords[i], path_coords[i+1]] for i in range(len(path_coords)-1)]
    lc = LineCollection(lines, colors='blue', linewidths=1)
    ax.add_collection(lc)
    
    ax.set_title(title)
    ax.set_xlabel("X 軸")
    ax.set_ylabel("Y 軸")
    plt.grid()
    plt.show()


# 繪制適應(yīng)度進(jìn)化曲線
def plot_fitness_history(fitness_history, title="適應(yīng)度進(jìn)化曲線"):
    plt.figure(figsize=(10, 6))
    plt.plot(fitness_history, color='green')
    plt.title(title)
    plt.xlabel("迭代次數(shù)")
    plt.ylabel("最優(yōu)距離")
    plt.grid()
    plt.show()


# 主程序
if __name__ == "__main__":
    # 參數(shù)設(shè)置
    num_cities = 20
    pop_size = 100
    num_generations = 500
    mutation_rate = 0.02
    
    # 生成城市
    cities = generate_cities(num_cities)
    
    # 運行遺傳算法
    best_path, best_distance, fitness_history = genetic_algorithm(
        cities, pop_size=pop_size, num_generatinotallow=num_generations, mutation_rate=mutation_rate)
    
    print(f"最優(yōu)距離: {best_distance}")
    print(f"最優(yōu)路徑: {best_path}")
    
    # 繪制結(jié)果
    plot_path(cities, best_path, f"旅行推銷員問題(TSP) (最優(yōu)距離: {best_distance:.2f})")
    plot_fitness_history(fitness_history)