大家好
欢迎回来
我们这一节继续
基于仿生算法的人工智能系统
我们介绍基因遗传算法
那么基因遗传算法当中
我们会先给大家介绍一下什么是基因遗传算法
以及这个算法跟大自然的遗传和进化的规律是不是一样的
最后我们说应用基因遗传算法可以做哪些事情
首先第一遗传算法它是受到
达尔文自然进化的理论启发而构造出来的
而被发明出来一种搜索的启发式算法
我们在前面有提到过在很多的问题
它构造成一个决策树之后
因为它的可能性实在是太大
所以树非常的庞大
你要把这个树全部穷尽去搜索的话
当然能够得到最优解
但是事情往往不是这样
我们不可能去穷尽所有的树
因为组合爆炸的问题
所以只能够去搜索其中的一部分
那么这一部分怎么去构造
我们就需要有一些方法来缩小计算量
那么基因遗传算法是反映了自然选择的一个过程
那么他选择的通过自然选择
最适合的个体进行繁殖产生下一代的后代
然后最后逐渐能够得到我们接近最优解
或者说就是最优解的那一代
这是我们搜索过程当中跟遗传和进化进行一个关联
那么什么是自然选择呢
自然选择的过程就从始于从个体
生物的个体群体当中选择最适合的个体
最后能够存活下来被选下来
那么它的基本的理论是说
如果一个个体它能够很好地适应环境的话
那么它就更容易在环境当中存活下来
并且繁殖产生下一代
那么在下一代产生的过程当中
因为遗传基因的继承
那么它们的后代就更容易继承
适应环境的这些特征
并且能够更加容易地再继续存繁殖
并且再把这些特征影响到下一代
那么如果这个过程不断的迭代
那么最后我们发现经过若干代之后
那么最后存活下来的这些个体
都是最适应环境的
那么一般来讲
我们爱用长颈鹿的例子来举例
那么我们现在看到的世界上存活
的长颈鹿都是脖子特别长的
这个也反映了一个自然进化
自然选择的一个过程
那么在搜索问题当中
自然选择的概念也可以用于这种
大规模的海量的搜索里边
如果我们不能穷尽
那么我们是不是可以从一个最
初始的比较远不能够判断远离最
优解的群体
开始经过不断的进化
不断的进化
然后也是一个优化的过程
那么最后能够达到我们所需要的最优解
这是我们在搜索问题当中去应用
自然选择
那么这样的话
如果我们模拟基因遗传和进化的
理论来构造我们的基因遗传算法的话
那么我们也需要这么几个组成的部分
第一是编码
初始化我们生成一些遗传基因
第二是一个适应度函数
第三是选择
然后交叉和变异
那么这其中自适应度函数就是
用来描绘我们把这个问题变成
自然环境变成自然环境
然后选择就是一个自然选择的过程
那么一个适应度函数
他如果一个解能够越使得适应度
函数这个值越高
那就说明他越适应这个环境
那么在选择的时候它就越容易被选中
然后繁殖
然后产生下一代
那么这是进行遗传算法
那么如果我们跟自然界的遗传和
进化进行对照的话
那么其实这几个部分都是一一对照的
比如说编码和初始化
就说明生物的群体
它的老祖先诞生
当然如何诞生
我们不用管
总是有一群祖先的群体出来了
接下来适应度函数就表示表征了一个物种个体它的特征
适应自然环境的一个适应度的一个判定
那么如果说适应度函数计算得的值越高
那么就说明这个物种越适应自然环境
那么接下来选择交叉和变异
就体现了自然选择的一个过程
那么选择就是跟自然选择一样
当然自然选择是通过残酷的竞争
是一个生死的一个抉择
比较适应环境
那么他就被选择通过
他就能够存活下来
并且繁殖后代
如果不适应环境
那么他就在产生下一代的
过程当中可能就会困难
他慢慢的就会灭绝
那么交叉和变异整个就是我们
遗传变异的一个理论的基础
这是表现在突变基因突变和基因重组上
这是几个这种对照关系
那么所以按照我们自然选择的学说
我们对应过来的发明了基因遗传算法
它主要的流程就是这样
首先要随机生成一群初始的群体
当然在这之前我们已经制定好了
我们的解所需要的特征组成的虚拟的基因
然后接下来在初始群体的基础上
开始主循环
循环什么时候结束
可以有两个结束条件
一个是我固定的迭代次数
比如经过20万代就停下来
然后这个时候如果存活的这些个体
那么就是我们算法的解的一个次优解
或者说比较优解了
那么或者是我们表征一个条件
比如说当你这个适应度达到一个
什么样的要求
我就可以停下来了
如果说他适应度已经对这个环境
适应得特别的高
也就是说我他已经足够接近我们的最优解
我们也可以把这个算法停下来
在循环的过程中
循环一次就说明我们表征这个问题解的这些生物的群体
进化了一代
就进行繁殖了一代
这一代里头干什么
首先第一个就是执行一个策略
计算当前群体当中的每一个个体
他们的适应度怎么样
然后接下来从当前的群体当中
选择一些精英
这所谓的精英就是适应度很高的那些
我们可以比如说从最小到最大
比如说排一个从0到百分之百
比如说我们把前20%留下来
产生下一代
那么就意味着后适应度排在后80%的这些个体
在这一代统统都灭绝了
他们的所携带的问题解的这些这些基因就消失了
下面就没有
那么就是最优的那20%留下来
那么留下来怎么样
就开始进行繁殖下一代
那么繁殖下一代把选出来的精英的个体之间
因为是有性繁殖
然后进行配对
配对的过程当中就会交换基因
产生下一代
那么这是遗传
那么他们交换基因就有可能产生
更加适应环境的
就是适应度更高的新的个体就下一代
那么为了有一些变化
我们引入了一些突变
那么这个也是遗传基因遗传算法的精髓
因为如果没有突变的话
那么他的个体适应度它就不能够
得到一个革命性的变化
所以这里头还包括一个极小的概率对后代的进行变异
那么这也是符合我们自然界当中的遗传变异和进化的
然后完了以后就把子代的个体再添加回到新群体
他们就构成了一个新群体
这是第二代的新群体
接下来再重新开始去计算新群体的适应度
然后接下来来再选择
然后遗传
然后变异
然后繁殖下一代
那么反复的进行
一直到我们找到比较最为接近
我们问题最优解的那些群体为止
这是经遗传算法的主要的一个过程
那么这样的基因算法它是应用在
什么方面
当然最主要就是优化
而且这个优化就是我们需要在
可能解的庞大的搜索空间当中大海捞针
去找到我们最接近我们最优的那组解
那么这两种就可以归纳为叫做
函数优化和组合优化
那么不管是函数优化或者是组合优化
它都是把所有可能的解集合就是
一个特别大的一个空间
在搜索空间当中有那么一组点或者一些点是最佳的解决方案
那么我们优化的目的就是在搜索
空间当中找到这一组点
那么在组合爆炸的情况下
那么这一组点要找到
那无疑确实是大海捞针
那么基因遗传算法就为我们
提供了能够在很合理的计算量的前提下
以一个比较好的特点
比较好的令人满意的这种结果
能够得到比较接近这一组最佳解决方案的
这么一组点
那么我们来看它为什么会是这样
这里有一个搜索问题
当然这个是一个很简单的
那么横轴是参数的值
当然这个值只有一个变化
从零比如说从最小到最大
那么这个就是函数值
那么优化比如说我们需要找到最高就是最大值
那么当然这个函数有很多种情况
比如说这是一种通常的情况
我们会看到这个就像爬山一样
你要爬到一个最高峰
当然如果我们能够从最小到最大
挨个的搜索过去的话
那么这个肯定能够找到最高峰
但问题是实在数量太大
我们没有办法一一穷尽
那么这个遗传算法就能够为我们
带来一个全局搜索性比较好的
他更容易能够找到最高点
因为其它的算法
比如说你在局部比如随机确定一个点
然后往上爬
那么我们可能会确定到这样一个点
然后爬到山顶就停下来了
因为再往下它就往下走下坡路
我们可能认为这就有一个最大值
当然这显然不是最大值
它是一个局部的一个最大值
包括这里也是一样的
所以遗传算法
因为他最开始的时候是一群随机的个体
那么所以他可能会均匀分布在不同的地方
然后再继续让个体
因为适应度函数就是看函数值大
谁大越大就越适应
那么可能他就会每一代都会逐渐的往上爬
那么这样很容易某一代就能够
爬到最顶端
这是基因遗传算法
它的优点就是全局搜索性比较强
不太容易落入到局部的最优然后就停下来这个当中
但是它也有一些缺点
首先它就是计算量特别的大
那么这体现如果说你初始的群体
如果数量不够多
你可能还是会错过
全局的最优解
那么初始的数量就要足够多
然后第二个就是要迭代的代数要足够的多时间要足够长
那么这样才能够做到全局比较优的这种程度
所以它计算量比较大
所以我们说基因遗传算法只有到了
我们像这种能够提供强大的计算力的时代
它才能够展示出它的巨大的威力
那么另外基因遗传算法就有一个随机性
它没有办法保证这个解决方案
一定是最优的
因为无论是自然的进化也好
或者说是我们模拟的基因遗传算法的进化也好
那么它总是去描述若干个方面
解的若干个方面的这种适应度
那么这些适应度的表征就非常的关键
也可能它会落入到一个局部的一个最优解
或者说在爬山的过程当中爬得特别的慢
等我们迭代了足够多的代数之后
他还没有爬到山顶
那么这是也是有可能的
所以这个也是基因遗传算法的缺点之一
那么最后我们来总结一下
那么基因遗传算法它和我们
自然界当中的遗传变异和进化的法则一样
它都是从一个初始的种群出发
然后经过这个适应的适应度的自然选择
然后通过产生下一代产生
然后通过交叉变异繁殖
然后产生一个更适应环境的下一代
然后不停的进化
那么这样最终能够得到最优解
那么在自然界当中我们地球的
发展了406亿年以来
为什么是现在我们有这种
丰富多彩的物种
存活在世界的各个地各个角落
各个不同的环境里边
那么这个其实也是自然选择的结果
那么类似的我们也希望用基因遗传算法模拟自然选择
我们基本上也能够在很大的一个解空间当中
找到我们相对比较满意的搜索的解出来