遗传算法

此思维导图比较详细的介绍了遗传算法，包括它的特点、应用领域、基本流程、遗传算法的若干概念、遗传算法的应用步骤、遗传算法具体步骤等，欢迎小伙伴们观看使用。

遗传算法

• 概述
  • 模仿生物遗传进化原理，通过选择、交叉与变异等操作机制，使种群中个体的适应性不断提高
• 特点
  • 优点
    • 良好的并行性
      • 操作对象是一组可行解；搜索轨道有多条
    • 强大的通用性
      • 只需利用目标的取值信息，无需梯度等高价值信息
    • 良好的全局优化性和鲁棒性
    • 良好的可操作性
  • 缺点
    • 未成熟收敛问题
    • 收敛速度较慢，算法实时性欠佳
• 应用领域
  • 函数优化（经典应用）
  • 组合优化（旅行商问题——已成为衡量算法优劣的标准、背包问题、装箱问题等）
  • 生产调度问题
  • 自动控制（如航空控制系统的优化设计、模糊控制器优化设计和在线修改隶属度函数、人工神经网络结构优化设计和调整人工神经网络的连接权等优化问题）
  • 机器人智能控制（如移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解等）
  • 图像处理和模式识别（如图像恢复、图像边缘特征提取、几何形状识别等）
  • 机器学习（将GA用于知识获取，构建基于GA的机器学习系统）
• 基本流程
  • p
  • p
• 遗传算法的若干概念
  • 个体(Individual)
    • 称 p为个体空间，个体空间的元素 p称为个体，它是染色体带有特征的实体。分量p 称为基因，正整数 称为个体的基因长度。
  • 种群(Population)
    • 称个体空间S中N个个体组成的一个子集（个体允许重复）称为一个种群，记为：p，其中p，N称为种群规模
  • 适应度（Fitness）
    • 在遗传算法中，一般通过适应度函数（Fitness function）来衡量某一个体的适应度高低。
  • 编码（Coding）
    • 将一个待求解的问题的实际可行解从其解空间转换到遗传算法所能处理的搜索空间（即个体空间）的过程，就称为编码。
  • 解码（Decoding）
    • 解码是将遗传算法所搜索到的最优个体的染色体转换成待求解问题的实际最优解的过程，即编码的逆过程。
  • 选择操作（Selection）
    • 根据各个个体的适应度，按照一定的规则，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。一般地，选择操作通过选择算子（Selection Operator）进行
  • 交叉操作（Crossover）
    • 将群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率（称为交叉概率，Crossover Rate）遵循某一种规则交换它们之间的部分染色体。
  • 变异操作（Mutation）
    • 对群体P(t)中的每一个个体，以某一概率（称为变异概率，Mutation Rate）改变某一个或某一些基因座上的基因值为其他的等位基因。
