《进化优化》第4章 遗传算法的数学模型

4.1 图式理论

• 图式是描述一组个体的位模式，其中用*来表示不在乎的位。
• 长度为l的图式总共有3^l种。
• 长度为l的位串属于2^l个图式。
• 在一个图式中有定义的位的个数称为此图式的阶，记为o。
• 在图式中从最左边的定义位到最右边定义位的位的个数称为定义长度.
• 属于某个图示的一个位串称为此图式的一个实例。
• 一般来说，一个图式含有的实例个数等于2^A，这里A是图式中星号的个数。
• 平均适应度：

• 第t+1代实例个数的期望等于适应度总和/平均适应度
  
  交叉破坏图式的概率：
• 考虑图式h =1****.交叉不会破环这个图式.如果这个图式的一个实例与另一个位串交叉,至少会有一个子代仍是h的实例.
• 考虑图式h=11***.如果这个图式的一个实例与位串x交叉,交叉点可以有4个位置.如果交叉点在两个1位之间,图式可能会被破坏,它取决于x的值.如果交叉点在右边(另外三个可能的交叉点),图式就不会被破坏;至少有一个子代会是h的实例.由此可见,图式被破坏的概率小于或等于1/4,它取决于交叉发生的位置.
• 考虑图式h =1*1**.如果这个图式的一个实例与位串c交叉,则交叉点可以是4个位置中的其中一个.如果交叉点位于两个1位之间(有两个可能的交叉点),则图式可能被破坏,它取决于x的值.但是如果交叉点在最右边的1位的右边(另外两个可能的交叉点),则图式不会被破坏;至少有一个子代会是h的实例.由此可见,图式被破坏的概率小于或等于1/2,它取决于交叉发生的位置.

一般化：

变异概率：

泰勒展开：

类比：

图式定理：

定理4.1 具有高于平均适应度值的短的低阶图式在遗传算法种群中的代表数会呈指数增长.

4.2 马尔可夫链

马尔可夫链的核心三要素：

• 状态空间
• 无记忆性
• 转移矩阵

假设在时刻1状态：

则在时刻2处于状态1的概率：

将上面的推导一般化,我们发现在时刻2过程处于状态j的概率为

继续推理：

假设不知马尔可夫的初始状态，但是知道每个状态的概率，初始状态S(0)等于Sk的概率为pk(0），利用全概率定理得：

一般化：

4.3 进化算法的马尔可夫模型的符号

马尔可夫模型的缺点在于计算量大。

用N代表种群规模，v代表种群中个体x的个数，则：

进化算法的种群Y可以表示为：

例

在基数为n的搜索空间中,有可能存在多少个种群规模为N的进化算法的种群?[Nix and Vose,1992]证明了T为下面的二项式系数,也称为选择函数:

多项式定理：

多项式定理有几种陈述方式,其中包括下面这种:已知有K类物品,我们从中选出N个物品,每个选择独立于物品的次序,同时从每一类选出物品的次数不能多于M次,不同的选择方式的总个数是多项式中的系数qN:

4.4 遗传算法的马尔可夫模型

4.4.1 选择

首先考虑与适应度值成比例的(即轮盘赌)选择.由旋转轮盘选择个体xi的概率与个体xi的适应度和它在种群中的个数的乘积成正比.这个概率是正规化的,所以全部概率的和为1.在前面一节中定义vi是种群中个体xi的个数.所以,由旋转轮盘选出个体xi,的概率为:

4.4.2 变异

定义Mji为xj变异到xi的概率，在旋转依次轮盘并紧接着一次变异之后得到个体xi的概率为：

改写：

利用多项式分布理论得到：

4.4.3 交叉

现在假设在选择和变异之后进行交叉.

在两次旋转轮盘后,对被选中的每一个个体做单次变异然后再交叉,最后得到个体xi的概率为

利用多项式分布理论，得到：

维数灾

4.5 遗传算法的动态系统模型

本节用前面的马尔可夫模型推导遗传算法的动态系统模型.利用马尔可夫模型,能得到当代数趋于无穷大时每个种群分布发生的概率.这里推导的动态系统模型却很不同:它会告诉我们,当种群规模趋于无穷大时种群中每一个个体随时间变化的百分比.

4.5.1 选择

为找出只包含选择(即没有变异或交叉)的遗传算法的动态系统模型,可以对(4.36)式的分子和分母除以N,于是,从向量v描述的种群中选出个体xi的概率就可以写成:

根据大数定律,从大量试验得到的结果的平均值应该与单个试验结果的期望值接近.这意味着当种群规模变大,选择每一个个体xi的比例会接近于Prs(xi|v)．但是,选择xi的次数正好等于下一代的vi所以,对于大的种群规模,(4.50)式可以写成

现在假设：

由(4.52)式,当t=1时上式显然是正确的.假设对于t-1,(4.53)式成立,(4.52)式的分子可以写成

而(4.52)式的分母可以写成

把(4.54)式和(4.55)式代入(4.52)式,得到

在遗传算法仅实施选择(无变异或交叉)的情况下,这个等式给出了随着时间、适应度值以及初始比例向量变化的比例向量.

4.5.2 变异

根据大数定理，由（4.51）式可知，

如果选择之后变异，并且Mji是xj变异到xi的概率，则采用与(4.38)式类似的推导，得到

如果p(t)达到稳态值，则可以由pss=p(t-1)=p(t)将（4.60）式写成

4.5.3 交叉

下面推导由随机交叉得到xi的概率：