遗传算法是一种随机全局优化算法。
它可能与人工神经网络一样，是最受欢迎和广为人知的受生物学启发的算法之一。
该算法是一种进化算法，其优化过程受到自然选择生物进化理论的启发，具有二进制表示和基于遗传重组和遗传突变的简单算子。
在本教程中，您将了解遗传算法优化算法。
完成本教程后，您将了解：
- 遗传算法是一种受进化启发的随机优化算法。
- 如何在 Python 中从头实现遗传算法。
- 如何将遗传算法应用于连续目标函数。
通过我新书 《机器学习优化》 开启您的项目，其中包含分步教程和所有示例的Python源代码文件。
让我们开始吧。
Python 中从零开始的简单遗传算法
照片由 Magharebia 提供，保留部分权利。
教程概述
本教程分为四个部分；它们是
- 遗传算法
- 遗传算法从零开始
- OneMax 的遗传算法
- 连续函数优化的遗传算法
遗传算法
遗传算法是一种随机全局搜索优化算法。
它受到自然选择生物进化理论的启发。具体来说，是结合了遗传学理解和该理论的新综合。
遗传算法（算法 9.4）借鉴了生物进化的灵感，其中更适应的个体更有可能将其基因传递给下一代。
— 第 148 页，《优化算法》，2019 年。
该算法使用遗传表示（位串）、适应度（函数评估）、遗传重组（位串交叉）和突变（位翻转）的类似物。
该算法首先创建一个固定大小的随机位串种群。算法的主循环重复固定次数的迭代，或者直到最佳解决方案在给定次数的迭代中没有进一步改进。
算法的一次迭代就像一个进化代。
首先，使用目标函数评估位串种群（候选解）。每个候选解的目标函数评估被视为解决方案的适应度，这可以被最小化或最大化。
然后，根据适应度选择父代。给定的候选解可以被用作父代零次或多次。一种简单有效的选择方法是随机从种群中抽取k个候选解，然后从该组中选择具有最佳适应度的成员。这称为锦标赛选择，其中k是一个超参数，设置为 3 等值。这种简单的方法模拟了一种成本更高的适应度比例选择方案。
在锦标赛选择中，每个父代是种群中随机选择的 k 个染色体中最适应的那个。
— 第 151 页，《优化算法》，2019 年。
父代用于生成下一代候选点，并且每代需要一个父代。
然后将父代成对使用，以创建两个子代。重组使用交叉算子执行。这涉及在位串上选择一个随机分割点，然后创建一个子代，其位串从第一个父代开始直到分割点，从分割点到字符串末尾的位来自第二个父代。然后为第二个子代反转此过程。
例如，两个父代
- parent1 = 00000
- parent2 = 11111
可能产生两个交叉子代
- child1 = 00011
- child2 = 11100
这称为单点交叉，还有许多其他算子变体。
交叉以概率方式应用于每对父代，这意味着在某些情况下，父代的副本被用作子代，而不是重组算子。交叉由超参数控制，该超参数设置为较大的值，例如 80% 或 90%。
交叉是遗传算法的独特特征。它涉及混合和匹配两个父代的各个部分来形成子代。如何进行混合和匹配取决于个体的表示。
— 第 36 页，《元启发式算法要义》，2011 年。
突变涉及翻转创建的子代候选解中的位。通常，突变率设置为 1/L，其中 L 是位串的长度。
二进制值染色体中的每个位通常有很小的概率被翻转。对于具有 m 个位的染色体，此突变率通常设置为 1/m，平均每个子代染色体有一个突变。
— 第 155 页，《优化算法》，2019 年。
例如，如果一个问题使用了 20 位的位串，那么一个好的默认突变率将是 (1/20) = 0.05 或 5% 的概率。
这定义了简单的遗传算法过程。这是一个很大的研究领域，该算法有很多扩展。
现在我们熟悉了简单的遗传算法过程，让我们看看如何从头开始实现它。
想要开始学习优化算法吗？
立即参加我为期7天的免费电子邮件速成课程（附示例代码）。
点击注册，同时获得该课程的免费PDF电子书版本。
遗传算法从零开始
在本节中，我们将开发遗传算法的实现。
第一步是创建随机位串的种群。我们可以使用布尔值 True 和 False、字符串值 ‘0’ 和 ‘1’，或整数值 0 和 1。在这种情况下，我们将使用整数值。
我们可以使用 randint() 函数生成范围内的整数值数组，并指定范围为从 0 开始小于 2 的值，例如 0 或 1。我们还将把候选解表示为列表而不是 NumPy 数组，以保持简单。
可以按如下方式创建随机位串的初始种群，“n_pop”是控制种群大小的超参数，“n_bits”是定义单个候选解中位数数量的超参数。
|
1 2 3 |
... # 随机位串的初始种群 pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)] |
接下来，我们可以枚举固定次数的算法迭代，在本例中，由名为“n_iter”的超参数控制。
|
1 2 3 4 |
... # 枚举世代 for gen in range(n_iter): ... |
算法迭代的第一步是评估所有候选解。
我们将使用名为 objective() 的函数作为通用目标函数，并调用它来获得适应度得分，我们将对其进行最小化。
|
1 2 3 |
... # 评估种群中的所有候选解 scores = [objective(c) for c in pop] |
然后我们可以选择将用于创建子代的父代。
锦标赛选择过程可以实现为一个函数，该函数接受种群并返回一个选定的父代。k 值固定为 3，带有默认参数，但您可以尝试其他值。
|
1 2 3 4 5 6 7 8 9 |
# 锦标赛选择 def selection(pop, scores, k=3): # 第一次随机选择 selection_ix = randint(len(pop)) for ix in randint(0, len(pop), k-1): # 检查是否更优（例如，执行锦标赛） if scores[ix] < scores[selection_ix]: selection_ix = ix return pop[selection_ix] |
然后我们可以为种群中的每个位置调用此函数一次，以创建父代列表。
|
1 2 3 |
... # 选择父代 selected = [selection(pop, scores) for _ in range(n_pop)] |
然后我们可以创建下一代。
这首先需要一个执行交叉的函数。此函数将接受两个父代和交叉率。交叉率是一个超参数，它决定是否执行交叉，如果不执行，则父代将被复制到下一代。这是一个概率，通常有一个接近 1.0 的大值。
下面的 crossover() 函数使用 [0,1] 范围内的随机数绘制来实现交叉，如果执行交叉，则选择一个有效的交叉点。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# 交叉两个父代以创建两个子代 def crossover(p1, p2, r_cross): # 默认情况下，子代是父代的副本 c1, c2 = p1.copy(), p2.copy() # 检查是否重组 if rand() < r_cross: # 选择不在字符串末尾的交叉点 pt = randint(1, len(p1)-2) # 执行交叉 c1 = p1[:pt] + p2[pt:] c2 = p2[:pt] + p1[pt:] return [c1, c2] |
我们还需要一个执行突变的函数。
此过程仅通过由“r_mut”超参数控制的低概率翻转位。
|
1 2 3 4 5 6 7 |
# 突变算子 def mutation(bitstring, r_mut): for i in range(len(bitstring)): # 检查是否发生突变 if rand() < r_mut: # 翻转位 bitstring[i] = 1 - bitstring[i] |
然后，我们可以循环遍历父代列表并创建子代列表以用作下一代，根据需要调用交叉和突变函数。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
... # 创建下一代 children = list() for i in range(0, n_pop, 2): # 成对获取选定的父代 p1, p2 = selected[i], selected[i+1] # 交叉和突变 for c in crossover(p1, p2, r_cross): # 突变 mutation(c, r_mut) # 为下一代存储 children.append(c) |
我们可以将所有这些内容整合到一个名为 genetic_algorithm() 的函数中，该函数接受目标函数名称和搜索的超参数，并返回搜索过程中找到的最佳解决方案。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
# 遗传算法 def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut): # 随机位串的初始种群 pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)] # 跟踪最佳解决方案 best, best_eval = 0, objective(pop[0]) # 枚举世代 for gen in range(n_iter): # 评估种群中的所有候选解 scores = [objective(c) for c in pop] # 检查新的最佳解决方案 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])) # 选择父代 selected = [selection(pop, scores) for _ in range(n_pop)] # 创建下一代 children = list() for i in range(0, n_pop, 2): # 成对获取选定的父代 p1, p2 = selected[i], selected[i+1] # 交叉和突变 for c in crossover(p1, p2, r_cross): # 突变 mutation(c, r_mut) # 为下一代存储 children.append(c) # 替换种群 pop = children return [best, best_eval] |
现在我们已经开发了遗传算法的实现，让我们探讨一下如何将其应用于目标函数。
OneMax 的遗传算法
在本节中，我们将把遗传算法应用于基于二进制字符串的优化问题。
该问题称为 OneMax，它根据字符串中 1 的数量来评估二进制字符串。例如，长度为 20 位的位串，对于全为 1 的字符串，得分将是 20。
鉴于我们已经实现了最小化目标函数的遗传算法，我们可以为此评估添加一个负号，这样较大的正值就会变成较大的负值。
下面的 onemax() 函数实现了这一点，它以整数值位串作为输入，并返回值的负和。
|
1 2 3 |
# 目标函数 def onemax(x): return -sum(x) |
接下来，我们可以配置搜索。
搜索将运行 100 次迭代，我们的候选解将使用 20 位，这意味着最优适应度将是 -20.0。
种群大小将是 100，我们将使用 90% 的交叉率和 5% 的突变率。此配置是在一些试错之后确定的。
|
1 2 3 4 5 6 7 8 9 10 11 |
... # 定义总迭代次数 n_iter = 100 # 位 n_bits = 20 # 定义种群大小 n_pop = 100 # 交叉率 r_cross = 0.9 # 突变率 r_mut = 1.0 / float(n_bits) |
然后可以调用搜索并报告最佳结果。
|
1 2 3 4 5 |
... # 执行遗传算法搜索 best, score = genetic_algorithm(onemax, n_bits, n_iter, n_pop, r_cross, r_mut) print('Done!') print('f(%s) = %f' % (best, score)) |
总而言之，将遗传算法应用于 OneMax 目标函数的完整示例将在下方列出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
# OneMax 优化问题的遗传算法搜索 from numpy.random import randint from numpy.random import rand # 目标函数 def onemax(x): return -sum(x) # 锦标赛选择 def selection(pop, scores, k=3): # 第一次随机选择 selection_ix = randint(len(pop)) for ix in randint(0, len(pop), k-1): # 检查是否更优（例如，执行锦标赛） if scores[ix] < scores[selection_ix]: selection_ix = ix return pop[selection_ix] # 交叉两个父代以创建两个子代 def crossover(p1, p2, r_cross): # 默认情况下，子代是父代的副本 c1, c2 = p1.copy(), p2.copy() # 检查是否重组 if rand() < r_cross: # 选择不在字符串末尾的交叉点 pt = randint(1, len(p1)-2) # 执行交叉 c1 = p1[:pt] + p2[pt:] c2 = p2[:pt] + p1[pt:] return [c1, c2] # 突变算子 def mutation(bitstring, r_mut): for i in range(len(bitstring)): # 检查是否发生突变 if rand() < r_mut: # 翻转位 bitstring[i] = 1 - bitstring[i] # 遗传算法 def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut): # 随机位串的初始种群 pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)] # 跟踪最佳解决方案 best, best_eval = 0, objective(pop[0]) # 枚举世代 for gen in range(n_iter): # 评估种群中的所有候选解 scores = [objective(c) for c in pop] # 检查新的最佳解决方案 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])) # 选择父代 selected = [selection(pop, scores) for _ in range(n_pop)] # 创建下一代 children = list() for i in range(0, n_pop, 2): # 成对获取选定的父代 p1, p2 = selected[i], selected[i+1] # 交叉和突变 for c in crossover(p1, p2, r_cross): # 突变 mutation(c, r_mut) # 为下一代存储 children.append(c) # 替换种群 pop = children return [best, best_eval] # 定义总迭代次数 n_iter = 100 # 位 n_bits = 20 # 定义种群大小 n_pop = 100 # 交叉率 r_cross = 0.9 # 突变率 r_mut = 1.0 / float(n_bits) # 执行遗传算法搜索 best, score = genetic_algorithm(onemax, n_bits, n_iter, n_pop, r_cross, r_mut) print('Done!') print('f(%s) = %f' % (best, score)) |
运行示例将报告找到的最佳结果，然后是搜索结束时的最终最佳解决方案，我们期望它是最优解。
注意：由于算法的随机性或评估程序的随机性，或者数值精度的差异，您的结果可能会有所不同。请考虑多次运行示例并比较平均结果。
在这种情况下，我们可以看到搜索在大约八代后找到了最优解。
|
1 2 3 4 5 6 7 8 |
>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, 0, 1, 0, 1, 1]) = -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 完成！ 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 处具有最佳值。
|
1 2 3 |
# 目标函数 def objective(x): return x[0]**2.0 + x[1]**2.0 |
我们可以用遗传算法来最小化这个函数。
首先，我们必须定义每个输入变量的界限。
|
1 2 3 |
... # 定义输入范围 bounds = [[-5.0, 5.0], [-5.0, 5.0]] |
我们将“n_bits”超参数作为目标函数的每个输入变量的位数，并将其设置为 16 位。
|
1 2 3 |
... # 每个变量的位数 n_bits = 16 |
这意味着我们的实际位串将有 (16 * 2) = 32 位，因为有两个输入变量。
我们必须相应地更新我们的突变率。
|
1 2 3 |
... # 突变率 r_mut = 1.0 / (float(n_bits) * len(bounds)) |
接下来，我们需要确保初始种群创建的随机位串足够长。
|
1 2 3 |
... # 随机位串的初始种群 pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)] |
最后，我们需要在通过目标函数评估每个位串之前对其进行解码。
我们可以通过首先将每个子字符串解码为一个整数，然后将该整数缩放到所需的范围来实现。这将得到一个在给定范围内的值向量，然后可以将该向量提供给目标函数进行评估。
下面的 decode() 函数实现了这一点，它接受函数的边界、每个变量的位数以及位串作为输入，并返回一个解码后的实值列表。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# 将位串解码为数字 def decode(bounds, n_bits, bitstring): decoded = list() largest = 2**n_bits for i in range(len(bounds)): # 提取子字符串 start, end = i * n_bits, (i * n_bits)+n_bits substring = bitstring[start:end] # 将位串转换为字符组成的字符串 chars = ''.join([str(s) for s in substring]) # 将字符串转换为整数 integer = int(chars, 2) # 将整数缩放到期望的范围 value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0]) # 存储 decoded.append(value) return decoded |
然后，我们可以在算法循环开始时调用它来解码种群，然后评估解码后的种群。
|
1 2 3 4 5 |
... # 解码种群 decoded = [decode(bounds, n_bits, p) for p in pop] # 评估种群中的所有候选解 scores = [objective(d) for d in decoded] |
将这些内容整合在一起，用于连续函数优化的遗传算法的完整示例在下面列出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
# 用于连续函数优化的遗传算法搜索 from numpy.random import randint from numpy.random import rand # 目标函数 def objective(x): return x[0]**2.0 + x[1]**2.0 # 将位串解码为数字 def decode(bounds, n_bits, bitstring): decoded = list() largest = 2**n_bits for i in range(len(bounds)): # 提取子字符串 start, end = i * n_bits, (i * n_bits)+n_bits substring = bitstring[start:end] # 将位串转换为字符组成的字符串 chars = ''.join([str(s) for s in substring]) # 将字符串转换为整数 integer = int(chars, 2) # 将整数缩放到期望的范围 value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0]) # 存储 decoded.append(value) return decoded # 锦标赛选择 def selection(pop, scores, k=3): # 第一次随机选择 selection_ix = randint(len(pop)) for ix in randint(0, len(pop), k-1): # 检查是否更优（例如，执行锦标赛） if scores[ix] < scores[selection_ix]: selection_ix = ix return pop[selection_ix] # 交叉两个父代以创建两个子代 def crossover(p1, p2, r_cross): # 默认情况下，子代是父代的副本 c1, c2 = p1.copy(), p2.copy() # 检查是否重组 if rand() < r_cross: # 选择不在字符串末尾的交叉点 pt = randint(1, len(p1)-2) # 执行交叉 c1 = p1[:pt] + p2[pt:] c2 = p2[:pt] + p1[pt:] return [c1, c2] # 突变算子 def mutation(bitstring, r_mut): for i in range(len(bitstring)): # 检查是否发生突变 if rand() < r_mut: # 翻转位 bitstring[i] = 1 - bitstring[i] # 遗传算法 def genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut): # 随机位串的初始种群 pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)] # 跟踪最佳解决方案 best, best_eval = 0, objective(decode(bounds, n_bits, pop[0])) # 枚举世代 for gen in range(n_iter): # 解码种群 decoded = [decode(bounds, n_bits, p) for p in pop] # 评估种群中的所有候选解 scores = [objective(d) for d in decoded] # 检查新的最佳解决方案 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])) # 选择父代 selected = [selection(pop, scores) for _ in range(n_pop)] # 创建下一代 children = list() for i in range(0, n_pop, 2): # 成对获取选定的父代 p1, p2 = selected[i], selected[i+1] # 交叉和突变 for c in crossover(p1, p2, r_cross): # 突变 mutation(c, r_mut) # 为下一代存储 children.append(c) # 替换种群 pop = children return [best, best_eval] # 定义输入范围 bounds = [[-5.0, 5.0], [-5.0, 5.0]] # 定义总迭代次数 n_iter = 100 # 每个变量的位数 n_bits = 16 # 定义种群大小 n_pop = 100 # 交叉率 r_cross = 0.9 # 突变率 r_mut = 1.0 / (float(n_bits) * len(bounds)) # 执行遗传算法搜索 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 的输入。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
>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 完成！ f([-0.000152587890625, 0.0]) = 0.000000 |
进一步阅读
如果您想深入了解，本节提供了更多关于该主题的资源。
书籍
- Genetic Algorithms in Search, Optimization, and Machine Learning, 1989.
- An Introduction to Genetic Algorithms, 1998.
- 优化算法, 2019.
- 元启发式算法精要, 2011.
- 计算智能导论, 2007.
API
文章
总结
在本教程中，您了解了遗传算法优化。
具体来说，你学到了：
- 遗传算法是一种受进化启发的随机优化算法。
- 如何在 Python 中从头实现遗传算法。
- 如何将遗传算法应用于连续目标函数。
你有什么问题吗？
在下面的评论中提出你的问题，我会尽力回答。
我没有理解上面的算法。太复杂了
听到这个消息我很难过。
哪个部分令人困惑？
我明白了它是如何工作的，但我有一个疑问，你能告诉我你正在尝试解决什么问题吗？
正如教程中所述，我们正在解决两个不同的优化问题。
先生，我可以在我的大四项目中使用这些代码吗？因为我的团队正在研究遗传算法。
这是一个常见的请求，我在这里回答
https://machinelearning.org.cn/faq/single-faq/can-i-use-your-code-in-my-own-project
我认为您必须一步一步地通过代码传递数字，然后您就能理解了。
这对我来说很有效 🙂
谢谢 Jason！你给了我很大的启发。
不客气。
非常感谢。内容对我非常有帮助，因为我正在进行遗传算法的博士研究。您能否进一步帮助我？我需要一些关于后续实现的帮助。请尽快给我发邮件。
抱歉，我没有能力帮助您的研究项目。
你好，我正在攻读硕士学位，研究将遗传算法与动态规划结合来解决旅行商问题。
我对实现部分有疑问。我之所以问你，是因为你正在攻读博士学位。
希望您能帮助我
谢谢你
很棒的文章，虽然有点长，但作为学习的绝佳示例。谢谢
谢谢！
嗨，Jason，
感谢您分享您的知识和代码。我使用了它，它运行得很好。
我有一个问题：您如何知道这是全局最优解？
你好 Indira，
您使用了哪个代码？请记住，对于提供的一些简单示例，我们已经知道了全局最优解。
此致，
我使用了此帖子最后一个示例中的代码，但我将其修改为多目标。
Obj1=abs(x[0]*a0 + x[1]*a1 + x[2]*a2 – a_target)**2
Obj2=abs(x[0] + x[1] + x[2])
我对 x 也有一些约束。
如我所说，代码运行正常，解决方案也相当合理。但是，我想知道是否能以某种方式证明这是全局最优解，甚至是局部最优解。
很棒的一课。谢谢！
不客气！
我能把代码复制到我的 Python 里吗？因为我想练习一下。
是的。
你好 Jason。
感谢这个有用的教程。
您能否提供一个关于使用遗传算法进行特征选择的教程？
不客气！
感谢您的建议！
你好 Jason，感谢这个精彩的教程。我喜欢阅读并逐步输入代码以真正跟进并理解它。
我修改了我的 genetic_algorithm，使其也具有 decode 和 bounds 输入参数，以便可以为两个示例重用。我为 oneup 添加了一个 decode，它只返回输入值，并更改了您的 decode，以便位串可以解码为具有相同位数 的多个参数。
希望这是正确的重用方向。
我在 decode 中发现了一个错误。largest 应该是 (2**n_bits) -1
不客气！
干得好！
收到。
亲爱的，遗传算法这样重要的主题很难理解。不过，非常感谢您为此提供了一些启发。
不客气。
非常棒的文章 Jason 先生，非常感谢您将所有内容都写成了代码，这将对我们进行各种实验非常有帮助。
我只是在想这些算法，可以说损失函数之于梯度下降，目标函数也为遗传算法提供了同样的作用吗？
与遗传算法相比，梯度下降算法不是更基于目标吗？我的意思是，它们完全由找到最佳停止点来指导，而遗传算法或多或少地依赖于变异和交叉来达到相同的目的。
谢谢！
是的，当然。损失函数是梯度下降优化算法的目标函数。
不，它们只是不同的算法。GD 使用更多信息（例如导数），而 GA 则不使用。
嗨，Jason，
这是一段很棒的代码和遗传算法 (GA) 的介绍，作为人工神经网络 (ANN) 的一个很好的替代方案。恭喜这篇帖子！。
我对 GA 如何快速收敛到最小二次函数感到惊讶！。
在我看来，ANN 与 GA 的主要区别在于
使用 ANN，我们通过数据集和学习权重的神经网络模型来“映射”输出与输入；而 GA 则通过“人工基因选择”来解决“最小/最大”优化问题。也就是说，将“基因”问题编码为比特 > 初始化种群 > 通过评估对目标更好适应性的目标函数选择父母 > 执行交叉基因 > 变异基因 > 每代替换父母种群为子代种群。
因此，关键问题是将问题变量编码为比特，以便能够应用交叉和比特变异方法，并通过更好的目标性能选择父母。
– 我直觉地认为，支持这种“人工选择”（或 GA）用于优化问题解决的一些“概率”收敛支柱，以及支持 ANN 的一些 SGD 和反向传播方法（最小误差）作为支柱。
我尝试了其他目标函数，例如三次函数等，在所有这些函数中，代码的性能都很好，并且很快就找到了最小值。
就“人工选择”方法而言，我唯一担心的是，当然，种群中的至少一个成员能很快获得搜索到的最小值，但种群的其余部分（即使改变变异和交叉率）仍然在该最优“基因”值之外，即使我玩弄不同数量的种群、代数、变异和交叉率等...
所以最后我们无法完全将旧种群进化为“新物种”种群，至少用这部分算法来说，但大自然可以自然进化，产生新物种，这与旧物种不同 :-))
感谢您启发了所有这些美妙的问题！
此致
谢谢！
是的，我喜欢将其视为解决两种非常不同类型问题的技术：“函数逼近”与“函数优化”。
请小心，调整 GA 可能会让人上瘾 ：)
第 63 行有一个错误
>> best, best_eval = 0, objective(pop[0])
应该是
best, best_eval = 0, objective(decode(bounds, n_bits, pop[0])
同意！
谢谢，已修正。
…并且在第 63 行末尾缺少一个括号。
你好 Jason，非常好的教程，就像你所有的其他教程一样。我有一个问题，每一代，我们是不是应该保留上一代的所有的父母，加上当前的子代，根据分数对它们进行排序，然后保留最高或最低分数的前几名？原因是有些父母比孩子更好，所以我们想保留表现最好的？谢谢
谢谢！
有很多算法的修改版本，包括保留上一代的最佳父母。这被称为精英主义。
你好 Jason，您能做一个类似的关于遗传编程的教程吗？或者您可以告诉我算法需要改变什么才能成为遗传编程算法而不是 GA？
感谢您的建议。
您好，在第 52 行的 onmax 目标函数中
应该是这样的吗
if score[i] > best_eval
best, best_eval = pop[i], scores[i]
我们对 one max 目标函数进行了反转，使其最小化。
谢谢 Jason，我是这里的常客，我想我在为一个课程项目使用你的 GA 教科书？
当然，这会有帮助
https://machinelearning.org.cn/faq/single-faq/can-i-use-your-code-in-my-own-project
你好，我这里有语法错误，为什么？
for gen in range(n_iter)
^
SyntaxError: invalid syntax
很抱歉听到这个消息，也许这些提示会有帮助。
https://machinelearning.org.cn/faq/single-faq/why-does-the-code-in-the-tutorial-not-work-for-me
选择交叉和变异率的数值依据是什么？
试错，或使用在其他问题上长期有效的数值。
python 中的 rastrigins 函数是什么？
我该如何在 python 中实现它
抱歉，我认为我没有示例。
文件“”，第 65 行
for gen in range(n_iter)
^
SyntaxError: invalid syntax
Jason，连续函数代码中，我直接复制粘贴，就出现这个错误
这有助于您在没有错误的情况下复制代码
https://machinelearning.org.cn/faq/single-faq/how-do-i-copy-code-from-a-tutorial
非常好的文章！
我开始阅读神经网络，在谷歌搜索遗传算法时偶然发现了这个页面。它帮助我理解了一些基本概念。
谢谢！
不客气！
亲爱的Jason
您的文章非常好。但是，我还不熟悉 GA，无法逐行理解。但我获得了一些对我的股票价格预测项目有用的信息。但是，我对 GA 在价格预测中的实现有很多疑问。您能在这一领域帮助我吗。
谢谢！
如果您对时间序列预测感兴趣，也许可以从这里开始
https://machinelearning.org.cn/start-here/#timeseries
代码中有一个错误。
best, best_eval = 0, objective(decode(bounds, n_bits, pop[0])
应该是
best, best_eval = 0, objective(decode(bounds, n_bits, pop[0]))
也就是说，最后一个括号。这就是为什么很多人有语法错误。
谢谢
谢谢，已修正。
您好！首先，感谢您的教程。我目前正在进行一个依赖于 4 个变量的函数的改编，在解码函数方面遇到了一些麻烦。以下是正确的吗？
def decode(bounds, n_bits, bitstring)
decoded = list()
largest = 4**n_bits-1
for i in range(len(bounds))
# 提取子字符串
start, end = i * n_bits, (i * n_bits)+n_bits
substring = bitstring[start:end]
# 将位串转换为字符组成的字符串
chars = ”.join([str(s) for s in substring])
# 将字符串转换为整数
integer = int(chars, 4)
# 将整数缩放到所需范围
value = bounds[i][0] + (integer/largest) * (bounds[i][1] – bounds[i][0])
# 存储
decoded.append(value)
return decoded
不客气。
抱歉，我没有能力审查/调试您的扩展。希望您能理解。
这非常清晰和富有启发性。我以前研究过 Matlab 的 GA 代码，但觉得非常困难。现在我意识到不是算法本身很难，而是我之前读的代码写得不好。谢谢！
不客气！
Jason 你好！感谢您完成此教程。我想知道是否可以绘制您的遗传算法的收敛图？如果可以，您会如何实现？
是的，您可以在每次迭代时将最佳适应度保存在一个列表中，然后在运行结束时绘制该列表。
嗨，Jason，
感谢分享🙂 我正试图将此应用于同时具有整数和连续变量的问题。有什么建议吗？我在想，在解码函数中，只有一部分值应该被解码为连续值，其余的应该保持为二进制或整数。
也许可以先将所有值都转换为二进制数，然后将一些整数转换为所需的浮点数范围。
谢谢标题
我有一个问题，我有一些来自函数的数据，我能预测出实际函数是什么吗？使用 GP
您可以近似一个与数据匹配的函数。这就是应用机器学习（函数逼近）的目标。
非常感谢，Jason！
如果有人想使用 python 2.x，有几点说明：
1) 对于 OneMax 示例，将 c1, c2 = p1.copy(), p2.copy() 替换为 c1, c2 = p1[:], p2[:]
2) 对于连续函数，在代码开头写上以下内容：
from __future__ import division
Jason，做得好！
感谢分享！
你真是天使！
非常感谢 <3
你好，我需要一些家庭作业的帮助。我需要从 onemax 的 20 个个体中选出最好的 20 个孩子。我应该如何修改你提供的 onemax 代码？我对此类事情是新手。
选出 20 个中的 20 个：这不就是指挑选所有人吗？
你好，我有一个关于最大化函数的问题
我们只需要改变
if scores[i] best_eval
?
是的。在这种情况下，您会记住您见过的最大值
你好，
谢谢。我正在尝试使用遗传算法来解决加权集合覆盖问题。数据如下：
Universe = set([1.,2.,3.,4.,5.,6.,7.,8.])
Subsets = [set([1.,2.]),
set([3.,4.]),
set([5.,6.]),
set([7.,8.]),
set([2.,4.,6.,8.])]
weights = [1.,1.,1.,1.,1.]
如何定义目标函数？
也许是重叠量？
Objective() 需要导入任何库吗？
scores = [Objective(c) for c in pop]
NameError: name ‘Objective’ is not defined
你好 Yousaf…请提供完整的代码列表，以便我们确定可能需要什么。
此致，
你好，
希望有人能帮帮我，拜托了。
我使用了此帖子最后一个示例中的代码，但我将其修改为多目标。
Obj1=abs(x[0]*a0 + x[1]*a1 + x[2]*a2 – a_target)**2
Obj2=abs(x[0] + x[1] + x[2])
我对 x 也有一些约束。
代码运行正常，解决方案也非常合理。但是，我想知道是否能证明这是全局最优解，甚至是局部最优解。我想知道这是否在您此处发布的某本书中。
谢谢。
如何使用 GA 来找到太阳能系统的最佳布线，您能否举例说明？
你好 Jack…虽然我没有能力处理你的具体应用，但我非常乐意回答你关于我们材料的任何具体问题。
嗨
我想为具有 10 个变量和 n_step=21（我的意思是 t-21 到 t）的 10 个变量使用 LSTM 网络，所有这些变量都有其各自的边界……我在解码器和 LSTM 网络的输入维度方面遇到了一些问题……任何帮助都将不胜感激。
你好 Milad…以下内容是一个很好的起点。
https://machinelearning.org.cn/multivariate-time-series-forecasting-lstms-keras/
嗨
谢谢您的回复
我已阅读 machinelearningmastery 关于在 python 中实现各种机器学习方法的文章。（我是您网站的忠实粉丝）但找不到解决方案……
代码的第一行
pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)]
不起作用。
我说的对吗？
你好 Silviu…你能提供你遇到的确切错误消息吗，以便我们更好地帮助你？
容易理解，我精通 python，但现在才开始学习 GA。从网页复制的代码充满了错误和遗漏；我设法修复了。
特别是，MUTATION 函数缺少 RETURN 语句。我还发现，在没有变异的情况下，GA 的效果更好！
感谢 Lupus 的反馈！如果您有任何问题，请随时告知我们。
嗨，Jason，
为什么您要在连续函数优化中使用“二进制数”？
我们能否直接在遗传算法函数中使用实数？
谢谢，
Iman
你好 Iman…您可能会发现以下内容很有趣。
https://pubs.acs.org/doi/pdf/10.1021/jp063998e
你好 James，感谢您的精彩解释。你能把您在这篇文章中使用的完整代码发给我吗？
你好 Boutine…不客气！完整的代码列表可在文章中以下文字下方找到
“总而言之，用于连续函数优化的遗传算法的完整示例列在下面。”
嗨，Jason，
我叫 Matt。
谢谢您的教程。
我训练了一个 GBM 模型，该模型可以预测三个目标变量。现在，我将把 GBM 模型与 GA 集成，以找到最小化目标变量的预测变量的最佳集合。
我在网上搜索过，但没有找到资源或教程。
您能帮忙吗？
非常感谢
你好 Matt…以下资源可能对您感兴趣。
https://towardsdatascience.com/genetic-algorithm-to-optimize-machine-learning-hyperparameters-72bd6e2596fc
谢谢 James 分享资源。
但我想要的不是使用 GA 进行超参数调整。
我将使用 GA 来查找我用于训练 GBM 模型的预测变量的最佳集合。预测变量集使得目标变量最小化。
这有道理吗？
提前感谢。
谢谢 James 分享资源。
但我想要的不是使用 GA 进行超参数调整。
我将使用 GA 来查找我用于训练 GBM 模型的预测变量的最佳集合。预测变量集使得目标变量最小化。
这有道理吗？
提前感谢。
你好 James，亲爱的，你能告诉我是否可以获得 PSO 算法中那样 GA 算法的 gif 动画吗？
你好 Amir…以下内容可能对您感兴趣。
https://ieeexplore.ieee.org/document/6016133
嗨 James，
如果我们的输出有约束怎么办？如何将该约束添加到您的代码中？您能建议一下吗？
你好 Matt…请看我之前的评论。
嗨 James，
如何将约束添加到此代码中？
谢谢
你好 Matt…请澄清约束的目标和意图，以便我们更好地帮助你。
嗨 James，
当然，我正在尝试解决的问题的约束是预算约束。输入是建筑材料。所以我想添加的约束是，当 GA 代码选择一个种群时，会检查其成本影响，如果低于 10,000 美元，它就可以进入 GA 的其他步骤。否则，需要更改种群，直到满足预算约束。
如果需要进一步说明，请告知。
谢谢
嗨 James，
当然，我正在尝试解决的问题的约束是预算约束。输入是建筑材料。所以我想添加的约束是，当 GA 代码选择一个种群时，会检查其成本影响，如果低于 10,000 美元，它就可以进入 GA 的其他步骤。否则，需要更改种群，直到满足预算约束。
如果需要进一步说明，请告知。
谢谢
嗨 James，
GA 是否可用于离散优化？
如果可以，您是否有任何参考资料解释如何做到这一点？
谢谢
你好 Matty…您可能会发现以下内容很有趣。
https://www.researchgate.net/publication/2404185_Genetic_Algortihms_For_Mixed_DiscreteContinuous_Optimization_In_Multidisciplinary_Design
嗨 James，
它可能会反复从所有候选者中选择同一个人“selected = [selection(pop, scores) for _ in range(n_pop)]”。例如，selected = [pop[2], pop[3], pop[2]…]，所以 p1 和 p2 可能是 pop[2] 和 pop[2]。在现实世界中，一个人和他的副本无法生育。
嗨 James，
它可能会在“selected = [selection(pop, scores) for _ in range(n_pop)]”中反复选择同一个人，例如，“selected = [pop[3], pop[0], pop[3], …]，所以父母 p1 和 p2 可能是 pop[3] 和 pop[3]。一个人和他的副本无法生育。
嘿，请问我能从您这里获取推荐系统遗传算法的源代码吗？谢谢。
你好 Muhammad…总的来说，我们不提供源代码作为服务。我们确实包含我们所有电子书中提供的源代码，以帮助您开始自己的项目。
https://machinelearning.org.cn/products/
在交叉函数中，在以下行选择交叉点，它应该是 len(p1)-1，因为 randint 使用 high 作为独占。
pt = randint(1, len(p1)-2)
感谢Tareque的反馈！