遗传算法理解与代码实战（一）- demo（python手写代码）_遗传算法实战

遗传算法（Genetic Algorithm, GA）是模拟自然界中生物进化的机制来搜索最优解的方法。遗传算法属于进化计算的一部分，它借鉴了达尔文的自然选择和孟德尔的遗传学原理。

1、算法背景

遗传算法的灵感来源于生物进化过程。在自然界中，生物通过基因的遗传和变异，以及环境的自然选择，逐步演化出适应环境的特征。遗传算法模拟这一过程，通过编码表示问题解的“染色体”，并利用选择、交叉（重组）、变异等操作来模拟生物进化过程，从而搜索问题的最优解。

2、算法原理

遗传算法通常包含以下几个基本步骤：

1. 初始化：随机生成一组候选解（个体），这些解通常以二进制字符串（染色体）的形式表示。
2. 评估：使用适应度函数评估每个个体的适应度，即解的好坏。
3. 选择：根据适应度，从当前群体中选择优良的个体作为父本，用于产生下一代。
4. 交叉（Crossover）：随机选择交叉点，将父本的染色体交换部分基因，产生新的个体（后代）。
5. 变异：以一定的概率随机改变个体的某些基因，引入新的遗传多样性。
6. 迭代：用新生成的后代替换掉当前群体中的一部分或全部个体，形成新的群体。
7. 终止：当达到一定的迭代次数或找到满足条件的解时，算法终止。

3、算法优势

遗传算法具有以下优势：

• 全局搜索能力：通过模拟自然选择和遗传，遗传算法能够在整个搜索空间中进行全局搜索，减少陷入局部最优解的风险。
• 鲁棒性：遗传算法对问题的初始条件要求不高，且在迭代过程中不易受到噪声等不利因素的影响。
• 并行性：遗传算法的多个个体并行搜索，易于实现并行处理，提高搜索效率。
• 灵活性：遗传算法不依赖于具体问题的数学模型，适应性强，适用于多种类型的问题。

4、应用场景

遗传算法广泛应用于各种优化和搜索问题，如工程优化、机器学习、经济调度、自动控制等领域。

遗传算法作为一种有效的全局搜索算法，通过模拟生物进化过程，能够在复杂问题中找到满意的解。它以其独特的搜索机制和优点，在多个领域得到了广泛的应用。然而，遗传算法也有其局限性，如算法参数的选择、计算量较大等问题，需要在实际应用中加以考虑和优化。

5、简单实例

我们哪一个非常简单的优化为例讲一下：
目标函数：$y=x^2$
我们在一组数据中找到可以使得目标函数达到最大的值，x的取值范围是[0，31]

5.1 名词解释说明

• 种群（Population）：
  遗传算法保持大量的个体（individuals）——针对当前问题的候选解集合。由于每个个体都由染色体表示，因此这些种族的个体（individuals）可以看作是染色体集合。比如我们在这里x的取值范围是[0，31]，我们随机取5个数字[2，5，11，24，7]作为一个种群，其中每一个数字就是个体；

• 基因（Genotype）：
  在自然界中，通过基因型表征繁殖，繁殖和突变，基因型是组成染色体的一组基因的集合。在遗传算法中，每个个体都由代表基因集合的染色体构成。例如，一条染色体可以表示为二进制串，其中每个位代表一个基因。比如我们上面随机取5个数字[2，5，11，24，7]作为一个种群，每一个数字就是一个个体，每个数字用二进制表示，比如数字2的二进制表示是：00010，一共有5个基因，

  我们这里x的取值范围是[0，31]，也就是为了将基因的最大个数限制在5个，因为5个基因最大数值是：11111，转换为十进制就是31 。当然其实自己可是设置更大的基因个数，这里只是用来演示简单的过程。

• 适应度函数（Fitness function）
  在算法的每次迭代中，使用适应度函数（也称为目标函数）对个体进行评估。目标函数是用于优化的函数或试图解决的问题。适应度得分更高【适应度可以根据目标函数的需求来设定是取大还是取小】的个体代表了更好的解，其更有可能被选择繁殖并且其性状会在下一代中得到表现。比如我们这里的适应度函数就是个体数值的平方，随着遗传算法的进行，解的质量会提高，适应度会增加，一旦找到具有令人满意的适应度值的解，终止遗传算法。

• 选择（Selection）
  在计算出种群中每个个体的适应度后，使用选择过程来确定种群中的哪个个体将用于繁殖并产生下一代，具有较高值的个体更有可能被选中，并将其遗传物质传递给下一代。仍然有机会选择低适应度值的个体，但概率较低。这样，就不会完全摒弃其遗传物质。

• 交叉（Crossover）
  为了创建一对新个体，通常将从当前代中选择的双亲样本的部分染色体互换（交叉），以创建代表后代的两个新染色体。此操作称为交叉或重组。
  

