主要内容

遗传算法是如何工作的

算法概述

下面概述了遗传算法的工作原理:

  1. 算法首先创建一个随机的初始种群。

  2. 然后，该算法创建一个新的种群序列。在每一步中，算法使用当前代中的个体来创建下一个种群。为了创建新的种群，算法执行以下步骤:

    1. 通过计算当前种群的每个成员的适应度值来评分。这些值被称为原始健康分数。

    2. 缩放原始健康分数，将其转换为更可用的值范围。这些按比例缩放的值称为期望值。

    3. 根据他们的期望选择成员，称为父母。

    4. 当前种群中适应度较低的个体被选为精英．这些精英个体被传递给下一个群体。

    5. 从父节点生成子节点。孩子的产生要么是通过随机改变一个单一的父母-突变-或通过组合一对父元素的向量项-交叉．

    6. 用后代替换当前的种群，形成下一代。

  3. 当满足其中一个停止条件时，算法停止。看到算法停止条件．

  4. 该算法对线性约束和整数约束进行了改进。看到整数和线性约束．

  5. 针对非线性约束，进一步改进了算法。看到非线性约束求解算法．

初始种群

算法首先创建一个随机的初始种群，如下图所示。

在本例中，初始填充包含20.个人。注意，初始种群中的所有个体都位于图的右上象限，也就是说，它们的坐标位于0到1之间。对于本例，使用InitialPopulationRange选择是[0, 1]．

如果你大概知道一个函数的最小值点在哪里，你应该设置InitialPopulationRange所以这个点在这个范围的中间。例如，如果你认为Rastrigin函数的最小值点在这个点附近[0 0]，你可以设置InitialPopulationRange是(1; 1)．然而，正如这个例子所示，遗传算法可以在小于最优选择的情况下找到最小值InitialPopulationRange．

创造下一代

在每一步中，遗传算法使用当前的种群来创建组成下一代的子种群。该算法在当前种群中选择一组个体，称为父母，他们贡献了基因-向量的分量-到子结点。该算法通常选择适合度值较高的个体作为亲本。控件中选择父节点时使用的函数SelectionFcn选择。看到选择选项．

遗传算法为下一代创造了三种类型的孩子:

  • 精英是当前这一代人中拥有最佳健身价值观的人。这些个体会自动存活到下一代。

  • 交叉由一对父向量组合而成。

  • 突变孩子们是通过将随机变化或突变引入单个亲本而产生的。

下面的示意图说明了三种类型的儿童。

精英子女与其父母完全相同。一个交叉的孩子得到了父母双方的一些。一个突变子来自一个亲本，并且包含一个变化。

突变与交叉解释如何指定算法生成的每种类型的子类型的数量以及用于执行交叉和突变的函数。

下面几节将解释该算法如何创建交叉和突变子算法。

交叉的孩子

该算法通过结合当前人口中的父母对来创建交叉儿童。在子向量的每个坐标上，默认交叉函数随机选择一个条目或基因，并将其分配给子节点。对于线性约束的问题，默认的交叉函数将子函数创建为父函数的随机加权平均值。

突变的孩子

该算法通过随机改变单个父母的基因来产生突变的孩子。默认情况下，对于无约束的问题，该算法从高斯分布中添加一个随机向量到父向量。对于有界或线性约束的问题，子问题仍然可行。

下图显示的是初始种群的后代，即第二代种群，并表明他们是精英后代、交叉后代还是突变后代。

后人的情节

下图显示了迭代60、80、95和100时的填充。

人口分布广泛

中等分散人口

人口分散度低

人口集中到一个点

随着代数的增加，种群中的个体越来越接近，并接近最小值[0 0]．

算法停止条件

遗传算法使用以下选项来确定何时停止。通过运行查看每个选项的默认值Opts = optimoptions('ga')．

  • MaxGenerations—当代数达到时，算法停止MaxGenerations．

  • MaxTime—算法运行一段时间(秒)后停止运行MaxTime．

  • FitnessLimit—当当前种群中最优点的适应度函数值小于或等于时，算法停止FitnessLimit．

  • MaxStallGenerations—当适应度函数值的平均相对变化结束时，算法停止MaxStallGenerations小于功能公差．

  • MaxStallTime—如果目标函数在一段时间(秒)内没有改善，算法将停止MaxStallTime．

  • FunctionTolerance-算法运行直到适应度函数值的平均相对变化结束MaxStallGenerations小于功能公差．

  • ConstraintTolerance- - -ConstraintTolerance不用作停止判据。它被用来确定关于非线性约束的可行性。同时,max (sqrt (eps), ConstraintTolerance)确定线性约束的可行性。

只要满足这些条件中的任何一个，算法就会停止。

选择

