用 Python 从零开始实现简单遗传算法-轻识

遗传算法是一种随机全局优化算法。连同人工神经网络，它可能是最流行和广为人知的生物学启发算法之一。该算法是一种进化算法，它通过自然选择，具有二进制表示形式和基于遗传重组和遗传突变的简单算子，来执行受进化生物学理论启发的优化过程。

在本教程中，您将发现遗传算法优化算法。完成本教程后，您将知道：

遗传算法是一种受进化启发的随机优化算法。
如何在Python中从头开始实现遗传算法。
如何将遗传算法应用于连续目标函数。

教程概述

本教程分为四个部分。他们是：

遗传算法
从零开始的遗传算法
OneMax的遗传算法
连续函数优化的遗传算法

遗传算法

遗传算法是一种随机全局搜索优化算法。它受到自然选择进化生物学理论的启发。具体来说，是将对遗传学的理解与理论相结合的新综合方法。

该算法使用遗传表示（位串），适应度（功能评估），基因重组（位串交叉）和突变（翻转位）的类似物。该算法的工作原理是首先创建固定大小的随机位串。重复算法的主循环固定次数的迭代，或者直到在给定迭代次数的最佳解决方案中看不到进一步的改善为止。该算法的一次迭代就像是进化的一代。

首先，使用目标函数评估总体位串（候选解决方案）。每个候选解决方案的目标函数评估被视为解决方案的适用性，可以将其最小化或最大化。然后，根据他们的健康状况选择父母。给定的候选解决方案可以用作父级零次或多次。一种简单有效的选择方法包括从总体中随机抽取k个候选者，并从适应性最好的组中选择成员。这就是所谓的锦标赛选择，其中k是一个超参数，并设置为诸如3的值。这种简单的方法模拟了成本更高的适应度成比例的选择方案。

父母被用作生成下一代候选点的基础，并且人口中的每个职位都需要一个父母。

然后将父母配对，并用来创建两个孩子。使用交叉算子执行重组。这涉及在位串上选择一个随机的分割点，然后创建一个子对象，该子对象的位从第一个父级到分割点直至从第二个父级到字符串的末尾。然后，为第二个孩子倒转此过程。

例如，两个父母：

parent1 = 00000

parent2 = 11111

可能会导致两个交叉孩子：

子1 = 00011

孩童2 = 11100

这称为单点交叉，并且操作员还有许多其他变体。

交叉概率是对每对父母概率应用的，这意味着在某些情况下，父母的副本将作为孩子而不是重组算子。交叉由设置为较大值（例如80％或90％）的超参数控制。变异涉及在已创建的子候选解决方案中翻转位。通常，将突变率设置为1 / L，其中L是位串的长度。

例如，如果问题使用具有20位的位串，则良好的默认突变率将是（1/20）= 0.05或5％的概率。

这定义了简单的遗传算法过程。这是一个很大的研究领域，并且对该算法进行了许多扩展。

现在我们已经熟悉了简单的遗传算法过程，下面让我们看一下如何从头开始实现它。

从零开始的遗传算法

在本节中，我们将开发遗传算法的实现。第一步是创建随机位串。我们可以使用布尔值True和False，字符串值“ 0”和“1”，或者整数值0和1。在这种情况下，我们将使用整数值。我们可以使用randint（）函数生成一个范围内的整数值数组，并且可以将范围指定为从0开始且小于2的值，例如 0或1。为了简化起见，我们还将候选解决方案表示为列表而不是NumPy数组。可以如下创建初始的随机位串填充，其中“n_pop”是控制填充大小的超参数，“n_bits”是定义单个候选解决方案中位数的超参数：

# initial population of random bitstring
pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)]

接下来，我们可以枚举固定数量的算法迭代，在这种情况下，该迭代由名为“ n_iter”的超参数控制。

...
# enumerate generations
 for gen in range(n_iter):
 ...

算法迭代的第一步是评估所有候选解。

我们将使用一个名为Objective（）的函数作为通用目标函数，并对其进行调用以获取适合度得分，我们将其最小化。

# evaluate all candidates in the population
scores = [objective(c) for c in pop]

然后，我们可以选择将用于创建子代的父代。

锦标赛选择过程可以实现为一种函数，该函数可以获取总体并返回一个选定的父级。使用默认参数将k值固定为3，但是您可以根据需要尝试使用不同的值。

