遗传算法

9.1 遗传算法简介。

遗传算法（GA）是一种优化和搜索方法，灵感来自于自然选择的过程，模拟了生物进化过程。

遗传算法用于解决复杂问题，其中传统方法可能无效。它们使用选择、交叉（crossover）和变异的机制来进化解答。

工作原理：

1. 初始化：

创建初始种群的可能解（染色体）。每个解以字符串的形式编码（位串、字符串或其他结构）。

2 适应性函数（fitness function）：

评估种群中每个解的质量。

3. 评估：

每个解（个体）通过适应性函数（fitness function）进行评估，确定解答问题的效果。

4. 选择：

适应性更好的解有更多机会被选择用于繁殖。常用方法有轮盘选择（roulette wheel selection）、锦标赛选择（tournament selection）和排序选择（rank selection）。

5. 交叉（crossover）：

选定的解（父代）组合创建新的解（子代）。交叉可以是单点、双点或多点。

6. 变异：

在新解中施加随机更改（变异）以引入多样性。这帮助算法避免局部最小值。

7. 替换：

新的种群替换旧种群，过程重复直到满足停止条件（如达到一定代数或达到特定适应性）。

优点和缺点

优点：

• 应用广泛：可用于解决各种问题，包括分析方法不适用的问题。
• 全局优化：能够在多维和复杂空间中找到全局最优。
• 灵活性：可与任何适应性函数一起使用。

缺点：

• 高计算成本：对于大型种群和复杂问题，需要大量计算资源。
• 参数调节困难：调整参数（种群大小、变异和交叉概率）可能很困难，并对性能有很大影响。
• 没有最佳解的保证：不能保证找到的解是全局最优。

实际上，遗传算法是一种非常高效的启发式方法。即使它拥有全部数据，也不能保证能找到最佳解法。但是对于复杂情况和庞大数据量，它能很快给出接近理想的解。

9.2 应用示例

我们看看用遗传算法优化函数的例子。

import random

# 遗传算法参数
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# 定义适应性函数
def fitness_function(x):
    return -x**2 + 10*x
            
# 初始化种群
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# 选择（锦标赛选择）
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# 交叉（单点）
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# 变异
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# 遗传算法主循环
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# 输出最佳解
best_individual = max(population, key=fitness_function)
print("最佳解:", best_individual)
print("函数值:", fitness_function(best_individual))
            
        

优点和缺点

9.3 多维函数优化

任务:

找出多维函数的最小值。

解决方案：

我们使用之前的模板

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# 用例：
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"最佳解: {best_solution}")