import random

def initialize_population(num_points, pop_size):
    population = []
    for _ in range(pop_size):
        individual = list(range(num_points))
        random.shuffle(individual)
        population.append(individual)
    return population

def evaluate_fitness(individual, distances):
    fitness = 0
    num_points = len(individual)
    for i in range(num_points):
        city1 = individual[i]
        city2 = individual[(i + 1) % num_points]
        fitness += distances[city1][city2]
    return fitness

def crossover(parent1, parent2):
    child = [-1] * len(parent1)
    start_idx = random.randint(0, len(parent1)-1)
    end_idx = random.randint(start_idx+1, len(parent1))
    child[start_idx:end_idx] = parent1[start_idx:end_idx]
    for city in parent2:
        if city not in child:
            for i in range(len(child)):
                if child[i] == -1:
                    child[i] = city
                    break
    return child

def mutate(individual):
    idx1, idx2 = random.sample(range(len(individual)), 2)
    individual[idx1], individual[idx2] = individual[idx2], individual[idx1]

def genetic_algorithm(distances, pop_size, num_generations):
    num_points = len(distances)
    population = initialize_population(num_points, pop_size)

    for generation in range(num_generations):
        population_fitness = []
        for individual in population:
            fitness = evaluate_fitness(individual, distances)
            population_fitness.append((individual, fitness))

        population_fitness.sort(key=lambda x: x[1])  # 按适应度排序
        elite_individual = population_fitness[0][0]
        new_population = [elite_individual]

        while len(new_population) < pop_size:
            parent1, parent2 = random.choices(population_fitness, k=2)
            child = crossover(parent1[0], parent2[0])
            mutate(child)
            new_population.append(child)

        population = new_population

    best_individual = population_fitness[0][0]
    return best_individual

# 示例使用
# distances为距离矩阵
distances = [
    [0, 50, 99, 0, 64, 0],
    [50, 0, 12, 45, 74, 13],
    [99, 12, 0, 25, 0, 61],
    [0, 45, 25, 0, 45, 47],
    [64, 74, 0, 45, 0, 0],
    [0, 13, 61, 47, 0, 0]
]
population_size = 100
num_generations = 1000

best_solution = genetic_algorithm(distances, population_size, num_generations)
print(best_solution)