# tournament selection
def selection(pop, scores, k=3):
 # first random selection
 selection_ix = randint(len(pop))
 for ix in randint(0, len(pop), k-1):
 # check if better (e.g. perform a tournament)
 if scores[ix] < scores[selection_ix]:
 selection_ix = ix
 return pop[selection_ix]

然后，我们可以为总体中的每个位置调用一次此函数，以创建父母列表。

# select parents
selected = [selection(pop, scores) for _ in range(n_pop)]

然后，我们可以创建下一代。

这首先需要执行交叉的功能。此功能将占用两个父级和交叉率。交叉率是一个超参数，它确定是否执行交叉，如果不进行交叉，则将父级复制到下一代。这是一个概率，通常具有接近1.0的较大值。

下面的crossover（）函数使用范围为[0,1]的随机数来实现交叉以确定是否执行了交叉，然后如果要进行交叉则选择有效的分割点。

# crossover two parents to create two children
def crossover(p1, p2, r_cross):
 # children are copies of parents by default
 c1, c2 = p1.copy(), p2.copy()
 # check for recombination
 if rand() < r_cross:
 # select crossover point that is not on the end of the string
 pt = randint(1, len(p1)-2)
 # perform crossover
 c1 = p1[:pt] + p2[pt:]
 c2 = p2[:pt] + p1[pt:]
 return [c1, c2]

我们还需要执行突变的功能。该过程简单地以“ r_mut”超参数控制的低概率翻转位。

# mutation operator
def mutation(bitstring, r_mut):
 for i in range(len(bitstring)):
 # check for a mutation
 if rand() < r_mut:
 # flip the bit
 bitstring[i] = 1 - bitstring[i]

然后，我们可以遍历父级列表并创建要用作下一代的子级列表，根据需要调用交叉和变异函数。

# create the next generation
children = list()
for i in range(0, n_pop, 2):
 # get selected parents in pairs
 p1, p2 = selected[i], selected[i+1]
 # crossover and mutation
 for c in crossover(p1, p2, r_cross):
 # mutation
 mutation(c, r_mut)
 # store for next generation
 children.append(c)

我们可以将所有这些结合到一个名为generic_algorithm（）的函数中，该函数采用目标函数的名称和搜索的超参数，并返回在搜索过程中找到的最佳解决方案。

# genetic algorithm
def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut):
 # initial population of random bitstring
 pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)]
 # keep track of best solution
 best, best_eval = 0, objective(pop[0])
 # enumerate generations
 for gen in range(n_iter):
  # evaluate all candidates in the population
  scores = [objective(c) for c in pop]
  # check for new best solution
  for i in range(n_pop):
   if scores[i] < best_eval:
    best, best_eval = pop[i], scores[i]
    print(">%d, new best f(%s) = %.3f" % (gen,  pop[i], scores[i]))
  # select parents
  selected = [selection(pop, scores) for _ in range(n_pop)]
  # create the next generation
  children = list()
  for i in range(0, n_pop, 2):
   # get selected parents in pairs
   p1, p2 = selected[i], selected[i+1]
   # crossover and mutation
   for c in crossover(p1, p2, r_cross):
    # mutation
    mutation(c, r_mut)
    # store for next generation
    children.append(c)
  # replace population
  pop = children
 return [best, best_eval]

现在，我们已经开发了遗传算法的实现，让我们探讨如何将其应用于目标函数。

OneMax的遗传算法

在本节中，我们将遗传算法应用于基于二进制字符串的优化问题。该问题称为OneMax，并根据字符串中的1的个数评估二进制字符串。例如，长度为20位的位串对于全1的字符串的得分为20。假设我们已经实现了遗传算法以最小化目标函数，则可以在此评估中添加负号，以便大的正值变为大的负值。下面的onemax（）函数实现了此功能，并将整数值的位串作为输入，并返回值的负和。

# objective function
def onemax(x):
 return -sum(x)

接下来，我们可以配置搜索。

搜索将运行100次迭代，我们将在候选解决方案中使用20位，这意味着最佳适应度为-20.0。

人口总数将为100，我们将使用90％的交叉率和5％的突变率。经过一番尝试和错误后，才选择此配置。

