遗传算法的操作步骤是什么

A. 遗传算法选中次数怎么算

遗传算法选中次数算法如下：

1、在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T。

2、随机产生U中的N个个体s1, s2, sN，组成初始种群S={s1, s2, sN}，置代数计数器t=1。

3、计算S中每个个体的适应度f() 。

4、若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。

5、按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1。

6、按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2。

7、按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3。

8、将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3。

相关基本概念：

1、个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。

2、种群就是模拟生物种群而由若干个体组成的群体, 它一般是整个搜索空间的一个很小的子集。

3、适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。

4、适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。

B. 遗传算法理解

遗传算法是一种进化算法，进化是什么哪？就是种群逐渐适应生存环境，种群中个体不断得到改良的过程。

遗传算法是一种对生物遗传的模拟、在算法中，初始化一个种群，种群中的每个染色体个体都是一种解决方案，我们通过适应性fitness来衡量这个解决方案的好坏。并对它们进行选择、变异、交叉的操作，找到最优的解决方案。

总结一下遗传算法的基本的步骤：

1.初始化一个种群，并评估每条染色体所对应个体的适应度。

2.选择、交叉、变异，产生新的种群

3.再评估每个个体的适应值，如果适应值达到要求或者达到最大循环次数，否则重复2，不断产生新种群。

知道了GA的大致流程之后、来具体分析一下细节，怎么实现吧

我们知道遗传算法起源于生物遗传，因此在种群中每个个体就是一个染色体，那如何对染色体进行编码，让它表示我们的解决方案那（就是把现实要优化的参数用编码表示成一个染色体）。这里就遇到了一个编码、解码的问题，我们将需要优化的目标编码成染色体，然后再解码为我们可以用来计算fitness的解；

一般在进行参数优化时，一般有两种方式：实数编码、二进制编码

实数编码：基因直接用实数进行表示，这样的表示方法比较简单，不用特意解码了，但是在交叉和变异时，容易过早收敛，陷入局部最优。

二进制编码：将基因用二进制的形式表示，将参数的值转化为二进制形式，这样交叉、变异时更好操作，多样性好，但是占用的存储空间大，需要解码。

染色体就称为个体。对于一次实验，个体就是需要优化参数的一种解、许多这样的个体就构成了种群。

在面对群体中那么多个体时，如何判断个体的好坏呢，就是通过适应值函数了，将解带入适应值函数，适应值越大、解越好。

在遗传算法中，我们怎么使得里面的个体变得越来越优秀呢？

核心思想就是：选择优秀的、淘汰不好的，并且为了生成更好的解，我们要尝试交叉、变异，带来新的解。

选择就是从当前的种群中选择出比较好的个体、淘汰不好的个体

常见的选择方法有：轮盘赌选择、锦标赛选择、最佳保留选择等等

轮盘赌选择就是根据每个个体fitness和种群所有fitness之和比较，确定每个个体被选中的概率，然后进行n次选择，选择n个个体构成新种群，是一种放回抽样的方式。

锦标赛就是每次从种群中选择m个个体，选择最优的，放入新种群，重复选择，直到新种群中个体数目达到n。

最佳保留选择就是在轮盘赌的基础上，将fitness个体先加进新种群，因为轮盘赌是一种概率模型，可能存在最优个体没有进入新种群的情况。

在选择之后，就要考虑产生新的、更优秀的解，为种群带来新的血液。遗传算法的思路是交叉两个优秀的解，往往get好的解。

交叉通过在经过选择的种群中，随机选择一对父母，将它们的染色体进行交叉，生成新的个体，替代原来的解。

常用的交叉方法有：单点交叉、多点交叉等等。

交叉就像生物里面，染色体交换基因一样的～但是并不是种群中所有个体都进行交叉的，实现时可以，设置一个交叉率和交叉概率，随机选择种群中两个体、随机一个数，小于交叉率就进行交叉操作，并根据交叉概率判断交叉的程度，从而生成新个体，反之就保留这两个体。

变异也是一种产生新个体的方式，通过改变个体上基因，期望产生更好的解。比如在以二进制编码的个体上，将里面的0、1进行等位变化啥的，就是0变1、1变0这样。同样也要考虑变异率、变异产生的新解是不可控的，可能很好，也可能很坏，不能像交叉一样，确保一定的效果，所以往往变异率设置的比较小。

C. 遗传算法的主要步骤

为了使用遗传算法来解决优化问题，准备工作分为以下四步^{［56，57，61］}。

