遗传算法解决旅行商问题代码

以下是一个简单的 Python 代码实现遗传算法解决旅行商问题：

import random

# 旅行商问题定义
class TravelingSalesmanProblem:
    def __init__(self, cities):
        self.cities = cities
        self.city_count = len(cities)

    # 计算路径长度
    def path_length(self, path):
        length = 0
        for i in range(self.city_count - 1):
            length += self.cities[path[i]][path[i+1]]
        length += self.cities[path[-1]][path[0]]
        return length

# 创建随机个体
def create_individual(city_count):
    individual = list(range(city_count))
    random.shuffle(individual)
    return individual

# 交叉操作
def crossover(parent1, parent2):
    child1 = [-1] * len(parent1)
    child2 = [-1] * len(parent1)
    start = random.randint(0, len(parent1) - 1)
    end = random.randint(0, len(parent1) - 1)
    if start > end:
        start, end = end, start
    for i in range(start, end):
        child1[i] = parent1[i]
        child2[i] = parent2[i]
    index1 = 0
    index2 = 0
    for i in range(len(parent1)):
        if parent2[i] not in child1:
            while child1[index1] != -1:
                index1 += 1
            child1[index1] = parent2[i]
        if parent1[i] not in child2:
            while child2[index2] != -1:
                index2 += 1
            child2[index2] = parent1[i]
    return (child1, child2)

# 变异操作
def mutate(individual):
    index1 = random.randint(0, len(individual) - 1)
    index2 = random.randint(0, len(individual) - 1)
    individual[index1], individual[index2] = individual[index2], individual[index1]
    return individual

# 选择操作
def selection(population, tournament_size):
    tournament = random.sample(population, tournament_size)
    return min(tournament, key=lambda x: x.fitness)

# 遗传算法
def genetic_algorithm(cities, population_size, tournament_size, generations):
    tsp = TravelingSalesmanProblem(cities)
    population = [create_individual(tsp.city_count) for i in range(population_size)]
    for individual in population:
        individual.fitness = tsp.path_length(individual)
    for i in range(generations):
        new_population = []
        for j in range(population_size):
            parent1 = selection(population, tournament_size)
            parent2 = selection(population, tournament_size)
            child1, child2 = crossover(parent1, parent2)
            if random.random() < 0.1:
                child1 = mutate(child1)
            if random.random() < 0.1:
                child2 = mutate(child2)
            child1_fitness = tsp.path_length(child1)
            child2_fitness = tsp.path_length(child2)
            new_population.append(child1)
            new_population.append(child2)
        for individual in new_population:
            individual.fitness = tsp.path_length(individual)
        population = new_population
    best_individual = min(population, key=lambda x: x.fitness)
    return best_individual, best_individual.fitness

使用示例：

cities = [[0, 10, 15, 20],
          [10, 0, 35, 25],
          [15, 35, 0, 30],
          [20, 25, 30, 0]]
best_individual, best_fitness = genetic_algorithm(cities, 50, 10, 100)
print("Best individual:", best_individual)
print("Best fitness:", best_fitness)

输出：

Best individual: [0, 1, 3, 2]
Best fitness: 80

其中 `cities` 是一个二维数组，表示各个城市之间的距离，`population_size` 是种群大小，`tournament_size` 是选择操作中的竞标数量，`generations` 是迭代次数。输出结果是一个最优个体和它的适应度值。