锦标赛选择算法

‘壹’ 遗传算法中的锦标赛选择算法的思想是什么

我理解的是，在50个人中，随机选择两组人，每组10个人，对于每组的10个人按适应度进行排列，选择两组中适应度最好的两个个体作为母代进行两两交叉；
然后再从剩下来的48个人中，随机选择两组人，每组10个人，对于每组的10个人按适应度进行排列，选择两组中适应度最好的两个个体作为母代进行两两交叉；
依此类推，知道你选出的母代个数满足你的要求，这里母代个数肯定是少于50的。

‘贰’ 关于自适应遗传算法的交叉操作

不是随机选择的，是有规律的选，一般是等间隔选择，例如两个相邻的个体。

如图红色是一种选择方式：1&2, 3&4, 5&6, 7&8, 9&10

蓝色也是一种选择方式：1&6, 2&7, 3&8, 4&9, 5&10

当然，也要尽量避免相同个体交叉。

‘叁’ 计算机经典算法——锦标赛排序算法

关键词 ：二叉树
生活中的淘汰锦标赛 ：在单淘汰的锦标赛中，选手们两两比赛，胜者晋级，败者被淘汰。比如世界乒乓球锦标赛或者大满贯网球赛就是这么进行的。
这样一来，就可以把比赛的赛程和结果对应成一个二叉树。在树中每一个选手是二叉树中的一个叶子结点，每一场比赛就相当于两个数字在比大小，数字大的选手获胜进入下一轮，成为树干上的根。所以，进入到某一轮比赛的选手，其实都是某个子数干的根结点。最后的冠军就是整个二叉树的根结点。这种赛制的合理性需要一个假设：A>B, B>C --> 必然有A>C（输赢的传递性）

工程中，要比较两个数字的大小
第一步：把所有的数字放到二叉树的叶子节点，然后按照锦标赛单淘汰的方式，两两比较选出最大
第二步：对于第二大的，从所有被最大的数字淘汰的数字中选择，以此类推选择对于第三、第四大的数字

假定有25名短跑选手比赛竞争金银铜牌，赛场上有5条赛道，因此一次可以有5个人同时比赛。比赛不及时，只看相应的名次。假如选手的发挥是稳定的，也就是说如果约翰比张三跑的快，张三比凯利跑的快，那么约翰一定比凯利跑得快。最少需要几组比赛才能决出前3名？

第一步，将25名选手分成5组，每组5人。让每个组分别比赛，排出各组的名次来，假设他们的名字就是他们在小组中的编号。

第二步，让各组的第一名，也就是A1、B1、C1、D1、E1再比一次。假设A1在这次比赛中获胜，这样我们就知道了第一名。

第四步，如上图通过8次（5 +1 + 1 +1）选出的5人进行第三名的比赛，前3全部产生

更好的答案：
前6次比赛都是必须的，最佳答案的前2步和上述方案中的前2步是相同的。在第6组比赛（即5个第一名的比赛）结束之后，最后的2名已经没有资格角逐前3名了。

不妨假设那一次比赛从最快到最慢的结果是A1、B1、C1、D1、E1，在D1和E1之前已经有3名选手了，他们肯定不是前3名。
谁还会是第二名的候选呢？根据锦标赛排序的原则，直接输给第一名的人，也就是A2，以及最后附加赛输给他的B1，仅此两人而已。
谁会是第三名的候选呢？和A1在某一组比赛的第三名，他们是A3、C1，或者输给第二名候选人B1的人，即B2。

因此，第二、第三名的候选人一共只有5个， A2、A3、B1、B2和C1，刚好凑一组。这样加上前6次，只需要赛7组，这是最佳方法。

注：来自吴军老师得到课程

‘肆’ 技能闪充--锦标赛排序法

第一步：把所有的数字放到二叉树的叶子结点，然后按照锦标赛单淘汰的方式，两两比较选出最大的。
第二步：对于第二大的，从所有被最大的数字淘汰的数字中选择。比如在某次比赛中被RNG淘汰的是FW，KT等战队，那么这些战队在进行单淘汰，选亚军。对于第三第四大的数字，可以以此类推。

按照这种方式将所有的数字排序，算法的复杂度，或者说量级是N乘以LogN，和快排差不多。那么为什么不直接使用快速排序，而要发明出这么一种不太容易理解的算法呢？因为在特定的场合下他更快速。比如说，如果我们只需要选出第一名，这种算法的复杂度只有N，不是N乘以LogN，如果要选出第二名，则额外加上LogN次计算就可以了，对第三名也是如此。也就是说，这种方法在从N个选手中选出K个选手的事情特别快。