7.4.1 确定问题的潜在解的遗传表示方案

在基本的遗传算法中，表示方案是把问题的搜索空间中每个可能的点表示为确定长度的特征串（通常是二进制串）。表示方案的确定需要选择串长l和字母表规模k。在染色体串和问题的搜索空间中的点之间选择映射有时容易实现，有时又非常困难。选择一个便于遗传算法求解问题的表示方案经常需要对问题有深入的了解。

7.4.2 确定适应值的度量

适应值度量为群体中每个可能的确定长度的特征串指定一个适应值，它经常是问题本身所具有的。适应值度量必须有能力计算搜索空间中每个确定长度的特征串的适应值。

7.4.3 确定控制该算法的参数和变量

控制遗传算法的主要参数有群体规模Pop-Size、算法执行的最大代数N-Gen、交叉概率P_c、变异概率P_m和选择策略R等参数。

（1）群体规模Pop-Size。群体规模影响到遗传算法的最终性能和效率。当规模太小时，由于群体对大部分超平面只给出了不充分的样本量，所以得到的结果一般不佳。大的群体更有希望包含出自大量超平面的代表，从而可以阻止过早收敛到局部最优解；然而群体越大，每一代需要的计算量也就越多，这有可能导致一个无法接受的慢收敛率。

（2）交叉率P_c。交叉率控制交叉算子应用的频率，在每代新的群体中，有P_c·Pop-Size个串实行交叉。交叉率越高，群体中串的更新就越快。如果交叉率过高，相对选择能够产生的改进而言，高性能的串被破坏得更快。如果交叉率过低，搜索会由于太小的探查率而可能停滞不前。

（3）变异率P_m。变异是增加群体多样性的搜索算子，每次选择之后，新的群体中的每个串的每一位以相等的变异率进行随机改变。对于M进制串，就是相应的位从1变为0或0变为1。从而每代大约发生P_m·Pop-Size·L次变异，其中L为串长。一个低水平的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。高水平的变异率产生的实质是随机搜索。

比起选择和交叉，变异在遗传算法中是次要的，它在恢复群体中失去的多样性方面具有潜在的作用。例如，在遗传算法执行的开始阶段，串中一个特定位上的值1可能与好的性能紧密联系，也就是说从搜索空间中某些初始随机点开始，在那个位上的值1可能一致地产生适应性度量好的值。因为越好的适应值与串中那个位上的值1相联系，复制作用就越会使群体的遗传多样性损失。当达到一定程度时，值0会从整个群体中的那个位上消失，然而全局最优解可能在串中那个位上是0。一旦搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是达到全局最优解所需的。这仅仅是一种说明搜索空间是非线性的方式，这种情形不是假定的，因为实际上所有我们感兴趣的问题都是非线性的。变异作用提供了一个恢复遗传多样性的损失的方法。

（4）选择策略R。有两种选择策略。一是利用纯选择，即当前群体中每个点复制的次数比与点的性能值成比例。二是利用最优选择，即首先执行纯选择，且具有最好性能的点总是保留到下一代。在缺少最优选择的情况下，由于采样误差、交叉和变异，最好性能的点可能会丢失。

通过指定各个参数Pop-Size、P_c、P_m和R的值，可以表示一个特定的遗传算法。

7.4.4 确定指定结果的方法和停止运行的准则

当遗传的代数达到最大允许代数时，就可以停止算法的执行，并指定执行中得到的最好结果作为算法的结果。

基本的遗传算法

1）随机产生一个由固定长度字符串组成的初始群体。

2）对于字符串群体，迭代地执行下述步骤，直到选择标准被满足为止。

①计算群体中的每个个体字符串的适应值；

②实施下列三种操作（至少前两种）来产生新的群体，操作对象的选取基于与适应度成比例的概率。

选择：把现有的个体串按适应值复制到新的群体中。

交叉：通过遗传重组随机选择两个现有的子串进行遗传重组，产生两个新的串。

变异：将现有串中某一位的字符随机变异产生一个新串。

3）把在后代中出现的最好适应值的个体串指定为遗传算法运行的结果。这一结果可以是问题的解（或近似解）。

基本的遗传算法流程图如图7-1所示。

D. 遗传算法第一次提出来是在什么文献中

《搜索、优化和机器学习中的遗传算法》。

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法的基本运算过程如下：

（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

（2）个体评价：计算群体P(t)中各个个体的适应度。

（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

（6）终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。