遗传算法python实现_遗传算法解释：Python实现

遗传算法python实现

遗传算法（也称为“ GA”）是受查尔斯·达尔文（Charles Darwin）的自然选择理论启发而提出的算法，旨在为我们不太了解的问题找到最佳解决方案。例如：当您不能推导给定函数的最大值或最小值时，如何找到它？它基于三个概念：选择，复制和变异。我们随机生成一个个体集合，选择最好的，在最后越过它们稍微变异的结果-一遍又一遍，直到我们找到一个可接受的解决方案。您可以在Goldberg的书中检查其他搜索方法的一些比较。

让我们检查一下如何使用Python编写遗传算法的简单实现！

我们将在这里尝试解决的问题是找到类似于帽子的3D功能的最大值。它定义为f（x，y）= sin（sqrt（x ^ 2 + y ^ 2）） 。我们将问题限制在4≥x≥- 4和4≥y≥- 4的边界上。

（ 函数定义在我们定义的边界之间，由 CalcPlot3D 创建）

第一步是生成我们的初始人口。人口或世代是我们当前称为个人的可能解决方案集。我们将反复进行几代的改进，直到找到可接受的解决方案。第一代是随机生成的。

import random

def generate_population (size, x_boundaries, y_boundaries) :
    lower_x_boundary, upper_x_boundary = x_boundaries
    lower_y_boundary, upper_y_boundary = y_boundaries

    population = []
    for i in range(size):
        individual = {
            "x" : random.uniform(lower_x_boundary, upper_x_boundary),
            "y" : random.uniform(lower_y_boundary, upper_y_boundary),
        }
        population.append(individual)

    return population

我们的创始函数需要三个参数：人口应该拥有的个体数量，一个元组指示x轴上的边界，一个元组指示y轴上的边界，因此我们的个体随机地拟合这些边界。

继续，让我们定义健身功能。这将是我们的评估者，它将表达一个人彼此之间的好坏程度。身体最好的人应该得到保护和繁殖，而最坏的人应该跌倒-就像自然界一样。在我们的案例中，我们要如何找到函数的最大值，我们可以简单地将目标函数应用于个人，最大的数字也将是最大的适用性。如果我们想找到最小值，则适应度可以表示为功能时间-1的结果，因此较小的值将变为较大的适应度。

import math

def apply_function (individual) :
    x = individual[ "x" ]
    y = individual[ "y" ]
    return math.sin(math.sqrt(x ** 2 + y ** 2 ))

由于我们拥有人口产生器和健康评估器，因此我们可以开始繁殖我们的个体以实现下一代。我们将一直这样做，直到找到可接受的解决方案。停止条件有好几种，其中一个被广泛使用的标准是“ n代具有陈旧的适应性”，但我们将使用一个更简单的标准，即n代-我们将使用100。到目前为止，我们的输入函数如下：

generations =100

population = generate_population(size= 10 , x_boundaries=( -4 , 4 ), y_boundaries=( -4 , 4 ))

i = 1
while True :
    print( f"🧬 GENERATION {i} " )

    for individual in population:
        print(individual)

    if i == generations:
        break

    i += 1

    # Make next generation...

为了选择要复制的个体，我们将使用一种被广泛采用的方法，称为轮盘赌法，该方法包括将圆分成多个部分，例如饼图，其中每个个体的比例都与其适应度成正比，然后旋转它。通过这种方式，我们可以确保最好的个人有更好的机会被选中，而最坏的人仍然有机会，尽管这是次要的。

def choice_by_roulette (sorted_population, fitness_sum) :
    offset = 0
    normalized_fitness_sum = fitness_sum

    lowest_fitness = apply_function(sorted_population[ 0 ])
    if lowest_fitness < 0 :
        offset = -lowest_fitness
        normalized_fitness_sum += offset * len(sorted_population)

    draw = random.uniform( 0 , 1 )

    accumulated = 0
    for individual in sorted_population:
        fitness = apply_function(individual) + offset
        probability = fitness / normalized_fitness_sum
        accumulated += probability

        if draw <= accumulated:
            return individual

为了说明我们的方法，假设我们有四个个人：A，B，C和D分别具有0、50、200和250的适应度。总适应度的总和为500，因此每个人都有被选择适应度/ total_fitness的机会：0％，10％，40％，50％。我们选择一个介于0和1之间的随机数，然后验证哪个人在所选部分中：A [0，0]，B（0，0.1]，C（0.1，0.5]，D（0.5，1]。

由于我们的方案可能具有负适应性，因此我们首先必须通过选择最低适应性，乘以-1并将其相加来对我们的个体进行归一化（例如，如果我们有两个个体的适应性分别为-10和5，我们将10加为0和15）。我们还希望将人口论证按照适合度升序排列，因此更容易找到最坏和最好的人。

