遗传算法简介及代码详解

简述遗传算法和代码细节声明：本文件的内容是在网上整理的，认为原作者同意转载，如果有失礼的话请联系我。遗传算法的基本内容遗传算法是集体优化算法，即从多个初始分解开始优化，每个解决方案称为一条染色体，每个染色体都通过竞争、合作、单独变异进行了进化。遗传学和遗传算法的基本术语比较染色体(chromosome)数据，数组，序列基因(gene)个别元素，位元等位基因(allele)数据值、属性和值基因座(locus)位置，iterator位置表示型(phenotype)参数集、解码结构、候选解决方案染色体：也可以称为遗传型个体群体/群体：特定数量的个体组成，特定数量的染色体组成，组中的个体数量数量称为组大小。早期群体：多个染色体的集合，即解决方案的大小，例如30、50等，被认为是随机选择的数据集合。可变性：个人对环境的适应程度如何优化时要把实际问题转化为遗传空间。也就是说，将实际问题的解码表示为染色体，逆向过程是解码/解码。优化后评估(此时获得的解决方案是否比以前的解决方案优越)，因此必须返回问题空间解密。SGA使用二进制符号，染色体是二进制符号，每个都可以说是基因。如果直接生成二进制初始群体，则无需编码过程，但在需要解码时，将染色体解码在问题的可执行区域内。基因算法准备：1)数据转换操作，包括从表型到基因型的转换和从基因型到表型的转换。前者将解决方案空间的参数转换为遗传空间的染色体或个体，后者是反操作(2)确定适合度计算函数。该函数通过充分显示解决方法有多好的拟合度计算函数将各个值转换为相应个人的拟合度。非常重要的过程。遗传算法的基本过程是：1)编码，创建初始组2)计算组的个人适合性3)资格评估4)根据适应性图选择个人5)选择进行交叉繁殖的实体6)在繁殖过程中引入变异机制7)繁殖新群体，返回第二阶段示例1:(建议从示例2开始查看。)在范围中查找最小值1)选择编码算法为“转换为二进制字符串”，字符串长度为5个字符(字符串长度可以解释为更长，具体取决于解决方案的精度设置)。(等位基因的值为0 or 1)。2)首先解码单个字符串，将其转换为int型x值，然后使用该适合性计算相应的值(因为是最小值，所以结果越小越合适)。将原始目的函数设置为适合性函数是可选的，但可能不是最合适的方法。3)正式开始，将群体大小设置为4，然后将群体=(在0，31范围内随机选择4个整数进行编码)4)可变Fi计算(由于解决方案的最小值，您可以选择大基线1000之一)，以获取详细信息(5)计算每个人的选择概率，选择概率要能反映个人的优秀度。这里有一个很简单的决定选择概率的方法6)选择根据所有个人的选择概率进行淘汰选择。这里使用的是赌轮的去除方法。首先，根据每个对象的选择概率创建赌局，然后生成4次，每次0-1的随机十进制数，并确保在该线段内选择相应的对象。在这个过程中，选择概率高的对象可以被多次选择，概率低的对象可以被淘汰。以下是简单赌博车轮的示例13% 35% 15% 37%-是-是-是-是-物件1物件2物件3 0.67物件4随机数是0.67在对象4的末尾，这次选择了对象4。选定的对象将进入准备开始繁殖的配对池。7)简单交集首先，将配对库中的实体随机配对，然后在成对的两个实体上设置交集，交换两个实体的信息，最后创建下一层代。例如(|表示简单字符串的交点位置)(0110|1，1100 | 0)-交集-(01100，11001)(01|000，11 | 011)-交集-(01011，11000)两个父系的物件相交后，产生了下一代相同数量的物件。复杂的交点在交点，交点的方法，双亲都可以选择。其目的是尽可能培养优秀的后代8)变异每计算2万个基因座就发生变异(目前每个个体有5个基因座)。1，000代进化后，其中一个基因座发生了变异)变异，结果基因座的等位基因发生了变化。其中范例是将0变更为1，或将1变更为0。此时，我们创建了一个新的(下一代)群体，然后回到第四阶段继续生活。范例2:为了便于理解，手动计算以简单模拟遗传算法的各个关键执行步骤：(1)个别代码遗传算法的运算对象是表示对象的符号字符串，因此必须将变量x1，x2编码为某种符号字符串。在这个语句中，用无符号二进制整数(有更多的编码方法)表示。X1，x2是0-7之间的整数，因此分别表示为3位无符号二进制整数，将它们组合在一起的6位无符号二进制数构成了对象的基因型，表示了可行的解决方案。例如，基因型x=的表型为x=5，6。可以在对象的表型x和基因型x之间通过编码和解码程序相互转换。(2)创建初始组遗传算法是对群体的进化计算，需要为淮河准备一些表示开始搜索点的早期群体数据。在此范例中，群组大小的大小(随机选取)为4。也就是说，群组包含4个物件，每个物件都可以随机产生。例如：(3)适宜性果汁计算遗传算法中，以个别适合度的大小评估每个人的优劣，以确定其遗传机会的大小。在此示例中，目标函数始终采用非负值，并将函数的最大值作为优化目标，因此可以直接使用目标函数值作为个人的适合性(适合性函数可以有多个)。(4)选择运算选择运算(或克隆运算)，根据一定的规则或模型将更多适应当前群体的对象遗传给下一代。一般来说，适应性高的个人会给下一代群体更多的机会。在此示例中，我们使用与适应性成比例的概率来确定每个对象复制到下一代的数量。具体的操作过程如下：首先计算组中所有个人的适应性。第二，计算每个个体的相对适应能力大小，这是每个个体遗传给下一代的概率。每个概率值构成所有概率值之和为1的面积。最后，根据上述概率区域中的随机数出现在哪个区域，再生成一个介于0和1之间的随机数，确定每个对象被选择的次数。(请参阅下图。)(5)交叉运算交叉运算是遗传算法中生成新实体的主要操作过程，以某种概率在两个实体之间交换一些染色体。本范例使用单点相交方法，具体程序如下：先把群体随机配对。其次，随机设定交点位置。最后，染色体之间的一些基因相互交换。(6)转移运算突变运算是将个体的一个或部分基因座中的基因值转化为某种小概率，也是产生新个体的一种操作手段。在此范例中，使用以下基本位元转移方法执行转移运算：首先找出每个人的基因变异位置，下表显示随机生成的变异点的位置，这里的数字表示变形点设置在基因座上。然后根据某种概率反转变异点的原始基因值。选择、交叉、变换组P(t)以获得下一代组p(t 1)。如上表所示，群体通过一代人的进化，其适应度的最大值和平均值有了很大改善。事实上，这是最好的物体。请参阅必须说明表中某些列的数据是随机生成的。在这里，为了更好地说明问题，我们特别选择了更好的值，以便取得更好的结果。实际运算可能需要一定的周期数来获得此最佳结果。选择能够合理反映“适者生存法则”的自然法则，交叉应尽可能传给下一代的有利基因(这就是算法中的关键！)，以获取详细信息算法过程有几个随机过程。(1)初始群体的发生是随机发生的，但有时为了更好地重复，可以知道并承认在特定值附近存在解决方案设定初始总量(2)在决定个人选择的次数时，结果是随机数据(3)交点(4)转移点伪代码：/Init populationForeach individual in populationIndividual=Encode(Random(0，31)；While (App .IsRun)/计算个别符合性int TotalF=0；Foreach individual in populationindividual . f=1000-(decode(individual)-10)2；TotalF=individual。f；/选择过程，计算单个选择概率-Foreach individual in populationindividual . p=individual . f/totalf；/选择for(int I=0)；i4；I)/SelectIndividual(float p)是根据任意数字计算段落中选定对象的函数mating poolI=populationselect individual(random(0，1)；/简单交集-/配对2次，因为只有4个对象for(int I=0)；I2；I)Matingpool.parents I。mother=mating pool . random pop()；Matingpool.parents I。father=mating pool . random pop()；/相交后创建新组Population。clean()；foreach parent in mating pool . parents/复制父母的染色体时，注意没有出现发生在哪个基因座的变异。child 1=parent . mother . div header parent . father . divend；child 2=parent . father . div header parent . mother . divend；population . push(child 1)；population . push(child 2)；完整的代码如下：# include“stdafx . h”#include#include#include#define POPSIZE 500#define MAXIMIZATION 1 /解析函数用于最大值#define MINIMIZATION 2 /解决最小值的函数#define Cmax 100 /解决最大值时可变函数的基准数# define cmii 0/求解最小值时可变函数的基准数#define LENGTH1 10 /每个解决方案都用位基因表示#define LENGTH2 10# define chrom length 1 length 2Int FunctionMode=MAXIMIZATION/函数值解析类型为最大值Int PopSize=80/人口规模Int MaxGeneration=100/最大层代数，即最大迭代数双Pc=0.6/变异概率双Pm=0.001/交叉概率Struct individual /个别定义char chro