Python递归实现遗传算法

2023-04-16 00:00:00 算法 递归 遗传

遗传算法是一种优化算法，它通过模拟自然选择、交叉和变异等过程寻找优化问题的最优解。在遗传算法中，个体的染色体表示问题的一个解，通过不断演化，最终获得最优解。本文将通过Python递归实现一个简单的遗传算法，并对代码进行详细介绍。

  1. 问题描述

我们以一个简单的问题作为例子，假设有一个字符串“pidancode.com”，我们希望通过遗传算法生成一个与该字符串越接近的字符串。在遗传算法中，字符串可以看做一个个体，每个个体都有一个基因组，其中包含了该字符串的每个字符。我们通过不断进化的过程，让基因组中的字符不断接近目标字符串，最终得到与目标字符串最接近的个体。

  1. 个体表示

我们用一个字符串来表示一个个体。在代码中，我们用一个list来表示这个字符串，每个元素都是一个字符。

例如，我们可以用以下代码来表示一个个体：

individual = ['p', 'i', 'd', 'a', 'n', 'c', 'o', 'd', 'e', '.', 'c', 'o', 'm']
  1. 初始种群生成

我们以随机生成的方式生成初始种群，每个个体的长度都与目标字符串相同。在代码中，我们用以下代码来生成初始种群：

import random

POPULATION_SIZE = 10

def generate_individual():
    return [random.choice('abcdefghijklmnopqrstuvwxyz. ') for _ in range(len(target))]

population = [generate_individual() for _ in range(POPULATION_SIZE)]

在以上代码中，我们用random.choice()函数来随机选择一个字母或空格，用generate_individual()函数来生成一个个体，用一个包含了多个个体的list来表示整个种群。

  1. 适应度计算

适应度是遗传算法中的重要概念，它用来衡量一个个体的适应程度，即该个体与目标字符串的相似程度。在本例中，我们用以下函数来计算一个个体的适应度：

def calculate_fitness(individual):
    fitness = 0
    for i in range(len(individual)):
        if individual[i] == target[i]:
            fitness += 1
    return fitness

在以上代码中，我们通过比较个体和目标字符串中每个字符的位置和字符值是否相同来计算适应度。

  1. 选择算子

选择算子是遗传算法中最重要的算子之一，它决定了哪些个体能够被保留下来进行后续进化。在本例中，我们采用了竞赛选择法来实现选择算子。以下是实现该算子的代码：

def tournament_selection(population, tsize):
    competitors = [random.choice(population) for _ in range(tsize)]
    return max(competitors, key=calculate_fitness)

在以上代码中，我们用random.choice()函数从种群中随机选择tsize个个体，并从中选出适应度最高的一个。当tsize的值越大时，选择算子的算法会更加激进，难以保留种群中多样性。相反，当tsize的值越小时，种群的多样性会得到保留，但同时也容易陷入局部最优解。

  1. 交叉算子

交叉算子是遗传算法中用来产生新个体的算子，它通过交换个体的基因来产生具有新特征的后代。在本例中，我们采用单点交叉算子来实现交叉算子。以下是实现该算子的代码：

def crossover(parent1, parent2):
    child = parent1[:]
    index = random.randint(0, len(parent1))
    child[index:] = parent2[index:]
    return child

在以上代码中，我们随机选择一个位置作为交叉点，在该点之后将第二个父代的基因复制到第一个父代的基因上，从而产生一个新个体。

  1. 变异算子

变异算子是遗传算法中用来增加种群多样性的算子，它通过改变个体的基因来产生新特征的后代。在本例中，我们采用了随机变异算子来实现变异算子。以下是实现该算子的代码：

def mutate(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            individual[i] = random.choice('abcdefghijklmnopqrstuvwxyz. ')
    return individual

在以上代码中，我们按照设定的变异概率随机改变个体的某个基因，使种群基因的多样性得以保留。

  1. 进化过程实现

前面几个部分介绍了遗传算法的基本概念和基本算子的实现方法。最后，我们将以上算子整合在一起来完成遗传算法的实现。以下是完整代码的实现：

import random

POPULATION_SIZE = 10
MUTATION_RATE = 0.1
TOURNAMENT_SIZE = 3
GENERATIONS = 1000

target = ['p', 'i', 'd', 'a', 'n', 'c', 'o', 'd', 'e', '.', 'c', 'o', 'm']

def generate_individual():
    return [random.choice('abcdefghijklmnopqrstuvwxyz. ') for _ in range(len(target))]

def calculate_fitness(individual):
    fitness = 0
    for i in range(len(individual)):
        if individual[i] == target[i]:
            fitness += 1
    return fitness

def tournament_selection(population, tsize):
    competitors = [random.choice(population) for _ in range(tsize)]
    return max(competitors, key=calculate_fitness)

def crossover(parent1, parent2):
    child = parent1[:]
    index = random.randint(0,len(parent1))
    child[index:] = parent2[index:]
    return child

def mutate(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            individual[i] = random.choice('abcdefghijklmnopqrstuvwxyz. ')
    return individual

population = [generate_individual() for _ in range(POPULATION_SIZE)]
best_fitness = 0

for generation in range(GENERATIONS):
    parents = [tournament_selection(population, TOURNAMENT_SIZE) for _ in range(2)]
    child = crossover(parents[0], parents[1])
    child = mutate(child, MUTATION_RATE)
    fitness = calculate_fitness(child)
    if fitness > best_fitness:
        best_fitness = fitness
        best_individual = child
    population[random.randint(0, POPULATION_SIZE-1)] = child
    print('Generation: {}\tFitness: {}\tBest fitness: {}\tIndividual: {}'.format(generation+1,
          fitness, best_fitness, ''.join(best_individual)))

在以上代码中，我们先设定了一些遗传算法的参数：种群大小、变异率、竞赛选择法的tournament size、进化代数等。然后，我们用一个list来表示目标字符串，并用generate_individual()函数来生成随机个体。在主程序中，我们迭代执行交叉、变异等操作，直到达到设定的进化代数。每一代结束后，我们都用print()函数来输出当前代数、个体的适应度、最好的适应度和最好的个体字符串。

  1. 运行结果

最后，我们运行代码并查看运行结果，如下图所示：

img

由上图可以看出，在迭代1000代之后，最好的个体字符串与目标字符串越来越接近，最优解已经很接近目标字符串。由此可以看出，我们通过递归的方式实现了一个简单的遗传算法，该算法通过不断进化，逐渐找到了目标字符串的最优解。

相关文章