7.群智能算法
人工智能文章系列
- 第1章：AI绪论与概述
- 第2.1章：知识表示
- 第2.2章：知识图谱
- 第3章：确定性推理
- 第4章：不确定性推理方法
- 第5章：搜索求解策略
- 第6章：专家系统
- 第7章：群智能算法
- 第8章：机器学习概述
- 第9章：神经网络
概述
受自然界和生物界规律的启迪，人们根据其原理模仿设计了许多求解问题的算法，称为 “生物智能算法”，属于典型的元启发式随机优化方法。
主要包括“进化算法、群智能算法”两类。
遗传算法（重点）：提供了进化算法的框架，然后介绍几种比较典型的改进遗传算法及其应用。
群体智能算法（次重点）：包括“粒子群算法、蚁群算法”等。
进化算法EA - 定义、起源思想、应用
定义：进化算法(evolutionary algorithms)是一种基于自然选择和遗传学机理等生物进化机制的一种搜索算法，非常适用于处理“传统搜索方法”难以解决的“复杂和非线性优化问题”。
起源思想：以达尔文的进化论思想为基础，通过模拟生物进化过程与机制，而实现求解问题的自组织、自适应的人工智能技术。
进化算法EA - 生物学背景
大自然有种神奇的力量，生物通过进化，能够将优良的基因保留下来，从而进化出更加强大、更加适合生存的基因。
进化算法类似于生物进化，需经过长时间的成长演化，最后收敛到最优化问题的一个或多个解。
生物进化 - 基本过程
如图所示，不适合的个体会逐步退出这个循环圈，成为被淘汰的群体。
种群的多样性。
生物进化 - 物质基础
生物进化的物质基础是“种群中存在可遗传的变异”，简称“遗传多样性”。
- 染色体(chromosome)：生物的遗传物质的主要载体。
- 基因(gene) ： 具有遗传效应的 DNA片段，用于扩展生物性状的遗传物质的功能单元和结构单位。
- 基因座（locus）：染色体中基因的位置。
- 等位基因（alleles）：基因所取的值。
进化算法EA - 基本框架
进化算法：类似于生物进化，需要长时间的成长演化。主要通过“选择、重组和变异”这三种操作实现优化问题的求解，最后会慢慢收敛到最优化问题的一个或者多个解。其中“适者生存”是生物演化的一个过程规律。算法簇都包括“遗传算法、遗传规划、进化策略、进化规划”。其中“ 遗传基因表达方式、交叉和变异算子、特殊算子、再生和选择方法” 等，都是可调变量。
进化算法EA - 特点与对比
| 对比项 | 普通搜索算法 | 进化算法EA的特点 | 备注（针对进化算法） |
|---|---|---|---|
| 算法类型 | 迭代搜索算法 | - | |
| 起始点 | 从单一搜索点开始 | 从一组解出发，到另一组解 | 从一组解出发，通过选择、重组和变异操作，逐步改进到更优的解。 |
| 解的处理 （终点） | 只对结果值进行参数优化 | 需对结果值进行编码 | - |
| 搜索过程 | 能否使用的辅助信息有限 | 有效利用“结构化、随机性”信 息 | 利用结构化和随机性的信息，使最满 足目标的决策获得最大的生存可能 |
| 搜索信息 | 目标函数的导数 或具体问题有关的特殊知 识（启发式信息） | 目标函数值 | 广泛的应用性 l高度的非线性 l易修改性 l可并行性 |
| 全局优化方法 | 传统基于微积分的方法 穷举法 | 全局优化方法 | 自组织、自适应、自学习 l能适应不同环境和不同问题 l能够有效处理大规模复杂优化问题 |
进化算法EA - 设计原则
| 原则 | 说明 |
|---|---|
| 适用性 | 指该算法所能适用的问题种类，它取决于算法所需的限制与假 定。 |
| 可靠性 | l能可靠地求解大多数问题，即使在问题数据或控制参数发生 微小变化时也能得到合理的结果。 l指算法对于所设计的问题，以适当的精度求解其中大多数问题的能力。 |
| 收敛性 | 能收敛到全局最优解，且收敛速度较快。 |
| 稳定性 | 对控制参数和问题数据不敏感，即对控制参数或问题数据的微 小扰动不应导致算法结果的剧烈变化。 |
| 生物类比 | 生物界有效方法及操作可以通过类比的方法引入到算法中，有 时会带来较好的结果。 |
进化算法EA - 应用
遗传算法
遗传算法 - 概述
遗传算法（Genetic Algorithm，GA）：是一种模拟自然选择和遗传学机理的生物进化过程的计算模型。它最早由美国学者John Holland于20世纪70年代提出，主要用于搜索最优解。它是进化算法的一种。
Holland的学生Goldberg总结出了基本遗传算法(Simple Genetic Algorithms)，只使用选择算子、交叉算子和变异算子三种基本遗传算子，其遗传进化操作过程简单，容易理解，给各种遗传算法提供了一个基本框架。
基本思想：在求解最优化问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。
遗传算法的发展历史
基本遗传算法SGA - 特点
特点：遗传算法得到的是整体水平最优的一组解，各有好的特性，而不是以前最优化方法的单一的最优解。
遗传算法 - 重要概念
| 生物遗传概念 | 遗传算法中的应用 |
|---|---|
| 适者生存 | l适应度越大的个体被保留到下一代的概率越大(并不是一定会保留) |
| 个体（Individual） | l适应度函数中的特定解 |
| 染色体 （Chromosome） | l解的编码（字符串、向量等） |
| 基因（Gene） | l解的编码中每一分量 |
| 适应性（Fitness） | l适应度函数的函数值 |
| 群体（Population） | l根据适应度值选定的一组解（解的个数为群体的规模） |
| 婚配（Marry） | l交叉（Crossover）选择两个染色体进行交叉产生一组新的染色体的过程 |
| 变异（Mutation） | l编码的某一分量发生变化的过程 |
基本遗传算法SGA - 流程与5大要素
SGA1(选基因) - 参数编码
- 重要性：对一个具体的应用问题如何编码，是应用遗传算法求解的首要问题，也是遗传算法应用的难点。
- 引入原因：为什么需要对空间参数进行编码？由于遗传算法不能直接处理问题空间的参数，因此，必须通过编码将要求的问题，表示成遗传空间的染色体或者个体（它们由基因按一定结构组成）。编码后即可进行一般性操作，与具体问题无关，形成一般性的方法，从而能用在工程学上。
- 影响度：由于遗传算法的健壮性，对编码的要求并不苛刻。
SGA1(选基因) - 参数编码
| 编码方法（大类） | 小类 | 优点 | 二进制编码 缺点 lHamming悬崖 l要先给出求解的精度。 l求解高维优 | |
|---|---|---|---|---|
| 位串编码（一维染色体编码方法）：将问题空间的参数编码为一维排列的染色体的方法。 | 二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间 B={0，1}上，然后在位串空间上进行遗传操作。 | l类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等很容易实现； l算法处理的模式数最多。 | ||
| Gray编码：将二进制编码通过一个变换进行转换得到的编码。 | 克服了Hamming悬崖。 | |||
| 实数编码：用若干实数表示一个个体，然后在实数空间上进行遗传算法。 | - | 不必进行数制转换，可直接在解的表现型上进行遗传操作。 | ||
| 多参数映射编码：把每个参数 先进行二进制编码，得到子串，再把这些子串连成一个完整染 色体。 | - | l主要用于“多参数优化问题”； l每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。 |
SGA2(选人群) - 初始群体的设定
初始种群的产生
随机产生群体规模数目的个体作为初始群体。根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。
种群规模的确定
太小：遗传算法的优化性能不太好，易陷入局部最优解；
太大：计算复杂；
模式定理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测M3个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。
结论：种群规模一般取为20~100。
SGA3(竞争) - 适应度函数设计(直观法）
在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。一般而言，适应度函数是由目标函数变换得到的。
- 直观法：就是直接将“目标函数”映射成“适应度函数”，不加额外的处理。
- 欺骗问题：指在遗传算法中，所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题，主要会造成以下两种情况。
| 现象 | 原因 | 内容 | 解决方法 |
|---|---|---|---|
| 过早收敛 | 存在超级个体 | 某个体的适应值远超过群体的平均适应度值，在按比例进行选择时，该具体很快会在群体 中占据绝对比例。 | 缩小这些个体的适应度，以降低这些超级个体的竞争力。 |
| 停滞现象 | 群体平均适应值接近最优适应度 | 搜索过程后期，群体有足够多样性，但群体 平均适应值会接近群体的最佳适应度值，导 致群体中已不存在竞争，搜索目标难以改善。 | 改变原始适应值的比例关系，以提高个体之间的竞争力。 |
SGA4(遗传操作1) – 自然选择1
选择（也称复制，reproduction）操作：是从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则：是每个个体的适应度值；个体适应度越高，其被选择的机会就越多。
存在问题:
| 现象 | 原因 | 内容 | 解决方法 |
|---|---|---|---|
| 过早收敛 | 总选择最好的个体 | 变成确定性优化方法，使种群过快收敛到局部最优解。 | 找到一个策略，即要种群能较快 ， 地收敛，也要维 持种群的多样性。 |
| 收敛时间长，或不收敛 | 只做随机选择 | 变成了完全随机方法，需要很长时间才能收敛甚至不收敛。 |
其他的解决方法
| 类别 | 目标 | 可选方法 | 内容 | 特点 |
|---|---|---|---|---|
| 根据个体适应度，确定分配 “每个个体被选择的概率” （先验概率？） | 既要使得种群较快地收敛，也要维持种群的多样性。 | 适应度比例法， 或叫蒙特卡罗法 （Monte Carlo） | 每个个体被选择的概率和其适应度值成比例； | 容易“过早收 敛和停滞现象” |
| 排序法 | l线性排序：按适应值大小对个体进行排序，然后把事先设计好的概率按排序分配给个体，作为各自的选择概率。 l非线性排序：将群体成员按适应值从好到坏依次排列，并按某种方式分配选择概率。 | 克服了“过早收敛和停滞现象” |
轮盘赌选择算法
重要性：在遗传算法中使用得最多,同时也是其他选择算法的基本框架。
具体步骤：先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。
| 个体 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 适应度值 | 2 | 4 | 6 | 8 | 10 |
| 个体被选择的概率 | 0.07 | 0.13 | 0.2 | 0.27 | 0.33 |
| 累积概率 | 0.07 | 0.2 | 0.4 | 0.67 | 1 |
范 例
假设第一轮产生随机数0.21，则会落在个体3，表明本轮选择到了个体3(红色框框表示)
假设第二轮产生随机数0.04，则会落在个体1，表明本轮选择到了个体1(蓝色框框表示)
其他方法
| 名称 | 内容 | 特点 | |
|---|---|---|---|
| 方法2 | 锦标赛选择 法 | 从群体中随机选择k个个体，将适应度最高的保存到下一代，反复执行直到保存到下一代的个体数达到预设数量。参数k称为竞赛规模。 | 克服了适应值比例选择和排名选择在大规模群体中的额外计算量问题。比轮盘赌选择方法能够得到更多样化的群体。 适应值好的个体有较大的生存机会。使用适应值相对值作为选择标准，避免超级个体的影响，一定程度上避免过早收敛和停滞现象。 |
| 方法3 | 最佳个体 保存法 （精英选拔法，保送生） | 将群体中适应度最高的一个或多个个体不进行交叉，直接复制到下一代，保证遗传算法终止时得到历代最高适应度的个体 | 提高遗传算法的收敛速度。保留种群个体总数的2%~5%的适应度最高的个体，效果最理想。 l注意：在使用其他选择方法时，一般同时使用最佳个体保存方法，以保证不会丢失最优个体。 |
SGA4(遗传操作1) - 交叉
定义：当两个生物机体配对或者复制时，其染色体相互混合，产生一个由双方基因
组成的全新染色体组。该过程称为重组(recombination)或者交叉(crossover)。
单点交叉（常用方法）
原理：在随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。该方法交叉混合的速度较慢。
交叉概率：用来确定两个染色体进行局部互换以产生两个新子代的概率，取值为 0.25-1.00。实验表明通常取0.7比较理想。
其他修正交叉方法：部分匹配交叉、顺序交叉、循环交叉等。（详见课本内容）
SGA4(基因突变) - 变异
- 定义：进化机制除了改进已有的特征，也能够产生新的特征。基因传送给子孙后代过程中，会有很小的概率发生差错，从而使基因发生微小的改变，这就是基因的变异。
- 主要目的：维持群体的多样性，为选择、交叉过程中可能丢失的某些遗传基因进行修复和补充。
- 具体实施方法：将个体编码中的一些位进行随机变化。
- 变异算子的基本内容：对群体中的个体串的某些基因座上的基因值作变动。
- 变异操作：按位进行的，即把某一位的内容进行变异。
- 变异概率：在一个染色体中按位进行变化的概率。在实际应用中通常取值为0.001左右
| 变异方式 | 内容 |
|---|---|
| 位点变异 | 群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动 |
| 逆转变异 | 在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中 |
| 插入变异 | 在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间 |
| 互换变异 | 随机选取染色体的两个基因进行简单互换 |
| 移动变异 | 随机选取一个基因，向左或者向右移动一个随机位数。 |
总结：遗传算法一般步骤
遗传算法的特点
遗传算法比起其他普通的优化搜索，采用了许多独特的方法和技术，是一种全局优化搜索算法。
| 特点 | 说明 |
|---|---|
| 编码操作 | l可以直接对结构对象进行操作，如集合、序列、矩阵、树、图等，具有广泛的应用领域 |
| 随机技术 | l利用随机技术来指导对被编码的参数空间进行高效率搜索，而不是无方向的随机搜索 |
| 群体搜索 | l采用同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估，具有较好的全局搜索性能，减少了陷于局部优解的风险，也易于并行化 |
| 适应度函数 | l不用搜索空间的知识或其他辅助信息，而仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。 l适应度函数不受连续可微的约束，定义域可以任意设定，只要能够算出可以比较的正值。适合于解决复杂优化问题 |
SGA的改进算法
| 对比项 | SGA(单体遗传) | 双倍体遗传 | 双种群遗传 | 自适应遗传 |
|---|---|---|---|---|
| 染色体数目 | 每个基因有一条染色体 | 两个染色体：显性和隐性进行进化， | 不限 | 不限 |
| 适用生物群体 | 简单植物 | 高级植物 大多数动物 | 不限 | 不限 |
| 特点 | 简洁 | 提供一种记忆以前有用基因块的能力 | 使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破群内平衡状态达到更高平衡 | 使交叉概率Pc 和变异概率Pm 能随适应度变化而自动改变 |
| 优点 | 易实现 | 延长了有用基因块的寿命，提高算法收敛能力； l在变异概率低的情况下也保持种群的多样性 l动态跟踪能力强于SGA | 本质是一种并行算法，可提升算法效率 l有利于算法跳出局部 | 可以方便确定Pc和Pm 易于找到每个问题 的最佳值 |
群体智能算法 - 产生背景
群智能算法（Swarm algorithms，SI）：受动物群体智能启发的算法。
群体智能：由简单个体组成的群落与环境以及个体之间的互动行为。
粒子群优化算法PSO - 背景与思想
产生背景：粒子群优化（Particle Swarm Optimization, PSO）算法是由美国普渡大学的Kennedy和Eberhart于1995年提出，它的基本概念源于对鸟群觅食行为的研究。
核心思想：利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的可行解。
粒子群优化算法PSO - 场景
场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。
鸟群觅物最优策略：最简单有效的就是搜寻目前离食物最近的鸟的周围区域。小鸟们的目标很简单，要在这一带找到食物最充足的位置安家、休养生息。试着想一下一群鸟在寻找食物，在这个区域中只有一只虫子，所有的鸟都不知道食物在哪。但是若：1）它们知道自己的当前位置距离食物有多远；2）同时它们知道离食物最近的鸟的位置。想一下这时候会发生什么？
鸟A：哈哈哈，原来虫子离我最近！
鸟B,C,D：我得赶紧往 A 那里过去看看！
同时各只鸟在位置不停变化时候，离食物的距离也不断变化，所以一定有过离食物最近的位置，这也是它们的一个参考。
某鸟：我刚刚的位置好像靠近了食物，我得往那里靠近！（鸟类的这几种想法是粒子群算法的核心）
粒子群优化算法PSO - 基本原理
基于以上情况，鸟群在该地方的搜索策略如下：
1.每只鸟随机找一个地方，评估这个地方的食物量；
2.所有的鸟一起开会，选出这群鸟遇到的食物量最多的地方作为安家的候选点G（未来）；
3.每只鸟回顾自己的旅程，记住自己曾经去过的食物量最多的地方P（过去）；
4.每只鸟为找到食物量更多的地方，于是向着G飞行，但是呢，不知是出于选择困难症还是对P的留恋，或者是对 G的不信任，小鸟向G飞行时，时不时也向P飞行，其实它自己也不知道到底是G的食物多还是向P的食物多。毕竟G和P方向的食物都比较多；
5.另外还考虑鸟儿飞行的惯性，也就是鸟儿无法立即停下来，由于惯性它会下一次飞行到达点Q（当前）；
6.又到开会时间，如果小鸟们决定停止寻找，则会选择G来安家；否则继续2->3->4->5->6来寻找栖息地。
现在我们赋予鸟儿一些参数：
粒子群优化算法PSO - 效果
PSO的优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。
蚁群算法ACO - 产生背景
F20世纪90年代，意大利科学家Marco Dorigo提出模拟自然界中蚂蚁觅食行为的ACO。
ACO具有“分布计算、信息正反馈和启发式搜索”特征，是一种启发式全局优化算法。
该算法在网络路由中的应用受到广泛关注，因具有“信息分布式性、动态性、随机性和异步性”等特点，能够满足网络路由的需求。
- 灵感：来源于蚂蚁在寻找食物过程中发现最短路径的行为。
- 信息素累积：蚂蚁在觅食时会在其经过的路径上释放一种称为信息素的物质，其他蚂蚁能够感知环境中的信息素并倾向于选择信息素浓度较高的路径。
- 正反馈机制：随着时间的推移，信息素的积累和挥发形成了一种正反馈机制，使得蚁群能够找到最短路径到达食物源。
蚁群算法ACO - 核心思想
蚁群算法的核心包括三个方面：
蚂蚁利用信息素进行通信。蚂蚁会在经过的路径上释放信息素，其他蚂蚁能够感知环境中的信息素并选择信息素浓度较高的路径。
蚂蚁具有记忆行为。一个蚂蚁一般不会选择相同的路径两次。
蚂蚁具有集群活动。某条路径上通过的蚂蚁越多，路径上留下的信息素就越高，信息素还会挥发。
蚁群算法的一个重要原则是避障原则，即蚂蚁不能穿过障碍物。此外，蚂蚁在刚离开窝或者食物附近播散的信息素最多，信息素会自然挥发。蚁 群 算 法 最 早 用 来 求 解 旅 行 商 问 题（Traveling Salesperson Problem, TSP），并且表现出了很大的优越性。它具有分布式特性、鲁棒性强并且容易与其他算法结合，但是同时也存在收敛速度慢、容易陷入局部最优等缺点。
