第六章 智能计算及其应用

一、进化算法介绍

进化算法（evolutionary algorithms，EA）：是基于自然选择和自然遗传等生物进化机制的一种搜索算法。
是一个算法簇：

• 一种迭代算法。在最优解的搜索过程中，普通算法是从某个单一的初始点开始搜索，而进化算法是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。

• 进化算法不是直接对问题的具体参数进行处理，而是要求当原问题的优化模型建立后，还必须对原问题的解进行编码

  进化算法的生物学背景

  揭示了生物进化的一个规律：最适合自然环境的个体产生后代的可能性大。
  

  进化算法的设计原则

• 适用性

• 可靠性
• 收敛性
• 稳定性
• 生物类比

二、基本遗传算法（Simple Genetic Algorithms，SGA）

由不同的编码方式和不同的遗传算子构成了不同的遗传算法。共同特点是对生物遗传和进化过程中的选择、交叉、变异机理的模仿。Goldberg总结出了基本遗传算法，其只使用选择、交叉、变异三种基本遗传算子。

遗传算法包含五个基本要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作设计（选择、交叉、变异）、控制参数设定

近年来，遗传算法已广泛地应用于作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。

编码

遗传算法不能直接处理问题空间的参数，必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。应用难点，还不存在一种通用的编码方法。

位串编码

将问题空间的参数编码为一维排列的染色体的方法，称为一维染色体编码方法。最常用的是二进制编码

二进制编码

用若干二进制数表示一个个体，将原问题的解空间映射到位串空间B={0,1}上，然后在位串空间上进行遗传操作。
优点：类似生物染色体的组成，使算法易于用生物遗传理论来解释，可解释性较好。使得遗传操作如交叉、变异很容易实现。此外，算法处理的模式数最多。

• 可解释性较好
• 遗传操作容易实现
• 算法处理的模式数最多

缺点：

• Hamming悬崖（Hamming cliffs）：相邻整数的二进制编码具有较大的Hamming距离，例如15和16的二进制编码分别为01111,10000，从15->16需要改变所有的位。降低遗传算子的搜索效率。
• 二进制编码时，要先给出求解的进度。但求解的精度确定后，就很难在算法执行过程中进行调整，缺乏微调（fine-tuning）的功能。若在算法一开始就选取较高的进度，则串长很大，也将降低算法的效率。
• 在求解高维优化问题时，二进制编码串非常长，降低搜索效率，高维优化效率低。

  Gray编码

  将二进制编码通过一个变换进行转换得到的编码。设二进串对应Gray串
  从二进制编码到Gray编码的变换为：
  
  优点：克服了二进制编码的Hamming悬崖

  实数编码

  适用于问题的变量是实向量的情形。
  实数编码是用若干实数表示一个个体，然后在实数空间上进行遗传操作，从而引入与问题领域相关的启发式信息增加搜索能力。在求解高维或复杂优化问题时一般使用实数编码。

多参数级联编码

适用于多参数优化问题。基本思想：把每个参数先进行二进制编码得到子串，再把子串练成一个完整的染色体。每个子串对应各自的编码参数，可以有不同的串长度和参数的取值范围

群体设定

遗传是对群体进行操作的，必须为遗传操作准备一个由若干初始解组成的初始群体

初始种群的产生

• 根据问题只是，设法把握最优解所占空间在整个问题空间的分布范围，然后在此分布范围内设定初始群体。

• 先随机产生一定数目的个体，然后从中挑选最好的个体加入初始群体中。这种过程不断迭代，直到初始群体中的个体数目达到了预先确定的规模。

  种群规模的确定

  种群规模：群体中个体的数量。
  种群规模既不能太小，也不能太大。

• 种群太小，会使搜索空间有限，陷入局部最优解。

• 种群太大，计算量较大，影响效率。群体个体数量较多时，少量适应度很高的个体被选择而生存下来，大都数个体被淘汰，影响配对库的形成，影响交叉操作。

种群规模一般20-100

适应度函数

遗传算法遵循自然界优胜劣汰的原则，搜索中基本不用外部信息，而是用适应度值表示个体的优劣，作为遗传操作的依据。一般而言，适应度函数是由目标函数变化得到的。

目标函数映射成适应度函数的方法

若目标函数 为最大化问题，则适应度函数取：

若目标函数 为最小化问题，则适应度函数取：

适应度函数的尺度变化

对适应度函数值域的某种映射变换称为适应度函数的尺度变化（fitness scaling）或者定标。

背景：设计遗传算法时，群体的规模一般在几十至几百，与实际物种的规模相差很远。因此，个体繁殖数量的调节在遗传操作中就显得比较重要。
有以下两种情况需要改变原始的适应度值，以此提高个体之间的竞争力。