• 突变（Mutation）
  突变操作的目的是定期随机更新种群，将新模式引入染色体，并鼓励在解空间的未知区域中进行搜索。
  突变可能表现为基因的随机变化。变异是通过随机改变一个或多个染色体值来实现的。例如，翻转二进制串中的一位。
  

5.2 代码参数设置

# 参数设置
CHROMOSOME_SIZE = 5  # 染色体长度
POPULATION_SIZE = 10  # 种群大小
CROSSOVER_RATE = 0.7  # 交叉率，就是有70%的概率会交叉，30%直接返回原始的基因
MUTATION_RATE = 0.01  # 变异率
GENERATIONS = 100  # 迭代次数

# 初始化种群
population = np.random.randint(2, size=(POPULATION_SIZE, CHROMOSOME_SIZE))

array([[1, 0, 0, 1, 0],
       [0, 1, 0, 0, 1],
       [0, 1, 1, 0, 1],
       [0, 0, 1, 1, 0],
       [1, 0, 0, 1, 0],
       [1, 0, 1, 1, 0],
       [1, 0, 0, 1, 1],
       [0, 1, 1, 0, 0],
       [1, 1, 0, 1, 1],
       [1, 0, 0, 0, 1]])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

我们可以看到这里有10条数据，就是个体数为10 的种群。

5.3 定义适应度、选择、交叉和变异函数

# 适应度函数，计算个体的适应度
def fitness(chromosome):
    x = int(''.join(str(gene) for gene in chromosome), 2)#转换成十进制
    return x ** 2

# 选择函数，基于适应度进行选择
def select(population):
    fitness_values = np.array([fitness(individual) for individual in population])
    return population[np.random.choice(range(POPULATION_SIZE), size=POPULATION_SIZE, replace=True, p=fitness_values / fitness_values.sum())]

# 交叉函数，随机选择交叉点，进行基因交换
def crossover(parent1, parent2):
    if np.random.rand() < CROSSOVER_RATE:
        point = np.random.randint(1, CHROMOSOME_SIZE - 1)
        return np.concatenate((parent1[:point], parent2[point:])), np.concatenate((parent2[:point], parent1[point:]))
    else:
        return parent1, parent2

# 变异函数，随机翻转基因
def mutate(chromosome):
    for i in range(CHROMOSOME_SIZE):
        if np.random.rand() < MUTATION_RATE:
            chromosome[i] = 1 - chromosome[i]
    return chromosome


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 选择函数解析：

  • population: 这是一个参数，代表当前种群的个体集合。在遗传算法中，种群是所有可能的解决方案的集合。
  • fitness_values = np.array([fitness(individual) for individual in population]):
    这里使用列表推导式来计算种群中每个个体的适应度值。适应度函数fitness(individual)是一个用户定义的函数，用于评估个体individual的适应度，即它在解决问题上的好坏。
    np.array将计算出的适应度值列表转换为NumPy数组，以便进行下一步的计算。
  • population[np.random.choice(range(POPULATION_SIZE), size=POPULATION_SIZE, replace=True, p=fitness_values / fitness_values.sum())]:
    • np.random.choice: 这是一个NumPy函数，用于根据给定的概率随机抽取样本。
      range(POPULATION_SIZE): 创建一个从0到种群大小-1的序列，用于np.random.choice作为抽样范围的参数。
    • size=POPULATION_SIZE: 指定抽样的数量等于种群的大小，这意味着我们将从当前种群中选择相同数量的个体形成新的种群。
    • replace=True: 允许重复抽样，即同一个个体可以被多次选中进入新的种群。
    • p=fitness_values / fitness_values.sum(): 指定每个个体被选中的概率，这个概率与个体的适应度值成正比。这里首先将所有个体的适应度值相加得到总和，然后将每个个体的适应度值除以这个总和，得到归一化的概率。这样，适应度更高的个体有更大的概率被选中。

• 交叉函数

  • parent1 和 parent2: 这两个参数代表选择用于交叉操作的两个父代个体。
  • if np.random.rand() < CROSSOVER_RATE::
    • np.random.rand(): 生成一个0到1之间的随机数。
    • CROSSOVER_RATE: 这是一个预设的交叉概率，用于决定是否进行交叉操作。如果生成的随机数小于CROSSOVER_RATE，则进行交叉；否则，不进行交叉，直接返回父代个体。
      point = np.random.randint(1, CHROMOSOME_SIZE - 1):
    • np.random.randint: 用于生成一个指定范围内的随机整数。
      1, CHROMOSOME_SIZE - 1: 指定交叉点的生成范围。交叉点不能在染色体的起始或结束位置，因此范围是从1到CHROMOSOME_SIZE - 1（CHROMOSOME_SIZE是染色体的长度）。
  • return np.concatenate((parent1[:point], parent2[point:])), np.concatenate((parent2[:point], parent1[point:])):
    • np.concatenate: 用于连接两个或多个数组。
      这行代码创建了两对新的子代个体。第一对是将parent1的前半部分与parent2的后半部分连接起来，第二对是将parent2的前半部分与parent1的后半部分连接起来。这样，每个子代都会从两个父代那里继承一部分基因。
  • else: return parent1, parent2:
    如果没有进行交叉（即随机数大于等于CROSSOVER_RATE），则直接返回父代个体，不做任何改变。