有了上述算法，我们讲解下高盛和Google的面试题了，当然任何算法用于实际的问题，都需要变通一下。

第一步：25名选手分成五组，为了便于说明我们把25人根据所在的组进行编号，A1-A5在A组，B1-B5在B组...最后E1-E5在E组。
然后让各组分别比赛，排除名次。不是一般性，我们假设他们的名次就是他们在小组中的编号，即A组的名次是A1、A2、A3、A4、A5，B组和其它组的名次也是类似(如下图)

第二步：让各组的第一名，也就是A1、B1、C1、D1、E1再比一次，上图中是第一排红色的，这样就能决出第一名。由于A1是第一名，A2可能也很厉害，只是运气不好，小组赛遇到了A1，当A1已经获得冠军了，他就应该作为亚军的候选。接下来就是第三步。
A2和另外四个组的第一名竞争亚军。如果这一次A2赢了，他显然是亚军，就由A3递进参加争夺第三名的比赛。我在下图中用红色圈定了这种情况下参加第八次比赛的五位选手。如果A2没有赢，另四组的某个第一名赢了，哪个赢的人是亚军，就由那个组下一位选手递进，角逐第三名。

第四步，如上图选出五个人进行第三名比赛，致辞，前三名全部产生。但是这个答案并不完美。最好的答案是什么呢？
其实前六次比赛是必须的，但是上述方案中有一个信息忽略了，就是第六组比赛之后（即五个第一名的比赛）结束之后，最后的两名已经没有资格角逐前三名了。我们假设那一次比赛从最快到最慢的结果是A1、B1、C1、D1、E1。在D1和E1之前已经有三名选手了，他们肯定不是前三名。

那么谁会是第二名的候选人呢？根据锦标赛的排序原则，直接输给第一名的人也就是A组的A2，以及最后附加赛输给他的B1，仅此两个人而已。接下来我们要问，除了A2和B1，谁还会是第三名的候选呢？和A1在某一组比赛的第三名，他们是A3、C1，或者输给第二名候选人B1的人哪个人，即B2.
因此，第二、三名的候选人一共只有五个，即A2、A3、C1，或者输给第二名候选人B1的那个即B2。
因此，第二、三名的候选人一共只有五个，即A2、A3、B1、B2、C1（下图中红色的选手），刚好凑一组。第七次，这五个人再跑一把即可，这样只需要七次，最佳方法。

‘伍’ 遗传算法的专业术语谁给翻译一下

这是遗传算法的各种选择方法，按顺序分别为：精英选择法、适应度比例选择法、轮盘赌选择法、定标选择法、锦标赛选择法、排序选择法、多世代选择法、稳态选择法、层次选择法。其中精英选择法、适应度比例选择法、轮盘赌选择法、锦标赛选择法、排序选择法是比较常见的选择方法。

‘陆’ 遗传算法--GA

        遗传算法（GA）属于 人工智能启发式算法 ，启发式算法的目标就是 寻找原始问题的最优解 ，该算法的定义为

         人类通过直观常识和生活经验，设计出一种以搜索最优解为目的，通过仿真大自然规律的算法，该算法在可以在接受的花销（计算时间和存储空间）范围内找到问题实例的一个可行解，且该可行解和真实最优解的误差一般不可以被估计

        当下主要有的启发式算法包括 遗传算法、退火法，蚁群算法、人工神经网络等 ，这篇文章主要介绍遗传算法

        遗传算法的基本原理是模拟达尔文进化论 "物竞天择，适者生存" 的自然法则，其核心思想为

（1）将原始问题的参数，抽象为基因编码

（2）将原始问题的可行解，抽象为基因排列的染色体组合

（3）将原始问题的解集规模，抽象为一定数量染色体组成的种群

（4）寻找可行解的过程，抽象为种群的进化过程（染色体选择、交叉、变异等）

（5）比较可行解的优劣，抽象为量化比较不同种群对当前环境的适应程度

（6）逼近最优解的过程，抽象为淘汰适应度差的种群，保留适应度高的种群进行下一次进化

（7）问题的最优解，抽象为经过多次进化后，最终生存下来的精英种群

        理论上，通过有限次种群进化，生存下来的种群都是 精英染色体 ，是最适合当前环境条件的种群，也就可以无限逼近原始问题的最优解

