进化算法的选择交叉编译

㈠ 进化算法的简介

进化算法包括遗传算法、遗传规划、进化规划和进化策略等等。进化算法的基本框架还是简单遗传算法所描述的框架，但在进化的方式上有较大的差异，选择、交叉、变异、种群控制等有很多变化，进化算法的大致框图可描述如右图所示：
同遗传算法一样，进化算法的收敛性也有一些结果，文献证明了在保存最优个体时通用的进化计算是收敛的，但进化算法的很多结果是从遗传算法推过去的。
遗传算法对交叉操作要看重一些，认为变异操作是算法的辅助操作；而进化规划和进化策略认为在一般意义上说交叉并不优于变异，甚至可以不要交叉操作。

㈡ 多目标优化算法

多目标优化算法如下：

一、多目标进化算法（MOEA）

1、MOEA通过对种群X（t）执行选择、交叉和变异等操作产生下一代种群X（t+1）。

2、在每一代进化过程中 ,首先将种群X（t）中的所有非劣解个体都复制到外部集A（t）中。

2、智能优化算法：包括进化算法（简称EA）、粒子群算法（简称PSO）等。

两者的区别：传统优化技术一般每次能得到Pareo解集中的一个，而用智能算法来求解，可以得到更多的Pareto解，这些解构成了一个最优解集，称为Pareto最优解（任一个目标函数值的提高都必须以牺牲其他目标函数值为代价的解集）。

㈢ 遗传算法的优缺点

优点：

1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行操作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传操作算子的运用。

另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。

2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。

3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。

另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。

4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。

5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。

缺点：

1、遗传算法在进行编码时容易出现不规范不准确的问题。

2、由于单一的遗传算法编码不能全面将优化问题的约束表示出来，因此需要考虑对不可行解采用阈值，进而增加了工作量和求解时间。

3、遗传算法效率通常低于其他传统的优化方法。

4、遗传算法容易出现过早收敛的问题。

(3)进化算法的选择交叉编译扩展阅读

遗传算法的机理相对复杂，在Matlab中已经由封装好的工具箱命令，通过调用就能够十分方便的使用遗传算法。

函数ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最优解，fval是最优值，@fitnessness是目标函数，nvars是自变量个数，options是其他属性设置。系统默认求最小值，所以在求最大值时应在写函数文档时加负号。

为了设置options，需要用到下面这个函数：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通过这个函数就能够实现对部分遗传算法的参数的设置。

