遗传算法-GA

一、前言

遗传算法（英语：Genetic Algorithm，GA）是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。

遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

二、遗传算法概述

1. 开始：生成n个染色体的随机群体(问题的合适解决方案)

2. 适应度：评估群体中每个染色体x的适应度f(x)

3. 新群体：通过重复以下步骤创建新群体，直到新群体完成

    3.1 选择：根据适应度从群体中选择两条亲代染色体(适应度越好，被选择的机会越大)

    3.2 交叉：以交叉概率与父代交叉，形成新的后代(子代)。如果没有进行杂交，子代就是父代的精确拷贝。 

    3.3 突变：具有突变概率在每个基因体(染色体中的位置)突变新的后代。

    3.3 接受：将新的后代放入新的种群中

4. 替换：使用新生成的群体进一步运行算法

5. 测试：如果满足结束条件，停止并返回当前种群中的最佳解

6. 循环：转到步骤2

正如你所看到的，基本遗传算法的轮廓非常笼统。有许多参数和设置可以在各种问题中以不同的方式实现。

首先要问的问题是如何创建染色体，以及选择什么类型的编码。然后，我们解决交叉和变异，遗传算法的两个基本操作。编码、交叉和变异将在下一章介绍。

接下来的问题是如何选择杂交的亲本。这可以通过许多方式实现，但主要思想是选择更好的父母(最好的幸存者)，希望更好的父母会产生更好的后代。 你可能认为只从双亲中产生群体可能会导致你失去上一个群体中最好的染色体。这是真的，所以精英主义经常被使用。这意味着，一代人的最佳解决方案中至少有一个被复制，而没有改变到新的群体，因此最佳解决方案可以存活到下一代。

三、GA的运算

概述

从遗传算法概述中可知交叉和突变是最重要的部分 遗传算法。性能主要受这两个运算过程的影响。 在我们解释更多关于交叉和突变的信息之前，先了解一些信息 。下面将给出关于染色体的信息。

染色体的编码

染色体应该以某种方式包含它所代表的解的信息。最常用的编码方式是二进制字符串。一条染色体可能是这样的:

每个染色体由一个二进制字符串表示。字符串中的每一位都可以代表解决方案的一些特征。另一种可能性是整个字符串可以代表一个数字。

当然，还有很多其他的编码方式。编码主要取决于所解决的问题。例如，可以直接对整数或实数进行编码，有时对一些排列等进行编码也很有用。

交叉

在我们决定使用什么样的编码后，我们就可以进行交叉操作了。交叉对来自亲代染色体的选定基因进行操作，并产生新的后代。最简单的方法是随机选择一个交叉点，从第一个父节点复制该点之前的所有内容，然后从另一个父节点复制交叉点之后的所有内容。

交叉可以如下图所示:(|是交叉点):

还有其他方法来进行交叉，例如我们可以选择更多的交叉点。交叉可能相当复杂，主要取决于染色体的编码。针对特定问题的特定交叉可以提高遗传算法的性能。

突变

交叉完成后，变异就发生了。变异是为了防止群体中的所有解陷入所解决问题的局部最优。变异操作随机改变交叉产生的后代。在二进制编码的情况下，我们可以将一些随机选择的比特从1切换到0或者从0切换到1。

突变可以如下图所示:

突变(以及交叉)的技术主要取决于染色体的编码。例如，当我们编码排列时，突变可以作为两个基因的交换来进行。

四、案例

使用遗传算法（Genetic Algorithm, GA）来优化一个线性方程 y=w1​x1​+w2​x2​+w3​x3​+w4​x4​+w5​x5​+w6​x6​ 的权重 w1​ 到 w6​，其中 x1​ 到 x6​ 是给定的固定值。

4.1 计算当前种群中每个解的适应值

def cal_pop_fitness(equation_inputs, pop):   
    fitness = numpy.sum(pop * equation_inputs, axis=1)  
    return fitness 

