当前课程知识点:智能控制 > 第七章 遗传算法及其应用 > 7.4 遗传算法的基本操作之交叉与变异 > 7.4 遗传算法的基本操作之交叉与变异
下面我们介绍一下
遗传算法的第二个基本操作
叫交叉
那么简单的交叉分两步
在由等待配对的位串
构成的匹配池中
第一步
将复制产生位串的个体
随机两两配对
就是解决谁和谁配对的问题
第二步
随机地选择交叉点
对匹配的位串进行交叉繁殖
产生一对新的位串
第二个问题就是解决
在哪个位置进行交叉的问题
假定位串的字符长度为l
那么在1到l-1的范围内
随机地选取一个整数值k
k的范围是1到l-1
可以作为交叉点
然后将两个配对位串
从位置k后
所有字符进行交换
从而生成两个新的位串
举个例子
交叉前是01101和11000
那么先确定这两个位串进行交叉
那么位串长度l等于5
我们交叉点可以选取在1到4之间
假定选择了交叉点是3
那么就把第三位以后的
所有的位串进行对调
我们就可以得到了
交叉之后
它的基因是01100
11001
这是交叉操作
我们发现在原始的四个种群的基础上
把第二个个体复制了两次之后
得到了复制后的匹配值
就是01101
11000
11000
10011
然后我们进行交叉操作
那么第一步要解决配对问题
假定一和二个体进行配对
三和四个体进行配对
那么这个位串的长度是五
交叉点可以在1到4之间随机选择
假定第一个个体和第二个个体
交叉点选择4
那么就把第五位1和0对调一下
就得到新个体
01100和11001
然后将第三个个体
第四个个体配对
交叉点选择2
所以将000和011进行对调
得到的结果就是11011和10000
那么这是它的基因型
也就是它的位串
也就是说经过一次复制
一次交叉之后
当前种群是01100
11001
11011
10000
这是它的基因型
对应的表现型
x值就是8+4等于12
16+8+1等于25
16+8+2+1等于27
16等于16
这样的话在它对应的表现型
分别为12、25、27、16
那么按照适配值函数计算出来的结果就是
对应的适配值分别为144
625
729
256
总计是1754
那么平均值达到了439
最大值达到了729
我们观察一下
刚才原始的个体
在复制操作之前
当前第一代种群的个体
它的适配值总数是1170
现在变成了1754
第一代种群个体的适配值
平均值是293
现在变成了439
用原来的最大值是576
现在变成了729
这样显著提升了
这样体现它的计算简单
但是功能强大
下面介绍一下遗传算法的第三个操作变异
尽管复制交叉操作都非常重要
在遗传算法中是第一位的
但是不能保证不会遗漏
一些重要的遗传信息
那么在人工遗传系统中
变异用来防止这种不可弥补的遗漏
在简单遗传算法中
变异就是某个字符串某一位的值
偶然的概率很小的
随机的改变
也就是把某些特定位置上
简单地把1变为0或者0变成1
而变异就是沿着
位串字符空间的随机移动
当它有节制的和交叉一起使用
就可以防止过度成熟
而丢失重要概念
变异是沿着位串字符空间的随机移动
那么当它有节制的和交叉一起使用的时候
就可以防止过度成熟
我们看这样一个例子
如果当前种群
它的四个个体
分别是01101
10001
00101
11100
我们发现这四个个体的第四位都是0
你无论怎么复制交叉
它永远无法达到它的最优点五个1
这时候就需要用变异
变异就是选择它某一位
比如说第四位0
某一个个体的0随机的变为1
那么变异前个体是01100
那么个体发生变异之后
第四位发生变异之后
那么变异后得到的结果就是01110
那么根据经验
变异的频率大概为
每一千位位串中只变1位
也就是变异的概率为0.001
也就是变异的概率
不要太频繁了
但如果太小的话
那就没什么效果
太频繁的话
可能会发生不好的效果
那么我们有四个个体
每个个体是有五个位串的
总共有20个位串字符号
那么期望的变异串位数
就是20乘以千分之一 0.02位
所以这个例子里面
并没有位串值得改变
下面我们看一个例子
设函数f(x)等于x的平方
x为整数
且x范围是0到15
而且它的最大值
那么这里面x范围是0到15
总共16个数
所以对于一个个体来说
要采用二进制编码时
只需要四位长度就可以了
因为四个0表示0
四个1表示15
然后我们直接将函数值f(x)等于x的平方
作为个体x的适应度值
也就是适配值函数
那么它的适应值越大
解的满意度就越高
其他参数分别如下
解的群体规模M为4
交叉概率为1.0
变异概率为0.01
选择机制用轮盘赌法
这样的话我们发现
如果初始个体
第一代是0111
0101
0001和1000
那么经过五次迭代
经过五代的迭代
复制交叉
变异操作后
在第五代就可以得到出现了
四个1
两个个体都是四个1
也就是我们这个问题的最优解
当x等于基因型为四个1
表现型为15的时候
函数f(x)有最大值225
那么这个过程
其实也体现了遗传算法的一个功能
也就是说它是
多点进行并行进行优化
而且它的优化效率很高
很快就是趋于收敛
计算简单
功能强大
也体现了遗传算法的一些特点
那么遗传算法很多优点
你说它并没有要求目标函数
可达可为连续等等
它只需要告诉它目标函数
定义一个适配值函数
然后给一些种群
给多个体进行优化
同步优化
那么它要很广泛的应用
函数优化
组合优化
生产调度问题
自动控制
机器人
图像处理
人工生命
遗传编程
机器学习等等各个领域
得到了广泛的应用
-开篇
--开篇
-1.1课程考试方式
-1.2 数据、信息、知识与智能
-1.3传统控制面临的挑战
-1.4 控制科学发展过程
-1.5 智能控制的多元论
--1.5
-1.6 控制策略的渗透与融合
--1.6
-1.7 智能控制与传统控制的联系与区别
--1.7
-1.8 智能控制的类型之分级递阶智能控制系统
--1.8
-1.9 智能控制的类型之专家控制系统
--1.9
-1.10 智能控制的类型之模糊控制系统
--1.10
-1.11 智能控制的类型之神经网络控制系统,智能控制的类型之基于规则的仿人智能控制系统,集成智能控制系统,组合智能控制
--1.11
-1.12智能控制系统的类型之基于规则的仿人智能控制系统,集成智能控制系统,组合智能控制
--1.12
-1.13本章小结
--1.13
-第一章测试
-2.1基于搜索的问题求解
-- 2.1.7 均一代价搜索
-- 2.1.10 A星算法
-2.2 专家系统简介
- 2.3 专家PID
-第二章测试
-3.1 模糊控制概述
-3.2 模糊集合
-3.3 隶属函数
--3.3隶属函数.
-3.4 模糊关系及其运算
-第三章测试
- 4.1 模糊自适应整定PID控制原理
-4.2 基于FF的模糊PID控制试验验证
-第四章测试
- 5.1 神经网络简介
- 5.2 神经网络的发展简史
-5.3 神经网络的基本概念
- 5.4 神经网络的分类
-5.5 神经网络的学习算法、基本特征和研究领域
-第五章测试
-6.1 感知器
--6.1.2.1 感知器应用实例分析(实现逻辑运算与或非)
- 6.2 BP神经网络
--6.2.2.1 BP神经网络应用实例分析之一:逻辑运算异或实现
--6.2.2.2 BP神经网络应用实例分析之二:非线性函数拟合
-第六章测试
- 7.1 什么是遗传算法
-7.2 遗传算法的特点
-7.3 遗传算法的基本操作之复制
-7.4 遗传算法的基本操作之交叉与变异
-第七章测试
-8.1 遗传编程工作原理
-8.2 遗传编程基本操作之复制
-8.3 遗传编程基本操作之交换和突变
- 8.4 遗传编程的工作步骤及实例分析
-第八章测试
-期末测试