㈣ 网络架构搜索

        作为计算智能方法的代表，起源于上个世纪四十年代的人工神经网络经历了五六十年代的繁荣，七十年代的低潮，八十年代的再次复苏，到近十年的广泛关注，如今已经成为理论日趋完善，应用逐步发展的前沿方向。Hinton 等人2006 年在《Science》上发表的文章引发了深度神经网络研究的热潮。面对大数据的诸多挑战，以深度信念网络、卷积神经网络和递归神经网络为代表的深度神经网络模型在很多应用领域展示出明显的优势和潜力，特别是随着数据量和数据维数的增加，深度学习的优势愈加突出。例如，Google 借助深度学习开发的AlphaGo 能从海量的对弈中学习正确的决策，微软语音识别采用深度学习使识别错误率显着降低，网络基于深度学习开发的机器人“小度”在跨年龄人脸识别上超越了人类。

       经过多年的研究和发展，基于人工神经网络的识别方法也逐渐取代传统的模式识别方法。神经网络已成为当前比较先进的技术，用来解决许多具有挑战性的识别任务如文字识别、语音识别、指纹识别、遥感图像识别、人脸识别、手写体字符的识别等。其中主流的神经网络模型有卷积网络和递归神经网络，卷积神经网络由 Yann LeCun 在 1998 年提出，自从 AlexNe 在 2012 年的 ImageNet 比赛中使用了这一架构拔得头筹，卷积神经网络迅速流行起来并广泛应用到视觉任务。如今，最先进的卷积神经网络算法在进行图像识别时，甚至可以超过人类肉眼识别的准确率。递归神经网络网络提出于 1990 年，被视为循环神经网络的推广，递归神经网络可以引入门控机制以学习长距离依赖，适用于包含结构关系的机器学习任务，在序列识别方面有重要应用。

        深度神经网络和深度学习算法因为在科研工作与工程任务中都取得了显着的效果从而大受欢迎。它取代了传统的手动提取特征方法，够端到端地自动提取和学习特征。而其中取得显着成功的深度神经网络通常是由于它们成功的架构设计，研究的工作重心从提取特征转移到了寻找最优架构上。通常来说，模型的容量越大网络的性能就越好，能够拟合任意函数。因此为了提升网络性能，网络结构被设计的越来越复杂。例如，VGG-16 约有1.4亿浮点数参数，整个网络占用超过500兆存储空间，需要153亿次浮点操作来处理一个$224\times224$大小的图像。虽然更深的网络层次和复杂的拓扑结构能够更有效地学习特征，但是网络规模的增大意味着人工设计网络时需要花费更多时间来反复试验，即使是专家也需要大量的资源和时间来创建性能良好的模型。

        神经网络架构搜索(NAS)是一种自动化学习网络结构的新方法，用于减少繁重的网络设计成本。目前为止，NAS方法设计的网络在识别任务上的表现已经超过了人工设计的架构。NAS可以视作自动机器学习（AutoML）的子领域，与超参数优化和元学习有明显的重叠。不同的NAS方法的区别主要在于三个维度：搜索空间、搜索策略和性能评估，我们对此分别进行了调研。

        搜索空间：搜索空间定义了网络的所有可选结构和操作，通常指数级大，甚至无界。在设计搜索空间时结合先验知识，即参考现有的针对当前任务的先进结构设计知识，能够有效减小搜索空间并简化搜索。但这也会引入偏好，从而限制网络学习到超越当前人类知识的结构。

        搜索策略：定义搜索空间后，搜索策略引导寻找高性能的模型架构，其中的难点是保证探索和利用的平衡。一方面，希望快速找到性能良好的架构，另一方面，需要避免过早收敛到次优的架构。

        性能评估：NSA的目的是找到一个在未知数据上具有良好泛化性能的架构，一旦模型生成，就需要对其性能进行评估。直观的方法是在训练集上训练收敛，并在验证集上得到其性能，但是这种方法会耗费巨大的算力，从而限制了可探索的网络结构。一些先进的方法关注于减小性能评估时的计算代价，但会引入误差。因此，平衡评价的效率和效果是一个需要研究的问题。

       从计算的角度来看，神经网络代表了一个通过一系列操作将输入变量 x 转换为输出变量 y 的函数。基于计算图语言，神经网络可以表示为一个有向无环图(DAG)，其中每个节点表示一个张量 z ，通过边连接其父节点 I(k)，每条边表示从候选操作集O中选择的一个操作 o 。节点 k 的计算公式为：

        其中候选操作集合$O$主要包括卷积、池化、激活函数、跳跃连接、拼接、加法等基本操作。此外，为了进一步提高模型的性能，一些先进的人工设计模块也可以作为候选操作，如深度可分离卷积、膨胀卷积、组卷积。基于操作的类型可以选择不同的超参数，例如输入节点选取、卷积核数量、尺寸、步长等。不同的搜索空间设计，选择和组合操作的方法也不同所以参数化的形式也不一样。一般来说，一个好的搜索空间应该能够排除人类的偏见，并且足够灵活，能够覆盖更广泛的模型架构。

        全局搜索空间搜索一个完整的网络结构，具有很高的自由度。最简单的例子是链式搜索空间，见图1左。固定的数量的节点按顺序堆叠，只有前一个节点的输出提供给后一个节点作为输入，每个节点代表一个层，并具有指定的操作。右图引入更复杂的跳跃链接和多支路结构，此时当前节点可以结合前面所有节点的输出作为输入，使得搜索的自由度显着增大。许多网络都是多分支网络的特例，比如

1）链式网络： ；

2）残差网络： ；