# define the total iterations
n_iter = 100
# bits
n_bits = 20
# define the population size
n_pop = 100
# crossover rate
r_cross = 0.9
# mutation rate
r_mut = 1.0 / float(n_bits)

然后可以调用搜索并报告最佳结果。

# perform the genetic algorithm search
best, score = genetic_algorithm(onemax, n_bits, n_iter, n_pop, r_cross, r_mut)
print('Done!')
print('f(%s) = %f' % (best, score))

结合在一起，下面列出了将遗传算法应用于OneMax目标函数的完整示例。

# genetic algorithm search of the one max optimization problem
from numpy.random import randint
from numpy.random import rand
 
# objective function
def onemax(x):
 return -sum(x)
 
# tournament selection
def selection(pop, scores, k=3):
 # first random selection
 selection_ix = randint(len(pop))
 for ix in randint(0, len(pop), k-1):
  # check if better (e.g. perform a tournament)
  if scores[ix] < scores[selection_ix]:
   selection_ix = ix
 return pop[selection_ix]
 
# crossover two parents to create two children
def crossover(p1, p2, r_cross):
 # children are copies of parents by default
 c1, c2 = p1.copy(), p2.copy()
 # check for recombination
 if rand() < r_cross:
  # select crossover point that is not on the end of the string
  pt = randint(1, len(p1)-2)
  # perform crossover
  c1 = p1[:pt] + p2[pt:]
  c2 = p2[:pt] + p1[pt:]
 return [c1, c2]
 
# mutation operator
def mutation(bitstring, r_mut):
 for i in range(len(bitstring)):
  # check for a mutation
  if rand() < r_mut:
   # flip the bit
   bitstring[i] = 1 - bitstring[i]
 
# genetic algorithm
def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut):
 # initial population of random bitstring
 pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)]
 # keep track of best solution
 best, best_eval = 0, objective(pop[0])
 # enumerate generations
 for gen in range(n_iter):
  # evaluate all candidates in the population
  scores = [objective(c) for c in pop]
  # check for new best solution
  for i in range(n_pop):
   if scores[i] < best_eval:
    best, best_eval = pop[i], scores[i]
    print(">%d, new best f(%s) = %.3f" % (gen,  pop[i], scores[i]))
  # select parents
  selected = [selection(pop, scores) for _ in range(n_pop)]
  # create the next generation
  children = list()
  for i in range(0, n_pop, 2):
   # get selected parents in pairs
   p1, p2 = selected[i], selected[i+1]
   # crossover and mutation
   for c in crossover(p1, p2, r_cross):
    # mutation
    mutation(c, r_mut)
    # store for next generation
    children.append(c)
  # replace population
  pop = children
 return [best, best_eval]
 
# define the total iterations
n_iter = 100
# bits
n_bits = 20
# define the population size
n_pop = 100
# crossover rate
r_cross = 0.9
# mutation rate
r_mut = 1.0 / float(n_bits)
# perform the genetic algorithm search
best, score = genetic_algorithm(onemax, n_bits, n_iter, n_pop, r_cross, r_mut)
print('Done!')
print('f(%s) = %f' % (best, score))

运行示例将报告沿途发现的最佳结果，然后在搜索结束时给出最终的最佳解决方案，我们希望这是最佳解决方案。

注意：由于算法或评估程序的随机性，或者数值精度的差异，您的结果可能会有所不同。考虑运行该示例几次并比较平均结果。

在这种情况下，我们可以看到搜索在大约八代之后找到了最佳解决方案。

>0, new best f([1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]) = -14.000
>0, new best f([1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0]) = -15.000
>1, new best f([1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]) = -16.000
>2, new best f([0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]) = -17.000
>2, new best f([1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) = -19.000
>8, new best f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) = -20.000
Done!
f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) = -20.000000

连续函数优化的遗传算法

优化OneMax功能不是很有趣。我们更可能希望优化连续函数。例如，我们可以定义x ^ 2最小化函数，该函数接受输入变量并在f（0，0）= 0.0时具有最优值。

# objective function
def objective(x):
 return x[0]**2.0 + x[1]**2.0

我们可以使用遗传算法最小化此功能。首先，我们必须定义每个输入变量的界限。

# define range for input
bounds = [[-5.0, 5.0], [-5.0, 5.0]]