相关生物学术语：

    为了大家更好了解遗传算法，在此之前先简单介绍一下相关生物学术语，大家了解一下即可。

基因型(genotype)：性状染色体的内部表现；

表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；

进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。

适应度(fitness)：度量某个物种对于生存环境的适应程度。

选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。

复制(reproction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。

交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；

变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。

编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。

解码(decoding)：基因型到表现型的映射。

个体（indivial）：指染色体带有特征的实体；

种群（population）：个体的集合，该集合内个体数称为种群

大体实现过程

遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。 遗传算法的实现过程实际上就像自然界的进化过程那样。

基本遗传算法概述

    1.[开始]生成n个染色体的随机群体（适合该问题的解决方案）

    2.[适应度]评估群体中每个染色体x的适应度f（x）

    3.[新种群]通过重复以下来创建新种群直到新种群完成的步骤

        3.1 [选择]根据种群的适合度选择两个亲本染色体（更好的适应性，更大的选择机会）

        3.2 [交叉]以交叉概率跨越父母形成新的后代（儿童） ）。如果没有进行交叉，后代就是父母的确切副本。

        3.3 [突变]突变概率突变每个基因座（染色体中的位置）的新后代。

    4.[接受]在新种群中放置新后代[替换]使用新生成的种群进一步运行算法

    5.[测试]如果满足结束条件，则停止并返回当前种群中的最佳解

    6。[循环]转到步骤2

影响GA的因素

    从遗传算法概述可以看出，交叉和变异是遗传算法中最重要的部分。性能主要受这两个因素的影响。在我们解释有关交叉和变异的更多信息之前，我们将给出一些有关染色体的信息。

染色体编码

染色体应该以某种方式包含它所代表的解决方案的信息。最常用的编码方式是二进制字符串。然后染色体看起来像这样：

每个染色体由二进制字符串表示。字符串中的每个位都可以表示解决方案的一些特征。另一种可能性是整个字符串可以表示一个数字 - 这已在基本的GA小程序中使用。当然，还有许多其他的编码方式。编码主要取决于解决的问题。例如，可以直接编码整数或实数，有时对某些排列等进行编码很有用。

染色体交叉

在我们确定了将使用的编码之后，我们可以继续进行交叉操作。 Crossover对来自亲本染色体的选定基因进行操作并产生新的后代。最简单的方法是随机选择一些交叉点，并在此点之前从第一个父项复制所有内容，然后在交叉点之后复制另一个父交叉点之后的所有内容。交叉可以说明如下:( |是交叉点）：

还有其他方法可以进行交叉，例如我们可以选择更多的交叉点。交叉可能非常复杂，主要取决于染色体的编码。针对特定问题进行的特定交叉可以改善遗传算法的性能。

4.染色体突变

在执行交叉之后，发生突变。突变旨在防止群体中的所有解决方案落入解决问题的局部最优中。突变操作随机改变由交叉引起的后代。在二进制编码的情况下，我们可以将一些随机选择的位从1切换到0或从0切换到1.突变可以如下所示：

突变（以及交叉）技术主要取决于染色体的编码。例如，当我们编码排列时，可以将突变作为两个基因的交换来进行。

GA的参数

    1.交叉和突变概率

    GA有两个基本参数 - 交叉概率和变异概率。

     交叉概率 ：交叉的频率。如果没有交叉，后代就是父母的精确副本。如果存在交叉，则后代由父母染色体的部分组成。如果交叉概率为100％，那么所有后代都是由交叉产生的。如果它是0％，那么全新一代都是从旧种群的染色体的精确拷贝制成的（但这并不意味着新一代是相同的！）。交叉是希望新染色体将包含旧染色体的良好部分，因此新染色体将更好。但是，将旧人口的一部分留给下一代是好的。

     突变概率 ：染色体部分突变的频率。如果没有突变，则在交叉（或直接复制）后立即生成后代而不进行任何更改。如果进行突变，则改变染色体的一个或多个部分。如果突变概率为100％，则整个染色体发生变化，如果是0％，则没有变化。突变通常会阻止GA陷入局部极端。突变不应该经常发生，因为GA实际上会改变为随机搜索。

    2.其他参数

     种群规模 ：种群中有多少染色体（一代）。如果染色体太少，GA几乎没有可能进行交叉，只探索了一小部分搜索空间。另一方面，如果染色体太多，GA会减慢。研究表明，经过一定的限制（主要取决于编码和问题），使用非常大的种群是没有用的，因为它不能比中等规模的种群更快地解决问题。

     3      选择

正如您从GA概述中已经知道的那样，从群体中选择染色体作为交叉的父母。问题是如何选择这些染色体。根据达尔文的进化论，最好的进化能够创造出新的后代。选择最佳染色体的方法有很多种。例如轮盘赌选择，Boltzman选择，锦标赛选择，等级选择，稳态选择和其他一些选择。

1.轮盘赌选择

父母根据他们的健康状况选择。染色体越好，它们被选择的机会就越多。想象一下轮盘赌轮，人口中的所有染色体都放在那里。轮盘中截面的大小与每条染色体的适应度函数的值成比例 - 值越大，截面越大。有关示例，请参见下图。

轮盘赌中放入一块大理石，并选择停止的染色体。显然，具有较大适应值的染色体将被选择更多次。

该过程可以通过以下算法来描述。

[Sum]计算总体中所有染色体拟合度的总和 - 总和S.

[Select]从区间（0，S）-r生成随机数。

[循环]遍历总体并从0 - 总和中求和。当总和s大于r时，停止并返回您所在的染色体。当然，对于每个群体，步骤1仅执行一次。

2.排名选择

当健身值之间存在很大差异时，先前的选择类型会出现问题。例如，如果最佳染色体适应度是所有拟合度总和的90％，那么其他染色体将很少被选择的机会。等级选择首先对群体进行排序，然后每个染色体接收由该等级确定的适合度值。最差的将是健身1，第二个最差的2等等，最好的将具有适应度N（人口中的染色体数量）。您可以在下面的图片中看到，在更改适应性与排名确定的数字后情况如何变化。

排名前的情况（适合度图）

排名后的情况（订单号图）

现在所有染色体都有机会被选中。然而，这种方法会导致收敛速度变慢，因为最好的染色体与其他染色体的差别不大。

3.稳态选择

这不是选择父母的特定方法。这种选择新种群的主要思想是染色体的很大一部分可以存活到下一代。稳态选择GA以下列方式工作。在每一代中，选择一些好的（具有更高适应性）染色体来创建新的后代。然后去除一些不好的（具有较低适合度）染色体并将新的后代放置在它们的位置。其余人口幸存下来。

4.精英

精英主义的想法已经被引入。当通过交叉和变异创建新的种群时，我们有很大的机会，我们将失去最好的染色体。精英主义是首先将最佳染色体（或少数最佳染色体）复制到新种群的方法的名称。其余人口以上述方式构建。精英主义可以迅速提高GA的性能，因为它可以防止丢失最佳找到的解决方案。

交叉(Crossover)和突变 (Mutation)

交叉和变异是GA的两个基本运算符。 GA的表现非常依赖于它们。运算符的类型和实现取决于编码以及问题。有多种方法可以执行交叉和变异。在本章中，我们将简要介绍一些如何执行多个编码的示例和建议。

1.二进制编码

交叉

单点交叉 - 选择一个交叉点，从第一个父项复制从染色体开始到交叉点的二进制字符串，其余从另一个父项复制

选择两点交叉 - 两个交叉点，从第一个父节点复制从染色体开始到第一个交叉点的二进制字符串，从第一个父节点复制从第一个交叉点到第二个交叉点的部分，其余的是再次从第一个父级复制

均匀交叉 - 从第一个父项或第二个父项中随机复制位

算术交叉 - 执行一些算术运算以产生新的后代

突变

位反转 - 选择的位被反转

2.置换编码

交叉

单点交叉 - 选择一个交叉点，将排列从第一个父项复制到交叉点，然后扫描另一个父项，如果该数字还没有在后代中，则添加它注意：还有更多方法如何在交叉点之后产生休息

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

变异

顺序更改 - 选择并交换两个数字

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

3.值编码

交叉

可以使用来自二进制编码的所有交叉

变异

添加一个小数字（用于实数值编码） - 将一个小数字添加到（或减去）所选值

（1.29 5.68 2.86 4.11 5.55）=>（1.29 5.68 2.73 4.22 5.55）

4.树编码

交叉

树交叉 - 在父母双方中选择一个交叉点，父母在该点被分割，交换点下面的部分被交换以产生新的后代

变异

更改运算符，数字 - 选定节点已更改

补充:

疑惑点：

初始种群是啥：

利用二进制（一般）表示最终解

例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}

用六位二进制数表示由x，y组成的解，例如：001100 表示x=1，y=4

001100 称为一条基因序列，表示的是该问题的一种解决 方案

种群是包含多个基因序列（解决方案/个体）的集合

适应度函数是啥，有什么作用：

适应度函数可以理解成“ 游戏 规则”，如果问题较为复杂，需要自定义适应度函数，说明如何区分优秀与不优秀的个体; 如果问题比较简单，例如上述求最大值的问题，则直接用此函数式作为适应度函数即可。作用：评定个体的优劣程度，从而决定其遗传机会的大小。

怎么选择：

定义“适者生存不适者淘汰”的规则，例如：定义适应度高的被选择的概率更大

怎么交叉：

利用循环，遍历种群中的每个个体，挑选另一个体进行交叉。例如，通过遍历为基因序列A挑选出B配对，则取A的前半部分，B的后半部分，组合成新的个体（基因序列）C

如何变异：

随机挑选基因序列上的某一位置，进行0-1互换

建议 GA的参数

如果您决定实施遗传算法，本章应该为您提供一些基本建议。这些建议非常笼统。您可能希望尝试使用自己的GA来解决特定问题，因为没有一般理论可以帮助您针对任何问题调整GA参数。

建议通常是对GA的经验研究的结果，这些研究通常仅在二进制编码上进行。

交叉率

交叉率一般应高，约为80％-95％。 （但是有些结果表明，对于某些问题，交叉率约为60％是最好的。）

突变率

另一方面，突变率应该非常低。最佳利率似乎约为0.5％-1％。

人口规模

可能令人惊讶的是，非常大的人口规模通常不会改善GA的性能（从找到解决方案的速度的意义上说）。良好的人口规模约为20-30，但有时大小为50-100是最好的。一些研究还表明，最佳种群规模取决于编码字符串（染色体）的大小。这意味着如果你有32位染色体，那么人口应该高于16位染色体。

选择

可以使用基本的轮盘赌选择，但有时排名选择可以更好。查看有关选择优缺点的章节。还有一些更复杂的方法可以在GA运行期间更改选择参数。基本上，这些表现类似于模拟退火。如果您不使用其他方法来保存最佳找到的解决方案，则应确保使用精英主义。您也可以尝试稳态选择。

编码

编码取决于问题以及问题实例的大小。查看有关编码的章节以获取一些建议或查看其他资源。

交叉和变异

运算符取决于所选的编码和问题。查看有关操作员的章节以获取一些建议。您还可以查看其他网站。

搜索空间

    如果我们正在解决问题，我们通常会寻找一些最好的解决方案。所有可行解决方案的空间（所需解决方案所在的解决方案集）称为搜索空间（也称为状态空间）。搜索空间中的每个点代表一种可能的解决方案。每个可能的解决方案可以通过其对问题的值（或适应度）进行“标记”。通过GA，我们在众多可能的解决方案中寻找最佳解决方案 - 以搜索空间中的一个点为代表。然后寻找解决方案等于在搜索空间中寻找一些极值（最小值或最大值）。有时可以很好地定义搜索空间，但通常我们只知道搜索空间中的几个点。在使用遗传算法的过程中，随着进化的进行，寻找解决方案的过程会产生其他点（可能的解决方案）。

    问题是搜索可能非常复杂。人们可能不知道在哪里寻找解决方案或从哪里开始。有许多方法可用于寻找合适的解决方案，但这些方法不一定能提供最佳解决方案。这些方法中的一些是爬山，禁忌搜索，模拟退火和遗传算法。通过这些方法找到的解决方案通常被认为是很好的解决方案，因为通常不可能证明最佳方案。

NP-hard Problems

NP问题是一类无法用“传统”方式解决的问题。我们可以快速应用许多任务（多项式）算法。还存在一些无法通过算法解决的问题。有很多重要问题很难找到解决方案，但是一旦有了解决方案，就很容易检查解决方案。这一事实导致了NP完全问题。 NP代表非确定性多项式，它意味着可以“猜测”解决方案（通过一些非确定性算法），然后检查它。如果我们有一台猜测机器，我们或许可以在合理的时间内找到解决方案。为简单起见，研究NP完全问题仅限于答案可以是或否的问题。由于存在输出复杂的任务，因此引入了一类称为NP难问题的问题。这个类并不像NP完全问题那样受限。 NP问题的一个特征是，可以使用一个简单的算法，可能是第一眼看到的，可用于找到可用的解决方案。但是这种方法通常提供了许多可能的解决方案 - 只是尝试所有可能的解决方案是非常缓慢的过程（例如O（2 ^ n））。对于这些类型问题的更大的实例，这种方法根本不可用。今天没有人知道是否存在一些更快的算法来提供NP问题的确切答案。对于研究人员来说，发现这样的算法仍然是一项重大任务（也许你！:-)）。今天许多人认为这种算法不存在，因此他们正在寻找替代方法。替代方法的一个例子是遗传算法。 NP问题的例子是可满足性问题，旅行商问题或背包问题。可以获得NP问题汇编。