3）DenseNets：

        虽然整体结构搜索很容易实现，但它也有一些缺点。首先，搜索空间的大小与网络深度是指数级关系，寻找泛化性能好的深度网络计算成本高。此外，生成的架构缺乏可迁移性和灵活性，在小型数据集上生成的模型可能不适合较大的数据集。有研究提出，初始架构的选择在搜索全局结构时十分重要。在适当的初始条件下，可以获得与单元搜索空间性能相当的架构，但是初始架构选择的指导原则仍然不明确。

        基于单元的搜索空间受启发于人工设计知识，许多有效的网络结构都会重复使用固定结构，例如在RNNs中重复LSTM块或堆叠残差模块。因此可以只搜索这样的重复单元(cells)，整个神经结构的搜索问题被简化为在单元搜索空间中搜索最优的单元结构，从而极大的减小搜索空间。大多数研究对比了基于全局搜索空间和单元搜索空间的实验结果，证明在基于单元的搜索空间中可以获得良好的性能。单元搜索空间的另一个优势是能方便地在数据集和任务之间进行泛化，因为通过增减卷积核和单元的数量，架构的复杂性几乎可以任意改变。

        NASNet是最早提出的单元搜索空间之一，也是当前最热门的选择，之后的大部分改进只是在此基础上对操作选择和单元组合策略进行了少量修改。如图2所示，它由两种单元组成，分别为保持输入特征维度的标准单元(normal cell)，和减小空间维度的简化单元(rection cell)。每个单元由b个块组成，每个块由它的两个输入和相应的操作定义。可选的输入包括前两个单元的输出和单元中先前定义的块的输出，所以它支持跨单元的跳跃连接。未使用的块被连接起来并作为单元格的输出，最终通过预定义好的规则级联这些单元。

        不同于上面将单元结构按照人工定义的宏结构进行连接，层次结构是将前一步骤生成的单元结构作为下一步单元结构的基本组成部件，通过迭代的思想得到最终的网络结构。Hier提出的层次搜索空间，通过合并低层单元生成高级单元实现单元级别和网络级别的同时优化。此方法具体分为3层。第一层包含一系列的基础操作；第二层通过有向无环图连接第一层的基础操作，构建不同的单元，图结构用邻接矩阵编码；第三层是网络级的编码，决定如何连接第二层的单元，组合成一个完整的网络。基于单元的搜索空间可以看作是这种层次搜索空间的一个特殊情况。

        强化学习方法（RL）能够有效建模一个顺序决策的过程，其中代理与环境相互作用，代理学会改善其行为从而使目标回报最大化。（图3）给出了一个基于强化的NAS算法的概述。代理通常是一个递归神经网络(RNN)，它在每一步t执行一个动作 来从搜索空间采样一个新的样本，同时接收状态 的观察值和环境中的奖励 ，以更新代理的采样策略。这种方法非常适合于神经结构搜索，代理的行为是生成神经结构，行为空间是搜索空间，环境是指对代理生成的网络进行训练和评估，奖励是训练后的网络结构对未知数据的预测性能，在最后一个行为之后获得。

4.2进化算法

        进化算法（EA）是一种成熟的全局优化方法，具有较高的鲁棒性和广泛的适用性。许多研究使用进化算法来优化神经网络结构。进化算法演化了一组模型，即一组网络；在每个世代中，至少从这组模型中选择一个模型，作为亲本在突变后作为生成子代。在对子代进行训练之后，评估它们的适应度并将它们添加到种群中。

        典型的进化算法包括选择、交叉、变异和更新等步骤。选择时一般使用联赛选择算法对父类进行采样，其中适应性最好的一个作为亲本。Lemonade对适应度使用核密度估计，使网络被选择的概率与密度成反比。交叉方式因编码方案的不同而不同。突变针对的是亲本的部分操作，例如添加或移除层，改变层的超参数，添加跳跃连接，以及改变训练超参数。对于产生的后代，大多数方法随机初始化子网络权重，而Lemonade把父网络学习到的权重通过使用网络态射传递给其子网络。Real等人让后代继承其父母的所有不受突变影响的参数，虽然这种继承不是严格意义上的功能保留，它可以加速学习。生成新的网络的同时需要从种群中移除一些个体。Real等人从群体中移除最差的个体，AmoebaNet移除最老的个体。也有一些方法定期丢弃所有个体，或者完全不移除个体。EENA通过一个变量调节最坏模型和最老模型的删除概率。

        基于代理模型的优化方法(SMBO)用一个代理模型来近似目标函数。即不需要训练采样到的网络结构，只需要训练一个代理模型，使用代理模型预测网络的性能。通常在实践中只需要得到架构的性能排序，而不一定要计算出具体的损失值，因此代理模型只需要预测相对得分并选出有前途的候选架构。然后只对预测性能好的架构进行评估，用它们的验证精度更新代理模型，这样只需要完全训练少量候选架构，大大减少搜索时间。代理模型通常训练为最小化平方误差：

        贝叶斯优化（BO）是用于超参数优化的最流行的方法之一。最经典的是基于高斯过程的BO，生成的神经结构的验证结果可以建模为高斯过程，然而，基于高斯的BO方法在观察次数上的推理时间尺度是立方的，并且不擅长处理变长神经网络。有些工作使用基于树或者随机森林的方法来在非常高维的空间中高效的搜索，并且在很多问题上取得了优异的效果。Negrinho利用其搜索空间的树形结构，并使用蒙特卡洛树搜索。虽然没有完整的比较，但初步的证据表明这些方法可以超越进化算法。

        上面的搜索策略搜是从一个离散的搜索空间提取神经结构样本。DARTS提出搜索空间的连续松弛，在连续可微的搜索空间上搜索神经架构如图4所示，并使用如下softmax函数来松弛离散空间:

 

