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

2024-1-23

[[387899]]

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

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

  •  遗传算法是一种受进化启发的随机优化算法。
  •  如何在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”是定义单个候选解决方案中位数的超参数： 

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

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

 
 
 
    
  
  
  
  1. ...  
    2. 
  
  
  
  2. # enumerate generations  
    3. 
  
  
  
  3.  for gen in range(n_iter):  
    4. 
  
  
  
  4.  ... 
    5.

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

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

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

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

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

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

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

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

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

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

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

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

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

 
 
 
    
  
  
  
  1. # mutation operator  
    2. 
  
  
  
  2. def mutation(bitstring, r_mut):  
    3. 
  
  
  
  3.  for i in range(len(bitstring)):  
    4. 
  
  
  
  4.  # check for a mutation  
    5. 
  
  
  
  5.  if rand() < r_mut:  
    6. 
  
  
  
  6.  # flip the bit  
    7. 
  
  
  
  7.  bitstring[i] = 1 - bitstring[i] 
    8.

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

 
 
 
    
  
  
  
  1. # create the next generation  
    2. 
  
  
  
  2. children = list()  
    3. 
  
  
  
  3. for i in range(0, n_pop, 2):  
    4. 
  
  
  
  4.  # get selected parents in pairs  
    5. 
  
  
  
  5.  p1, p2 = selected[i], selected[i+1]  
    6. 
  
  
  
  6.  # crossover and mutation  
    7. 
  
  
  
  7.  for c in crossover(p1, p2, r_cross):  
    8. 
  
  
  
  8.  # mutation  
    9. 
  
  
  
  9.  mutation(c, r_mut)  
    10. 
  
  
  
  10.  # store for next generation  
    11. 
  
  
  
  11.  children.append(c) 
    12.

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

 
 
 
    
  
  
  
  1. # genetic algorithm  
    2. 
  
  
  
  2. def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut):  
    3. 
  
  
  
  3.  # initial population of random bitstring  
    4. 
  
  
  
  4.  pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)]  
    5. 
  
  
  
  5.  # keep track of best solution  
    6. 
  
  
  
  6.  best, best_eval = 0, objective(pop[0])  
    7. 
  
  
  
  7.  # enumerate generations  
    8. 
  
  
  
  8.  for gen in range(n_iter):  
    9. 
  
  
  
  9.   # evaluate all candidates in the population  
    10. 
  
  
  
  10.   scores = [objective(c) for c in pop]  
    11. 
  
  
  
  11.   # check for new best solution  
    12. 
  
  
  
  12.   for i in range(n_pop):  
    13. 
  
  
  
  13.    if scores[i] < best_eval:  
    14. 
  
  
  
  14.     best, best_eval = pop[i], scores[i]  
    15. 
  
  
  
  15.     print(">%d, new best f(%s) = %.3f" % (gen,  pop[i], scores[i]))  
    16. 
  
  
  
  16.   # select parents  
    17. 
  
  
  
  17.   selected = [selection(pop, scores) for _ in range(n_pop)]  
    18. 
  
  
  
  18.   # create the next generation  
    19. 
  
  
  
  19.   children = list()  
    20. 
  
  
  
  20.   for i in range(0, n_pop, 2):  
    21. 
  
  
  
  21.    # get selected parents in pairs  
    22. 
  
  
  
  22.    p1, p2 = selected[i], selected[i+1]  
    23. 
  
  
  
  23.    # crossover and mutation  
    24. 
  
  
  
  24.    for c in crossover(p1, p2, r_cross):  
    25. 
  
  
  
  25.     # mutation  
    26. 
  
  
  
  26.     mutation(c, r_mut)  
    27. 
  
  
  
  27.     # store for next generation  
    28. 
  
  
  
  28.     children.append(c)  
    29. 
  
  
  
  29.   # replace population  
    30. 
  
  
  
  30.   pop = children  
    31. 
  
  
  
  31.  return [best, best_eval] 
    32.

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