参考：

         https://www.jianshu.com/p/ae5157c26af9

        https://www.jianshu.com/p/b36b520bd187

‘柒’ asp.net常用的而且比较经典的算法都有哪些

文件结构：
插入排序
1.直接插入排序
2.二叉插入排序
3.2路插入排序
4.表插入排序
5.希尔排序
选择排序
1.简单选择排序
2.锦标赛排序（树选择排序）
3.堆排序
交换排序
1.冒泡排序
2.鸡尾酒排序（双向冒泡排序）
3.快速排序

归并排序

1.归并排序

分配排序
1.箱排序（桶排序）
2.基数排序

注意：

1.箱排序没有太大实用价值，主要是被基数排序所调用。该排序对不同的数据类型有不同的比较方法，本函数中针对整形数据进行比较。

2.快速排序和堆排序具有较高的效率，但是为了兼具高效保持排序的稳定性，建议使用归并排序。

‘捌’ 堆排序过程

1，实用的排序算法：选择排序
（1）选择排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在后面n-i个待排序元素中选择排序码最小的元素，作为有序元素序列的第i个元素。待到第n-2趟做完，待排序元素只剩下一个，就不用再选了。
（2）三种常用的选择排序方法
1>直接选择排序
2>锦标赛排序
3>堆排序
其中，直接排序的思路和实现都比较简单，并且相比其他排序算法，直接选择排序有一个突出的优势——数据的移动次数少。
（3）直接选择排序简介
1>直接选择排序（select sort）是一种简单的排序方法，它的基本步骤是：
1）在一组元素V[i]~V[n-1]中选择具有最小排序码的元素；
2）若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素对调；
3）在这组元素中剔除这个具有最小排序码的元素，在剩下的元素V[i+1]~V[n-1]中重复执行1、2步骤，直到剩余元素只有一个为止。
2>直接选择排序使用注意
它对一类重要的元素序列具有较好的效率，这就是元素规模很大，而排序码却比较小的序列。因为对这种序列进行排序，移动操作所花费的时间要比比较操作的时间大的多，而其他算法移动操作的次数都要比直接选择排序来的多，直接选择排序是一种不稳定的 排序方法。
3>直接选择排序C++函数代码