• 群体中出现了超级个体，即该个体的适应度值大大超过群体的平均适应度值，从而导致算法过早的收敛到一个局部最优点——过早收敛。过拟合（陷入局部最优解）
• 在搜索的后期，虽然群体具有足够的多样性，但群体的平均适应度可能会接近群体的最优适应度值，群体中已不存在竞争，从而搜索目标也难以得到改善——停滞现象。欠拟合（梯度消失）

线性变换

非线性变换

• 幂函数变换法：

• 指数变换法：基本思想来源于模拟退火过程，a决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应度的个体。

遗传操作

选择

选择操作也称为复制（reproduction）操作，是从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。被选择的标准是个体的适应度值，适应度值越高，其被选择的机会就越多。
不能完全挑选适应度最好的个体，不然遗传算法就成为了确定性优化方法，使种群过快收敛到局部最优解。

个体选择概率分配方法

遗传算法中，哪个个体被选择进行交叉（繁殖后代）是按照概率进行的。

• 适应度比例方法（fitness proportional model）（蒙特卡罗法）。各个个体被选择的概率和其适应度值成比例。设种群规模大小为，个体i的适应度值为，则这个个体被选择的概率为：

• 排序方法：在计算每个个体的适应度后，根据适应度大小顺序对群体中个体进行排序，然后将事先设定好的概率按顺序分配给个体，作为各自的选择概率。
  • 优点：克服了适应度比例选择策略的过早收敛和停滞现象，对于极大值和极小值，不需要进行标准化和调节。具有较好的健壮性。
  • 线性排序
  • 非线性排序

选择个体方法

根据个体的选择概率确定哪些个体被选择进行交叉、变异等操作

• 轮盘赌选择：先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉
• 锦标赛选择：从群体中随机选择k个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。参数k称为竞赛规模。
• 最佳个体保存方法（精英选拔方法）：把群体中适应度最高的一个或者多个个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。

交叉

当两个生物机体配对或者复制时，它们的染色体相互混合，产生一对由双方基因组成的新的染色体。这一过程称为交叉（crossover）或者重组（recombination）。
遗传算法中起核心作用的是交叉算子，也称为基因重组。采用的交叉方法应能够使父串的特征遗传给子串。子串应能够部分或者全部地继承父串的结构特征和有效基因。

基本交叉算子

• 一点交叉（single-point crossover）：个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。
• 二点交叉（two-point crossover）：与一点交叉类似，设置了两个交叉点（仍然是随机设定），将两个交叉点之间的码串相互交换。

• 多点交叉（multiple-point crossover）：与上述类似

  修正的交叉方法

  背景：由于交叉，可能出现不满足约束条件的非法染色体。所以需要对交叉、变异等遗传操作进行适当地修正，使其满足优化问题的约束条件。

• 部分匹配交叉（partially matched crossover，PMX）

• 顺序交叉（order crossover，OX）

• 循环交叉（cycle crossover，CX）

  变异

  在遗传算法中，变异是将个体编码中的一些位进行随机变化。变异的主要目的是维持群体的多样性，为选择、交叉过程中可能丢失的某些遗传基因进行修复和补充。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。变异操作是按位进行的，即把某一位的内容进行变异。
  在遗传算法中，变异属于辅助性的搜索操作。变异概率一般不能大，防止群体中的某些重要的、单一的基因被丢失。若变异概率太大，会使遗传算法趋于纯粹的随机搜索。为0.001左右。

• 位点变异

• 逆转变异
• 插入变异
• 互换变异

遗传算法的步骤

终止条件：

• 完成预先给定进化代数；
• 连续若干代没有改进。

遗传算法的特点

• 编码操作可以使遗传算法直接对结构对象继续操作。结构对象泛指集合、序列、矩阵、树、图、链和表等各种一维、二维甚至三维结构形式的对象
• 遗传算法是利用随机技术来指导对一个被编码的参数空间进行高效率搜索的方法，不是无方向的随机搜索。
• 许多传统搜索方法是单解搜索算法，即通过一些变动规则，将问题的解从搜索空间中的当前解移到另一解。对于多峰分布的搜索空间，这种点对点的搜索算法常常会陷与局部的最优解。遗传算法采用群体搜索策略，即采用同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估，具有较好的全局搜索性能，但还是不能保证每次都得到全局最优解。
• 基本遗传算法中，基本上不用搜索空间的知识或者其他辅助信息，仅仅使用适应度函数来评估个体。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定，唯一要求是能够算出可以比较的正值。

遗传算法的改进算法

双倍体遗传算法

双种群遗传算法

建立两个遗传算法群体，分别独立地运行复制、交叉、变异操作，同时当每一代运行结束以后，选择两个种群中的随机个体及最优个体分别交换。

自适应遗传算法

群智能算法

粒子群算法

PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解称为个体极值pbest。另个一是整个种群目前找到的最优解，这个解称为全局极值gbest

蚁群算法