然后让我们填充下一代。它的长度应与第一个相同，因此我们将重复10次，使用轮盘赌选择两个人，然后越过他们。结果产生的个体将受到较小的扰动（变异），因此我们不会坚持舒适区，而是要寻找比目前为止更好的解决方案。

实数有几种交叉技术：例如，我们可以取个体A的x和个体B的y ，可以取每个的几何平均值，或者最简单的取每个的算术平均值。如果要处理二进制数据，最常用的技术是选择A的一部分位串和B的一部分位。出于简单起见，让我们使用算术平均值。

对于突变也有很多选择-我们将简单地将固定间隔之间的一个小的随机数求和。该间隔是突变率，可以相应地进行微调，让我们使用[-0.05，0.05]。对于较大的搜索空间，您可以选择较大的间隔并逐代减小。处理二进制数据时，您可以简单地翻转单个字符串的随机选择的位。

def sort_population_by_fitness (population) :
    return sorted(population, key=apply_function)


def crossover (individual_a, individual_b) :
    xa = individual_a[ "x" ]
    ya = individual_a[ "y" ]

    xb = individual_b[ "x" ]
    yb = individual_b[ "y" ]

    return { "x" : (xa + xb) / 2 , "y" : (ya + yb) / 2 }


def mutate (individual) :
    next_x = individual[ "x" ] + random.uniform( -0.05 , 0.05 )
    next_y = individual[ "y" ] + random.uniform( -0.05 , 0.05 )

    lower_boundary, upper_boundary = ( -4 , 4 )

    # Guarantee we keep inside boundaries
    next_x = min(max(next_x, lower_boundary), upper_boundary)
    next_y = min(max(next_y, lower_boundary), upper_boundary)

    return { "x" : next_x, "y" : next_y}


def make_next_generation (previous_population) :
    next_generation = []
    sorted_by_fitness_population = sort_population_by_fitness(previous_population)
    population_size = len(previous_population)
    fitness_sum = sum(apply_function(individual) for individual in population)

    for i in range(population_size):
        first_choice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)
        second_choice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)

        individual = crossover(first_choice, second_choice)
        individual = mutate(individual)
        next_generation.append(individual)

    return next_generation

就是这样！现在，我们有了GA的所有三个步骤：选择，交叉和突变。我们的主要方法就是这样：

generations =100

population = generate_population(size= 10 , x_boundaries=( -4 , 4 ), y_boundaries=( -4 , 4 ))

i = 1
while True :
    print( f"🧬 GENERATION {i} " )

    for individual in population:
        print(individual, apply_function(individual))

    if i == generations:
        break

    i += 1

    population = make_next_generation(population)

best_individual = sort_population_by_fitness(population)[ -1 ]
print( "\n🔬 FINAL RESULT" )
print(best_individual, apply_function(best_individual))

在这100代之后， best_individual变量将使我们的个体适应度最高。不管它是否是精确的最佳解决方案，您都必须微调参数（变异率，世代等）和技术（选择，交叉和变异方法），直到无法改善为止。让我们看一下实验运行的最后输出行（请注意，由于随机参数，您很可能会获得不同但相似的结果）：

🧬 GENERATION 100
{'x': -1.0665224807251312, 'y': -1.445963268888755} 0.9745828000809058
{'x': -1.0753606354537244, 'y': -1.4293367491155182} 0.976355423070003
{'x': -1.0580786664161246, 'y': -1.3693549033564183} 0.9872729309456848
{'x': -1.093601208942564, 'y': -1.383292089777704} 0.9815156357267611
{'x': -1.0464963866796362, 'y': -1.3461172606906064} 0.9910018621648693
{'x': -0.987226479369966, 'y': -1.4569537217049857} 0.9821687265560713
{'x': -1.0501568673329658, 'y': -1.430577408679398} 0.9792937786319258
{'x': -1.0291192465186982, 'y': -1.4289167102720242} 0.9819781801342095
{'x': -1.098502968808768, 'y': -1.3738230550364259} 0.9823409690311633
{'x': -1.091317403073779, 'y': -1.4256574643591997} 0.9748817266026281

🔬 FINAL RESULT
{'x': -1.0464963866796362, 'y': -1.3461172606906064} 0.9910018621648693

我们的最终结果非常接近一种可能的解决方案（此函数在我们的边界内具有多个最大值，如开始时在图上所见，该最大值为1.0）。请注意，我们使用的是不太复杂的技术，因此可以预期得到此结果-这是微调的起点，直到我们能够找到世代较少的更好的解决方案为止。

这是一篇有关使用Python的遗传算法的入门文章。如果您喜欢它，您肯定会想更多地了解您可以对其进行的所有可能的改进以及可以使用它的应用程序。我强烈建议阅读开头提到的“ 搜索，优化和机器学习中的遗传算法 ”这本书。