简单遗传算法

发表于 更新于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

还是实习期间的笔记，但是没学完。无奖竞猜，我会填坑吗？

简单遗传算法原理

其实这是一张mermaid图，但是我还没加mermaid扩展，脑补吧

1
2
3
4
5
6
7
8
9
10
11
12
13
---
title: 遗传算法的基本框架
config:
  flowchart:
    curve: monotoneX
---
flowchart LR
开始([开始])-->编码-->产生初始种群-->计算适应度-->chosen{是否满足优化规则}-->|Yes|最佳个体-->encoding["解码（基因到性状）"]-->结束([结束])
chosen-->|No|选择
subgraph 遗传
    选择-->交叉-->变异
end
变异--子代-->计算适应度

基本原理博客园

step 1: 编码

编码包括

  1. 二进制编码
  2. 格雷码
  3. 实数编码（高维复杂情况下常用）
  4. 多参数级联编码（多个子串串连）

二进制编码缺点：

  1. 进位时要改变所有的位()，用格雷码可以克服
  2. 要先给出求解的精度，没法微调，精度低误差大，精度高串长效率低
  3. 高维优化问题，串非常长，效率很低

格雷码

这里⊕为异或符号

alt text

step 2: 群体设定

可以随机生成，组成初始群体；也可以根据先验知识生成。种群规模一般取为20~100。
规模小了优化性能不好且可能引起未成熟收敛，规模大计算复杂。

step 3: 适应度评估

适应度函数
适应度越高，个体越好。一般最大化问题，适应度函数取；最小化则

设变换前适应度为，变换后适应度为
不同的变换方法：

  • 线性变换：
  • Boltzmann变换：
  • 乘幂变换：
  • 归一化变换：

适应度共享：根据个体在某个距离内与其他个体的临近程度，来确定该个体的适应度应改变多少。
根据距离测度分类：

  • 基因型共享：码空间距离
  • 表现型共享：解空间距离

step 4: 选择

选择：从群体中选择优胜个体，淘汰劣质个体的操作。即从当前群体中选择适应度较高的个体以生成配对池。
选择压力：最佳个体选中的概率平均选中概率

选择方式如下：

随机选择

  • 选择幅度决定了每个个体被复制的次数
  • 选择幅度由以下两部分组成
    • 确定染色体的期望值
    • 将期望值转换成实际值（即该染色体后代个体）的数目
  • 常用选择方式
    • 轮盘赌（比例选择算子）
    • 一次随机采样

确定性采样

（直接放书本原文了）
确定性采样就是从父代和子代个体中选择最优的个体。具体举例如下：
(1) (μ+λ)-selection(μ个父代，λ个子代，从μ+λ中选择最好的μ个个体)；
(2) (μ，λ)-selection(μ个父代，λ个子代，从λ中选择最好的μ个个体)；
(3) Truncation selection(截断选择)；
(4) Block selection(块选择)；
(5) Elitist selection(贪婪选择，在比例选择最优个体时没有被选择，进行强制选择)；
(6) The generational replacement(代替换)；
(7) Steady-state reproduction(稳态再生，n个最差的父代个体被子代替换)。

混合采样

混合采样同时具有随机性和确定性，具体举例如下：
(1) Tournament selection(竞赛选择)；
(2) Binary tournament selection(规模为2的竞赛选择)；
(3) Stochastic tournament selection(采用普通的方法计算选择概率，然后采用赌盘选择个体，适应度高的进入群体，否则被抛弃)；
(4) Remainder stochastic sampling(随机保留采样，期望选择次数的整数部分确定，小数部分随机)。

step 5: 交叉

交叉：把两个父代个体的部分结构加以替换，生成新的个体，来提高搜索能力。
原理动图

step 6: 变异

变异：将染色体编码串中的某些基因用其它的基因来替换，改善局部搜索能力。

随机变异

1 2 3 4 5 6 7 8 9
↓
1 2 5 3 4 6 7 8 9

或者

1 2 3 4 5 6 7 8 9
↓
1 5 3 4 2 6 7 8 9

实数变异

基于方向的变异

高斯变异