《关于遗传算法的数学基础》由会员分享，可在线阅读，更多相关《关于遗传算法的数学基础（7页珍藏版）》请在金锄头文库上搜索。
1、1、遗传算法的数学基础（1 1）模式定理）模式定理 （2 2）积木块假设）积木块假设 模式模式模式是指种群个体基因串中的相似样模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三的结构。在二进制编码中，模式是基于三个字符集个字符集(0,1,*)(0,1,*)的字符串，符号的字符串，符号* *代表任意代表任意字符，即字符，即 0 0 或者或者 1 1。 模式示例：模式示例：10*110*1两个定义两个定义定义定义1 1：模式：模式 H H 中确定位置的个数称为模式中确定位置的个数称为模式 H H 的阶，记作的
2、阶，记作O(H)O(H)。例如。例如O(10*1)=3 O(10*1)=3 。定义定义2 2：模式：模式 H H 中第一个确定位置和最后一中第一个确定位置和最后一个确定位置之间的距离称为模式个确定位置之间的距离称为模式 H H 的定义的定义距，记作距，记作(H)(H)。例如。例如(10*1)=4 (10*1)=4 。 模式的阶和定义距的含义模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。 模式定理模式定理：具有低阶、短定义距以及模式定理：具有低阶、短定义距以及
3、平均适应度高于种群平均适应度的模式在平均适应度高于种群平均适应度的模式在子代中呈指数增长。子代中呈指数增长。模式定理保证了较优的模式（遗传算模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。遗传算法机理提供了数学基础。 模式定理模式定理从模式定理可看出，有高平均适应度、短从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破最好的模式
4、有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几变概率又相当小，因而它对这些重要的模式几乎没有影响。乎没有影响。 积木块假设积木块假设 积木块假设：遗传算法通过短定义距、低阶积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。生成全局最优解。
