二进制

7.1 标准遗传算法

1 GA简介

• 进化计算技术中的一种
  • 进化计算起源1960s,是仿生学开始发展的年代
• 以达尔文进化论为理论基础
• Michigan大学的J.Holland教授75

 

• 简单
• 通用
• 鲁棒
• 并行

遗传算法怎么用， 

• 广泛应用于
• 优化问题求解
• 自适应控制
• 规划设计
• 机器学习
• 人工生命

2 生物学背景

3 标准遗传算法

1编码

• 可行解x编码成可用于遗传算法操作的形式
• 5位二进制无符号整
• 13编码成01101
• 编码后,把原问题的解空间对应到染色体集合。

2初始种群的生成

• 遗传算法的操作是群体型操作

• 首先要有一个群体，

• 混合遗传算法？最初确定的这个群体称初始种群。

• 选4个个体组成初始种群

01101
11000
01000
10011

• 由算法设计者决定种群的规模

3适应度评估检测

 

• 遗传算法简单易懂的例子，本例关心的是函数值

• 可行解“含有适应外部环境的信息”为：

  • 该解的函数值

• 函数值越大，解性质越好

 

• 初始种群中的4组解适应度

4选择

• 从当前种群中选择性状优良的个体,使它们有机会作为父代,
  • 繁殖出性状优良的下一代。
• 适应度越高的个体,被选择的机会就越多
• 用轮盘赌方法来选择

遗传算法基因长度，

 

 

• 第1次选择:指针向①,选第1个个体
• 01101

 

• 第二次
• 11000

基因算法和遗传算法？ 

• 三次
• 11000

 

• 四次
• 10011

 

• 作为父本，参与繁殖

 

• 选择操作结束后,
• 被选中的个体是其本身的遗传性状比较好,选择概率大。

5交叉操作

• 对配对库中的个体随机配对

 

 

• 模仿DNA复制的机制，对配对的个体进行交叉

 

• 对另一对个体交叉

 

• 交叉后，得新种群

• 经过前面的部分操作，

  • 新一代种群的遗传特性应该优于前一代种群

• 本问题，得到的新的可行解的函数值更大了，距离最优解更近

6 变异

• 变异操作是按位进行，

  • 把一位的内容进行变异。

• 对二进制编码的个体，若某一位原为0，则变异后就变成1，

• 变异概率应该很小。

• 本例子中取P=0.001。

• 平均来说1000位中才有一位要进行变异操作。

• 群体中共有20位，繁殖一次后没有一位可变异。

  • 至少要繁殖50代后，才有一位可变异。

 

• 第1代繁殖完成,产生新的种群。
• 也就是第1次迭代结束,产生新的可行解。
• 要得到更好可行解,要继续迭代。
• 演示第2次迭代

第二次迭代

• 对新种群

• 作如下

适应度计算

选择

• 用轮盘赌方法选择。

 

• 第1次选择:
  • $y_1$
• 第2次
  • $y_3$
• 第三次
  • $y_2$
• 第四次
  • $y_2$

 

• 被选中的个体送到配对库

• 作为父本，繁殖下一代。

交叉操作

• 首先，对配对库中的个体随机配

• 其次，模仿DNA复制的机制，对配对的个体交叉

• 同理，对另一对个体交叉

 

• 交叉后的新的种群

• 经过前面各部分操作,新一代种群的遗传特性应优于前一代种群的特性
• 本问题中,就是得到的新的可行解的函数值更大

变异

• 群体中共有20位，再繁殖一次后仍没有一位可变异。

• 第2代繁殖完成,产生新的种群。

• 第2次迭代结束,产生新的可行解。

• 要得到更好的可行解,还要继续迭代

上例每次迭代

• 初始种群

 

• 第一次迭代

 

• 第2次迭代结果

 

• 每次迭代,群体中的个体的遗传性状都有改良,
  • 可行解中最好解的函数值都在增大
  • 这种逐步向最优解靠近的性质称为收敛性
• 标准遗传算法的原理和操作流程介绍完