//函数功能，直接选择排序算法对数列排序
//函数参数，数列起点，数列终点
void dselect_sort(const int start, const int end) {
for (int i = start; i < end; ++i) {
int min_position = i;
for (int j = i + 1; j <= end; ++j) { //此循环用来寻找最小关键码
if (numbers[j] < numbers[min_position]) {
min_position = j;
}
}
if (min_position != i) { //避免自己与自己交换
swap(numbers[min_position], numbers[i]);

（4）关于锦标赛排序
直接选择排序中，当n比较大时，排序码的比较次数相当多，这是因为在后一趟比较选择时，往往把前一趟已经做过的比较又重复了一遍，没有把前一趟的比较结果保留下来。
锦标赛排序（tournament sort）克服了这一缺点。它的思想与体育比赛类似，就是把待排序元素两两进行竞赛，选出其中的胜利者，之后胜利者之间继续竞赛，再选出其中的胜利者，然后重复这一过程，最终构造出胜者树，从而实现排序的目的。

2，堆排序的排序过程
（1）个人理解：堆排序是选择排序的一种，所以它也符合选择排序的整体思想。直接选择排序是在还未成序的元素中逐个比较选择，而堆排序是首先建立一个堆（最大堆或最小堆），这使得数列已经“大致”成序，之后只需要局部调整来重建堆即可。建立堆及重建堆这一过程映射到数组中，其实就是一个选择的过程，只不过不是逐个比较选择，而是借助完全二叉树来做到有目的的比较选择。这也是堆排序性能优于直接选择排序的一个体现。
（2）堆排序分为两个步骤：
1>根据初始输入数据，利用堆的调整算法形成初始堆；
2>通过一系列的元素交换和重新调整堆进行排序。
（3）堆排序的排序思路
1>前提，我们是要对n个数据进行递增排序，也就是说拥有最大排序码的元素应该在数组的末端。
2>首先建立一个最大堆，则堆的第一个元素heap[0]具有最大的排序码，将heap[0]与heap[n-1]对调，把具有最大排序码的元素交换到最后，再对前面n-1个元素，使用堆的调整算法siftDown(0,n-2)，重新建立最大堆。结果具有次最大排序码的元素又浮到堆顶，即heap[0]的位置，再对调heap[0]与heap[n-2]，并调用siftDown(0，n-3)，对前n-2个元素重新调整，……如此反复，最后得到一个数列的排序码递增序列。
（4）堆排序的排序过程：
下面给出局部调整成最大堆的函数实现siftDown()，这个函数在前面最小堆实现博文中的实现思路已经给出，只需做微小的调整即可用在这里建立最大堆。

‘玖’ 遗传算法

优化的算法有很多种，从最基本的梯度下降法到现在的一些启发式算法，如遗传算法(GA)，差分演化算法(DE)，粒子群算法(PSO)和人工蜂群算法(ABC)。

举一个例子，遗传算法和梯度下降：

梯度下降和遗传算法都是优化算法，而梯度下降只是其中最基础的那一个，它依靠梯度与方向导数的关系计算出最优值。遗传算法则是优化算法中的启发式算法中的一种，启发式算法的意思就是先需要提供至少一个初始可行解，然后在预定义的搜索空间高效搜索用以迭代地改进解，最后得到一个次优解或者满意解。遗传算法则是基于群体的启发式算法。

遗传算法和梯度下降的区别是：

1.梯度下降使用误差函数决定梯度下降的方向，遗传算法使用目标函数评估个体的适应度
2.梯度下降是有每一步都是基于学习率下降的并且大部分情况下都是朝着优化方向迭代更新，容易达到局部最优解出不来；而遗传算法是使用选择、交叉和变异因子迭代更新的，可以有效跳出局部最优解
3.遗传算法的值可以用二进制编码表示，也可以直接实数表示

遗传算法如何使用它的内在构造来算出 α 和 β ：

主要讲一下选择、交叉和变异这一部分：
1.选择运算:将选择算子作用于群体。选择的目的是把优秀（适应值高）的个体直接遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

2.交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。交叉算子是将种群中的个体两两分组，按一定概率和方式交换部分基因的操作。将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。例如：（根据概率选取50个个体，两两配对，交换x,y，比如之前两个是(x1,y1),(x2,y2)，之后变成了（x1,y2）,(x2,y1)）

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

遗传算法就是通过对大量的数据个体使用选择、交叉和变异方式来进化，寻找适合问题的最优解或者满意解。

遗传算法参数的用处和设置：

1.编码选择：通常使用二进制编码和浮点数编码，二进制适合精度要求不高、特征较少的情况。浮点数适合精度高、特征多的情况
2.种群：种群由个体组成，个体中的每个数字都代表一个特征，种群个体数量通常设置在40-60之间；迭代次数通常看情况定若计算时间较长可以在100内，否则1000以内都可以。
3.选择因子：通常有轮盘赌选择和锦标赛选择，轮盘赌博的特点是收敛速度较快，但优势个体会迅速繁殖，导致种群缺乏多样性。锦标赛选择的特点是群多样性较为丰富，同时保证了被选个体较优。
4.交叉因子：交叉方法有单点交叉和两点交叉等等，通常用两点交叉。交叉概率则选择在0.7-0.9。概率越低收敛越慢时间越长。交叉操作能够组合出新的个体，在串空间进行有效搜索，同时降低对种群有效模式的破坏概率。
5.变异因子：变异也有变异的方法和概率。方法有均匀变异和高斯变异等等；概率也可以设置成0.1。变异操作可以改善遗传算法的局部搜索能力，丰富种群多样性。
6.终止条件：1、完成了预先给定的进化代数；2、种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进；3、所求问题最优值小于给定的阈值.

‘拾’ 遗传算法理解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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