松弛后，架构搜索的任务转化为网络架构与神经权值的联合优化。这两类参数分别在训练集和验证集上交替优化，表示为一个双层优化问题。

        为了对搜索过程进行引导，必须对产生的神经网络性能进行评估。一种直观的方法是训练网络至收敛，然后评估其性能。但是，这种方法需要大量的时间和计算资源。因此提出了几种加速模型评估的方法。

        为了减少计算负担，可以用实际性能的低质近似来估测性能。实现方法包括: 缩短训练时间、选择数据集的子集、在低分辨率的图像上训练、每层使用更少的通道数、堆叠更少的单元结构。在低质条件下搜索到的最优网络或单元，构建出最终结构在数据集上重新训练，得到目标网络。虽然这些低精度的近似能够减少训练花费，但性能被低估的同时不可避免地引入了误差。最近的研究表明，当这种低质评价与完全评价之间的差异较大时，网络性能的相对排名可能变化很大，并强调这种误差会逐渐增加。

        早停技术最初用于防止过拟合。一些研究通过在训练初期预测网络性能，在验证集上预计表现不佳的模型被强制停止训练，以此来加速模型评估。一种在早期估计网络性能的方法是学习曲线外推法。Domhan 等提出训练初期对学习曲线进行插值，并终止那些预测性能不好的网络结构的训练。Swersky等在评估学习曲线的好坏时，把网络架构的超参数作为参考因素。另一种方法根据梯度的局部统计信息实现早期停止，它不再依赖验证集，允许优化器充分利用所有的训练数据。

        代理模型可以被训练用预测网络性能。PNAS提出训练一个代理网络（LSTM）来预测网络结构的性能，他不考虑学习曲线而是基于结构的特点来预测性能，并在训练时推断更大的网络结构。SemiNAS是一种半监督NAS方法，利用大量的未标记架构进一步提高搜索效率。不需要在对模型进行训练，只使用代理模型来预测模型精度。预测网络性能的主要难点是：为加快搜索过程，需要在对较大的搜索空间进行较少的评估的基础上进行良好的预测。当优化空间过大且难以量化，且对每个结构的评估成本极高时，基于代理的方法就不适用。

        代理模型还可以用来预测网络权重。超网络（Hypernetworks）是一种神经网络，被训练来为各种架构生成网络权值。超网络在搜索过程中节省了候选体系结构的训练时间，因为它们的权值是通过超网络的预测得到的。Zhang等人提出了一种计算图表示，并使用图超网络(GHN)比常规超网络(SMASH)更快更准确地预测所有可能架构的权值。

        权重继承是让新网络结构继承之前训练完成的其他网络结构的权值。其中一种方法是网络态射，一般的网络设计方法是首先设计出一个网络结构，然后训练它并在验证集上查看它的性能表现，如果表现较差，则重新设计一个网络。可以很明显地发现这种设计方法会做很多无用功，因此耗费大量时间。而基于网络态射结构方法能够在原有的网络结构基础上做修改，修改后的网络可以重用之前训练好的权重。其特殊的变换方式能够保证新的网络结构还原成原网络，因此子网络的表现至少不会差于原网络，并且能在较短的训练时间内继续成长为一个更健壮的网络。具体地，网络射态能够处理任意非线性激活函数，可以添加跳跃连接，并且支持添加层或通道得到更深或更宽的等效模型。经典的网络态射只能使网络变大，这可能导致网络过于复杂，之后提出的近似网络态射通过知识蒸馏允许网络结构减小。进化算法经常使用基于网络态射的变异，或者直接让孩子继承亲本的权重，再执行一般变异操作，这样产生的网络具有一个更好的初始值，而不用重头开始训练。

