数据挖掘：遗传算法GA Genetic Algorithms
遗传算法是一种高效的启发式搜索技术，模拟生物进化过程，通过“适者生存”的原则优化潜在解决方案。每个候选解称为染色体，由基因组成，适应度函数衡量其生存能力。染色体通过繁殖、交叉和突变进行进化：繁殖选择适应度高的父母，交叉在染色体中随机位置交换基因段，突变随机改变基因值以避免局部最优。精英主义保留最佳解，确保下一代有良好起点。遗传算法在《Vector Game》中应用，通过迭代优化猜出二进制字符串，比随机策略更高效。
文章目录
-
-
-
- 遗传算法
-
- 简介
- 相关概念
- Example: The Vector Game
-
遗传算法
简介
它是一种广为采用的启发式搜索技术
它模拟生物进化过程
该软件程序采用进化方式进行学习和搜索，类似于生物进化系统的方式
该方法在广泛的问题域中表现出色，且具有高度的通用性
其主题是适者生存理论
通过选择最适合的解决方案进行繁殖，逐步优化问题解决的质量
每个候选解被定义为染色体。染色体由基因组成，通过适应度函数评估它们的生存能力。染色体能够通过进化机制进行复制、交配以及发生突变。
在迭代算法中，通过组合候选方案，精英主义产生后代个体。这些后代被称为一代人。这些后代个体可以作为候选方案参与后续迭代。在适者生存的机制下，后代与父母共同生存，并将作为下一阶段父母的角色繁殖后代。
相关概念
繁殖：通过繁殖过程，遗传算法GA通过选择具有较高适应性评级的父母个体或通过调整这些父母个体的选择概率，从而促进繁殖过程，生成新一代的潜在改进方案。
交叉即通过二进制符号（响应决策变量）来编码染色体（潜在解）。交叉过程涉及在字符串中随机选择一个分割点，然后将该点一侧的基因段与另一字符串对应位置的基因段进行交换。
突变（Mutation）是染色体表示的任意（最小）变化，该变异操作通常用于防止算法陷入局部最优状态。该过程通过随机选择一条染色体（其中具有更好适应值的染色体被选中的概率更高），并随机识别染色体中的一个基因，将其值反转（从0变为1，或从1变为0），从而为下一代生成一条新染色体。突变发生的概率通常被设定为非常低，例如0.1%。该过程随机选择一条染色体（给具有更好适应值的染色体更多的概率），并随机识别染色体中的一个基因并反转其值（从0到1或从1到0），从而为下一代生成一条新染色体。突变发生的概率通常被设定为非常低，例如0.1%。
精英主义：遗传算法的一个重要方面是保留或选择一些最优的解决方案，以便于在几代中逐步发展。这样做的意义是确保最终能够获得该算法当前应用的最佳解决方案。在实践中，这些最佳解决方案将被迁移到下一代。
Example: The Vector Game
标识包含 6 个二进制数字的字符串
猜一个二进制字符串：001010
默认策略：随机试验与错误。需要进行64次猜测，其中一个是正确答案。平均而言，每次猜测的成功率是32%。
采用遗传算法作为改进策略。通过迭代机制，运用遗传算子，识别出对手的数字序列。
1.展示四个字符串，随机选择。（任意选择四个。通过实验，你可能会发现五六个会更好。假设您选择了以下四个：
（A） 110100;分数 = 1（即，正确猜测的一位数字）
（B）111101;分数 = 1
（C）011011;得分 = 4
（D） 101100;得分 = 3
2. 由于没有一个字符串是完全正确的，请继续。
3.但是，我们可以删除（A）和（B），因为它们的分数很低。保留 C 和 D 并命名 （C） 和 （D） 父项。
4.通过在第二位和第三位数字之间拆分每个数字来“配对”父母（拆分的位置是随机选择的）：
（C） 01：1011
（D） 10：1100
现在将 （C） 的前两位数字与 （D） 的最后四位数字组合在一起（这称为交叉）。结果是（E），第一个后代：
（E） 011100;得分 = 3
同样，将 （D） 的前两位数字与 （C） 的最后四位数字组合在一起。结果是（F），第二个后代：
（F） 101011;得分 = 4
看起来后代并不比父母好多少。
5. 现在复制原件（C）和（D）。
6.配对和交叉新父母，但使用不同的分割。现在你有两个新的后代，（G）和（H）：
（C） 0110：11
（D） 1011：00
（G） 0110：00;得分 = 4
（H） 1011：11;得分 = 3
接下来，重复步骤2：从所有先前的解决方案中选择要重现的最佳“耦合”。
您有几个选项，例如 （G） 和 （C）。选择 （G） 和 （F）。
现在复制和交叉。结果如下：
（F） 1：01011
（G） 0：11000
（I） 111000;得分 = 3
（J） 001011;得分 = 5
生成更多后代：
（F） 101：011
（G） 011：000
（K） 101000;得分 = 4
（L） 011011;得分 = 4
现在，以 （J） 和 （K） 作为父级重复这些过程，并复制交叉：
（J） 00101：1
（K） 10100：0
（M） 001010;得分 = 6
就是这样！经过13次猜测，您已经找到了解决方案。与随机猜测策略的预期平均值32相比，这并不坏。