选择和适应度函数20160510课件

1、11/30/202112016年年 教学公开课教学公开课选择和适应度函数选择和适应度函数计算智能导论电子工程学院电子工程学院尚荣华尚荣华2016.05n 问题介绍问题介绍2016年年 教学公开课教学公开课从群体中选择优胜个体，淘汰劣质个体的操作叫从群体中选择优胜个体，淘汰劣质个体的操作叫选择选择。选择的基础选择的基础是达尔文的适者生存理论；是达尔文的适者生存理论；遗传算法本质上是一种随机搜索，遗传算法本质上是一种随机搜索，选择算子选择算子则将遗传搜索的方向则将遗传搜索的方向引向引向 最优解所在区域最优解所在区域；选择的作用选择的作用使得群体最优解所在区域移动。使得群体最优解所在区域移动。 se

2、lection主要内容：主要内容：n选择压力选择压力n选择方式选择方式n适应度函数适应度函数n适应度共享适应度共享选择和适应度函数选择和适应度函数一、选择压力一、选择压力定义（选择压力）：定义（选择压力）： 最佳个体选中的概率与平均选中概率的比值。最佳个体选中的概率与平均选中概率的比值。n合适的选择压力很重要；合适的选择压力很重要；n选择压力太大容易早熟，选择压力太大容易早熟， 选择压力太小，进化缓慢。选择压力太小，进化缓慢。n我们希望初始阶段选择压力小，最终选择压力大。具体如下图所示：我们希望初始阶段选择压力小，最终选择压力大。具体如下图所示： 二、选择方式二、选择方式2.1 2.1 随机选

3、择随机选择n选择幅度决定了每个个体被复制的次数；选择幅度决定了每个个体被复制的次数； n选择幅度由以下两部分组成选择幅度由以下两部分组成: : i.i.确定染色体的期望值；确定染色体的期望值；ii.ii. 将期望值转换为实际值，即该染色体后代个体的数目。将期望值转换为实际值，即该染色体后代个体的数目。n经过选择将期望转化为实际值即后代个数的常用的选择方式：经过选择将期望转化为实际值即后代个数的常用的选择方式：i.i.轮盘赌的选择方式；轮盘赌的选择方式；ii.ii. 一次随机采样。一次随机采样。二、选择方式二、选择方式2.1 2.1 随机选择随机选择轮盘赌选择轮盘赌选择又称比例选择算子，其基本思

4、想是：个体被选中的概又称比例选择算子，其基本思想是：个体被选中的概率与其适应度函数值成正比。率与其适应度函数值成正比。二、选择方式二、选择方式step 1:计算群体的总适应度：计算群体的总适应度：step 2:计算染色体计算染色体vk的选择概率的选择概率pk ：step 3:计算染色体计算染色体vk的累积概率的累积概率 qk ：step 4:随机产成一个随机产成一个0, 1的数的数r；step 5:如果如果r q1, 选择第一条染色体选择第一条染色体 v1; 否则否则, 如果如果qk-1 r qk, 选择第选择第 k条染色体条染色体 vk (2 k popsize).输入输入: 群体群体 p(

5、t-1), c(t-1)输出输出: 群体群体p(t), c(t)轮盘赌选择轮盘赌选择的的具体步骤如下：具体步骤如下：问题问题1 1：轮盘赌选择方轮盘赌选择方式是式是如何如何做到个体做到个体被选中的概率与其被选中的概率与其适应度函数值成正适应度函数值成正比的？比的？二、选择方式二、选择方式轮盘赌选择轮盘赌选择问题问题2 2：轮盘赌选择轮盘赌选择结果中结果中个体个体的实际值与期望值一致吗的实际值与期望值一致吗? ?二、选择方式二、选择方式2.1 2.1 随机选择随机选择问问题题3 3：这两种采样方式有什么区别？这两种采样方式有什么区别？二、选择方式二、选择方式2.2 2.2 确定性选择确定性选择所

6、谓确定性选择就是从父代和子代个体中选择最优的个体。所谓确定性选择就是从父代和子代个体中选择最优的个体。具体举例如下：具体举例如下：n( + )-selection( 个父代，个父代， 个子代个子代, 从从 + 选择最好的选择最好的 )n( , )-selection( 个父代，个父代， 个子代个子代, 从从 选择最好的选择最好的 ) nelitist selection(贪婪选择，在比例选择最优个体没有被选择，强制选择贪婪选择，在比例选择最优个体没有被选择，强制选择) nthe generational replacement(代替换代替换) nsteady-state reproductio

7、n(稳态再生，稳态再生，n个最差的父代个体被子代替换个最差的父代个体被子代替换) 问问题题4 4：请大家分析请大家分析( + )-selection和和( , )-selection两种两种选择选择方式中，哪种选择压力大，哪种选择压力小？方式中，哪种选择压力大，哪种选择压力小？二、选择方式二、选择方式2.3 2.3 混合选择混合选择混合选择同时具有随机性和确定性，如混合选择同时具有随机性和确定性，如tournament selection(竞赛选择竞赛选择)。 竞赛选择竞赛选择: 竞赛规模竞赛规模= t repeat t times从种群中随机选择一个个体并记下其适应度；从种群中随机选择一个个

