遗传算法是如何工作的
算法概述
下面的大纲总结了遗传算法的工作原理:
该算法首先创建一个随机初始种群。
然后，算法会创建一个新的种群序列。在每一步，算法都使用当前这一代的个体来创建下一个种群。为了创建新的种群，算法执行以下步骤:
通过计算当前群体中的每个成员的适应度值对其进行评分。这些值称为原始适应度分数。
对原始的适合度分数进行测量，将其转换为更可用的值范围。这些缩放后的值称为期望值。
根据他们的期望，选择被称为家长的成员。
当前人群中一些适合度较低的个体被选为精英．这些精英个体被传给下一个种群。
从父母那里生出孩子。孩子的产生要么是通过对单亲的随机改变突变-或通过组合一对父元素的向量项-交叉．
用儿童取代现有人口，形成下一代。
当满足停止条件之一时，算法停止。看到算法的停止条件．
该算法对线性和整数约束采取改进的步骤。看到整数和线性约束．
针对非线性约束条件，进一步改进了算法。看到非线性约束求解算法．
初始种群
算法首先创建一个随机初始种群，如下图所示。
在本例中，初始种群包含20.个人。注意，初始种群中的所有个体都位于图的右上象限，也就是说，它们的坐标在0到1之间。对于本例，InitialPopulationRange选择是[0, 1]．
如果你知道函数的最小值点的大致位置，你应该设置InitialPopulationRange所以这个点在这个范围的中间。例如，如果你相信拉斯特里金函数的最小值点在这个点附近[0 0]，你可以设置InitialPopulationRange是(1; 1)．然而，如这个例子所示，遗传算法可以找到最小值，即使小于最优选择InitialPopulationRange．
创造下一代
在每一步，遗传算法都使用当前的人口来创造下一代。算法选择当前种群中的一组个体，称为父母，他们贡献了自己的力量基因-他们的带菌者的条目-传给他们的孩子。该算法通常选择适应度值较高的个体作为父母。属性中选择父级的算法使用的函数SelectionFcn选择。看到选择选项．
遗传算法为下一代创造了三种类型的孩子:
精英是当前这一代拥有最佳适应度值的个体。这些个体自动存活到下一代。
交叉是由一对父母的向量组合而成的。
突变孩子们是通过向单亲引入随机变化或突变而产生的。
下面的示意图说明了这三种类型的孩子。
变异和交叉说明如何指定算法生成的每种类型的子节点的数量及其用于执行交叉和变异的函数。
下面几节解释该算法如何创建交叉和变异子节点。
交叉的孩子
该算法通过结合当前人口中的父母对来创建交叉子女。在子向量的每个坐标上，默认交叉函数随机选择一个条目，或基因，并将其分配给子节点。对于线性约束的问题，默认的交叉函数将子节点创建为父节点的随机加权平均值。
突变的孩子
该算法通过随机改变父母个体的基因来产生突变子。默认情况下，对于不受约束的问题，算法将从高斯分布添加一个随机向量到父向量。对于有界或线性约束的问题，子结点仍然是可行的。
下图显示了初始种群的后代，即第二代种群的后代，并指出了他们是精英、跨界还是突变的后代。
后代人的地块
下图显示了迭代60、80、95和100时的种群。
|
|
|
|
|
|
随着世代数的增加，种群中个体之间的距离越来越近，逼近最小值点[0 0]．
算法的停止条件
遗传算法使用以下选项来决定何时停止。通过运行查看每个选项的默认值选择= 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，则最优适应度值只能由一代下降到下一代。这就是你想要发生的，因为遗传算法使适应度函数最小化。设置EliteCount值越高，适者生存的个体占种群的主导地位，搜索效率就越低。CrossoverFraction-除精英子女外，跨界创造的下一代个体的比例。设置交叉分数的值如何CrossoverFraction影响遗传算法的性能。
因为精英已经被评估过了，遗传算法在繁殖过程中不重新评估精英个体的适应度函数。这种行为假设个体的适应度函数不是随机的，而是一个确定的函数。要更改此行为，请使用输出函数。看到EvalElites在国家结构．
变异和交叉
遗传算法利用当前这一代的个体来创造下一代的孩子。除了精英儿童(elite children)，它对应的是当前这一代拥有最佳适应度值的个体
通过从当前这一代的一对个体中选择载体条目或基因，并将它们组合成一个孩子
通过对当前这一代的单个个体应用随机变化来产生一个孩子
这两个过程对遗传算法来说都是必不可少的。交叉使算法能够从不同的个体中提取出最好的基因，并将它们重新组合成可能更优秀的后代。突变增加了种群的多样性，从而增加了算法产生具有更好适应度值的个体的可能性。
看到创造下一代以举例说明遗传算法如何应用变异和交叉。
你可以指定算法创建的每种类型的子元素的数量，如下所示:
EliteCount指定精英子女的数量。CrossoverFraction指定除精英子女外，人口中跨性别子女的比例。
例如，如果PopulationSize是20.,EliteCount是2,CrossoverFraction是0.8，每一种类型的孩子在下一代的数量如下:
有两个优秀的孩子。
除精英儿童外，共有18个个体，因此算法将0.8*18 = 14.4 ~ 14轮算得到跨界儿童的数量。
剩下的四个个体，除了精英儿童之外，都是突变儿童。
整数和线性约束
当一个问题有整数或线性约束(包括边界)时，算法修改种群的进化。
当问题有整数和线性约束时，软件修改所有生成的个体，使其在这些约束下是可行的。您可以使用任何创建、变异或交叉函数，并且整个种群对于整数和线性约束仍然是可行的。
当问题只有线性约束时，软件不会根据这些约束修改个体以使其可行。必须使用相对于线性约束保持可行性的创建、变异和交叉函数。否则，人口会变得不可行的，结果也会不可行的。默认操作符保持线性可行性:
gacreationlinearfeasible或gacreationnonlinearfeasible为创造,mutationadaptfeasible突变,crossoverintermediate交叉。
整数可行性和线性可行性的内部算法类似于surrogateopt．当问题有整数约束和线性约束时，算法首先创建线性可行点。然后，该算法试图通过使用试图保持线性可行点的启发式算法将线性可行点舍入为整数来满足整数约束。当这个过程不能获得足够的可行点来构建种群时，算法调用intlinprog试着找到更多关于边界，线性约束，和整数约束的可行点。
之后，当变异或交叉产生新的种群成员时，算法通过相似的步骤确保新成员是整数且线性可行的。如果有必要，每个新成员都会被修改，使其尽可能接近其原始值，同时也满足整数和线性约束和边界。
相关的话题
你也可以从以下列表中选择一个网站:
