数据挖掘——第六章遗传算法.pptVIP

遗传算法;遗传算法〔GA，GeneticAlgorithms〕是由霍兰德(JohnHolland)与其同事、学生于1975年在Michigan大学所开展的。

GA是一种借鉴生物界自然选择和进化机制开展起来的高度并行、随机、自适应有哪些信誉好的足球投注网站算法。简单而言，它使用了有哪些信誉好的足球投注网站技术，将种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新一代的种群，并逐步使种群进化到包含近似最优解的状态。;生物进化理论和遗传学的根本知识;生物进化理论和遗传学的根本知识;生物进化理论和遗传学的根本知识;生物进化理论和遗传学的根本知识;生物进化理论和遗传学的根本知识;遗传算法可定义为一个8元组：

GA=(C,E,P0,M,?,?,?,T)

式中， C—个体的编码方法；

E—个体适应值评价函数；

P0—初始种群；

M—群体大小；

?—选择算子；

?—交叉算子；

?—变异算子；

T—遗传算法终止条件。;初始化种群;遗传算法的关键技术包括：

编码问题；

初始种群的产生；

确定适应值函数；

选择遗传操作算子；

停机条件。;编码问题

由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。

编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化的效率。由于不同的编码方法具有不同的特点，为了提高遗传算法的效率，应根据不同的情况采用不同的编码方式。

主要的编码方法有二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。;编码问题

由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。

编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化的效率。由于不同的编码方法具有不同的特点，为了提高遗传算法的效率，应根据不同的情况采用不同的编码方式。

主要的编码方法有二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。;编码问题

在遗传算法中一般用二值〔0，1〕向量表示染色体，故先要对规那么进行编码。

编码采用二进制，将由特征和类别组成的???练例子集编码成二进制字符串的遗传样本。一个样本Mi是一个二元组，其形式如下：Mi=[xi，yi]，其中：i为样本号；x为条件局部，即训练例子的各特征编码；y为结论局部，即训练例子的类别。;具体的编码规那么如下：

假设属性为范畴型，定义属性段的宽度等于属性取值个数。对于每个属性段，假设第一位为‘*’，表示该属性取值可以为任意；否那么，各位假设取值为1，表示取该属性值，0表示不取该属性值。例如，某条件属性Ci对应的编码二进制串为011001，表示该属性取第二个属性值或第三个属性值或第六个属性值，即

假设属性为数值型，定义属性段的宽度，其中n为该属性的取值个数。对于每个属性段，假设第一位为‘*’，表示该属性取值可以为任意;初始种群的产生

GA以初始种群作为初始点开始迭代。初始种群大小表示群体中所含个体的数量。当个体数量取值较小时，可提高遗传算法的运算速度，但有哪些信誉好的足球投注网站空间分布范围有限，降低了群体的多样性，有可能会引起遗传算法的早熟现象；当个体数量取值较大时，一方面计算复杂，会使遗传算法的运行效率降低，另一方面，局部高适应值的个体可能被淘汰，影响交叉。初始种群的一般取值范围是20~100。;产生初始种群的方法通常有两种：

〔1〕对问题的解无任何先验知识的情况，采用随机产生样本的方法；

〔2〕对于具有某些先验知识的情况，可首先将这些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中随机地选取样本。这样选择初始种群可使遗传算法更快地到达最优解。;遗传算法关键技术;遗传算法关键技术;选择遗传操作算子;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法关键技术;遗传算法的步骤;遗传算法的实例;4〕选择率和期望值

选择率：

平均适应值：

期望值：

5〕实选值

期望值取整数。如下表：;表1：初始种群参数计算;表2：初始种群的遗传过程;表3：新种群参数计算;表4：新种群的遗传过程;标准遗传算法使用固定长度的二进制符号串，来表示群体中的个体，基因数串中的各位置均由0或1所组成。初始群体中各个个体的基因可用均匀分布的随机数来产生。

例如就可以表示一个个体，该个体之染色体长度是n=18。; 要进行编码工作，即将变量转换成二进位数串。串的长度取决于所要求的精度。

例如：

变量x的区间是[L,U]，要求的精度是小