选择和适应度函数20160510

2016年教学公开课选择和适应度函数《计算智能导论》电子工程学院尚荣华2016.05问题介绍2016年教学公开课从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择的基础是达尔文的适者生存理论；遗传算法本质上是一种随机搜索，选择算子则将遗传搜索的方向引向

最优解所在区域；选择的作用使得群体最优解所在区域移动。Selection主要内容：选择压力选择方式适应度函数适应度共享选择和适应度函数一、选择压力定义（选择压力）：

最佳个体选中的概率与平均选中概率的比值。合适的选择压力很重要；选择压力太大容易早熟，选择压力太小，进化缓慢。我们希望初始阶段选择压力小，最终选择压力大。具体如下图所示：

二、选择方式2.1随机选择选择幅度决定了每个个体被复制的次数；

选择幅度由以下两部分组成:确定染色体的期望值；将期望值转换为实际值，即该染色体后代个体的数目。经过选择将期望转化为实际值即后代个数的常用的选择方式：轮盘赌的选择方式；一次随机采样。二、选择方式2.1随机选择轮盘赌选择又称比例选择算子，其基本思想是：个体被选中的概率与其适应度函数值成正比。二、选择方式step1:计算群体的总适应度：step2:计算染色体vk的选择概率pk：step3:计算染色体vk的累积概率qk：step4:随机产成一个[0,1]的数r；step5:如果r

q1,选择第一条染色体v1;否则,如果qk-1<r

qk,选择第k条染色体vk(2

k

popSize).输入:群体P(t-1),C(t-1)输出:群体P(t),C(t)轮盘赌选择的具体步骤如下：问题1：轮盘赌选择方式是如何做到个体被选中的概率与其适应度函数值成正比的？二、选择方式轮盘赌选择问题2：轮盘赌选择结果中个体的实际值与期望值一致吗?二、选择方式2.1随机选择问题3：这两种采样方式有什么区别？二、选择方式2.2确定性选择所谓确定性选择就是从父代和子代个体中选择最优的个体。具体举例如下：(+)-selection(个父代，个子代,从+选择最好的)(,)-selection(个父代，个子代,从选择最好的)Elitistselection(贪婪选择，在比例选择最优个体没有被选择，强制选择)Thegenerationalreplacement(代替换)Steady-statereproduction(稳态再生，n个最差的父代个体被子代替换)问题4：请大家分析(+)-selection和(,)-selection两种选择方式中，哪种选择压力大，哪种选择压力小？二、选择方式2.3混合选择混合选择同时具有随机性和确定性，如Tournamentselection(竞赛选择)。

竞赛选择:竞赛规模=t

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

1）对最小化问题，建立如下适应函数和目标函数的映射关系：其中，cmax可以是一个输入值或是理论上的最大值，或者是当前所有大或最近K代中g(x)的最大值，此时cmax随着代数会有变化。

2）对于最大化问题，一般采用以下映射：

其中，cmin可以是一个输入值，或是当前所有代或最近K代中g(x)的最小值。三、适应度函数

3.2适应度变换引例：对于最大化问题，假定群体中有以下5个个体，其适应度分别为：100,0.4,0.3,0.2,0.1--最好个体的适应度为其余个体适应度和的100倍！可以对适应度做如下变换：200,100.4,100.3,100.2,100.1--比较合理的情况！定义：这种适应度的缩放调整称为适应度变换。适应度变换有两个目的：维持个体之间的合理差距，加速竞争；避免个体之间的差距过大，限制竞争。假定第k个染色体的原始的适应度为fk,变换后的适应度fk'为:fk'=g(fk

)函数g(·)根据采用的形式不同会产生不同的变换方法，具体如下：

线性变换

指数变换归一化变换Boltzmann变换三、适应度函数四、适应度共享共享函数法根据个体某个距离内与其他个体的临近程度来确定该个体的适应度应改变多少。在拥挤的峰周围的个体的复制概率受到抑制，利于其他个体产生后代。适应度共享可用于多峰搜索,共享函数的作用在于根据个体临域内个体的分布情况对个体的适应度进行惩罚！四、适应度共享根据两个染色体之间采用的举例测度的不同，分为以下两类:Genotypicsharing(基因型共享)个体之间的距离在码空间进行计算,具体如下:其中,

si表示编码形式的一个字符串或者一条染色体。Phenotypicsharing(表现型共享)个体之间的距离在解空间进行计算,具体如下:

其中,

xi表示解码后的一个解。四、适应度共享共享函数Sh(dij)定义如下:

其中，

是一个常数，share

是用户定义的小生境半径。给定了适应度函数的定义之后，一个染色体的共享适应度fi'

定义如下：mi

为给定染色体i的小生境计数（thenichecount），为染色体i与群体中所有染色体之