㈤ 优化算法笔记（七）差分进化算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
差分进化算法（Differential Evolution Algorithm，DE）是一种基于群体的进化算法，它模拟了群体中的个体的合作与竞争的过程。算法原理简单，控制参数少，只有交叉概率和缩放比例因子，鲁棒性强，易于实现。
差分进化算法中，每一个个体的基因表示待求问题的一个候选解。每次迭代将先进行变异操作，选择一个或多个个体的基因作为基，然后选择不同的个体的差分来构成差分基因，最后将作为基的基因与差分基因相加来得出新的个体。交叉操作将新的个体将于父代的对应个体交叉，然后进行选择操作，比较交叉后的个体与父代的对应个体，选择较优的个体保留至下一代。在迭代完成之后将选择种群中最优个体的基因作为解。
差分进化算法可以算是我所使用过的优化算法中大魔王级别的算法，虽然它每个方面都没有强到离谱，但是综合起来的效果好于大多数算法。它就像一个每个科目都能考到90分（百分制）的学生，虽然没门课都不是最优秀的，但是论综合，论总分，它有极大的概率是第一名。

在我研究优化算法的小路上，我的目标就是找到一个能打败大魔王或是能在大多数方面压制魔王的算法。

这次的主角就选魔王军吧（或者蚁王军，为了与蚁群算法区别还是叫魔王军吧），个体则称之为魔王兵。
魔王兵的能力取决于它们的基因，它们可以根据环境或者需要改变自己的基因使得自己更加强大，更方便的处理问题，问题的维度与基因维度相同。

表示第i个魔王兵在进化了第t次后的基因，该个体有D位基因。
与遗传算法同为进化算法的差分进化算法，它们的操作（算子）也都非常相似的，都是交叉，变异和选择，流程也几乎一样（遗传算法先交叉后变异，差分进化算法先变异后交叉）。

说到差分进化算法中的变异，我就想到一句论语 “三人行，必有我师焉。择其善者而从之，其不善者而改之。” ，其实这句论语已经向我们说明了差分进化算法的整个流程：
“三人行，必有我师焉”——变异，交叉。
“择其善者而从之，其不善者而改之”——选择。
差分进化算法中，当一个魔王兵变异时，它会先找来3个小伙伴，当然是随机找来3个小伙伴，避免同化。在一个小伙伴的基因上加上另外两个小伙伴基因之差作为自己的目标基因。其变异公式如下：

表示第i个魔王兵找到了编号为r1、r2和r3的三个魔王兵，当然了i、r1、r2、r3为互不相同的整数，F为缩放比例因子，通常 ，一般取F=0.5。 为第i个魔王兵交叉后的目标基因图纸，不过这是个半成品，再经过交叉后，目标基因图纸才算完成。
其实现在我们已经有了5个基因图纸了 ，接下来将进行交叉操作。由于变异操作，差分进化算法的种群中个体数至少为4，即魔王军中至少有4个小兵。

交叉操作中，魔王兵i会将目标基因图纸 进行加工得到 ，加工过程如下：

其中 。 为交叉概率，其值越大，发生交叉的概率越大，一般取 。 为{1,2,…,D}中的随机整数，其作用是保证交叉操作中至少有一维基因来自变异操作产生的基因，不能让交叉操作的努力白费。
从公式上可以看出交叉操作实际上是从变异操作得出的基因图纸上选择至少一位基因来替换自己的等位基因，得到最终的基因图纸。

选择操作相对简单，魔王兵i拿到了最终的基因图纸 ，大喊一声，进化吧，魔王兵i的基因改变了。它拿出了能力测量器fitness function,如果发现自己变强了，那么就将基因 保留到下一代，否则它选择放弃进化，让自己还原成 。

实验又来啦，还是那个实验 ，简单、易算、好画图。
实验1 ：参数如下

图中可以看出在第20代时，群体已经非常集中了，在来看看最终得出的结果。

这结果真是好到令人发指，恶魔在心中低语“把其他的优化算法都丢掉吧”。不过别往心里去，任何算法都有优缺点，天下没有免费的午餐，要想获得某种能力必须付出至少相应的代价。
实验2：
将交叉率CR设为0,即每次交叉只选择保留一位变异基因。

看看了看图，感觉跟实验1中相比没有什么变化，那我们再来看看结果。

结果总体来说比实验1好了一个数量级。为什么呢？个人感觉应该是每次只改变一位基因的局部搜索能力比改变多位基因更强。下面我们将交叉率CR设为1来看看是否是这样。
实验3：
将交叉率CR设为1,即每次交叉只选择保留一位原有基因。

