遗传算法解决路径规划问题 python代码

以下是一个简单的遗传算法解决路径规划问题的 Python 代码示例：

import random

# 地图边界
MAP_WIDTH = 10
MAP_HEIGHT = 10

# 起点和终点
START_POINT = (0, 0)
END_POINT = (9, 9)

# 障碍物位置
OBSTACLES = [(2, 2), (3, 2), (4, 2), (5, 2), (6, 2),
             (2, 7), (3, 7), (4, 7), (5, 7), (6, 7)]

# 遗传算法参数
POPULATION_SIZE = 50
GENERATION_COUNT = 100
MUTATION_RATE = 0.1

# 初始化种群
def init_population():
    population = []
    for i in range(POPULATION_SIZE):
        chromosome = [random.randint(0, 3) for _ in range(MAP_WIDTH * MAP_HEIGHT)]
        population.append(chromosome)
    return population

# 计算染色体代表的路径的长度
def calculate_fitness(chromosome):
    x, y = START_POINT
    distance = 0
    for gene in chromosome:
        if gene == 0 and y > 0:
            y -= 1
        elif gene == 1 and x < MAP_WIDTH - 1:
            x += 1
        elif gene == 2 and y < MAP_HEIGHT - 1:
            y += 1
        elif gene == 3 and x > 0:
            x -= 1
        if (x, y) in OBSTACLES:
            return 0
        if (x, y) == END_POINT:
            return distance
        distance += 1
    return distance

# 选择操作
def selection(population):
    fitness_values = [calculate_fitness(chromosome) for chromosome in population]
    total_fitness = sum(fitness_values)
    roulette_wheel = []
    for i in range(POPULATION_SIZE):
        selection_prob = fitness_values[i] / total_fitness
        roulette_wheel.extend([i] * int(selection_prob * 100))
    selected_chromosomes = []
    for i in range(POPULATION_SIZE):
        selected_index = random.choice(roulette_wheel)
        selected_chromosomes.append(population[selected_index])
    return selected_chromosomes

# 交叉操作
def crossover(parent1, parent2):
    crossover_point = random.randint(0, len(parent1) - 1)
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]
    return child1, child2

# 变异操作
def mutation(chromosome):
    for i in range(len(chromosome)):
        if random.random() < MUTATION_RATE:
            chromosome[i] = random.randint(0, 3)
    return chromosome

# 遗传算法主函数
def genetic_algorithm():
    population = init_population()
    for i in range(GENERATION_COUNT):
        selected_population = selection(population)
        offspring_population = []
        for j in range(POPULATION_SIZE // 2):
            parent1 = random.choice(selected_population)
            parent2 = random.choice(selected_population)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutation(child1)
            child2 = mutation(child2)
            offspring_population.extend([child1, child2])
        population = offspring_population
    fitness_values = [calculate_fitness(chromosome) for chromosome in population]
    best_index = fitness_values.index(min(fitness_values))
    best_chromosome = population[best_index]
    return best_chromosome

# 测试
best_chromosome = genetic_algorithm()
print(best_chromosome)

代码中，我们首先定义了地图边界、起点、终点和障碍物的位置。然后根据遗传算法的流程，实现了初始化种群、计算适应度、选择、交叉和变异等操作。最后，我们使用遗传算法求解出了一条从起点到终点的最短路径。