6.1 遗传算法在线视频

遗传算法

第一我们首先看一下遗传算法的概述

遗传算法是上一世纪60年代末70年代初

由美国密西根大学的一些学者研究发展起来的一种

现代的优化方法

那么它的标志是1985年在美国卡耐基梅隆大学

召开的第一届国际遗传算法大会

那么这次会议中人们承认了这个算法

并且逐步推广了这么一个算法

那么遗传算法的基本思想是将自然界遗传学和

计算机科学结合起来的一种全新的概率优化方法

它是根据达尔文提出的生物界进化论的思想

就是我们说的三句话

物竞天择

适者生存

优胜劣汰

这样的一个思想

然后与计算机相结合来实现了一种优化方法

自然界生物进化我们来看一下

我们都知道对于任何一个种群

那么它的一代一代的进化过程是什么样

一个种群我们通过竞争

那么这里的竞争可以是竞争自然资源

也可能是相互的竞争

通过竞争不幸有一些不太适应自然环境的

或者不太适应生存的就会被淘汰了

我们称为是淘汰种群

那么留下来种群怎么办

通过了婚配发展到了下一代

就我们称为是子代

这里边子代可能过程中会有一些我们称为是变异

然后充实到整个种群里边

那么它实际上我们看自然界的生物总是向着最强壮

最适用于生存的方向去发展

那么它实际上整个过程就是我们说的通过竞争

通过婚配好的留到了下一代

然后中间可能有一些变异

最后又充实到种群中

一代一代的最后适应了环境

生存下来

种群得以强壮得以发展下来

这是自然界的方法

人们就想自然界这样的种群的这样的发展

不刚好也是向着寻优的方向发展

我们的优化问题不也是想找到最优的方案吗

那么这两者能不能结合

因此说人们把通过生物学家和计算科学学家相结合

他们共同研究提出了遗传算法

我们看看遗传算法特点

主要特点具有鲁棒性

我们称为是稳定的收敛性

这是它的第一个特点

第一

遗传算法是对问题变量的编码及进行操作

而不是变量的本身

因此说它有适应性

使得问题的表述和求解比较灵活

第二遗传算法从一组初始点而不是一个初始点

进行搜索

具有很好的并行性

算法能够获得较多的峰值

那么遗传算法能够很好的避免陷入

局部最小值的可能性

第三点遗传算法仅使用问题本身

那就是它的目标函数的信息

而不需要使用什么倒数或其他的辅助信息

因此什么

它的适应面比较广

第四

遗传算法采用随机变换规则

而不是确定性的规则

这是四点

我们看看遗传算法的优点

那么它就是应用的广泛性

容易写出一个通用的算法

求解不同类型的优化问题

第二

非线性性

大多数现行的优化算法都基于线性的凸性的

可微性的等等有一些限制条件

但是遗传算法没有这样的要求

因此遗传算法只需评价目标函数值的优劣性

第三

适应性

如果把原问题进行一些很小的修改的时候

那么大多数的现行的优化方法很可能不能使用

或者需要进行较大的修改

而遗传算法仅需要做很小的修改

就能够适应新的问题

第四

并行性

遗传算法的隐含的对问题的空间

许多解是

并行搜索的

就像我们刚才讲的

它的出发点初始点就是一群解空间

由多点出发共同的去寻优

因此说它的搜索速度快

稳定性是很强的

这是它的并行性

第五

启发式的搜索技术

它不是简简单单的枚举

因而其搜索效率优于枚举的方法

收敛速度快

并且遗传算法的计算量与求解的规模

是线性增长关系的

而不是指数增长关系

因此避免了维数灾难的问题

因此遗传算法在自然科学工程技术商业医学

社会科学等领域都被广泛的使用

我们下面来看看遗传算法的基本的原理

基本原理以生物进化论的原理为基础

遵从物竞天择

适者生存

优胜劣汰这样的自然选择的原则和遗传机制

抽象出来的

而形成了一种非常便于计算机实现的方法

我们看一下生物界与遗传算法的一些术语的

对应关系

左边是生物界

右边是遗传算法

首先是染色体

我们这边对应的是遗传算法的决策变量

我们知道每一个个体决定它的性状是

由它染色体决定的

那么对于遗传算法来说

对应的就是我们的决策变量

编码的字符串或称为是基因链

第二个基因

那么对应的我们是遗传算法里边的变量的分类值

我们的字符串中的字符

下面我们看一下

对于基因型