我们将“ n_bits”超参数作为目标函数每个输入变量的位数，并将其设置为16位。

# bits per variable
n_bits = 16

这意味着在给定两个输入变量的情况下，我们的实际位字符串将具有（16 * 2）= 32位。

# mutation rate
r_mut = 1.0 / (float(n_bits) * len(bounds))

接下来，我们需要确保初始填充会创建足够大的随机位串。

# initial population of random bitstring
pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)]

最后，在使用目标函数评估每个位串之前，我们需要将这些位串解码为数字。

我们可以通过首先将每个子字符串解码为整数，然后将整数缩放到所需范围来实现此目的。这将提供一个范围内的值向量，然后可将其提供给目标函数进行评估。

下面的decode（）函数以函数的界限，每个变量的位数和一个位串作为输入来实现此目的，并返回已解码实数值的列表。

# decode bitstring to numbers
def decode(bounds, n_bits, bitstring):
 decoded = list()
 largest = 2**n_bits
 for i in range(len(bounds)):
  # extract the substring
  start, end = i * n_bits, (i * n_bits)+n_bits
  substring = bitstring[start:end]
  # convert bitstring to a string of chars
  chars = ''.join([str(s) for s in substring])
  # convert string to integer
  integer = int(chars, 2)
  # scale integer to desired range
  value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0])
  # store
  decoded.append(value)
 return decoded

然后，我们可以在算法循环的开始处调用它来解码总体，然后评估总体的解码版本。

# decode population
decoded = [decode(bounds, n_bits, p) for p in pop]
# evaluate all candidates in the population
scores = [objective(d) for d in decoded]

结合在一起，下面列出了用于连续函数优化的遗传算法的完整示例。

# genetic algorithm search for continuous function optimization
from numpy.random import randint
from numpy.random import rand
 
# objective function
def objective(x):
 return x[0]**2.0 + x[1]**2.0
 
# decode bitstring to numbers
def decode(bounds, n_bits, bitstring):
 decoded = list()
 largest = 2**n_bits
 for i in range(len(bounds)):
  # extract the substring
  start, end = i * n_bits, (i * n_bits)+n_bits
  substring = bitstring[start:end]
  # convert bitstring to a string of chars
  chars = ''.join([str(s) for s in substring])
  # convert string to integer
  integer = int(chars, 2)
  # scale integer to desired range
  value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0])
  # store
  decoded.append(value)
 return decoded
 
# tournament selection
def selection(pop, scores, k=3):
 # first random selection
 selection_ix = randint(len(pop))
 for ix in randint(0, len(pop), k-1):
  # check if better (e.g. perform a tournament)
  if scores[ix] < scores[selection_ix]:
   selection_ix = ix
 return pop[selection_ix]
 
# crossover two parents to create two children
def crossover(p1, p2, r_cross):
 # children are copies of parents by default
 c1, c2 = p1.copy(), p2.copy()
 # check for recombination
 if rand() < r_cross:
  # select crossover point that is not on the end of the string
  pt = randint(1, len(p1)-2)
  # perform crossover
  c1 = p1[:pt] + p2[pt:]
  c2 = p2[:pt] + p1[pt:]
 return [c1, c2]
 
# mutation operator
def mutation(bitstring, r_mut):
 for i in range(len(bitstring)):
  # check for a mutation
  if rand() < r_mut:
   # flip the bit
   bitstring[i] = 1 - bitstring[i]
 
# genetic algorithm
def genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut):
 # initial population of random bitstring
 pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)]
 # keep track of best solution
 best, best_eval = 0, objective(pop[0])
 # enumerate generations
 for gen in range(n_iter):
  # decode population
  decoded = [decode(bounds, n_bits, p) for p in pop]
  # evaluate all candidates in the population
  scores = [objective(d) for d in decoded]
  # check for new best solution
  for i in range(n_pop):
   if scores[i] < best_eval:
    best, best_eval = pop[i], scores[i]
    print(">%d, new best f(%s) = %f" % (gen,  decoded[i], scores[i]))
  # select parents
  selected = [selection(pop, scores) for _ in range(n_pop)]
  # create the next generation
  children = list()
  for i in range(0, n_pop, 2):
   # get selected parents in pairs
   p1, p2 = selected[i], selected[i+1]
   # crossover and mutation
   for c in crossover(p1, p2, r_cross):
    # mutation
    mutation(c, r_mut)
    # store for next generation
    children.append(c)
  # replace population
  pop = children
 return [best, best_eval]
 
