Envolutionary Algorithm

进化算法

进化算法:

  • 后设启发式算法:适合多种最优化问题,但不保证找到全局最优

Genetic Algorithm

遗传算法:模拟自然界生物进化过程,采用人工进化的方式对目标 空间进行搜索

  • 本质是高效、并行、全局搜索方法
  • 能在搜索过程中自动获取、积累有关搜索空间的知识,并自适应 的控制搜索过程以求的最佳解

思想

  • 将问题域中可能解看作是染色体,将其编码为符号串的形式
  • 对染色体群体反复进行基于遗传学的操作:选择、交叉、变异
  • 根据预定目标适应度函数对每个个体进行评价,不断得到更优 群体,从中全局并行搜索得到优化群体中最优个体

实体

  • population:群体,GA的遗传搜索空间
  • individual:个体,搜索空间中可能解
  • chromosome:染色体,个体特征代表
    • 由若干段基因组成
    • GA中基本操作对象
  • gene:基因
    • 染色体片段
  • fitness:适应度,个体对环境的适应程度

基本操作

  • selection:选择,根据个体适应度在群体中按照一定概率 选择个体作为父本

    • 适应度大个体被选择概率高
    • 体现了适者生存、优胜劣汰的进化规则
  • crossover:交叉,将父本个体按照一定概率随机交换基因 形成新个体

  • mutate:变异,按照一定概率随机改变某个体基因值

串编码方式

  • 把问题的各种参数用二进串进行编码构成子串
  • 把子串拼接成染色体
    • 串长度、编码方式对算法收敛影响极大

二进制编码方式

二进制法:使用二进制染色体表示所有特征

  • 优点

    • 编码、解码操作简单
    • 交叉、变异等遗传操作便于实现
    • 符合最小字符集编码原则
    • 利于模式定理对算法理论分析
  • 缺点

    • 连续函数离散化存在误差,染色体长度短时达不到精度 要求,较长时解码难度大、搜索空间增大
    • 对连续函数优化问题,随机性使得其局部搜索能力较差, 接近最优值时不稳定

浮点编码

浮点法:个体的每个基因值用某一范围内的一个浮点数表示

  • 必须保证基因之在给定区间限制范围内

    • 交叉、变异等遗传算子结果也必须在限制范围内
  • 优点

    • 适用于在遗传算法中表示范围较大的数
    • 精度较高
    • 便于较大空间的遗传搜索
    • 改善了遗传算法的计算复杂性,提高了运算效率
    • 便于遗传算法与经典优化方法的混合使用
    • 便于设计针对问题的专门知识的知识型遗传算子
    • 便于处理复杂的决策变量约束条件

符号编码法

符号法:个体染色体编码串基因值取自无意义字符集

  • 优点
    • 符合有意义积木块编码原则
    • 方便利用所求解问题的专门知识
    • 访问GA和相关近似算法的混合使用

Fitness Function

适应度/对象函数

  • 一般可以把问题模型函数作为对象函数

  • 过程

    • 解码个体,得到个体表现型
    • 由个体表现型计算个体目标函数值
    • 根据最优化问题类型,由目标函数值按一定转换规则求出 个体适应度

操作

选择函数

  • Roulette Wheel Selection:轮盘赌选择,个体进入下一代 概率为其适应度与整个种群适应度之比

    • 放回式随机抽样
    • 选择误差较大
  • Stochastic Tournament:随机竞争选择,每次按轮盘赌选择 一对个体,选择适应度较高者,重复直到选满

  • 最佳保留选择:按轮盘赌选择方法执行遗传算法选择操作,然后 t将当前群体中适应度最高的个体结构完整地复制到下一代群体中

  • Excepted Value Selection:无回放随机选择,根据每个个体 在下一代群体中的生存期望来进行随机选择运算

    • 计算群体中每个个体在下一代群体中的生存期望数目N
    • 若体被选中参与交叉运算,则它在下一代中的生存期望数目 减去0.5,否则在下一代中的生存期望数目减去1.0
    • 随着选择过程的进行,当个体的生存期望数目小于0时,则 该个体就不再有机会被选中。
  • 确定式选择:按照一种确定的方式来进行选择操作

    • 计算群体中各个体在下一代群体中的期望生存数目N
    • 用N的整数部分确定个体在下一代群体中的生存数目
    • 用N的小数部分对个体进行降序排列,顺序取前M个个体加入 到下一代群体
    • 完全确定出下一代群体中M个个体
  • 无回放余数随机选择

    • 可确保适应度比平均适应度大的一些个体能够被遗传到 下一代群体中
    • 选择误差比较小
  • 均匀排序:对群体中的所有个体按期适应度大小进行排序,基于 这个排序来分配各个个体被选中的概率

  • 最佳保存策略:当前群体中适应度最高的个体不参与交叉运算 和变异运算,而是用它来代替掉本代群体中经过交叉、变异等 操作后所产生的适应度最低的个体

  • 随机联赛选择:每次选取几个个体中适应度最高个体遗传到 下一代群体中。

  • 排挤选择:新生成的子代将代替或排挤相似的旧父代个体,提高 群体的多样性

Cross Over

  • One-point Crossover:单点交叉,在个体编码串中只随机 设置一个交叉点,然后再该点相互交换两个配对个体的部分 染色体

  • Two-point Crossover:两点交叉,在个体编码串中随机设置 两个交叉点,然后再进行部分基因交换

  • Multi-point Crossover:多点交叉

  • Uniform Crossover:均匀交叉/一致交叉,两个配对个体的 每个基因座上的基因都以相同的交叉概率进行交换,从而形成 两个新个体

  • Arithmetic Crossover:算术交叉,由两个个体的线性组合 而产生出两个新的个体

    • 操作对象一般是由浮点数编码表示的个体

Mutation

  • Simple Mutation:基本位变异,对个体编码串中以变异概率 、随机指定的某一位或某几位仅因座上的值做变异运算
  • Uniform Mutation:均匀变异,用符合某一范围内均匀分布 的随机数,以较小的概率来替换个体编码串中各个基因座上原有 基因值

    • 适用于在算法的初级运行阶段
  • Boundary Mutation:边界变异,随机的取基因座上的两个 对应边界基因值之一去替代原有基因值

    • 适用于最优点位于或接近于可行解的边界时的一类问题
  • 非均匀变异:对原有的基因值做一随机扰动,以扰动后的结果 作为变异后的新基因值

    • 对每个基因值都以相同的概率进行变异运算之后,相当于 整个解向量在解空间中作了一次轻微的变动
  • 高斯近似变异:进行变异操作时用符号均值为P、方差$P^2$的 正态分布的一个随机数来替换原有的基因值

GA超参设置

  • 群体大小$n$:过小难以求出最优解,过大难收敛,一般取 $n = 30 ~ 160$

  • 交叉概率$P_c$:太小难以前向搜索,太大容易破坏高适应 值结构,一般取$P_c = 0.25 ~ 0.75$

  • 变异概率$P_m$:太小难以产生新结构,太大则变为单纯 随机搜索,一般取$P_m = 0.01 ~ 0.2$

算法

  1. 随机初始化种群
  2. 估初始种群:为种群每个个体计算适应值、排序
  3. 若没有达到预定演化数,则继续,否则结束算法
  4. 选择父体
    • 杂交:得到新个体
    • 变异:对新个体变异
  5. 计算新个体适应值,把适应值排名插入种群,淘汰最后个体
  6. 重复3

Differential Evolution

差分进化算法:

Particle Swarm Optimization

粒子群/微粒群算法:

Author

UBeaRLy

Posted on

2019-07-21

Updated on

2019-07-21

Licensed under

Comments