实验3的图与实验1和实验2相比好像也没什么差别,只是收敛速度好像快了那么一点点。再来看看结果。

发现结果比实验2的结果还要好？那说明了实验2我得出的结论是可能是错误的，交叉率在该问题上对差分进化算法的影响不大，它们结果的差异可能只是运气的差异，毕竟是概率算法。
实验4：
将变异放缩因子设为0，即变异只与一个个体有关。

收敛速度依然很快，不过怎么感觉结果不对，而且个体收敛的路径好像遗传算法，当F=0，时，差分进化算法退化为了没有变异、选择操作的遗传算法，结果一定不会太好。

果然如此。下面我们再看看F=2时的实验。
实验5：
将变异放缩因子设为2。

实验5的图可以明显看出，群体的收敛速度要慢了许多，到第50代时，种群还未完全收敛于一点，那么在50代时其结果也不会很好，毕竟算法还未收敛就停止进化了。

结果不算很好但也算相对稳定。

通过上面5个实验，我们大致了解了差分进化算法的两个参数的作用。
交叉率CR，影响基因取自变异基因的比例，由于至少要保留一位自己的基因和变异的基因导致CR在该问题上对算法性能的影响不大（这个问题比较简单，维度较低，影响不大）。
变异放缩因子F，影响群体的收敛速度，F越大收敛速度越慢，F绝对值越小收敛速度越快，当F=0是群体之间只会交换基因，不会变异基因。

差分进化算法大魔王已经如此强大了，那么还有什么可以改进的呢？当然有下面一一道来。
方案1 .将3人行修改为5人行，以及推广到2n+1人行。
实验6：
将3人行修改为5人行，变异公式如下：

五人行的实验图看起来好像与之前并没有太大的变化，我们再来看看结果。

结果没有明显提升，反而感觉比之前的结果差了。反思一下五人行的优缺点，优点，取值范围更大，缺点，情况太多，减慢搜索速度。

可以看出算法的收敛速度比之前的变慢了一点，再看看结果。

比之前差。

差分进化算法的学习在此也告一段落。差分进化算法很强大，也很简单、简洁，算法的描述都充满了美感，不愧是大魔王。不过这里并不是结束，这只是个开始，终将找到打败大魔王的方法，让新的魔王诞生。
由于差分进化算法足够强，而文中实验的问题较为简单导致算法的改进甚至越改越差（其实我也不知道改的如何，需要大量实验验证）。在遥远的将来，也会有更加复杂的问题来检验魔王的能力，总之，后会无期。
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（六）遗传算法
下一篇 优化算法笔记（八）人工蜂群算法

优化算法matlab实现（七）差分进化算法matlab实现

㈥ 请问，遗传算法中的交叉编译概率在编写子函数时为啥要在rand(1)小于概...

遗传算法中的交叉变异概率在编子函数时，应该是rand(1)产生的随机数小于交叉率pc,或交叉率pm才能进行交叉变异操作。
因为遗传算法中，交叉变异操作是以一定的交叉率pc和一定的变异率pm执行的。所以首先选择参与交叉或变异操作的个体进入到交配池，选择过程是随机选择的，即满足rand(1)
<pc或rand(1)
<pm才被选择

㈦ 各种进化算法有什么异同

（差异进化算法DE）是一种用于优化问题的启发式算法。本质上说，它是一种基于实数编码的具有保优思想的贪婪遗传算法[1] 。同遗传算法一样，差异进化算法包含变异和交叉操作，但同时相较于遗传算法的选择操作，差异进化算法采用一对一的淘汰机制来更新种群。由于差异进化算法在连续域优化问题的优势已获得广泛应用，并引发进化算法研究领域的热潮。 差异进化算法由Storn 以及Price [2]提出，算法的原理采用对个体进行方向扰动，以达到对个体的函数值进行下降的目的，同其他进化算法一样，差异进化算法不利用函数的梯度信息，因此对函数的可导性甚至连续性没有要求，适用性很强。

㈧ 人工智能之进化算法

进化计算的三大分支包括：遗传算法(Genetic Algorithm ，简称GA)、进化规划(Evolu-tionary Programming，简称EP)和进化策略(Evolution Strategies ，简称ES)。这三个分支在算法实现方面具有一些细微的差别，但它们具有一个共同的特点，即都是借助生物进化的思想和原理来解决实际问题。

遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国Holand J教授于1975年首次提出。它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织的、然而是随机的信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。遗传算法尤其适用于处理传统搜索方法难于解决的复杂的非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。

1964年，由德国柏林工业大学的RechenbergI等人提出。在求解流体动力学柔性弯曲管的形状优化问题时，用传统的方法很难在优化设计中描述物体形状的参数，然而利用生物变异的思想来随机地改变参数值并获得了较好效果。随后，他们便对这种方法进行了深入的研究和发展，形成了进化计算的另一个分支——进化策略。

进化策略与遗传算法的不同之处在于：进化策略直接在解空间上进行操作，强调进化过程中从父体到后代行为的自适应性和多样性，强调进化过程中搜索步长的自适应性调节;而遗传算法是将原问题的解空间映射到位串空间之中，然后再施行遗传操作，它强调个体基因结构的变化对其适应度的影响。

进化策略主要用于求解数值优化问题。

进化规划的方法最初是由美国人Fogel LJ等人在20世纪60年代提出的。他们在人工智能的研究中发现，智能行为要具有能预测其所处环境的状态，并按照给定的目标做出适当的响应的能力。在研究中，他们将模拟环境描述成是由有限字符集中符号组成的序列。

进化算法与传统的算法具有很多不同之处，但其最主要的特点体现在下述两个方面：

进化计算的智能性包括自组织、自适应和自学习性等。应用进化计算求解问题时，在确定了编码方案、适应值函数及遗传算子以后，算法将根据“适者生存、不适应者淘汰"的策略，利用进化过程中获得的信息自行组织搜索，从而不断地向最佳解方向逼近。自然选择消除了传统算法设计过程中的-一个最大障碍：即需要事先描述问题的全部特点，并说明针对问题的不同特点算法应采取的措施。于是，利用进化计算的方法可以解决那些结构尚无人能理解的复杂问题。

进化计算的本质并行性表现在两个方面：

一是进化计算是内在并行的，即进化计算本身非常适合大规模并行。

二是进化计算的内含并行性，由于进化计算采用种群的方式组织搜索，从而它可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得进化计算能以较少的计算获得较大的收益。

㈨ 各种进化算法有什么异同

同遗传算法一样，差异进化算法包含变异和交叉操作，但同时相较于遗传算法的选择操作，差异进化算法采用一对一的淘汰机制来更新种群。由于差异进化算法在连续域优化问题的优势已获得广泛应用，并引发进化算法研究领域的热潮。

进化算法

或称“演化算法” (evolutionary algorithms) 是一个“算法簇”，尽管它有很多的变化，有不同的遗传基因表达方式，不同的交叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，但它们产生的灵感都来自于大自然的生物进化。

与传统的基于微积分的方法和穷举法等优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性，能够不受问题性质的限制，有效地处理传统优化算法难以解决的复杂问题。

㈩ 进化算法的基本步骤

进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解进行编码。进化计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法。
一般来说，进化计算的求解包括以下几个步骤：给定一组初始解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础；再对其进行操作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解作为当前解重新操作。
以遗传算法为例，其工作步骤可概括为：
（1） 对工作对象——字符串用二进制的0/1或其它进制字符编码 。
（2） 根据字符串的长度L，随即产生L个字符组成初始个体。
（3） 计算适应度。适应度是衡量个体优劣的标志，通常是所研究问题的目标函数。
（4） 通过复制，将优良个体插入下一代新群体中，体现“优胜劣汰”的原则。
（5） 交换字符，产生新个体。交换点的位置是随机决定的
（6） 对某个字符进行补运算，将字符1变为0，或将0变为1，这是产生新个体的另一种方法，突变字符的位置也是随机决定的。
（7） 遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交换、突变等操作，直至满足终止条件。
将其用形式化语言表达，则为：假设α∈I记为个体，I记为个体空间。适应度函数记为Φ：I→R。在第t代，群体P(t)={a1(t),a2(t)，…，an(t)}经过复制r(reproction)、交换c(crossover)及突变m(mutation)转换成下一代群体。这里r、c、m均指宏算子，把旧群体变换为新群体。L：I→{True, Flase}记为终止准则。利用上述符号，遗传算法可描述为：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)};
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))};
reproction: P′(t):=r(P(t));
crossover: P″(t):=c(P′(t));
mutation: P(t+1):= m(P″(t));
t=t+1;
end