那么就是我们的变量的编码结构

下面表现型编码的解码结构

对于遗传算法里面的我们说它的操作非常简单

它的整个过程很简单

实际上它核心部分就是三个操作

选择交叉和变异

只有这三个操作

第一选择

什么是选择

我们来看一下作用模拟生物界

去劣存优的自然选择功能

我们说生物界某个个体不适用于环境了

或者竞争不过了

它会被淘汰

这个个体就是劣势的个体

那么强壮的适用于环境的个体生存下来

就是优良的个体

那么自然界有这样的去劣存优的功能

我们这里遗传算法中的选择的过程就是模拟生物界

这样的一个去劣存优的自然选择功能

规则适应度Fi目标函数值越大的染色体赋予

更大的选中概率

目的适应度高的染色体

有更多的机会繁衍后代

使其优良的特性得以遗传

这是它的目标

第二交叉作用

它就是模拟生物进化过程中的

繁衍的交配的这样的一个现象

方法很简单

两个母体或双亲位于交叉位置后的符号串进行互换

就形成了交叉

目的创造新的染色体

那么这个孩子既有父亲的特性

又有母亲的特性

一个X来自母亲的一个Y来自父亲的

那么来形成新的染色体

我们来举个例子

比如父代的一个是0100111

另外一个父代是1010010

然后我们选择了交叉位

比如说是第三位

那么怎么交叉在我们计算机来进行操作

很简单

把它的最后的三位进行互换

就形成了我们的子代

那么这里边我们交叉位也是可以进行随机选择的

你可以选择第三位

第四位都可以

那么子代就变成了什么

我们看一下

两个孩子

第一个是0100010

就是把父代第二个的染色体翻到上面来

那么另外一个是1010111

就把上面那个翻到底下来我们看子代的孩子

每一个孩子的染色体跟父代都是不一样的

但是它又有继承了父代中的一段的染色体

因此它又保持了父代中的某一些特殊的性状

这是我们的交叉

那么遗传算法寻优的过程就是由交叉来完成的

交叉的机理虽然非常简单

只涉及了随机数的生成部分基因的交换

但是交叉后随机信息使得遗传算法具有

令人惊奇的功能

成为快速并且鲁棒的寻求最优解的这样的一个方法

所以说交叉在影响中作用非常重要

第三变异

作用 模拟生物在自然界遗传环境中由于某些

偶然因素而引起的基因突变

我们知道生物界也会有基因突变的问题

基因突变并不代表一定是坏的

有可能是坏的

有可能是好的

那么有可能是突变以后能向着更好地适应自然界

环境的方向发展

那么这个个体就能够在下一代中保留下来

并且它这个突变的基因会在整个其中发扬光大

那么如果它突变是不好的

并不适应于环境

那么它自然会被淘汰的

这是我们的突变

方法那么在我们的遗传算法里边

方法是以一定的概率Pm从种群中

选取若干个染色体

随机的将其染色体中的基因进行翻转

简单0就变到1 1就变到0

目的增加了种群基因材料的多样性

增大了自然选择的余地

这是我们的变异

举个例子

变异前如果说一个个体是1100111

那么我随机的选择了一个遗传位或者

一个基因位变异以后这个基因元是1

那么变成什么

1000111变成0

随机的改变

这是我们的变异

下面我们来看看遗传算法的整个的迭代步骤

第一参数编码

那么对于种群我们进行参数编码

编码以后形成初始的解群

然后个体适应值的检测估计

就是说对于每一个个体每有一个解

实际上就是算出你的目标函数

来看它的目标函数值

然后检测进行估计

然后我们让第一代

所以说K等于1

这是计数的

进行遗传操作

形成第k代染色体

然后我们进行选择交叉和变异三项操作

然后产生新的种群计算第k代个染色体的

适应度的值

如果说我们K已经满足了我们设定的最大的

迭代的次数的话

我们就输出解码输出最优解

我们认为第M代最好的解就是我们的最优解

把它解码还原到你可读的这样的

一个实际的问题的解

然后输出自由解

如果没有到继续进行迭代

我们回到哪回到下一代

然后再进行遗传操作

选择交叉变异

一代一代这样的循环来实现这样的遗传操作

寻求最优解

我们看这个过程非常简单

好 我们下面用一个简单的例题

来看一看遗传算法的

实际的操作过程

满足

我们的目标函数是什么呢

是f(X)等于x平方

让使f(X)取最大值max

