遗传算法（Genetic Algorithm, GA）作为一种模拟自然选择和遗传机制的优化算法，在解决复杂的优化问题中展现出强大的能力。本文将以路径规划为例，深入探讨遗传算法的实现原理及其在具体问题中的应用。
路径规划是机器人导航、物流配送等领域中的一个关键问题。其目标是在给定环境中找到一条从起点到终点的最优路径。遗传算法因其全局搜索能力强、易于实现并行计算等特点，成为解决路径规划问题的有效工具。
遗传算法通过模拟自然选择和遗传过程，包括选择、交叉（杂交）和变异等操作，逐步优化一组候选解（种群），直到找到近似最优解。
以二维平面上的路径规划为例，具体步骤如下：
以下是一个简单的路径规划案例，使用遗传算法求解从左上角到右下角的最短路径。
在一个5x5的网格中，存在障碍物（用'#'表示），目标是从左上角（0,0）到右下角（4,4）找到一条最短路径。
网格示例：
0 0 0 0 0
0 # # # 0
0 0 # 0 0
0 # 0 0 0
0 0 0 0 0
根据上述遗传算法步骤，编写代码实现路径规划。以下是一个简化版本的Python代码示例：
import random
import numpy as np
# 定义网格和障碍物
grid = np.array([
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 1, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
])
# 初始化种群
def initialize_population(pop_size, chrom_length):
population = []
for _ in range(pop_size):
chromosome = [random.randint(0, 1) for _ in range(chrom_length)]
population.append(chromosome)
return population
# 计算适应度值
def calculate_fitness(chromosome, grid):
# 解码染色体为路径
path = decode_chromosome(chromosome, grid)
# 计算路径长度
length = len(path) - 1 # 排除起点
return 1 / (length + 1) # 适应度值越高越好
# 解码染色体为路径
def decode_chromosome(chromosome, grid):
x, y = 0, 0
path = [(x, y)]
for gene in chromosome:
if gene == 0:
if y > 0: # 向上
y -= 1
else: # 向左
x -= 1
else:
if y < grid.shape[1] - 1: # 向下
y += 1
else: # 向右
x += 1
if grid[x, y] == 1 or (x, y) in path: # 遇到障碍物或重复访问
return [] # 返回空路径表示无效
path.append((x, y))
return path
# 遗传算法主函数
def genetic_algorithm(grid, pop_size=50, chrom_length=20, generations=100):
population = initialize_population(pop_size, chrom_length)
for generation in range(generations):
# 计算适应度值
fitness_values = [calculate_fitness(chromosome, grid) for chromosome in population]
# 选择操作（轮盘赌选择）
selected_population = random.choices(population, weights=fitness_values, k=pop_size)
# 交叉操作（单点交叉）
new_population = []
for i in range(0, pop_size, 2):
parent1, parent2 = selected_population[i], selected_population[i + 1]
crossover_point = random.randint(1, chrom_length - 2)
child1 = parent1[:crossover_point] + parent2[crossover_point:]
child2 = parent2[:crossover_point] + parent1[crossover_point:]
new_population.extend([child1, child2])
# 变异操作
for i in range(pop_size):
mutation_point = random.randint(0, chrom_length - 1)
new_population[i][mutation_point] = 1 - new_population[i][mutation_point]
population = new_population
# 打印当前最优解
best_chromosome