这个函数通过计算每个个体（即权重数组）与给定的输入数组 equation_inputs 的逐元素乘积之和来工作，这正好对应于优化的线性方程 y=w1​x1​+w2​x2​+⋯+wn​xn​ 的形式。

4.2 选择适应度最高的个体作为下一代的父母

def select_mating_pool(pop, fitness, num_parents):
    parents = numpy.empty((num_parents, pop.shape[1]))
    for parent_num in range(num_parents):
        max_fitness_idx = numpy.where(fitness == numpy.max(fitness))
        max_fitness_idx = max_fitness_idx[0][0]
        parents[parent_num, :] = pop[max_fitness_idx, :]
        fitness[max_fitness_idx] = -99999999999
    return parents

定义的 select_mating_pool 函数旨在从当前种群中选择适应度最高的个体作为下一代的父母，但实现方式存在一些问题。特别是，当从 fitness 数组中选择了具有最高适应度的个体后，将其适应度值设置为一个非常小的负数，这可能会导致未来对 fitness 数组的最大值查找出现问题（因为可能不希望再次选择这个已经被选为父母的个体）。

然而，这种方法的一个主要问题是它只会选择单个最高适应度的个体作为所有父母，而不是选择多个不同的高适应度个体。这通常不是遗传算法中期望的行为，因为您希望从多种不同的优秀基因中混合和匹配。

一个更常见的方法是使用轮盘赌选择（Roulette Wheel Selection）或锦标赛选择（Tournament Selection）来从种群中随机但偏向于高适应度个体地选择父母。但如果您想要简单地选择适应度最高的前 num_parents 个个体，您可以这样做：

def select_mating_pool(pop, fitness, num_parents):  
    # 确保num_parents不超过种群大小  
    if num_parents > len(fitness):  
        raise ValueError("num_parents cannot be greater than the population size")  
  
    # 对索引进行排序，基于适应度值（从高到低）  
    sorted_indices = numpy.argsort(-fitness)  # 注意：numpy.argsort返回的是索引，前面的-号用于降序  
  
    # 选择前num_parents个个体作为父母  
    parents = pop[sorted_indices[:num_parents]]  
  
    return parents

在这个修正后的版本中，我们首先检查 num_parents 是否不大于种群大小。然后，我们使用 numpy.argsort 对索引进行排序，排序依据是适应度值的降序（通过 -fitness 实现）。最后，我们根据排序后的索引选择前 num_parents 个个体作为父母。

这种方法简单且有效，能够确保您从种群中选择出适应度最高的多个不同个体作为下一代的父母。

4.2.1 赌轮盘选择（Roulette Wheel Selection）

赌轮盘选择（Roulette Wheel Selection），也称为比例选择或适应度比例选择，是一种在遗传算法中用于选择父代个体的常用方法。这种方法基于个体的适应度值，适应度越高的个体被选中的概率越大。以下是使用Python和NumPy库实现的赌轮盘选择代码示例：

import numpy as np  
  
def roulette_wheel_selection(fitness, num_parents):  
    """  
    进行赌轮盘选择。  
      
    参数:  
    - fitness: 一个包含个体适应度值的NumPy数组。  
    - num_parents: 需要选择的父母个体数量。  
      
    返回:  
    - parents_indices: 一个包含被选中父母个体索引的NumPy数组。  
    """  
    # 确保num_parents不超过种群大小  
    if num_parents > len(fitness):  
        raise ValueError("num_parents cannot be greater than the length of fitness array")  
      
    # 计算适应度总和  
    total_fitness = np.sum(fitness)  
      
    # 计算每个个体被选中的概率  
    probabilities = fitness / total_fitness  
      
    # 累积概率，用于赌轮盘选择  
    cumulative_probabilities = np.cumsum(probabilities)  
      
    # 生成随机数以进行选择  
    random_numbers = np.random.rand(num_parents)  
      
    # 选择父母  
    parents_indices = []  
    for rand_num in random_numbers:  
        # 找到随机数所属的区间，该区间的起始索引即为被选中的个体索引  
        parent_idx = np.where(cumulative_probabilities >= rand_num)[0][0]  
        parents_indices.append(parent_idx)  
      
    # 将索引列表转换为NumPy数组  
    parents_indices = np.array(parents_indices)  
      
    return parents_indices  
  
