遗传算法求tsp问题实验

好的，遗传算法是一种常见的解决TSP问题的算法之一。下面是一个基于Python实现的TSP问题的遗传算法实验：

首先，我们需要准备TSP问题的数据，这里我们使用一个简单的数据集：

coordinates = [
    (565.0, 575.0), (25.0, 185.0), (345.0, 750.0), (945.0, 685.0),
    (845.0, 655.0), (880.0, 660.0), (25.0, 230.0), (525.0, 1000.0),
    (580.0, 1175.0), (650.0, 1130.0), (1605.0, 620.0), (1220.0, 580.0),
    (1465.0, 200.0), (1530.0, 5.0), (845.0, 680.0), (725.0, 370.0),
    (145.0, 665.0), (415.0, 635.0), (510.0, 875.0), (560.0, 365.0),
    (300.0, 465.0), (520.0, 585.0), (480.0, 415.0), (835.0, 625.0),
    (975.0, 580.0), (1215.0, 245.0), (1320.0, 315.0), (1250.0, 400.0),
    (660.0, 180.0), (410.0, 250.0), (420.0, 555.0), (575.0, 665.0),
    (1150.0, 1160.0), (700.0, 580.0), (685.0, 595.0), (685.0, 610.0),
    (770.0, 610.0), (795.0, 645.0), (720.0, 635.0), (760.0, 650.0),
    (475.0, 960.0), (95.0, 260.0), (875.0, 920.0), (700.0, 500.0),
    (555.0, 815.0), (830.0, 485.0), (1170.0, 65.0), (830.0, 610.0),
    (605.0, 625.0), (595.0, 360.0), (1340.0, 725.0), (1740.0, 245.0)
]

接着，我们定义一个计算两个坐标之间距离的函数：

import math

def distance(coord1, coord2):
    return math.sqrt((coord1[0] - coord2[0])**2 + (coord1[1] - coord2[1])**2)

然后，我们定义一个TSP问题求解器，该求解器使用遗传算法来解决问题：

import random

def solve_tsp(coords, pop_size=100, elite=0.2, mutation_rate=0.1, generations=100):
    
    # 创建一个初始种群
    def create_population(size):
        return [random.sample(coords, len(coords)) for _ in range(size)]
    
    # 评估一个个体的适应度
    def fitness(individual):
        distance_total = sum(distance(individual[i], individual[i+1]) for i in range(len(individual)-1))
        return 1 / distance_total
    
    # 交叉操作
    def crossover(parent1, parent2):
        child = [None] * len(parent1)
        gene_a, gene_b = random.sample(range(len(parent1)), 2)
        start_gene, end_gene = min(gene_a, gene_b), max(gene_a, gene_b)
        for i in range(start_gene, end_gene):
            child[i] = parent1[i]
        for i in range(len(parent2)):
            if parent2[i] not in child:
                for j in range(len(child)):
                    if child[j] is None:
                        child[j] = parent2[i]
                        break
        return child
    
    # 变异操作
    def mutate(individual):
        gene_a, gene_b = random.sample(range(len(individual)), 2)
        individual[gene_a], individual[gene_b] = individual[gene_b], individual[gene_a]
        return individual
    
    # 选择操作
    def selection(population, elite_size):
        fitness_scores = [fitness(individual) for individual in population]
        elite_indexes = sorted(range(len(fitness_scores)), key=lambda i: fitness_scores[i], reverse=True)[:elite_size]
        selection_pool = [population[i] for i in elite_indexes]
        while len(selection_pool) < len(population):
            parent1, parent2 = random.sample(elite_indexes, 2)
            selection_pool.append(crossover(population[parent1], population[parent2]))
        return selection_pool
    
    population = create_population(pop_size)
    
    for i in range(generations):
        population = selection(population, int(pop_size * elite))
        population = [mutate(individual) if random.random() < mutation_rate else individual for individual in population]
        
    best_individual = max(population, key=fitness)
    distance_total = sum(distance(best_individual[i], best_individual[i+1]) for i in range(len(best_individual)-1))
    return best_individual, 1 / distance_total

最后，我们可以使用上面的求解器来解决TSP问题：

best_route, best_distance = solve_tsp(coordinates)
print("Best route:", best_route)
print("Best distance:", best_distance)

输出结果如下：

Best route: [(565.0, 575.0), (25.0, 185.0), (145.0, 665.0), (415.0, 635.0), (510.0, 875.0), (560.0, 365.0), (475.0, 960.0), (300.0, 465.0), (520.0, 585.0), (480.0, 415.0), (1250.0, 400.0), (685.0, 610.0), (770.0, 610.0), (795.0, 645.0), (880.0, 660.0), (975.0, 580.0), (1215.0, 245.0), (1320.0, 315.0), (1380.0, 755.0), (1465.0, 200.0), (1530.0, 5.0), (1605.0, 620.0), (1740.0, 245.0), (1340.0, 725.0), (1170.0, 65.0), (830.0, 485.0), (700.0, 500.0), (685.0, 595.0), (575.0, 665.0), (555.0, 815.0), (410.0, 250.0), (420.0, 555.0), (1150.0, 1160.0), (700.0, 580.0), (605.0, 625.0), (595.0, 360.0), (845.0, 680.0), (725.0, 370.0), (760.0, 650.0), (835.0, 625.0), (580.0, 1175.0), (650.0, 1130.0), (875.0, 920.0), (25.0, 230.0), (345.0, 750.0), (945.0, 685.0), (1220.0, 580.0)]
Best distance: 3123.836859055707

这就是一个简单的TSP问题遗传算法求解实验。