4.1遗传算法在线视频

大家好

本次课主要讲授遗传算法

遗传算法又称基因算法

它是模拟生物遗传学和

自然选择机理

通过人工方式所构造的

一类优化搜索算法

是对生物进化过程

进行的一种数学仿真

是进化计算的最重要的形式

遗传算法最早由

美国密歇根大学的

Holland教授提出

起源于上世纪60年代

对自然和人工自适应系统的研究

上世纪70年代

De Jong基于遗传算法的思想

在计算机上进行了大量的

纯数值函数优化计算实验

在一系列研究工作的基础上

上世纪80年代由Goldberg

进行归纳总结

形成了遗传算法的基本框架

考虑全局优化目标函数求极小值

公式如4.1-1所示

其中D为可行域

在遗传算法中

需要对决策变量

也就是问题的解进行编码

通过编码变换F将

可行域D映射为Dg

要求F可逆

逆变换F-1称为解码

基本遗传算法只使用选择

交叉

变异

这三种基本遗传算子

其遗传进化操作过程简单

容易理解

是其他一些遗传算法的雏形和基础

它不仅给各种遗传算法

提供了一个基本框架

同时也具有一定的应用价值

基本遗传算法

步骤如下所示

在遗传算法中

编码的目的是为实现交叉

变异等类似于生物界的

遗传操作

编码的方式有二进制编码

实数编码

有序串编码

结构式编码

等多种

最常用的编码方式

是二进制编码

举例

例如

设某数的取值范围是A，B

用t位长的二进制编码

来表示该数

可将B-A分成2的t次方-1等份

假设某一个个体的编码是

则它对应的实数为式4.1-2所示.

在遗传算法中

适应度函数是衡量群体中

个体适应性的度量标准

是算法演化过程的驱动力

而在传统的优化方法中

判断一个解好坏是

根据目标函数值的大小

因此

存在目标函数到

适应值函数的对应问题

适应度函数应满足

第一

非负性

第二

目标函数的优化方向

对应适应度函数增加方向

对于极小化问题

可取适应度函数如式4.1-3所示

其中CM为接近f（X）上界的常数

对于极大化问题

可取适应度函数如式4.1-4所示

其中CM为接近f（X）下界的常数

满足算法停止的

最简单的两个条件

第一

完成了预先给定的进化代数则停止

第二

群体中的最优个体在连续若干代

没有改进或平均适应度

在连续若干代基本没有改进时停止

在遗传算法中

每一个个体都有相应的适应值

用以表示该个体对环境的适应能力

选择操作就是根据种群中

个体的适应值来确定

当前种群即父代中哪些个体

能进入下一代即子代继续演化

选择应保证高适应值的

个体被选择的机会高

它实际上是对自然选择

适者生存的模拟

不同的选择策略对对算法的

性能具有较大的影响

常用的选择策略包括

基于适应值比例的选择

基于排名的选择

基于局部竞争机制的选择等

其中基于适应值比例的选择

也是基本遗传算法中的选择

使用最多的一种选择

基于适应值比例的

选择算法步骤如下所示

例如

某种群有4个个体

X1,X2,X3,X4

其适应度分别为

150,80,40,100

那么X1,X2,X3,X4

的选择概率分别为

0.40，0.22，0.11，0.27

这样X1,X2,X3,X4

实际被选中的次数分别为2,1,0,1

交叉算子是一种

重要的遗传算子

种群通过交叉操作

产生新的个体

从而不断扩大搜索空间

最终达到全局搜索的目的

将被选择出的两个个体

A，B作为父母个体

将两者的部分码值

进行交换

例如

有两个8位的二进制码个体

A

1 0 0 0 1 1 1 0

B

1 1 0 1 1 0 0 1

那么根据随机产生的交叉位数

如3

产生0，1区间的随机数r

若r≤交叉概率Pc

则进行第3位的交换

得到两个新的个体

A1=1 0 0 0 1 0 0 1

B1=1 1 0 1 1 1 1 0

这就是它们的后代

作用在每个个体的

二进位串上

以较小的变异概率Pm随机地

改变个体串上的每一位

也就是将0与1互换

0变异为1

1变异为0

例如

某个码长为8位二进制的个体

1 0 1 0 0 1 1 0

根据随机产生的变异位数

如果是5

改变第5位的值

由0变1

得到

1 0 1 1 0 1 1 0

基本遗传算法有下述

4个运行参数需要提前设定

第一个

种群大小N

即群体中所含个体数目

一般取值是20~100

第二个

遗传运算的终止进化代数T

一般取为100~500

第三

交叉概率Pc

一般取为0.4~0.99

第四

变异概率Pm

一般取为0.0001~0.1

遗传算法通过模拟达尔文的

优胜劣汰

适者生存

的原理激励好的结构

遗传算法除了具有进化计算的

所有特征

同时还具有自身的特点

第一

遗传算法使用一组可行解

同时进行计算

具有很高的并行性和鲁棒性

第二

遗传算法选择

交叉

变异等运算都是以一种概率方式来进行

是一种概率搜索

具有较好的全局优化求解能力

三

遗传算法始终在适应度较高搜索空间中

从而提高了搜索效率

四

遗传算法的基本思想简单

实现步骤规范

便于具体使用

本次课程到此结束

谢谢大家

再见