遗传算法应用教程

遗传算法是一种模拟自然选择和遗传学原理的搜索启发式算法。它被广泛应用于优化问题、机器学习、人工智能等领域。以下是一些遗传算法的应用实例：

应用领域

机器学习：用于优化神经网络参数、特征选择等。
优化问题：求解旅行商问题、背包问题等组合优化问题。
工程设计：优化电路设计、结构设计等。
图像处理：图像分割、特征提取等。

实例教程

以下是一个简单的遗传算法实例教程，用于解决旅行商问题（TSP）。

1. 初始化种群

首先，我们需要初始化一个种群，种群中的每个个体代表一个可能的解决方案。

def initialize_population(pop_size, num_cities):
    population = []
    for _ in range(pop_size):
        individual = [random.randint(0, num_cities - 1) for _ in range(num_cities)]
        population.append(individual)
    return population

2. 适应度函数

适应度函数用于评估每个个体的优劣程度。

def fitness_function(individual, distances):
    total_distance = sum(distances[individual[i], individual[i + 1]] for i in range(len(individual) - 1))
    total_distance += distances[individual[-1], individual[0]]  # Return to the starting city
    return 1 / total_distance

3. 选择

选择操作用于从当前种群中选择个体进行交叉和变异。

def select(population, fitness):
    total_fitness = sum(fitness)
    selection_probs = [f / total_fitness for f in fitness]
    return random.choices(population, weights=selection_probs, k=2)

4. 交叉

交叉操作用于产生新的个体。

def crossover(parent1, parent2):
    crossover_point = random.randint(1, len(parent1) - 2)
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]
    return child1, child2

5. 变异

变异操作用于增加种群的多样性。

def mutate(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            individual[i] = random.randint(0, len(individual) - 1)
    return individual

6. 运行遗传算法

def genetic_algorithm(pop_size, num_cities, mutation_rate, generations):
    population = initialize_population(pop_size, num_cities)
    for _ in range(generations):
        fitness = [fitness_function(individual, distances) for individual in population]
        new_population = []
        for _ in range(pop_size // 2):
            parent1, parent2 = select(population, fitness)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutate(child1, mutation_rate)
            child2 = mutate(child2, mutation_rate)
            new_population.extend([child1, child2])
        population = new_population
    return max(population, key=fitness_function)