OneMax的遗传算法

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

 
 
 
    
  
  
  
  1. # objective function  
    2. 
  
  
  
  2. def onemax(x):  
    3. 
  
  
  
  3.  return -sum(x) 
    4.

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

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

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

 
 
 
    
  
  
  
  1. # define the total iterations  
    2. 
  
  
  
  2. n_iter = 100  
    3. 
  
  
  
  3. # bits  
    4. 
  
  
  
  4. n_bits = 20  
    5. 
  
  
  
  5. # define the population size  
    6. 
  
  
  
  6. n_pop = 100  
    7. 
  
  
  
  7. # crossover rate  
    8. 
  
  
  
  8. r_cross = 0.9  
    9. 
  
  
  
  9. # mutation rate  
    10. 
  
  
  
  10. r_mut = 1.0 / float(n_bits) 
    11.

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

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

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

 
 
 
    
  
  
  
  1. # genetic algorithm search of the one max optimization problem  
    2. 
  
  
  
  2. from numpy.random import randint  
    3. 
  
  
  
  3. from numpy.random import rand   
    4. 
  
  
  
  4. # objective function  
    5. 
  
  
  
  5. def onemax(x):  
    6. 
  
  
  
  6.  return -sum(x)   
    7. 
  
  
  
  7. # tournament selection  
    8. 
  
  
  
  8. def selection(pop, scores, k=3):  
    9. 
  
  
  
  9.  # first random selection  
    10. 
  
  
  
  10.  selection_ix = randint(len(pop))  
    11. 
  
  
  
  11.  for ix in randint(0, len(pop), k-1):  
    12. 
  
  
  
  12.   # check if better (e.g. perform a tournament)  
    13. 
  
  
  
  13.   if scores[ix] < scores[selection_ix]:  
    14. 
  
  
  
  14.    selection_ix = ix  
    15. 
  
  
  
  15.  return pop[selection_ix]  
    16. 
  
  
  
  16. # crossover two parents to create two children  
    17. 
  
  
  
  17. def crossover(p1, p2, r_cross):  
    18. 
  
  
  
  18.  # children are copies of parents by default  
    19. 
  
  
  
  19.  c1, c2 = p1.copy(), p2.copy()  
    20. 
  
  
  
  20.  # check for recombination  
    21. 
  
  
  
  21.  if rand() < r_cross:  
    22. 
  
  
  
  22.   # select crossover point that is not on the end of the string  
    23. 
  
  
  
  23.   pt = randint(1, len(p1)-2)  
    24. 
  
  
  
  24.   # perform crossover  
    25. 
  
  
  
  25.   c1 = p1[:pt] + p2[pt:]  
    26. 
  
  
  
  26.   c2 = p2[:pt] + p1[pt:]  
    27. 
  
  
  
  27.  return [c1, c2]  
    28. 
  
  
  
  28. # mutation operator  
    29. 
  
  
  
  29. def mutation(bitstring, r_mut):  
    30. 
  
  
  
  30.  for i in range(len(bitstring)):  
    31. 
  
  
  
  31.   # check for a mutation  
    32. 
  
  
  
  32.   if rand() < r_mut:  
    33. 
  
  
  
  33.    # flip the bit  
    34. 
  
  
  
  34.    bitstring[i] = 1 - bitstring[i]  
    35. 
  
  
  
  35. # genetic algorithm  
    36. 
  
  
  
  36. def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut):  
    37. 
  
  
  
  37.  # initial population of random bitstring  
    38. 
  
  
  
  38.  pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)]  
    39. 
  
  
  
  39.  # keep track of best solution  
    40. 
  
  
  
  40.  best, best_eval = 0, objective(pop[0])  
    41. 
  
  
  
  41.  # enumerate generations  
    42. 
  
  
  
  42.  for gen in range(n_iter):  
    43. 
  
  
  
  43.   # evaluate all candidates in the population  
    44. 
  
  
  
  44.   scores = [objective(c) for c in pop]  
    45. 
  
  
  
  45.   # check for new best solution  
    46. 
  
  
  
  46.   for i in range(n_pop):  
    47. 
  
  
  
  47.    if scores[i] < best_eval:  
    48. 
  
  
  
  48.     best, best_eval = pop[i], scores[i]  
    49. 
  
  
  
  49.     print(">%d, new best f(%s) = %.3f" % (gen,  pop[i], scores[i]))  
    50. 
  
  
  
  50.   # select parents  
    51. 
  
  
  
  51.   selected = [selection(pop, scores) for _ in range(n_pop)]  
    52. 
  
  
  
  52.   # create the next generation  
    53. 
  
  
  
  53.   children = list()  
    54. 
  
  
  
  54.   for i in range(0, n_pop, 2):  
    55. 
  
  
  
  55.    # get selected parents in pairs  
    56. 
  
  
  
  56.    p1, p2 = selected[i], selected[i+1]  
    57. 
  
  
  
  57.    # crossover and mutation  
    58. 
  
  
  
  58.    for c in crossover(p1, p2, r_cross):  
    59. 
  
  
  
  59.     # mutation  
    60. 
  
  
  
  60.     mutation(c, r_mut)  
    61. 
  
  
  
  61.     # store for next generation  
    62. 
  
  
  
  62.     children.append(c)  
    63. 
  
  
  
  63.   # replace population  
    64. 
  
  
  
  64.   pop = children  
    65. 
  
  
  
  65.  return [best, best_eval]  
    66. 
  
  
  
  66. # define the total iterations  
    67. 
  
  
  
  67. n_iter = 100  
    68. 
  
  
  
  68. # bits  
    69. 
  
  
  
  69. n_bits = 20  
    70. 
  
  
  
  70. # define the population size  
    71. 
  
  
  
  71. n_pop = 100  
    72. 
  
  
  
  72. # crossover rate  
    73. 
  
  
  
  73. r_cross = 0.9  
    74. 
  
  
  
  74. # mutation rate  
    75. 
  
  
  
  75. r_mut = 1.0 / float(n_bits)  
    76. 
  
  
  
  76. # perform the genetic algorithm search  
    77. 
  
  
  
  77. best, score = genetic_algorithm(onemax, n_bits, n_iter, n_pop, r_cross, r_mut)  
    78. 
  
  
  
  78. print('Done!')  
    79. 
  
  
  
  79. print('f(%s) = %f' % (best, score)) 
    80.

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

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

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

 
 
 
    
  
  
  
  1. >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  
    2. 
  
  
  
  2. >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  
    3. 
  
  
  
  3. >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  
    4. 
  
  
  
  4. >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  
    5. 
  
  
  
  5. >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  
    6. 
  
  
  
  6. >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  
    7. 
  
  
  
  7. Done!  
    8. 
  
  
  
  8. f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) = -20.000000 
    9.