• 遗传算法的应用步骤
  • （1）确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间
  • （2）建立优化模型，确定出目标函数的类型及其数学描述形式或量化方法。
  • （3）确定表示可行解的染色体编码方法，即确定出个体的基因型X*，及遗传算法的搜索空间。
    • 编码是遗传算法解决问题的先决条件和关键步骤
      • ①不仅决定个体基因的排列形式（从而决定选择与繁殖等操作的作用方式），而且也决定从搜索空间的基因型到解空间的表现型的解码方式（从而决定对GA所获解的翻译与理解）；
      • ②决定GA搜索的困难度与复杂性；
      • ③决定对问题的求解精度。
    • 常用的遗传算法编码方法主要有：二进制编码、浮点数编码等。可以证明，二进制编码比浮点数编码搜索能力强，但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样性。
    • 标准遗传算法多采用二进制编码方法，将决策变量用二进制字符串表示，二进制编码串的长度由所求精度决定。然后将各决策变量的二进制编码串连接在一起，构成一个染色体。 例如：变量x的定义域为[-2，3]，要求其精度为10-5，则需要将[-2，3]分成至少500 000个等长小区域，而每个小区域用一个二进制串表示。于是有p,p
  • （4）确定解码方法，即确定出由个体基因型X*，到个体表现型X的对应关系和转换方法。
    • 例如：对于二进制编码，其解码过程如下：若X*的取值范围为[Xl,Xr]，参数的二进制编码码长为L，码串对应的十进制整数为k，则解码公式为:p 式中， [Xl,Xr]——参数最小、最大值； L——参数编码长度； k——二进制串对应的实数值。
  • （5）确定个体适应度的量化评价方法，就是确定出由目标函数值到个体适应度的转换规则
    • 标准遗传算法的适应度函数常用一下三种
      • Ⅰ、直接以待求解的目标函数为适应度函数 若目标函数为最大值问题，则Fit(f(X))=f(X) 若目标函数为最小值问题，则Fit(f(X))=－f(X)
        • 优点：简单直观；
        • 缺点：其一，可能不满足非负的要求；其二，某些代求解的函数值分布相差很大，由此得到的平均适应度可能不利于体现种群的平均性能。
      • Ⅱ、界限构造法 若目标函数为最大值问题，则p Cmax为f(x)的最大值估计。 若目标函数为最小值问题，则p Cmin为f(x)的最小值估计。
        • 该方法是第一种方法的改进，但有时存在界限值预先估计困难或估计不精确等问题。
      • Ⅲ、 倒数法 若目标函数为最小值问题，则p 若目标函数为最大值问题，则p C为目标函数界限的保守估计值。
  • （6）确定各遗传具体操作方法
    • ①选择算子和选择操作
      • 个体选择概率的常用分配方法有以下两种
        • A、 按比例的适应度分配（Proportional Fitness Assignment） 亦可称为选择的蒙特卡罗方法，是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。若某个个体i，其适应度为fi，则其被选取的概率表示为,p，显然选择概率大的个体，能多次被选中，它的遗传因子就会在种群中扩大。
        • B、 基于排序的适应度分配（Rank-based Fitness Assignment） 在基于排序的适应度分配中，种群按目标值进行排序。适应度仅仅取决于个体在种群中的序位，而不是实际的目标值。 排序方法比比例方法表现出更好的鲁棒性，它能在一定程度上克服了比例适应度计算的尺度问题和过早收敛问题。
      • 个体选择概率确定后，可以选用的常用选择算法有轮盘赌选择法（Roulette Wheel Selection）、随机遍历抽样法（Stochastic Universal Sampling）、局部选择法（Local Selection）、截断选择法（Truncation Selection）和锦标赛选择法（Tournament Selection）等。标准遗传算法常用的轮盘赌选择法的原理如右下图所示。p
      • 几种提高遗传算法性能的选择方法
        • Ⅰ稳态繁殖（Steady State Reproduction） 在迭代过程中用部分优质新子个体来更新群体中部分父个体，作为下一代种群。
        • Ⅱ没有重串的稳态繁殖（Steady State Reproduction without Duplicates） 在稳态繁殖的基础上，形成下一代新种群时，使其中的个体不重复。
    • ② 交叉率及交叉操作
      • 交叉，也可以称为基因重组（Recombination），是遗传算法获取新的优良个体的最重要的手段，决定了遗传算法的全局搜索能力。
      • 一般地，当随机产生的概率大于交叉率，遗传算法就会按一定规则选择两个个体，执行交叉操作。交叉率的选择决定了交叉的频率，较大的交叉率使各代充分交叉，但群体中的优良模式遭到破坏的可能性增大，以致产生较大的代沟，从而使搜索走向随机化；交叉率越低，产生的代沟越小，就会使得更多的个体直接复制到下一代，遗传搜索可能陷入停滞状态，一般建议取值范围0.4~0.9。
      • 对于二进制编码，常用的交叉方法有：单点交叉、多点交叉和均匀交叉等。此外，还有部分匹配交叉（Partially Matched Crossover）、顺序交叉（Ordered Crossover）、洗牌交叉（Shuffle Crossover）等等。
    • ③变异率及变异操作
      • 变异本身是一种局部随机搜索，使遗传算法具有局部的随机搜索能力；同时使得遗传算法保持种群的多样性，以防止出现非成熟收敛。
      • 一般地，随机产生的概率大于变异率就会触发变异操作。变异率一般可取0.001~0.1。变异率不能取得太大，如果大于0.5，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特性和搜索能力也不复存在了。
      • 常用的变异操作方法有：实值变异法和二进制变异法等
        • p
        • p
  • （7）确定遗传算法的有关运行参数，包括群体规模(Population Size)、迭代次数（一般取为100~500）、选择算子、交叉率、变异率等等
    • p
  • （8）初始化群体
    • 初始群体一般随机产生
    • 初始值最好能在解空间中均匀采样（收敛速度比较快 ）
    • 对于非二进制编码，还要考虑所生成的染色体是否在可行区域内
  • （9）计算群体中个体解码后的适应值
  • （10）按照遗传策略，运用所选定的选择、交叉和变异算子作用于群体，生成下一代群体。
  • （11）判断群体性能是否满足某一指标或是否完成预定迭代次数，不满足则返回（9）。
• 未成熟收敛问题（Premature Convergence）
  • （1）未成熟收敛现象
    • 未成熟收敛现象是遗传算法中的特有现象，且十分常见。它是指，当遗传算法还没找到全局最优解或满意解时，群体中不能再产生性能超过父代的后代，群体中的各个个体非常相似。未成熟收敛的重要特征是群体中个体结构的多样性急剧减少。
  • （2）未成熟收敛产生的原因
    • 理论上考虑的选择、交叉、变异操作都是绝对精确的，他们相互协调，能搜索到整个解空间，但实际不然；
    • 存在随机误差（主要包括取样误差和选择误差）；
    • 所求解的问题是遗传算法欺骗问题。
  • （3）未成熟收敛的防止
    • p
• 遗传算法具体步骤
  • （1）选择编码策略，把参数集合（可行解集合）转换染色体结构空间；
  • （2）定义适应度函数，便于计算适应值；
  • （3)确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；
  • （4）随机产生初始化群体
  • （5）计算群体中的个体或染色体解码后的适应值
  • （6）按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体
  • （7）判断 群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步