那么取值范围x从0到31

这里边我们取整数

所有的整数解里边能让x平方最大的数求这个数

那么这里边第一步编码和初始化

那么我们说0到31一共32个解

一般会进行二进制编码会比较简单

计算机好读我们也好操作

那么对于二进制编码0到31三十二个数

那么刚好是什么

五位编码

那就是从00000到11111

刚好每一个代表1个数

那么则整个的人口数我们说种群数

就是每一代我们只要取四个

我们可以列下下面的表

表头包括个体序号

初始的人口随机生成的x的值

适应度的值

选择概率期望次数和我们的轮盘方法的期望次数

我们来看一看随机的取四个数

就在这样的0到31这种群里边

我们随机的取四个

很简单

我们让计算机随机生成就行了

我们取的是1，2

3，4

一是01101二是11000

三是01000四是10011

那么这表示什么

我们看第三列x的值就说第一个01101对应的是几

是13

那么第二对应的是24

第三个对应是8

第四个对应19

我们有了x值就可以带到f(X)里边

就能求出f(X)的值

那么一求出来是第一个的f(X)

我们的适应度函数值是169

第二个是576

第三个是64

第四个是361

那么可以来计算什么选择概率

什么叫选择概率

就是说我第一个解会被选中的概率是多少

这里怎么算

我们是用什么

Fi比上Σ求和f(X)

把这几个适用的函数值加起来

然后用每一个来比它因为你求max

实际是值越大的被选中概率越大

所以我们一看加起来算一下就可能

第二个的被选中概率非常大是0.49快1/2的概率

被选择了

那么比如说第三个是64被选择概率比较小

是0.06

实际上道理是很明显的

我们求的是

maxX平方

那值越大的我们的适应度函数越大的越容易被选择

被遗传到下一代

那么这后面是我们的期望次数是我们的Fi比上f(X)

那么下面是我们的被选择被选中的概率

我们一会看一看为什么会被选择一次

第二会被选择两次

第三个一次都没选择

然后这里是我们的累加次数

我们这里计算到我们的平均值等等

我们看一看我们累加起来适用函数是11700

我们的平均值是293

那意思说我们这一个初始代里边

我们的目标函数的最终的平均值是293

那么这两个值我们可以比一比后边代看后面进行

一代两代以后是不是平均值一步一步升高

最终逼近我的最优解

最大是哪个

是我们的第二个体

576

我们也可以看一看第二代的最大值是不比

第一代的最大值更好

也就是说我们的孩子中的最好的个体是不比

父亲中的最好的个体还要好

我们一代比一代强

最后找到了最优解

就是什么

步步逼近到最优解这个过程

好

我们来看一下复制我们计算出来的本代的一些数据

一些信息

我们来看一看怎么来进行下一代

由当前个体产生下一代临时个体用轮盘赌的方法

那么选择概率我们是Fi比上Σ求和Fi

具有较大满意度或者有较大的目标函数值的

个体能得到较大的复制

具有较小的满足度

或者说目标函数的个体将从人口中被删除

因为我们说什么

目标是要适应于环境

要找到目标函数最大值

所以说目标函数值小的那个没有用

我们就慢慢把它淘汰下去

那么大的留下来

我们轮盘赌可以用条状的形式来表示

我们或者用这样的一个圆盘的形式来表示

我们的概率是0到1

我们刚才计算了第一个个体

它所占的在0到1里面占是0.14

第二个体占的是0.49

第三个个体占到0.06

第四个个体占的是0.31

我们条状是这么分配

我们圆盘状也是这样分配

你看第二个体

0.49基本上占一半

那我们第三个体0.06占的非常少

这时候怎么办

我们在轮盘里边让这盘子转起来

或者说我们在这个条状里面

我们随机的丢一个小球

要看小球到底落在哪个区域内

那么哪个区域的所代表的个体就被选中

那怎么选择小球产生随机数

那就是产生0到1的一个随机数

我们这里写的是伪随机数

为什么伪随机数大家进行编程都知道计算机我不管

C语言还是什么语言所产生的Radeon这样的一个

随机数是一个伪随机数什么

只要你Radeon

后面括号里边值不变

那么产生的随机数永远是那一个值

所以说我们经常会把括号里边参量写成什么时间

或者写成一个什么随机数来进行改变

那么好了

第一次产生随机数是0.32

那么0.32

一看是哪在0.14到0.63这个之间

所以说第二个子代被选择