连续函数优化的遗传算法

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

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

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

 
 
 
    
  
  
  
  1. # define range for input  
    2. 
  
  
  
  2. bounds = [[-5.0, 5.0], [-5.0, 5.0]] 
    3.

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

 
 
 
    
  
  
  
  1. # bits per variable  
    2. 
  
  
  
  2. n_bits = 16 
    3.

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

 
 
 
    
  
  
  
  1. # mutation rate  
    2. 
  
  
  
  2. r_mut = 1.0 / (float(n_bits) * len(bounds)) 
    3.

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

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

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

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

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

 
 
 
    
  
  
  
  1. # decode bitstring to numbers  
    2. 
  
  
  
  2. def decode(bounds, n_bits, bitstring):  
    3. 
  
  
  
  3.  decoded = list()  
    4. 
  
  
  
  4.  largest = 2**n_bits  
    5. 
  
  
  
  5.  for i in range(len(bounds)):  
    6. 
  
  
  
  6.   # extract the substring  
    7. 
  
  
  
  7.   start, end = i * n_bits, (i * n_bits)+n_bits  
    8. 
  
  
  
  8.   substring = bitstring[start:end]  
    9. 
  
  
  
  9.   # convert bitstring to a string of chars  
    10. 
  
  
  
  10.   chars = ''.join([str(s) for s in substring])  
    11. 
  
  
  
  11.   # convert string to integer  
    12. 
  
  
  
  12.   intinteger = int(chars, 2)  
    13. 
  
  
  
  13.   # scale integer to desired range  
    14. 
  
  
  
  14.   value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0])  
    15. 
  
  
  
  15.   # store  
    16. 
  
  
  
  16.   decoded.append(value)  
    17. 
  
  
  
  17.  return decoded 
    18.

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

 
 
 
    
  
  
  
  1. # decode population  
    2. 
  
  
  
  2. decoded = [decode(bounds, n_bits, p) for p in pop]  
    3. 
  
  
  
  3. # evaluate all candidates in the population  
    4. 
  
  
  
  4. scores = [objective(d) for d in decoded] 
    5.

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

 
 
 
    
  
  
  
  1. # genetic algorithm search for continuous function optimization  
    2. 
  
  
  
  2. from numpy.random import randint  
    3. 
  
  
  
  3. from numpy.random import rand   
    4. 
  
  
  
  4. # objective function  
    5. 
  
  
  
  5. def objective(x):  
    6. 
  
  
  
  6.  return x[0]**2.0 + x[1]**2.0   
    7. 
  
  
  
  7. # decode bitstring to numbers  
    8. 
  
  
  
  8. def decode(bounds, n_bits, bitstring):  
    9. 
  
  
  
  9.  decoded = list()  
    10. 
  
  
  
  10.  largest = 2**n_bits  
    11. 
  
  
  
  11.  for i in range(len(bounds)):  
    12. 
  
  
  
  12.   # extract the substring  
    13. 
  
  
  
  13.   start, end = i * n_bits, (i * n_bits)+n_bits  
    14. 
  
  
  
  14.   substring = bitstring[start:end]  
    15. 
  
  
  
  15.   # convert bitstring to a string of chars  
    16. 
  
  
  
  16.   chars = ''.join([str(s) for s in substring])  
    17. 
  
  
  
  17.   # convert string to integer  
    18. 
  
  
  
  18.   intinteger = int(chars, 2)  
    19. 
  
  
  
  19.   # scale integer to desired range  
    20. 
  
  
  
  20.   value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0])  
    21. 
  
  
  
  21.   # store 
    22. 
  
  
  
  22.   decoded.append(value)  
    23. 
  
  
  
  23.  return decoded  
    24. 
  
  
  
  24. # tournament selection  
    25. 
  
  
  
  25. def selection(pop, scores, k=3):  
    26. 
  
  
  
  26.  # first random selection  
    27. 
  
  
  
  27.  selection_ix = randint(len(pop))  
    28. 
  
  
  
  28.  for ix in randint(0, len(pop), k-1):  
    29. 
  
  
  
  29.   # check if better (e.g. perform a tournament)  
    30. 
  
  
  
  30.   if scores[ix] < scores[selection_ix]:  
    31. 
  
  
  
  31.    selection_ix = ix  
    32. 
  
  
  
  32.  return pop[selection_ix]  
    33. 
  
  
  
  33. # crossover two parents to create two children  
    34. 
  
  
  
  34. def crossover(p1, p2, r_cross):  
    35. 
  
  
  
  35.  # children are copies of parents by default  
    36. 
  
  
  
  36.  c1, c2 = p1.copy(), p2.copy()  
    37. 
  
  
  
  37.  # check for recombination  
    38. 
  
  
  
  38.  if rand() < r_cross:  
    39. 
  
  
  
  39.   # select crossover point that is not on the end of the string  
    40. 
  
  
  
  40.   pt = randint(1, len(p1)-2)  
    41. 
  
  
  
  41.   # perform crossover  
    42. 
  
  
  
  42.   c1 = p1[:pt] + p2[pt:]  
    43. 
  
  
  
  43.   c2 = p2[:pt] + p1[pt:]  
    44. 
  
  
  
  44.  return [c1, c2]   
    45. 
  
  
  
  45. # mutation operator  
    46. 
  
  
  
  46. def mutation(bitstring, r_mut):  
    47. 
  
  
  
  47.  for i in range(len(bitstring)):  
    48. 
  
  
  
  48.   # check for a mutation  
    49. 
  
  
  
  49.   if rand() < r_mut:  
    50. 
  
  
  
  50.    # flip the bit  
    51. 
  
  
  
  51.    bitstring[i] = 1 - bitstring[i]  
    52. 
  
  
  
  52. # genetic algorithm  
    53. 
  
  
  
  53. def genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut):  
    54. 
  
  
  
  54.  # initial population of random bitstring  
    55. 
  
  
  
  55.  pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)]  
    56. 
  
  
  
  56.  # keep track of best solution  
    57. 
  
  
  
  57.  best, best_eval = 0, objective(pop[0])  
    58. 
  
  
  
  58.  # enumerate generations  
    59. 
  
  
  
  59.  for gen in range(n_iter):  
    60. 
  
  
  
  60.   # decode population  
    61. 
  
  
  
  61.   decoded = [decode(bounds, n_bits, p) for p in pop]  
    62. 
  
  
  
  62.   # evaluate all candidates in the population  
    63. 
  
  
  
  63.   scores = [objective(d) for d in decoded]  
    64. 
  
  
  
  64.   # check for new best solution  
    65. 
  
  
  
  65.   for i in range(n_pop):  
    66. 
  
  
  
  66.    if scores[i] < best_eval:  
    67. 
  
  
  
  67.     best, best_eval = pop[i], scores[i]  
    68. 
  
  
  
  68.     print(">%d, new best f(%s) = %f" % (gen,  decoded[i], scores[i]))  
    69. 
  
  
  
  69.   # select parents  
    70. 
  
  
  
  70.   selected = [selection(pop, scores) for _ in range(n_pop)]  
    71. 
  
  
  
  71.   # create the next generation  
    72. 
  
  
  
  72.   children = list() 
    73. 
  
  
  
  73.   for i in range(0, n_pop, 2):  
    74. 
  
  
  
  74.    # get selected parents in pairs  
    75. 
  
  
  
  75.    p1, p2 = selected[i], selected[i+1]  
    76. 
  
  
  
  76.    # crossover and mutation  
    77. 
  
  
  
  77.    for c in crossover(p1, p2, r_cross):  
    78. 
  
  
  
  78.     # mutation  
    79. 
  
  
  
  79.     mutation(c, r_mut)  
    80. 
  
  
  
  80.     # store for next generation  
    81. 
  
  
  
  81.     children.append(c)  
    82. 
  
  
  
  82.   # replace population  
    83. 
  
  
  
  83.   pop = children  
    84. 
  
  
  
  84.  return [best, best_eval]  
    85. 
  
  
  
  85. # define range for input  
    86. 
  
  
  
  86. bounds = [[-5.0, 5.0], [-5.0, 5.0]]  
    87. 
  
  
  
  87. # define the total iterations  
    88. 
  
  
  
  88. n_iter = 100  
    89. 
  
  
  
  89. # bits per variable  
    90. 
  
  
  
  90. n_bits = 16  
    91. 
  
  
  
  91. # define the population size  
    92. 
  
  
  
  92. n_pop = 100  
    93. 
  
  
  
  93. # crossover rate  
    94. 
  
  
  
  94. r_cross = 0.9  
    95. 
  
  
  
  95. # mutation rate  
    96. 
  
  
  
  96. r_mut = 1.0 / (float(n_bits) * len(bounds))  
    97. 
  
  
  
  97. # perform the genetic algorithm search  
    98. 
  
  
  
  98. best, score = genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut)  
    99. 
  
  
  
  99. print('Done!')  
    100. 
  
  
  
  100. decodedecoded = decode(bounds, n_bits, best)  
    101. 
  
  
  
  101. print('f(%s) = %f' % (decoded, score)) 
    102.

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

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

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

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

 

版权声明：
作者：后浪云
链接：https://www.idc.net/help/338083/
文章版权归作者所有，未经允许请勿转载。
THE END
Copyright © 2025 后浪云 网站地图