选择函数根据适应度缩放函数中父母的缩放值选择下一代的父母。缩放后的适应度值称为期望值。一个人可以被选择不止一次作为父母，在这种情况下，它将其基因贡献给一个以上的孩子。默认的选择选项，@selectionstochunif，表示一条直线，其中每个父结点对应于长度与其缩放值成比例的直线的一段。算法沿着这条线以相同大小的步骤移动。在每一步中，算法从它所在的部分分配一个父节点。

一个更具确定性的选择选项是@selectionremainder，执行两步:

  • 在第一步中，该函数根据每个个体的缩放值的整数部分确定地选择父元素。例如，如果一个个体的缩放值是2.3，该函数会选择该个体两次作为父对象。

  • 在第二步中，选择函数使用缩放值的小数部分选择额外的父母，就像随机均匀选择一样。该函数以分段的方式布局一条直线，其长度与个体缩放值的小数部分成正比，并沿着直线以相等的步长移动以选择父结点。

    请注意，如果缩放值的小数部分都等于0，可以使用前缩放，选择是完全确定的。

有关详细信息和更多选择选项，请参见选择选项．

复制选项

繁殖选项控制着遗传算法如何创造下一代。选项有

  • EliteCount-在当代中具有最佳适应度值且保证能存活到下一代的个体数量。这些人被称为精英的孩子．

    当EliteCount至少为1时，最佳适应度值只能从一代递减到下一代。这就是你想要的结果，因为遗传算法最小化了适应度函数。设置EliteCount到一个高的值会导致最适合的个体主导种群，这可能会降低搜索的有效性。

  • CrossoverFraction-在下一代中，除了精英子女，通过跨界培养出来的个体所占的比例。主题“设置交叉分数”变异、突变和交叉的值CrossoverFraction影响遗传算法的性能。

因为精英已经被评估过了，遗传算法在繁殖过程中不重新评估精英个体的适应度函数。这种行为假设个体的适应度函数不是随机的，而是一个确定的函数。要改变这种行为，请使用输出函数。看到EvalElites在国家结构．

突变与交叉

遗传算法使用当前一代的个体来创造组成下一代的孩子。除了精英子女(对应于当前一代中拥有最佳适应度值的个体)，算法还会创建

  • 通过从当前一代的一对个体中选择矢量条目或基因来杂交孩子，并将它们组合成一个孩子

  • 通过对当前代中的单个个体应用随机更改来创建子节点，从而对子节点进行突变

这两个过程对遗传算法都是必不可少的。交叉使算法能够从不同的个体中提取出最好的基因，并将它们重新组合成潜在的优秀后代。突变增加了种群的多样性，从而增加了算法生成具有更好适应度值的个体的可能性。

看到创造下一代举例说明遗传算法如何应用突变和交叉。

您可以指定算法创建的每种类型的子类型的数量，如下所示:

  • EliteCount指定精英子女的数量。

  • CrossoverFraction指定除精英儿童外，属于交叉儿童的人口比例。

例如，如果PopulationSize是20.,EliteCount是2，以及CrossoverFraction是0.8，每一类儿童在下一代中的数量如下:

  • 有两个精英孩子。

  • 除精英儿童外，共有18个个体，因此算法舍入0.8*18 = 14.4到14，得到交叉儿童的数量。

  • 除了精英儿童外，其余4人都是突变儿童。

整数和线性约束

当一个问题有整数或线性约束(包括边界)时，算法修改种群的进化。

  • 当问题同时具有整数和线性约束时，软件修改所有生成的个体，使其相对于这些约束是可行的。您可以使用任何创建、突变或交叉函数，并且整个种群相对于整数和线性约束仍然是可行的。

  • 当问题只有线性约束时，软件不会根据这些约束修改个体以使其可行。您必须使用与线性约束相关的保持可行性的创建、变异和交叉函数。否则，总体就变得不可行的，结果也就不可行的。默认操作符保持线性可行性:gacreationlinearfeasible或gacreationnonlinearfeasible为创造,mutationadaptfeasible对于突变，和crossoverintermediate交叉。

整数可行性和线性可行性的内部算法与线性可行性的内部算法相似surrogateopt．当问题具有整数和线性约束时，算法首先创建线性可行点。然后，该算法尝试通过使用尝试保持点线性可行的启发式将线性可行点舍入为整数来满足整数约束。当这个过程无法获得足够的可行点来构建总体时，算法调用intlinprog试着找到更多在边界，线性约束和整数约束下可行的点。

之后，当突变或交叉创建新的种群成员时，算法通过相似的步骤确保新成员是整数和线性可行的。如果需要，修改每个新成员，使其尽可能接近其原始值，同时满足整数和线性约束和边界。

相关的话题