遗传和进化算法的替代介绍
4.94/5 (32投票s)
本文介绍了一种非常小的演化算法，它能够发现一些数学表达式，以根据您提供的值给出结果。
引言和背景
我在大学时上过《人工智能》和《遗传算法》课程。两者之间并非完全依赖，但通常会联系起来。
老师们喜欢说的一件事是，逻辑思维的人比非逻辑思维的人更难理解这些算法，因为他们说这些算法不是基于逻辑的。
嗯，我当时不同意，现在仍然不同意。遗传算法是逻辑算法，但它们不是使用预先已知的公式来解决问题或尝试所有可能性，而是从一些“随机尝试的可能性”（通常是某种数学公式）开始，这些可能性可能包含也可能不包含问题的解决方案，如果都没有，算法会根据先前的可能性，通过对其进行随机（但受控）更改（这可能包括突变、排列、交叉或其他技术）来开发新的可能性群体。
新群体是“没有逻辑”的随机发展。事实上，使用随机仅仅是因为我们这些开发应用程序的人不知道更好的方法来直接改变群体以获得好的结果。如果知道，我们就可以简单地编写那个算法，它会更好，但就不再是遗传算法了。
然而，即使有随机变化，仍需进行分析以决定哪些解决方案是实现正确结果的“最佳候选者”。这仍然是一个正常的编程算法，其质量将直接影响遗传算法的结果（在性能、找到有效解决方案的概率以及在有效解决方案中找到最快解决方案的概率方面）。
实际与旧文档和示例
当我学习遗传算法时，老师们说这些算法有细胞。细胞自我繁殖，细胞可以与其他细胞交流等等。
现在，当我在互联网上搜索遗传算法时，我只找到谈论染色体和基因的文档。也许我的老师使用了错误的来源，因为遗传算法拥有染色体和基因似乎很自然。然而，细胞的概念仍然允许进化编程，这是一个更广泛的领域，包括遗传算法，在某些情况下，这只是命名问题。
回到遗传算法，它们被解释为在一组染色体上工作，“通常表示为字符串”，但我没有找到任何例外，所以似乎所有遗传算法都使用字符串，并且整个算法通过展示这些字符串如何被修改来解释。
为了看到一些极其简单的东西，有些例子是这样的
我们的目标染色体必须是这样的
01010101
然后，我们用如下染色体启动代码
00000000
和
11111111
在繁殖阶段，它们可能会发生交叉（在这种情况下，任意位置的单次交叉）
00001111 11110000 00111100
并且还会发生一些突变（在此示例中，每次繁殖恰好一次突变）
01001111 00001110 00101100
然后，下一步是选择最佳生成值，以查看是否找到了结果，或者是否需要新的繁殖。
问题
老师们还喜欢说的一件事是，遗传算法极其困难，我再次不同意。当然，一个人需要理解编程语言，并且可能很难理解具有“随机”因素并每秒执行数百万（甚至更多）操作的算法。然而，在我看来，让这些算法变得困难的是那些糟糕的例子，它们使一切看起来比实际需要更复杂。
首先，我不喜欢这些算法被解释为依赖于字符串，因为这些字符串稍后需要被解析。但我真正讨厌的是，它使得这个想法无法使用，那就是我们必须将答案作为输入。那么，为什么要编写代码来尝试找到我们已经知道的答案呢？
我说的不是编写代码来找到用户知道而计算机不知道的答案。那叫做测试。我说的代码是必须始终将正确答案作为输入接收的代码。它毫无用处，无论它是否总能找到正确答案，因为要做到这一点，我们只需避免任何复杂的逻辑并直接返回输入值即可。
遗传算法旨在解决那些我们不知道最终答案，也不知道更好算法来找到答案的问题。我们可能知道一些问题和一些答案，但我们期望它“学到足够多”，能够为那些我们用户尚无答案的问题提供正确答案。
一个更好的例子
对我来说，数学问题是更好的例子。有许多练习给我们一些输入值和它们的输出，然后要求我们给出样本中没有的另一个值的输出。例如：
- 输入1给出值3；
- 输入2给出值5；
- 输入3给出值7；
- 输入10给出值21。
输入 7 的结果是什么？
作为人类，我们可以通过在输入中加1，在输出中加2，直到得到正确的值来轻松回答这个问题，或者我们可以做得更好，开发一个公式，如下所示
F(x) = (x*2) + 1
因此，利用这个公式，F(7) = 15，所有输入和输出都可以被测试，更好的是，通过存储这个公式，我们可以生成任何其他输入的。结果。
为什么这是一个更好的例子？
我们只会给遗传算法一些输入和输出，它必须发现一个生成这些结果的公式。我们不期望它仅仅将这些值作为正确答案返回。如果算法发现了正确的公式，它将能够为任何输入提供答案，而不仅仅是那些用于开发公式的输入。从某种意义上说，它将“学习”如何从输入中生成结果。
但是，要创建这样的算法，我不会使用“染色体”。对我来说，这不是正确的想法。我将使用细胞，或者正如我决定称之为的神经元。因此，我将在本文中提出的算法可能不被认为是遗传算法，因为术语不同，也因为我没有直接操作字符串……但你知道，这只是偏好问题，因为我可以操作字符串并为它们编写解析器（这只会减慢速度，但这是可能的）。
注意：除了名称神经元之外，本文及其附带的代码与神经网络无关。
神经元的种类
在我的示例中，我将使用两种神经元：简单神经元和二元神经元。
简单神经元将直接返回输入值，或返回一个常数值，从而有效忽略输入。可以创建不同类型的简单神经元，但我决定就此打住。
二元神经元将对其他两个神经元应用一些数学运算（例如加法、减法等）（因此，它们与其他神经元通信并根据从该通信中接收到的两个答案生成一个新答案）。
二元神经元可以与任何其他神经元通信，包括其他二元神经元。这就是算法如何创建非常大的数学表达式。
那么，遗传算法（或者，如果您喜欢，演化算法）的目的是创建一些第一代“生物”（我们也可以称它们为大脑，因为它们只由神经元组成），检查它们中的任何一个是否产生了有效的结果，如果不是，则“繁殖”最好的那些（我不会讨论神经元是否繁殖，但可以考虑整个“大脑”被克隆并允许一些改变）。当然，在繁殖之后，将重新执行有效结果的验证，并且可能会发生新的繁殖……如果需要，这可以“永远”重复。
每个神经元都可以被视为数学表达式的一部分。神经元的繁殖允许表达式的各个部分发生突变。然而，没有直接的字符串操作，因此，即使公式可能无法生成正确的值，也不会出现编写不完整数学表达式的情况。如果使用对人类可读公式的直接字符串操作，我们很容易创建出开括号多于闭括号的表达式。
我们将通过获取从表达式中得到的结果与作为输入给出的预期结果之间的差异来评估我们距离正确结果的远近。
编程神经元
为了创建算法，我从INeuron接口开始。它由以下成员组成：
int? Execute(int input);
INeuron Reproduce();
int Complexity { get; }
Execute()方法接收一个输入并必须生成一个结果。我让它返回一个nullable int，因为有些表达式可能会失败（例如，将一个值除以零），我希望结果表示失败而不会生成异常；Reproduce()方法预期会繁殖一个Neuron。神经元本身决定如何繁殖。例如，二元神经元通常会繁殖它们与之通信的每个神经元，然后创建一个与这些新神经元通信的神经元；- 当选择最佳结果时，将使用
Complexity。如果两个或多个表达式给出相同的结果，我们将选择复杂度较低的表达式作为最佳表达式（即更小的公式）。
然后，我创建了InputNeuron，IntNeuron和BinaryNeuron。
InputNeuron简单地将输入值作为其结果返回。它不进行真正的繁殖，因为它永不改变，所以它的Reproduce()返回自身。对于计算机来说，它不进行真正的繁殖并不重要，因为“细胞”不会衰老。在像x + 1这样的公式中，这个细胞代表x；IntNeuron返回一个常量值。在其繁殖过程中，它可能会创建一个子代，其常量值比其自身的值略大或略小。在公式x + 1中，1是通过一个持有值1的IntNeuron实现的；BinaryNeuron进行加法、减法等数学运算，并对其他两个神经元的结果进行这些运算。因此，在x + 1公式中，+是一个BinaryNeuron，它对InputNeuron和一个IntNeuron使用加法运算。在其繁殖过程中，它可能会要求其他两个神经元繁殖（最常见的情况），或者可能决定增加细胞数量（有效地将一个BinaryNeuron作为其子神经元之一），甚至可能决定只返回其一个子神经元的子代作为其自身的子代（有效地减少表达式的大小）。
理论上，如果一个简单神经元可以通过变成一个BinaryNeuron来繁殖，那会更好，但我只是简单地认为让简单神经元只关心自己，并根据二元神经元来增加或减少细胞数量更容易。这意味着我们必须在第一代就有二元神经元，否则我们的表达式在繁殖过程中永远无法增加大小。
那么，来看一些代码，这些类是这样的
public interface INeuron
{
int Complexity { get; }
int? Execute(int input);
INeuron Reproduce();
}
public sealed class InputNeuron:
INeuron
{
public static readonly InputNeuron Instance = new InputNeuron();
public int Complexity
{
get
{
return 1;
}
}
public int? Execute(int input)
{
return input;
}
public INeuron Reproduce()
{
return this;
}
public override string ToString()
{
return "x";
}
}
public sealed class IntNeuron:
INeuron
{
private int _value;
public IntNeuron(int value)
{
_value = value;
}
public int Complexity
{
get
{
return 1;
}
}
public int? Execute(int input)
{
return _value;
}
public INeuron Reproduce()
{
int random = Program.GetRandom(11);
if (random >= 2)
{
// we don't really need to create a new object if we don't want to make any changes, so
// we simply return this.
return this;
}
int amountToChange = 1;
int percentualChange = Program.GetRandom(11);
if (percentualChange > 0)
{
amountToChange = _value * percentualChange / 100;
if (amountToChange == 0)
amountToChange = 1;
}
if (random == 0)
return new IntNeuron(_value - amountToChange);
return new IntNeuron(_value + amountToChange);
}
public override string ToString()
{
return _value.ToString();
}
}
public sealed class BinaryNeuron:
INeuron
{
public static BinaryNeuron Add(INeuron neuron1, INeuron neuron2)
{
return new BinaryNeuron((a, b) => a + b, " + ", neuron1, neuron2);
}
public static BinaryNeuron Subtract(INeuron neuron1, INeuron neuron2)
{
return new BinaryNeuron((a, b) => a - b, " - ", neuron1, neuron2);
}
public static BinaryNeuron Multiply(INeuron neuron1, INeuron neuron2)
{
return new BinaryNeuron((a, b) => a * b, " * ", neuron1, neuron2);
}
private readonly Func<int, int, int?> _function;
private readonly string _operatorName;
private readonly INeuron _neuron1;
private readonly INeuron _neuron2;
public BinaryNeuron(Func<int, int, int?> function, string operatorName, INeuron neuron1, INeuron neuron2)
{
_function = function;
_operatorName = operatorName;
_neuron1 = neuron1;
_neuron2 = neuron2;
Complexity = neuron1.Complexity + neuron2.Complexity;
}
public int Complexity { get; private set; }
public int? Execute(int input)
{
var value1 = _neuron1.Execute(input);
if (!value1.HasValue)
return null;
var value2 = _neuron2.Execute(input);
if (!value2.HasValue)
return null;
try
{
return _function(value1.Value, value2.Value);
}
catch
{
return null;
}
}
public INeuron Reproduce()
{
var neuron1 = _neuron1.Reproduce();
var neuron2 = _neuron2.Reproduce();
if (Program.GetRandom(100) != 0)
{
if (neuron1 == _neuron1 && neuron2 == _neuron2)
return this;
return new BinaryNeuron(_function, _operatorName, neuron1, neuron2);
}
return Program._ReproduceNeuron_Random(this, neuron1, neuron2);
}
public override string ToString()
{
return "(" + _neuron1.ToString() + _operatorName + _neuron2.ToString() + ")";
}
}
注意：示例中的BinaryNeuron更大，因为它处理更多的表达式。目前，我只想介绍这个想法，而不是完整的类。
主算法
主算法可以简化为
- 生成“生物”（或大脑，因为它们仅由神经元组成）的基础群体；
-
执行一个循环，该循环
- 根据它们与预期结果的匹配程度对生物进行排序；
- 检查算法是否找到了好的结果；
- 可能“杀死”并用新的第一代生物替换复杂或重复的生物；
- 繁殖最好的生物。
因此，要使主算法工作，我们必须有一些带有预期结果的输入值。在应用程序中，我首先询问将给定的输入/输出对的数量，然后询问这些对。这些输入是如何真正给定的对算法来说并不重要，但这就是我在示例中做的。
算法必须从一些“第一代”神经元开始。在我的实现中，这些神经元是随机生成的，使用
- 一些
IntNeurons可能具有1、2、3或10的值，因为大多数表达式使用这样的小值； - 任何用户提供的值作为
IntNeuron； InputNeuron；- 对其他随机生成神经元进行任何可能操作的
BinaryNeurons。
值得注意的是，神经元第一代的生成方式可能极大地提高或降低算法的质量。我没有对此进行深入研究（对于实际应用来说这可能是必要的），我只是决定使用对我来说看起来很自然的值。在我所知道的大多数公式中，至少有一个输入或输出值存在直接关系，这个值可能被乘、被减，甚至被提升到与任何其他输入/输出值或与1、2、3或10值相关的幂次方。因此，我决定将这些值用作可能出现在第一代中的值。
因此，即使第一代种群是随机生成的，它也并非简单地由“随机”值构成。
示例
此时，我强烈建议您下载示例并尝试使用如下值：
| 输入 | 输出 |
| 1 | 8 |
| 2 | 64 |
| 3 | 216 |
或
| 输入 | 输出 |
| 1 | 2 |
| 10 | 11 |
| 57 | 58 |
或者更复杂的值，例如
| 输入 | 输出 |
| 1 | 1 |
| 2 | -4 |
| 3 | 3 |
| 4 | -8 |
| 11 | 11 |
| 12 | -24 |
或
| 输入 | 输出 |
| 1 | 1 |
| 2 | 0 |
| 3 | 3 |
| 4 | 0 |
| 5 | 5 |
| 6 | 0 |
需要注意的是，示例中只使用了整数变量。因此，1 / 2最终结果为零。如果稍后乘以2（或任何其他值），它将保持零结果。
因此，如果您发现先除再乘以相同值的公式，请务必考虑到这一点，因为最终值可能是零而不是原始值。
问题
我希望您已经测试了示例应用程序。也许您会发现有时它很快给出结果，有时很慢，或者根本找不到结果，并且对于相同的输入/预期结果，它可能会生成不同的公式。
这都与遗传算法面临的“问题”有关。所以我会尝试解释其中一些问题。
多样性
拥有足够多的“生物”可供选择是很重要的。我选择一次使用5700个生物。一次只使用少量生物可能不好，因为我们在尝试寻找结果时可能只朝“一个方向”发展。如果它们能像现实生活中那样真正并行工作，那么使用更多的生物将是最好的解决方案，但在计算机中，它们会消耗CPU时间。因此，我们必须尝试使用一个足够大的值，以在不成为性能问题的情况下实现多样性。
我试图通过繁殖一半“最佳生物”（每个生物有2个子代，这就是它们填充所有5700个可用生物的方式）来保持多样性。我可以使用不同的公式，例如允许所有生物中最优秀的生物拥有比其他生物更多的子代。我非常确定这里可以进行许多优化。
我没有强行实现多样性。通过保留神经元“组”可以做到这一点。例如，创建非复杂神经元组和复杂神经元组……或者只使用基本数学运算的神经元组和使用其他运算的神经元组。事实上，表达式的复杂性只使用所涉及的神经元数量来计算，但在更好的算法中，我们可以将更容易解决的运算（如加法）分类为比涉及除法或幂运算的表达式更简单。
选择最佳结果
生物体的多样性和“朝着一个方向”实际上是另一个问题的一部分。我们如何选择最佳结果？
样本处理数学公式，生成整数结果。那么...
- 我们应该只使用预期值与生物体给出结果之间的差异吗？
- 我们应该考虑正确值的数量与错误值的数量，而不考虑差异的大小吗？
- 我们应该结合使用这些方法吗？还是采用其他类型的分析？
为了解释这个问题，考虑输入值1、2和3，以及结果11、12和13。
如果我们只考虑有多少结果得到了正确的值，那么像F(x) = x + 9这样的表达式会比像F(x) = x * 6这样的表达式差。这是因为x * 6至少能得到输入 2 -> 结果 12正确，而另一个表达式会错过所有值。
如果我们只考虑与正确值的差异之和，那么x + 9将优于x * 6。毕竟，即使它现在没有给出任何正确值，对于每个输入，它也只差1，总差异为3。另一个公式与预期结果值的总差异为10。
但是公式F(x)=12（是的，一个常数）如果与其他两个解决方案相比，将被认为是最好的。它将得到一个正确的值，而对于其他值，总差异只有2。但我们知道，一个简单的常数永远无法为所有输入提供正确的值。一个真正的公式（加法公式）可以做到，并且它非常接近正确结果（将9改为10，它就能找到正确答案）。
现在想象一下，我们只使用“最佳”公式进行繁殖（在这种情况下，常数 12）。它可以繁殖出 11 和 13（甚至其他值）。然而 12 将是最好的结果。考虑到我的实现，常数变量永远不会繁殖成两个细胞，所以我们将陷入无解的境地，仅仅因为“最佳”解决方案的发现使用了错误的分析来获得最佳结果。
这实际上意味着决定哪个生物提供最佳结果非常重要，因为一个糟糕的决策可能会将算法引导至次优结果。这就是为什么说大多数遗传算法需要领域特定的方式来选择最佳候选者（或领域特定的适应度函数）。然而，遗传算法用于更复杂的情况，我们并不知道答案，所以我们尝试使用“公平”的选择，为了解决那些我们没有真正选择最佳解决方案的情况，我们保持了良好的多样性，这样一些不太好的替代方案（由进行分析的函数判断）可能会演变为最佳方案。
示例算法
在我的算法中，我认为只给出单个正确结果的表达式并不优于所有结果都错误的表达式（这是为了避免将给出某个结果值的常数视为优于实际公式）。然而，为了尝试朝着正确的方向发展，使用了与预期结果的总差异加上表达式的复杂性。值越小，“越好”。
当一个表达式生成两个或更多个好的结果时，它被认为比生成较少好结果的表达式更好，而与结果的总差异无关。但是，与另一个生成相同数量好结果的表达式相比，我们仍然考虑与预期结果的总差异加上复杂性。最终，我们首先受益于具有更多好结果的表达式，然后是那些更简单且与预期结果差异更小的表达式。
当然，这可能仍然存在问题。我们可能会有一个公式，它拥有所有正确的运算符，只是缺少常量值，却被一个运算符完全错误但目前给出“更好值”的公式所淘汰。因此，这是一个对于专业用途来说非常重要的领域。
突变率
突变率是另一个非常重要的特征。如果它太小，我们可能会运行几代“相同”的表达式，仅仅因为种群没有变化，我们知道这样做会带来性能问题。
如果突变因子太大，我们可能在某一代中接近结果，而在下一次运行时却偏离太远，表达式中变化的项比需要的要多得多。
在我看来，如果我们能保证每次生物繁殖有1到2次突变，并且绝不允许没有突变或突变过多，那会更好。但示例算法只是随机的。它可能在每次繁殖中进行更多改变，也可能在繁殖后不进行任何改变。我尝试将突变率配置为适合我（通常是非常小的公式），但能够调整突变率（也许将它们存储为细胞/生物本身的特征）可能有助于产生更好的结果（或者只是更快地找到它们）。
交叉？
我的算法根本不处理交叉。我认为可能的交叉工作方式如下：
- 简单细胞不发生交叉。如果涉及简单细胞，则要么返回简单细胞，要么返回“另一个”细胞，无论另一个细胞是否简单；
- 考虑到我们只有两种细胞，当一个二元细胞尝试与另一个二元细胞交叉时，它的任一子表达式都可能被另一个细胞的任一子表达式替换，但交叉不一定发生在每个细胞上（就像繁殖时突变不发生在每个细胞上一样），所以一个二元细胞可能不直接交叉，但它可能会要求它的一个子细胞与另一个二元细胞的一个子细胞交叉。这意味着在大型表达式中，我们可能有大的交叉（例如直接取另一个表达式的一半）或只有小的交叉。
正如我已经说过的。我没有在这个示例中这样做……如果你想，请随意尝试。
次优解
遗传算法可能出现的问题之一是产生次优解。正如已经解释的，生成种群的多样性是为了避免在特定时刻“看起来更好”的劣质生物杀死优秀的生物。
但实际上，次优解决方案存在两个问题。一个问题是永远找不到解决方案，仅仅是因为我们正在试图进化错误的生物（或者可能根本没有完美的解决方案）。另一个问题是找到了一个有效的解决方案，但它做了比所需更多的工作。
在示例应用程序中，如果它没有找到所有正确答案，它将永远不会给你一个结果。在现实世界中，我们可能有来自“90%正确”来源的输入数据。因此，即使结果不是100%正确，我们也可能希望得到一个答案。
除此之外，通过运行示例应用程序，您会看到，如果输入像：1、2、3，必须生成像11、12、13这样的值，那么您可能会得到(9 + x) + 1这样的结果。这是另一种次优解，因为表达式比它需要的大。
实际上，样本会在第一个能为所有输入值提供有效结果的表达式处停止，无论其复杂性如何。对于实际情况，即使找到100%有效的解决方案，也可能继续寻找更好的解决方案。我们采取不同的做法，继续寻找给出相同结果但更简单（执行更快，操作更少等）的解决方案。
我们绝不能忘记遗传算法可以与其他解决方案结合使用。例如，将像(9 + x) + 1这样的表达式转换为像x + 10这样的表达式，可以通过专门简化表达式的算法轻松完成。这样的算法可能完全无法为某些输入和输出集发现表达式，但在通过消除“无操作”（如x * 0）、替换评估为常量的操作（如(x + x) / x变为2）甚至找到更快的操作（x power 3如果写成x * x * x可能会更快）来简化已生成的表达式方面做得非常出色。
放弃
该示例尝试在 5700 次迭代中找到解决方案。如果找不到，它会完全重置。也就是说，它会创建一个全新的初始种群并重新开始。作为用户，您可以随时停止它，但算法本身如果找不到解决方案将永远不会停止，它只会进行这些重置。
对于更专业的解决方案，算法本身可以被编程为在一段时间内找不到解决方案或在一定次数的迭代后看不到任何进化时放弃。而且，根据情况，它们仍然会给出一个结果，表明它不是100%正确但“可接受”。
并行化
许多文档都说遗传/进化算法是并行化的绝佳候选，但我提供的示例没有使用任何并行化。
我实际上试图保持代码简单。通过将大多数for循环替换为Parallel.For()方法，可以很容易地使其并行化。问题是Random类不是线程安全的，因此在调用Random.Next()方法时需要进行锁定。嗯，锁定实际上会降低代码的实际并行性，所以，如果我们要真正并行运行，最好的方法是忽略Parallel.For()方法，为每个CPU分配一个线程，每个线程都持有自己的Random实例，并且每个线程都知道应该在数组的哪个部分工作。重要的是要用不同的种子初始化每个Random实例，否则两个或更多CPU可能会一直生成完全相同的值。
因此，即使算法本身已准备好并行化，因为一个生物不依赖于其他生物，但Random类不是线程安全的这一事实意味着我们应该找到一个解决方案，在我看来，这不应该成为本文的一部分，因为有许多不同的方法可以解决这个问题，我认为探讨它们本身就足以构成一篇完整的文章。
结论
遗传和进化算法并不难。它们是简单的算法，由于缺乏更好的替代方案，它们将随机生成的值作为其过程的一部分。真正让它们变得困难的是糟糕的示例以及它们被用来解决非常复杂的问题并与其他复杂算法一起使用的事实。但是，当它们被很好地隔离时，它们是简单的算法，通过一些随机变化来不断繁殖好的解决方案，以尝试做得更好。
最终，进化算法帮助我们取得了令人难以置信的成果，而无需我们完全理解正在解决的问题。