数据挖掘遗传算法.ppt

《数据挖掘遗传算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、遗传算法一、遗传算法的描述二、基本遗传算法的构成要素三、基本遗传算法的一般框架四、遗传算法的数学理论五、遗传算法的基本实现技术六、遗传算法的特点七、遗传算法的应用一、遗传算法的描述例子：为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：（1）价格汉堡包的价格应该定在50美分还是1美元？（2）饮料和汉堡包一起供应的应该是酒还是可乐？（3）服务速度饭店应该提供慢的还是快的服务？目的：找到这三个决定的组合以产生最高的利润。上述问题的表示方案：串长(l＝3）＋字母表规模（k＝2）＋映射共有8种表示方案用遗传算法

2、解这个问题的第一步就是选取一个适当的表示方案。饭店编号价格饮料速度二进制表示1高可乐快0112高酒快0013低可乐慢1104高可乐慢010表1饭店问题的表示方案（其中的4个）群体规模N＝4第0代i串xi适应值f（xi）10113200113110640102总和12最小值1平均值3.00最大值6表2初始群体中经营决策的适应值一个简单的遗传算法由复制、杂交、变异三个算子组成第0代交配池i串xi适应值f（xi）f（xi）/f（xi）串f（xi）101130.250113200110.081106311060.501106401020.

3、170102总和1217最小值12平均值3.004.25最大值66表3使用复制算子后产生的交配池1.复制算子：采用赌盘选择2.杂交算子：采用一点杂交作用过程：a）产生一个在1到l－1之间的随机数ib）配对的两个串相互对应的交换从i＋1到l的位段例如：从交配池中选择编号为1和2的串进行配对，且杂交点选在2（用分隔符

4、表示），杂交算子作用的结果为：01

5、101011

6、0111对交配池中指定百分比的个体应用杂交算子，假设杂交概率pc＝50％，交配池中余下的50％个体仅进行复制运算，即复制概率pr＝50％。第0代交配池第1代i串xi适应值f

7、（xi）f（xi）/f（xi）串f（xi）杂交点xif（xi）101130.25011320102200110.08110621117311060.501106－1106401020.170102－0102总和121717最小值122平均值3.004.254.25最大值667表4使用复制和杂交算子的作用结果遗传算法利用复制和杂交算子可以产生具有更高平均适应值和更好个体的群体3.变异算子：以一个很小的概率pm随机改变染色体串上的某些位。对于二进制串，就是将相应位上的0变为1或将1变为0。例如：选交配池中编号为4的串进行变异，且变异点

8、在2，则010000变异算子相对而言，是次要算子，但在恢复群体中失去的多样性方面具有潜在的作用。小结上述遗传算法描述了从第0代产生第1代的过程，然后遗传算法迭代地执行这个过程，直到满足某个停止准则。在每一代中，算法首先计算群体中每个个体地适应值，然后利用适应值信息，遗传算法分别以概率pc、pr和pm执行杂交、复制和变异操作，从而产生新的群体。应用遗传算法求解问题需完成四个主要步骤：1.确定表示方案2.确定适应值度量3.确定控制算法的参数和变量4.确定指定结果的方法和停止运行的准则二、基本遗传算法的构成要素1.染色体编码方法最常用的是

9、二进制编码，对于离散性变量直接编码，对于连续性变量先离散化后再编码2.适应度函数评估函数——用来评估一个染色体的优劣的绝对值适应度函数——评估一个染色体相对整个群体的优劣的相对值的大小3.遗传算子复制算子、交叉算子、变异算子4.基本遗传算法运行参数•N：群体大小，即群体中所含个体的数量，一般取20～100•T：遗传算法的终止进化代数，一般取100～500•pc：杂交概率，一般取0.4～0.99•pm：变异概率，一般取0.0001～0.1•pr：复制概率三、基本遗传算法的一般框架算法过程：1.随机产生一个由确定长度的特征串组成的初始群

10、体2.对串群体迭代地执行下面的步（i）和步（ii），直到满足停止准则：（i）计算群体中每个个体的适应值（ii）应用复制、杂交和变异算子产生下一代群体3.把在任一代中出现地最好地个体串指定为遗传算法的执行结果，这个结果可以表示问题的一个解（或近似解）GEN＝0产生初始群体是否满足停止准则指定结果结束计算每个个体的适应值i＝0i＝N？以概率选择遗传算子GEN＝GEN＋1选择一个个体选择两个个体选择一个个体执行复制i＝i＋1执行变异复制到新群体执行杂交插入到新群体将两个子代串插入到新群体i＝i＋1是否是否prpcpmGEN—当前代数N—群

11、体规模四、遗传算法的数学理论几个相关的定义：1、模式——是一个相同的构形，它描述的是一个串的子集，这个集合中串之间在某些位上相同。例如，添加符号*表示不确定字母，即0或1，考虑串长为7的模式H＝*11*0**，则串A＝0111000是