8、体并记下其适应度；返回返回t个个体中最好的个体。个个体中最好的个体。可以通过可以通过选择选择t, 调节选择压力调节选择压力。当。当t =2为二进制竞赛选择为二进制竞赛选择。问问题题5 5：请大家分析请大家分析随着随着t的增大的增大选择压力选择压力如何变化如何变化？三、适应度函数三、适应度函数3.1 3.1 定义定义遗传算法在进化搜索中基本不用外部信息，仅用目标函数即适应度函数为依遗传算法在进化搜索中基本不用外部信息，仅用目标函数即适应度函数为依据，利用种群每个个体的适应度来指导搜索。据，利用种群每个个体的适应度来指导搜索。需要强调的是，需要强调的是，适应度函数值是选择操作的依据，适应度函数适应

9、度函数值是选择操作的依据，适应度函数(fitness (fitness function)function)的选取直接影响到遗传算法的收敛速度以及能否找到最优解。的选取直接影响到遗传算法的收敛速度以及能否找到最优解。三、适应度函数三、适应度函数 1）对最小化问题，建立如下适应函数和目标函数的映射关系：）对最小化问题，建立如下适应函数和目标函数的映射关系： 其中，其中，cmax可以是一个输入值或是理论上的最大值，或者是当前所有大或最可以是一个输入值或是理论上的最大值，或者是当前所有大或最近近k代中代中g(x)的最大值，此时的最大值，此时cmax随着代数会有变化。随着代数会有变化。 2）对于最大化

10、问题，一般采用以下映射：）对于最大化问题，一般采用以下映射： 其中，其中，cmin可以是一个输入值，或是当前所有代或最近可以是一个输入值，或是当前所有代或最近k代中代中g(x)的最小值。的最小值。否则若, 0)(),()(maxmaxcxgxgcxf否则若, 00)(,)()(minmincxgcxgxf三、适应度函数三、适应度函数 3.2 3.2 适应度变换适应度变换n引例：引例：对于最大化问题对于最大化问题，假定群体中有以下，假定群体中有以下5个个体，其适应度分别为：个个体，其适应度分别为： 100, 0.4, 0.3, 0.2, 0.1 -最好个体的适应度为其余个体适应度和的最好个体的适

11、应度为其余个体适应度和的100倍！倍！可以对适应度做如下变换：可以对适应度做如下变换：200, 100.4, 100.3, 100.2, 100.1 -比较合理的情况！比较合理的情况！n定义：定义：这种适应度的缩放调整称为适应度变换。这种适应度的缩放调整称为适应度变换。n适应度变换有两个目的：适应度变换有两个目的： 维持个体之间的合理差距，加速竞争；维持个体之间的合理差距，加速竞争； 避免个体之间的差距过大，限制竞争。避免个体之间的差距过大，限制竞争。假定第假定第k个染色体的原始的适应度为个染色体的原始的适应度为fk , 变换后的适应度变换后的适应度 fk为为: fk = g( fk ) 函数

12、函数g() 根据采用的形式不同会产生不同的变换方法，具体如下：根据采用的形式不同会产生不同的变换方法，具体如下： n线性变换线性变换bfafkkn 指数变换指数变换kkffminmaxmin, 01 ()kkfffff对于最大化问题n归一化变换归一化变换tfkkef/n boltzmann变换变换三、适应度函数三、适应度函数四、适应度共享四、适应度共享n共享函数法根据个体某个距离内与其他个体的临近程度来确定该个体共享函数法根据个体某个距离内与其他个体的临近程度来确定该个体的适应度应改变多少。的适应度应改变多少。n在拥挤的峰周围的个体的复制概率受到抑制，利于其他个体产生后代。在拥挤的峰周围的个体

13、的复制概率受到抑制，利于其他个体产生后代。n适应度共享可用于多峰搜索适应度共享可用于多峰搜索, , 共享函数的作用在于根据个体临域内个共享函数的作用在于根据个体临域内个体的分布情况对个体的适应度进行惩罚！体的分布情况对个体的适应度进行惩罚！四、适应度共享四、适应度共享根据两个染色体之间采用的举例测度的不同，分为以下两类根据两个染色体之间采用的举例测度的不同，分为以下两类: genotypic sharing(基因型共享基因型共享) 个体之间的距离在码空间进行计算个体之间的距离在码空间进行计算,具体如下具体如下:其中其中, si表示编码形式的一个字符串或者一条染色体。表示编码形式的一个字符串或者

14、一条染色体。 phenotypic sharing(表现型共享表现型共享)个体之间的距离在解空间进行计算个体之间的距离在解空间进行计算,具体如下具体如下: 其中其中, xi表示解码后的一个解。表示解码后的一个解。),(jiijddss),(jiijddxx四、适应度共享四、适应度共享共享函数共享函数sh(dij) 定义如下定义如下: 其中，其中， 是一个常数，是一个常数， share 是用户定义的小生境半径。是用户定义的小生境半径。给定了适应度函数的定义之后，一个染色体的共享适应度给定了适应度函数的定义之后，一个染色体的共享适应度fi 定义如下：定义如下：mi 为给定染色体为给定染色体i的小生境计数（的小生境计数（the niche count），为染色体），为染色体i与群体中所有染与群体中所有染色体之间共享函数之和，具体定义如下：色体之间共享函数之和，具体定义如下： otherwise, 0if,1shshareshareijijijdddiiimff popsizejijid