问题

• 遗传算法的各操作步骤中有哪些技术
• 编码有哪些技术
• 初始种群的生成
• 适应度的计算
• 交叉操作
• 变异操作
• 停机准则应怎样确定
• 算法是否有收敛性

7.2 遗传算法的基本原理和方法

7.2.1编码

编码定义

• 问题空间

  • 由GA表现型个体(有效的候选解)集合组成的空间

• GA空间

  • 基因型个体集合组成的空间

• 问题空间到GA空间的映射称coding

• GA空间到问题空间的映射称decoding

编码（译码）评估规范和编码原理

• 完备性：
  • 问题空间中的所有点（候选解）
  • 都能为GA空间中的点（染色体）表现
• 健全性：
  • GA空间中染色体能对应所有问题空间中的候选解
• 非冗余性
  • 染色体和候选解一一对应

编码规则

• 易于生成与所求问题相关的短距和低阶积木块。
• 采用最小字符集以使问题得到自然的表达或描述

编码技术

• (略)

7.2.2初始种群

• 初始种群的设定应满足一些策略
• 种群应具有多样性

7.2.3适应度函数

• 适应度函数的设计方法

适应度函数的定标(scaling)

• 适应度和幸存再生彼此相关
• 大量的后代幸存
  • 是由于它们能够适应环境,
  • 能适应环境是由于它们的有大量的后代幸存
• 自然界中,幸存是最终目标。
• 为此,有必要,也有机会来调整群体中成员的竞争水平,
  • 以便获得适应度高的个体。
• 这种对适应度的调整称为适应度定标

7.2.4遗传操作

• 遗传操作:选择、交叉、变异

• 选择操作

  • 常用方法
  • 适应度比例法,即轮盘赌方法
  • 最佳个体保存法
  • 期望值方法
  • 排序选择方法

 

• 交叉操作
• 常用的方法:
  • 一点交叉
  • 二点交又
  • 多点交又
  • 一致交叉

 

• 变异操作
• 常用的方法有
• 基本变异
• 逆转算子

7.2.5遗传算法的理论

模式理论

• 在整个算法的迭代过程中,每个个体中含有某种结构,这个结构叫模式

• 模式理论给出模式的定义,分析了在迭代过程中,

  • 模式是如何一代一代传下去的
  • 分析了模式的运作规律

依概率收敛理论

• 依概率收敛理论用概率论的原理和方法,
• 分析每一代个体(可行解)随迭代次数的增加
• 在概率意义下,逐步向最优解靠近的过程。
• 并给出一些结论。

马尔可夫链理论

• 马尔可夫链理论是用一类随机过程马尔可夫过程,
• 一代种群与下一代种群之间的概率特性,
  • 并给出一些结论

7.3 无标题

7.3.1 旅行商问题

1 旅行商问题

• C1,C2,…Cn。
• 推销员从C1出发,走遍所有城市,返C1
• 选什么路径,使总距离最短

2 编码

• 遍历城市的次序排列方式编码
• 串12345678表示

3 适应度计算

• 用路径长度的倒数.

• 长度越长，该串的适应度越小。
• 与目标：找长度最小的串，一致

4 交叉策略

• 若用一点交叉，则可能破坏遍历性，产非法路径

• 交叉后的串都没遍历8个城市，违反约束

1 （PMX, partally matched crossover）

 

2) 顺序交叉

• 与PMX相似，此法也开始选择一个匹配区域

• 区域外，找出交叉后产生重复数字的位置，并标出

 

• 移动匹配区域至起点，在其后面预留相等于匹配区域的空间，
  • 即H的数目，
  • 再将其余的码按照相对应的次序排列在预留区后面

 

• 最后将父串A、B的匹配区域交换
• 放到$A^{\prime \prime },B^{\prime \prime }$的预留区内，得

3) 循环交叉

• 以父串特征为参考，在满足城市约束条件下重组

 

 

 

 

• 共确定3个循环。

• 以循环为单位，交叉。

• 选择第2、3个循环交叉，其它循环不动，