遗传算法模式理论总论.ppt

遗传算法的理论基础 主要内容 1.遗传算法的模式理论 2.遗传算法实现中的一些基本问题 遗传算法的模式理论 从前面简单遗传算法的操作中，我们可以看到寻优问题的性能是朝着不断改进的方向发展的。但是我们怎么能知道对某一特定问题使用遗传算法会得到优化或接近优化的解呢？ 这一章节分析遗传算法中的模式理论： 模式； 复制对模式的影响； 交叉对模式的影响； 变异对模式的影响； 遗传算法有效处理的模式数量。 模式 一个模式(Schemata)就是一个描述种群中在 位串的某些确定位置上具有相似性的位串子集 的相似性模板(Similarity Template) 。 例如：(即取位串的十进制数值的平方) 位串 适配值 x=01101 f(x)=x2＝132＝169 11000 576 01000 64 10011 361 在上列种群里的各位串之间，我们能发现具有某 种相似性和这种相似性与高适配值之间具有某种因果 关系。 模式 位串 适配值 01101 169 11000 576 01000 64 10011 361 这种因果关系例如：凡是以“1”开始的位串，其适配值就高；以“0”开始的位串的适配值就低。 这种相似性正是遗传算法有效工作的因素。根 据对种群中高适配置位串之间的相似性的分析，Holland提出了遗传算法的模式理论. 模式 为了描述一个模式，在用以表示位串的两个字符的字母{0,1}中加入一个通配符“*”，就构成了一个表示模式用的三个字符的字母表{0，1，*}。 因此用三元素字母表{0，1，*}可以构造出任意一种模式。 一个模式与一个特定位串相匹配是指：该模式中的1与位串中的1相匹配，模式中的0与位串的0相匹配，模式中的“*”可以匹配位串中的0或1。 模式 例如： 模式00*00匹配了两个位{00100,00000} 模式*111*可以和{01110, 01111, 11110, 11111}中的任何一个位串匹配，即与长度为5中间三位为“1”的四个位串匹配； 模式0*1**则匹配了长度为5、第一位为0、第三位为1的8个位串{00100, 00101, 00110, 00111, 01100, 01101, 01110, 01111} 模式 模式的思路为我们提供了一种简单而有效的方法，使能够在有限字母表的基础上讨论有限长位串的严谨定义的相似性。 应强调的是，“*”只是一个元符号，既是代表其他符号的一个符号。它不能被遗传算法直接处理，只不过是允许来描述特定长度和特定字母表的位串的所有可能相似性的符号件。 模式 一般地，假定字母表的基数是k，例如{0,1}的 基数是2，则定义在该字母表上的长度为l 的位串中所有可能包含的最大模式数为（k+1)l，原因是在l个位置中的任何一个位置上都可以取k个字符中的任何一个及通配符“*” ，即共有k+1个位置中的任何 一个位置的全排列数为（k+1)l。 例如，对长度l ＝5，k=2则会有3×3×3×3×3＝35＝243＝(k+1)l 中不同的相似模板，而位串的数量仅为kl =25=32。可见，模式的数量要大于位串的数量。 模式 对于任一长度为l 的给定位串，其中所含模式数 为2l 个。因为在l 个位置中的任一位置除了取其确定值外，还可以取“*”,即任一位置上都有两种不同表示，故有2l 个不同模式，因此，对于大小为n的种群，则包含有2l ～n×2l 种模式. 种群中位串之间的众多的相似性，可引导遗传算法有效地有哪些信誉好的足球投注网站。因为即使是一个规模不大的种群，也包含了丰富的2l ～n×2l 个有关这种相似性的信息。 这些相似性和适配值之间的相关性正是是遗传算法能够进行有效有哪些信誉好的足球投注网站的根本所在。 模式 为论述方便，首先定义一些名词术语。不失一般性，考虑在二进制字母表V={0，1}上构造位串的表示。用大写字母表示一个位串，如 这里的 代表一个二值特性 ai又 可称为基因。相应地，一个模式是定义在 V＋＝{0,1,* }之上的，用大写字母H表示，如 H=10**11*。 在第t 代的种群用A(t )表示，种群中的个体位 串分别用Aj（j＝1，2，…，n）表示。 模式 为了区分不同类型的模式，对模式H定义两个 量：模式位数(Order)和模式的定义长度(Defining Length)分别表示为O(H)和δ(H)。 O(H)是H中有定义的非“*”为的个数； 模式的定义长度δ (H)是指H中最两端的有定义位置之间的距离 如H＝00*1*0， 则O(