人工智能入门课件第5章遗传算法.ppt
《人工智能入门课件第5章遗传算法.ppt》由会员分享,可在线阅读,更多相关《人工智能入门课件第5章遗传算法.ppt(44页珍藏版)》请在文库网上搜索。
1、第5章 遗传算法5.1 5.1 遗传算法的基本概念遗传算法的基本概念5.2 5.2 遗传编码遗传编码5.3 5.3 适应值函数适应值函数5.4 5.4 遗传操作遗传操作5.5 5.5 初始化群体初始化群体5.6 5.6 控制参数的选取控制参数的选取5.7 5.7 算法的终止准则算法的终止准则5.8 5.8 遗传算法的基本理论遗传算法的基本理论5.9 5.9 遗传算法简例遗传算法简例5.105.10遗传算法的应用领域遗传算法的应用领域5.1 遗传算法的基本概念遗传算法的基本概念l基本思想使用模拟生物和人类进化的方法求解复杂的基本思想使用模拟生物和人类进化的方法求解复杂的优化问题,因而也称为模拟进
2、化优化算法。优化问题,因而也称为模拟进化优化算法。l遗传算法将择优与随机信息交换结合在一起,在每一遗传算法将择优与随机信息交换结合在一起,在每一代中,使用用上代中最好的,即最适应环境的位或片代中,使用用上代中最好的,即最适应环境的位或片段,形成新的人工生物集。段,形成新的人工生物集。l遗传算法是一个迭代过程,在每次迭代中都保留一组遗传算法是一个迭代过程,在每次迭代中都保留一组候选解,并按某种优劣指标进行排序,然后按某种指候选解,并按某种优劣指标进行排序,然后按某种指标从中选出一些解,利用遗传算子,即下面要讲到的标从中选出一些解,利用遗传算子,即下面要讲到的遗传操作,对其进行运算以产生新一代的一
3、组解。重遗传操作,对其进行运算以产生新一代的一组解。重复上述过程,直到满足指定的收敛要求为止。复上述过程,直到满足指定的收敛要求为止。5.1.1 遗传算法的基本概念定义5.1 个体:个体是一个数据结构,用来描述基本的遗传结构。定义5.2 适应性:每个个体有一对应的适应值。在优化问题中,适应值来自于一个估计函数。定义5.3 群体:由个体组成的集合。定义5.4 遗传操作:遗传操作作用于群体而产生新的群体。标准的代遗传操作一般包括选择(或复制),交叉(或重组)和变异三种基本形式。例子例子 一个简单的遗传操作实例 5.1.2 遗传算法的基本流程遗传算法的基本流程遗传算法涉及五大要素:遗传算法涉及五大要
4、素:1.1.1.1.参数编码参数编码参数编码参数编码2.2.2.2.初始群体设定初始群体设定初始群体设定初始群体设定3.3.3.3.适应度函数设计适应度函数设计适应度函数设计适应度函数设计4.4.4.4.遗传操作设计遗传操作设计遗传操作设计遗传操作设计5.5.5.5.控制参数设定控制参数设定控制参数设定控制参数设定 确定实际问题参数集对参数进行编码初始化群体(t)评价群体满足停止准则?遗传操作结束群体(t)群体(t)三个基本操作:1.选择2.交叉3.变异其它高级操作标准遗传算法基本流程框图选择种群新后代变异交叉123411000111000111010101011101000110110110
5、1154.538.343.734.61324#位串适应值排序110001110001110100011100010001011101110011000101010110011100交叉点变异位标准遗传算法基本流程框图实例交配池遗传算法的执行过程遗传算法的执行过程1.1.选择编码策略,把参数集合选择编码策略,把参数集合和域转换为相应编码空间和域转换为相应编码空间;2.2.定义适应值函数定义适应值函数f f(X X););3.3.定义遗传策略,包括选择群体大小、选择、交叉、变异方法定义遗传策略,包括选择群体大小、选择、交叉、变异方法以及确定交叉概率以及确定交叉概率、变异概率、变异概率等遗传参数;等
6、遗传参数;4.4.随机初始化生成群体随机初始化生成群体(t t););5.5.计算群体中个体的适应值计算群体中个体的适应值f f(X X););6.6.按照遗传策略,运用选择、交叉和变异操作作用于群体,形按照遗传策略,运用选择、交叉和变异操作作用于群体,形成下一代群体;成下一代群体;7.7.判断群体性能是否满足某一指标,或已完成预定迭代次数,判断群体性能是否满足某一指标,或已完成预定迭代次数,不满足则返回步骤(不满足则返回步骤(6 6),或修改遗传策略再返回步骤),或修改遗传策略再返回步骤(6)(6)。5.2 遗传编码遗传编码5.2.1 二进制编码5.2.2 Gray编码5.2.3 实数编码5
7、.2.4 有序编码5.2.5 结构式编码5.2.1 二进制编码二进制编码在二进制编码过程中,首先要确定二进制串的长度在二进制编码过程中,首先要确定二进制串的长度l l,串长,串长l l取决于变量的定义域及计算所需的精度。取决于变量的定义域及计算所需的精度。例例例例5.25.2 变量变量x x的定义域为的定义域为 2 2,55,要求精度为,要求精度为1010-6-6,则我们需将则我们需将 2 2,55分成至少分成至少7 000 0007 000 000个等长小区个等长小区域,而每个小区域用一个二进制串表示。于是串长至域,而每个小区域用一个二进制串表示。于是串长至少等于少等于2323,这是因为:,
8、这是因为:4194304=24194304=2222270000002700000022323=8388608=8388608这样,计算中的任何一个二进制串(这样,计算中的任何一个二进制串(b b2222b b2121bb0 0)都)都对应对应-2-2,55中的一个点。中的一个点。5.2.2 Gray编码编码GrayGray编码即是将二进制码通过如下变换进行转编码即是将二进制码通过如下变换进行转换得到的码。换得到的码。设有二进制串(设有二进制串(1 1 2 2 n n),对应的),对应的GrayGray串为串为(1 1 2 2 n n),则从二进制码到),则从二进制码到GrayGray码的变换
9、为码的变换为其中其中表示模表示模2 2加法。加法。从一个从一个GrayGray码到二进制串的变换为码到二进制串的变换为例例例例5.35.3 二进制串二进制串11010111101011对应的对应的GrayGray串为串为101110101110。5.2.3 实数编码实数编码为了克服二进制编码的缺点,对于问题的变量为了克服二进制编码的缺点,对于问题的变量是实向量的情形,直接可以采用十进制进行编码,是实向量的情形,直接可以采用十进制进行编码,这样可以直接在解的表现形式上进行遗传操作,从这样可以直接在解的表现形式上进行遗传操作,从而便于引入与问题领域相关的启发式信息以增加系而便于引入与问题领域相关的
10、启发式信息以增加系统的搜索能力统的搜索能力 例例例例3 3 作业调度问题(作业调度问题(JSPJSP)的种群个体编码常用)的种群个体编码常用mm n n的矩阵的矩阵Y Y=y yij ij,i i=1=1,2 2,mm,j j=1=1,2 2,n n(n n为从加工开始的天数,为从加工开始的天数,mm为工件的优先顺为工件的优先顺序)。序)。y yij ij表示工件表示工件i i在第在第j j日的加工时间。下表是日的加工时间。下表是一个随机生成的个体所示。一个随机生成的个体所示。010102020303040405050606070708080909工件工件工件工件1 10 02 21 12 2
11、2 21 12 2工件工件工件工件2 20 01 12 20 00 04 4工件工件工件工件3 31 10 00 01 13 31 1工件工件工件工件4 40 02 23 30 00 01 1工件工件工件工件5 50 02 20 03 30 00 00 01 11 15.2.4 有序编码有序编码对很多组合优化问题,目标函数的值不仅与表示解的字对很多组合优化问题,目标函数的值不仅与表示解的字符串中各字符的值有关,而且与其所在字符串中的位置有关。符串中各字符的值有关,而且与其所在字符串中的位置有关。这样的问题称为有序问题。这样的问题称为有序问题。若目标函数的值只与表示解的字符串中各字符的位置有若目
12、标函数的值只与表示解的字符串中各字符的位置有关而与其具体的字符值无关,则称为纯有序问题,如采用顶关而与其具体的字符值无关,则称为纯有序问题,如采用顶点排列的旅行商问题。点排列的旅行商问题。例例例例5.4 5.4 有有1010个城市的个城市的TSPTSP问题,城市序号为问题,城市序号为11,2 2,1010,则编码位串:,则编码位串:1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10表示对城市采用按序号升序方法访问行走路线。表示对城市采用按序号升序方法访问行走路线。1 3 5 7 9 2 4 6 8 101 3 5 7 9 2 4 6 8 10表示按特定表示按特定“
13、1 3 5 7 9 2 4 6 8 10 1 3 5 7 9 2 4 6 8 10 1”1”依次访问各个城市。依次访问各个城市。5.2.5 结构式编码结构式编码l l对很多问题其更自然的表对很多问题其更自然的表示是树或图的形式,这时示是树或图的形式,这时采用其它形式的变可能很采用其它形式的变可能很困难。这种将问题的解表困难。这种将问题的解表达成树或图的形式的编码达成树或图的形式的编码称为结构式编码。称为结构式编码。5.3 适应值函数适应值函数l l适应值函数构成了个体的生成环境。根据个体的适应值函数构成了个体的生成环境。根据个体的适应值可以决定它在此环境下的生存能力。适应值可以决定它在此环境下
14、的生存能力。l l若若S SL L表示位串空间,表示位串空间,S SL L上的适应值函数可表示为上的适应值函数可表示为f f:S SL LR R+,f f为实值函数,为实值函数,R R+表示非负实数集合。表示非负实数集合。l l针对进化过程中关于遗传操作的控制的需要,选针对进化过程中关于遗传操作的控制的需要,选择函数变换择函数变换T T:g gf f,使得对于最优解,使得对于最优解x x*,max max f f(x x*)=opt*)=opt g g(x x*)(*)(x x*u u,v v)。5.4 遗传操作遗传操作5.4.1 选择(selection)5.4.2 交叉操作(crossov
15、er)5.4.3 变异操作(mutation)5.4.1 选择选择(selection)选择即从当前群体中选出个体以生成交配池(mating pool)的过程。所选出的这些个体具有良好的特征,以便产生优良的后代。1.基于适应值比例的选择基于适应值比例的选择2.基于排名的选择基于排名的选择3.基于局部竞争机制的选择基于局部竞争机制的选择1.基于适应值比例的选择基于适应值比例的选择(1 1)繁殖池选择)繁殖池选择 相对适应值:相对适应值:每个个体的繁殖量:每个个体的繁殖量:N Ni i=round(=round(relreli i N N)(2 2)转盘赌选择)转盘赌选择 2pi现生成一个0,1内
16、的随机数r,若p1+p2+pi-100,且,且p p1 1 p p2 2p pN N,故限定,故限定11a a22。通常使用的值为。通常使用的值为a a=1.1=1.1。2.基于排名的选择基于排名的选择(2)非线性排名选择 将群体成员按适应值从好到坏依次排列,并按下式进行分配选择概率:其中q是常数,表示最好的个体的选择概率。3.基于局部竞争机制的选择基于局部竞争机制的选择(1 1)锦标赛选择)锦标赛选择(tournament selection)(tournament selection)选择时,先随机地选择在群体中选择选择时,先随机地选择在群体中选择k k个个体(放回个个体(放回或不放回)进
17、行比较,适应值最好的个体将被选择作为或不放回)进行比较,适应值最好的个体将被选择作为生成下一代的父体。反复执行该过程,直到下一代个体生成下一代的父体。反复执行该过程,直到下一代个体数量达到预定的群体规模。参数数量达到预定的群体规模。参数k k称为竞赛规模,一般称为竞赛规模,一般取取k k=2=2。(2 2)(,)和和+选择选择 (,)选择是先从规模为选择是先从规模为 种群中随机选取个体通过种群中随机选取个体通过交叉和变异生成交叉和变异生成()个后代,然后再从这些后代中)个后代,然后再从这些后代中选取选取 个最优的后代作为新的一代种群。个最优的后代作为新的一代种群。+选择则是从选择则是从这些后代
18、与其父体共这些后代与其父体共+个后代中选取个后代中选取 个最优的后代。个最优的后代。5.4.2 交叉操作交叉操作(crossover)交叉的具体步骤为:1.1.从交配池中随机取出要交配的一对个体;从交配池中随机取出要交配的一对个体;2.2.根据位串长度根据位串长度L L,对要交配的一对个体,随,对要交配的一对个体,随机选取机选取11,L L11中一个或多个的整数中一个或多个的整数k k作为作为交叉点;交叉点;3.3.根据交叉概率根据交叉概率p pc(0c(0p pc1)c1)实施交叉操作,配实施交叉操作,配对个体在交叉点处,相互交换各自的部分内对个体在交叉点处,相互交换各自的部分内容,从而形成
19、新的一对个体。容,从而形成新的一对个体。对二进制编码常用的交叉算子有对二进制编码常用的交叉算子有单点交叉单点交叉、多点交多点交叉叉和和均匀交叉均匀交叉。对于从交配池中随机选择的两个串对于从交配池中随机选择的两个串 s s1 1=a a1111a a1212a a1 1l1l1a a1 1l l2 2a a1 1L L,s s2 2=a a2121a a2222a a2 2l1l1a a2 2l l2 2a a2 2L L 随机选择一个交叉位随机选择一个交叉位x x 11,2 2,L L1 1,不妨设,不妨设 l l1 1 x x l l2 2,对两个位串中该位置右侧部分的染色体位串进行交换,产
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能入门课件第5章 遗传算法 人工智能 入门 课件 遗传 算法