我们看动画把它落在了0.32概率曲线里边

所以说第二个体被选择

第二次0.87

0.87是在什么

第四个个体里边

落在了第四个个体的区间里边

所以说第四个体被选择了

第三个是0.56

0.56也是在0.14到0.63之间

所以说我们还是第二个体被选择上

那么第四个是0.12

0.12是在0到0.14之间

所以说个体1被选择了

那么这样子我们看 我们父代是四个个体

子代也要 需要四个个体的进行下一次遗传

那么选择了四次时候

个体2被选择了两次

个体1被选择了一次

个体4被选择一次个体3由于它的性状非常大

它的目标量值非常小

它没有机会被选择

实际上它没有机会选择

它就没有机会参与到下一代的

婚配的繁衍下一代的过程中

它就相于什么

它被淘汰了

这是我们这样的一个选择过程

这样子的选择相当于两个个体2

一个个体4

一个个体1进行什么

参与到了交配过程中

那么交配过程中我们很简单

我们这里边是随机选择的

我们第一个选择是什么

与2交配是什么

01101

我们交配位置是最后一位

我们让最后一位交配就可以了

那么第二个与11000与第一个交配

它们两个之间相互交配

那么都是最后一位

那么实际上交配干什么

进行一个翻转就可以了

那么计算出来的x值子代有两个新的值

一个是12

一个是25

这两个值跟父代的没有相同的

但是又保存了父代的一些特性

我们看这里边是在最后一位把父代的01101

和11000的最后一位1和0进行互换

那么第三个3与4交配10000 10011

我们随机选择一个交叉点选在哪

我们选择是第三位

那这样是11把第四位的拿上来

11011

10000

这样选择了这四个出来

就是什么子代变成12 25 27 16

我们算一算它的目标函数值

算出来目标函数值以后

我们再算算它的适应度函数

我们看目标函数值是什么

144

625

729和256

我们与前面那个表相比较

我们看到肯定这一代的个体的目标函数值比上一代

明显大了很多

然后我们还可以继续顺着选择概率

那么这时候我们再算一下它的平均值

看这一代的平均值

我们看一下是多少

439

上一代的只有是239

所以这一代明显好于上一代子代比父代要强

要更适用于环境

要更向着最优的目标前进了

适应度最大值

我们看看变到什么

729了

就是我们的第三个729

而上一代的最大值只有576

也看出来是大了很多

我们最好的值也向着更好的目标前进

显而易见

新一代的群体继承了上一代的传统的优良的特性

并且明显优于上一代

那么这里边我们说的影响里面有三个

这样的一个操作

选择交叉变异

那么看变异

那么一般概率选取的非常小

0.001这个概率我们一共只有四个要选取

0.001这么小的概率

本例中的这一代并没有基因从0变到1

我们也操作变异的

但是这一代没有个体被变异

那么就不用变异了

那么实际上变异操作也是非常重要的

虽然它的概率非常小

第一

通过变异

我们刚才讲能使整个个体种群的个体变成了多样性

那么如果说没有变异对于近亲繁衍来说

那么所有的个体可能都是由某一个

或某一对父母来决定的

那么他们可能是适用于当前的环境

那么一旦环境改变

则整个个体可能就会全部的消亡

这是我们的自然界里边的过程

那么映射到我们的遗传算法里面

可能所有的个体都去寻找某一个局部极优解

那么意思说什么

可能最后你所寻找出来的最后是一个局部极优解

而不是全局的最优解

整个种群里面的差异性太小

所有的个体都是落在了一个局部极值解

最优解的地方

那么这是它的问题

只有通过的变异能使某些个体跳出

局部最优解的过程来寻找整个全局的最优解

这是变异的重要性

那么重复上面的过程最终找到x的极值点是31

我们的f(X)是961

很显然这个题我们很简单

通过前面的给出题目时候

有些同学就看出来了

肯定x取出31的时候是最好的

因为什么

f(X)等于x平方求max

那么这是这个简单这道题

我们通过这道题通过编码

选择交叉我们这里变异

把整个遗传算法的过程给讲一下

我们通过过程看一下

方法很简单

过程很清楚

每一步都很好理解

能够对应到我们的自然界

能够对应到我们的实际的工程中

然后最终求解的效果也是非常好的

因此说遗传算法在我们的实际工程中

已经被广泛的使用

同学们如果遇到大型的工程优化问题时候

可以去考虑使用

遗传算法来进行求解

好 这一节我们就讲到这里