Python遗传算法（Genetic Algorithm）实现

2023-04-17 00:00:00 python 算法 遗传

遗传算法（Genetic Algorithm）是一种基于生物进化原理的优化算法，其基本思想是模拟自然界的选择、交叉和变异等过程，从而寻找问题的最优解。在Python中实现遗传算法，可以帮助我们解决许多实际问题，如旅行商问题、机器学习中的参数优化等。

遗传算法的基本流程

  1. 初始化种群：遗传算法首先需要随机生成一组种群，即一些随机的个体。这些个体通常是一个长度为n的二进制串，表示问题的解空间中的一个点。例如，如果要找到字符串中最长的子串，那么每个个体就是一个字符串。种群大小一般为几十或几百个，较小的种群往往会导致算法收敛速度缓慢，而较大的种群则会增加计算复杂度。

  2. 适应度函数评估：种群生成后，需要对每个个体进行适应度函数评估。适应度函数可以根据问题的具体特点而确定，它的作用是评估个体在解空间中的适应能力，即表现力或解空间中的位置质量。适应度值高的个体越有可能被选择，因为它们更有可能产生优秀的后代。适应度函数有多种计算方法，常用的是将目标函数（问题的优化目标）作为适应度函数。

  3. 选择：选择是指从种群中选择一些适应度较高的个体作为初始群体，并使它们在下一步交叉和变异后生成后代。选择方法有多种，如轮盘赌选择、锦标赛选择等。

  4. 交叉：交叉是指将已选个体的某些部分进行重新组合，生成新的后代。交叉的目的是将个体之间的优良特性进行合理组合，以产生更优秀的后代。交叉方法有多种，如单点交叉、多点交叉等。

  5. 变异：变异是指在后代中对某些个体进行随机变换，通常是将某个位置的基因值（1或0）更改为另一个值。变异的目的是使解空间更加丰富，防止算法陷入局部最优解。变异的概率通常很低，一般在0.001-0.01之间。

  6. 新一代个体生成：在经过选择、交叉和变异后，新一代个体已经生成完毕。接下来需要对新一代个体进行适应度函数评估，并更新种群。通常，新一代个体中的一部分会被替换掉旧的个体，这样可以保证种群中的品种多样性。

  7. 终止条件判断：遗传算法应该设置一个终止条件用于结束算法的迭代过程，例如达到最大迭代次数、适应度函数值已经收敛等。如果达到终止条件，则算法结束，输出当前解的值。

Python遗传算法实现

接下来，我们将以一个简单的例子来展示如何在Python中实现遗传算法。本例子的问题是求字符串中最长的子串。

首先，我们需要初始化种群。在这里，我们随机生成10个字符串，每个字符串长度为5。

import random

POPULATION_SIZE = 10
GENE_SIZE = 5

def generate_individual():
    return ''.join(random.choices("abcdefghijklmnopqrstuvwxyz", k=GENE_SIZE))

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

接着，我们需要定义适应度函数。在这里，我们将适应度定义为子串的长度。

def fitness(individual):
    max_len = 0
    for i in range(len(individual)):
        for j in range(i+1, len(individual)+1):
            if len(set(individual[i:j])) == j-i:
                max_len = max(max_len, j-i)
    return max_len

print(fitness("abcdxyz"))

然后，我们需要定义选择函数。在这里，我们使用轮盘赌选择法，即根据适应度概率选择个体。选择的过程也可以使用numpy库中的随机选择方法。

def selection(population):
    fitness_sum = sum(fitness(p) for p in population)
    probabilities = [fitness(p) / fitness_sum for p in population]
    return random.choices(population, weights=probabilities)

print(selection(population))

接下来，我们需要定义交叉和变异函数。在这里，我们选择多点交叉和单点变异。

def crossover(parent1, parent2):
    point1 = random.randint(1, GENE_SIZE-1)
    point2 = random.randint(point1, GENE_SIZE-1)
    return parent1[:point1] + parent2[point1:point2] + parent1[point2:]

def mutation(individual):
    point = random.randint(0, GENE_SIZE-1)
    return individual[:point] + random.choice("abcdefghijklmnopqrstuvwxyz") + individual[point+1:]

p1, p2 = population[0], population[1]
print(crossover(p1, p2))

p = population[0]
print(mutation(p))

最后，我们将所有的函数融合在一起，定义一个遗传算法函数，并运行它。

def genetic_algorithm():
    population = [generate_individual() for _ in range(POPULATION_SIZE)]
    best_individual = None
    best_fitness = 0

    for i in range(100):
        new_population = []
        for j in range(POPULATION_SIZE):
            parent1, parent2 = selection(population), selection(population)
            offspring = crossover(parent1, parent2)
            if random.random() < 0.01:
                offspring = mutation(offspring)
            new_population.append(offspring)

        population = new_population

        for ind in population:
            fit = fitness(ind)
            if fit > best_fitness:
                best_fitness = fit
                best_individual = ind

            if fit == GENE_SIZE:
                return ind

    return best_individual

print("Best individual: ", genetic_algorithm())

在这个例子中，我们使用遗传算法找到了一个字符串中最长的子串。实际上，遗传算法可用于更多复杂的问题。在具体实践中，我们需要确定种群大小、交叉和变异的概率等参数，并选择适当的适应度函数和选择策略，以获得更好的解决方案。

相关文章