• 变异解析

  • chromosome: 这个参数代表需要进行变异的个体（染色体）。在遗传算法中，个体通常表示为二进制数组，其中的每个元素称为基因。
  • for i in range(CHROMOSOME_SIZE)::
    这行代码遍历染色体中的每个基因。
    • if np.random.rand() < MUTATION_RATE::
    • np.random.rand(): 生成一个0到1之间的随机数。
      MUTATION_RATE: 这是一个预设的变异概率，用于决定是否对当前基因进行变异。如果生成的随机数小于MUTATION_RATE，则进行变异；否则，不进行变异。
    • chromosome[i] = 1 - chromosome[i]:
      如果决定对当前基因进行变异，则将基因的值取反。在二进制表示中，这意味着将0变为1，将1变为0。
  • return chromosome:
    在遍历完所有基因并可能进行了一些变异后，返回变异后的染色体。

5.4 主函数–遗传算法迭代

# 用于存储每代的最佳适应度，用于后续的可视化
best_fitness_over_generations = []

# 遗传算法主循环
for generation in range(GENERATIONS):
    selected_population = select(population)
    next_generation = []
    for i in range(0, POPULATION_SIZE, 2):
        parent1, parent2 = selected_population[i], selected_population[i + 1]
        offspring1, offspring2 = crossover(parent1, parent2)
        offspring1 = mutate(offspring1)
        offspring2 = mutate(offspring2)
        next_generation.append(offspring1)
        next_generation.append(offspring2)
    population = np.array(next_generation)
    # 更新最佳适应度
    best_fitness = max(fitness(individual) for individual in population)
    best_fitness_over_generations.append(best_fitness)
    print(f'Generation {generation + 1}, Best Fitness: {best_fitness}')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1. best_fitness_over_generations = []:
   • 这是一个空列表，用于存储每一代种群的最高适应度值，以便后续可以进行可视化分析。
2. for generation in range(GENERATIONS)::
   • 这行代码开始遗传算法的主循环，GENERATIONS是预设的迭代次数，即算法将运行的代数。
3. selected_population = select(population):
   • 调用之前定义的选择函数select，根据个体的适应度比例从当前种群中选择出新的种群。
4. next_generation = []:
   • 初始化一个空列表，用于存储新一代的个体。
5. for i in range(0, POPULATION_SIZE, 2)::
   • 这个循环遍历选择的种群，每次取出两个个体作为父母。(这里是每次间隔2取一次数，比如第一次取0，那么在下面代码去的是i和i+1，也就是取了0和1两个数，下一次取2 ，那么就是取了2和3两个数)
6. parent1, parent2 = selected_population[i], selected_population[i + 1]:
   • 从选择的种群中获取两个父母个体。
7. offspring1, offspring2 = crossover(parent1, parent2):
   • 调用之前定义的交叉函数crossover，对两个父母个体进行交叉操作，生成两个子代个体。
8. offspring1 = mutate(offspring1) 和 offspring2 = mutate(offspring2):
   • 调用之前定义的变异函数mutate，对两个子代个体进行变异操作。
9. next_generation.append(offspring1) 和 next_generation.append(offspring2):
   • 将变异后的子代个体添加到新一代种群列表中。
10. population = np.array(next_generation):
    • 将新一代种群列表转换为NumPy数组，更新当前种群。
11. best_fitness = max(fitness(individual) for individual in population):
    • 计算当前种群中个体的最高适应度值。
12. best_fitness_over_generations.append(best_fitness):
    • 将当前种群的最佳适应度添加到best_fitness_over_generations列表中，用于后续分析。
13. print(f'Generation {generation + 1}, Best Fitness: {best_fitness}'):
    • 打印当前代数和最佳适应度，以便监控算法的进度。

Generation 1, Best Fitness: 729
Generation 2, Best Fitness: 729
Generation 3, Best Fitness: 841
Generation 4, Best Fitness: 729
Generation 5, Best Fitness: 729
Generation 6, Best Fitness: 961
Generation 7, Best Fitness: 961
Generation 8, Best Fitness: 961
……
1
2
3
4
5
6
7
8
9