# 示例  
fitness = np.array([10, 20, 15, 5, 25])  # 假设的适应度值  
num_parents = 3  # 需要选择的父母个体数量  
  
parents_indices = roulette_wheel_selection(fitness, num_parents)  
print("Selected parents indices:", parents_indices)

 4.3 交叉

crossover 函数实现了一个简单的单点交叉操作，但在处理数组形状和索引时需要注意一些细节。特别是，当处理多维数组时，确保所有维度都被正确处理是很重要的。此外，numpy.empty 需要一个完整的形状元组作为参数，而不仅仅是数组的大小。

def crossover(parents, offspring_size):
    offspring = numpy.empty(offspring_size)
    # The point at which crossover takes place between two parents. Usually, it is at the center.
    crossover_point = numpy.uint8(offspring_size[1]/2)

    for k in range(offspring_size[0]):
        # Index of the first parent to mate.
        parent1_idx = k%parents.shape[0]
        # Index of the second parent to mate.
        parent2_idx = (k+1)%parents.shape[0]
        # The new offspring will have its first half of its genes taken from the first parent.
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        # The new offspring will have its second half of its genes taken from the second parent.
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring

下面是一个修正后的版本，它假设 parents 是一个二维 NumPy 数组，其中每一行代表一个个体（或染色体），每一列代表一个基因。offspring_size 应该是一个元组，指定输出后代的形状（通常是 (num_offspring, num_genes)）。 

import numpy as np  
  
def crossover(parents, offspring_size):  
    num_offspring, num_genes = offspring_size  
    offspring = np.empty(offspring_size)  
      
    # 确保交叉点是一个整数，并且不超过基因数的一半  
    crossover_point = int(num_genes / 2)  
      
    for k in range(num_offspring):  
        # 使用模运算确保索引在有效范围内  
        parent1_idx = k % parents.shape[0]  
        parent2_idx = (k + 1) % parents.shape[0]  
          
        # 防止索引越界（如果父母数量少于后代数量）  
        if parent2_idx >= parents.shape[0]:  
            parent2_idx = 0  # 或者可以选择其他策略来处理这种情况  
          
        # 执行单点交叉  
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]  
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]  
      
    return offspring  
  
# 示例  
parents = np.array([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])  
offspring_size = (5, 4)  # 想要生成5个后代，每个后代有4个基因  
  
offspring = crossover(parents, offspring_size)  
print(offspring)

在这个修正后的版本中，我添加了以下改进：

1. offspring_size 被解包为 num_offspring 和 num_genes，这样代码更清晰。
2. 交叉点 crossover_point 被强制转换为整数，因为索引必须是整数。
3. 添加了处理 parent2_idx 可能超出 parents 数组范围的逻辑。在这个简单的例子中，我选择了将 parent2_idx 重置为 0，但在实际应用中，您可能希望实现更复杂的策略（例如，循环使用父母，或者确保每个父母至少被选中一次）。

4.4 突变

import numpy as np  
  
def mutation(offspring_crossover, num_mutations=1):  
    # 确保 num_mutations 不超过基因总数  
    num_genes = offspring_crossover.shape[1]  
    if num_mutations > num_genes:  
        raise ValueError("num_mutations cannot be greater than the number of genes")  
      
    # 对每个后代个体进行突变  
    for idx in range(offspring_crossover.shape[0]):  
        # 随机选择 num_mutations 个不重复的基因索引进行突变  
        mutation_indices = np.random.choice(num_genes, num_mutations, replace=False)  
          
        # 对这些基因进行突变  
        for gene_idx in mutation_indices:  
            # 生成一个 -1.0 到 1.0 之间的随机值  
            random_value = np.random.uniform(-1.0, 1.0, 1)  
            # 将随机值加到选定的基因上  
            offspring_crossover[idx, gene_idx] += random_value  
      
    return offspring_crossover