# define range for input
bounds = [[-5.0, 5.0], [-5.0, 5.0]]
# define the total iterations
n_iter = 100
# bits per variable
n_bits = 16
# define the population size
n_pop = 100
# crossover rate
r_cross = 0.9
# mutation rate
r_mut = 1.0 / (float(n_bits) * len(bounds))
# perform the genetic algorithm search
best, score = genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut)
print('Done!')
decoded = decode(bounds, n_bits, best)
print('f(%s) = %f' % (decoded, score))

运行示例将报告最佳解码结果以及运行结束时的最佳解码解决方案。

注意：由于算法或评估程序的随机性，或者数值精度的差异，您的结果可能会有所不同。考虑运行该示例几次并比较平均结果。

在这种情况下，我们可以看到该算法发现了一个非常接近f（0.0，0.0）= 0.0的输入。

>0, new best f([-0.785064697265625, -0.807647705078125]) = 1.268621
>0, new best f([0.385894775390625, 0.342864990234375]) = 0.266471
>1, new best f([-0.342559814453125, -0.1068115234375]) = 0.128756
>2, new best f([-0.038909912109375, 0.30242919921875]) = 0.092977
>2, new best f([0.145721435546875, 0.1849365234375]) = 0.055436
>3, new best f([0.14404296875, -0.029754638671875]) = 0.021634
>5, new best f([0.066680908203125, 0.096435546875]) = 0.013746
>5, new best f([-0.036468505859375, -0.10711669921875]) = 0.012804
>6, new best f([-0.038909912109375, -0.099639892578125]) = 0.011442
>7, new best f([-0.033111572265625, 0.09674072265625]) = 0.010455
>7, new best f([-0.036468505859375, 0.05584716796875]) = 0.004449
>10, new best f([0.058746337890625, 0.008087158203125]) = 0.003517
>10, new best f([-0.031585693359375, 0.008087158203125]) = 0.001063
>12, new best f([0.022125244140625, 0.008087158203125]) = 0.000555
>13, new best f([0.022125244140625, 0.00701904296875]) = 0.000539
>13, new best f([-0.013885498046875, 0.008087158203125]) = 0.000258
>16, new best f([-0.011444091796875, 0.00518798828125]) = 0.000158
>17, new best f([-0.0115966796875, 0.00091552734375]) = 0.000135
>17, new best f([-0.004730224609375, 0.00335693359375]) = 0.000034
>20, new best f([-0.004425048828125, 0.00274658203125]) = 0.000027
>21, new best f([-0.002288818359375, 0.00091552734375]) = 0.000006
>22, new best f([-0.001983642578125, 0.00091552734375]) = 0.000005
>22, new best f([-0.001983642578125, 0.0006103515625]) = 0.000004
>24, new best f([-0.001373291015625, 0.001068115234375]) = 0.000003
>25, new best f([-0.001373291015625, 0.00091552734375]) = 0.000003
>26, new best f([-0.001373291015625, 0.0006103515625]) = 0.000002
>27, new best f([-0.001068115234375, 0.0006103515625]) = 0.000002
>29, new best f([-0.000152587890625, 0.00091552734375]) = 0.000001
>33, new best f([-0.0006103515625, 0.0]) = 0.000000
>34, new best f([-0.000152587890625, 0.00030517578125]) = 0.000000
>43, new best f([-0.00030517578125, 0.0]) = 0.000000
>60, new best f([-0.000152587890625, 0.000152587890625]) = 0.000000
>65, new best f([-0.000152587890625, 0.0]) = 0.000000
Done!
f([-0.000152587890625, 0.0]) = 0.000000

作者：沂水寒城，CSDN博客专家，个人研究方向：机器学习、深度学习、NLP、CV

Blog: http://yishuihancheng.blog.csdn.net

赞赏作者

更多阅读

2020 年最佳流行 Python 库 Top 10

2020 Python中文社区热门文章 Top 10

5分钟快速掌握 Python 定时任务框架

特别推荐

点击下方阅读原文加入社区会员