内容发布更新时间 : 2025/5/26 1:06:25星期一 下面是文章的全部内容请认真阅读。
基于遗传算法的k-means聚类挖掘方法研究
(4) 被选出的个体参加交叉、变异操作产生新的群体；
(5) 计算出新群体中的各条染色体的适应度值，用上一代中所记录的最优个体替换掉新种群中的最差个体，这样产生了下一代群体。
这种遗传操作既不断提高了群体的平均适应度值，又保证了最优个体不被破坏，使得迭代过程向最优方向发展。 4.5.7交叉操作
交叉操作是把两个父个体的部分结构加以替换重组而产生新个体的操作，也称为基因重组。交叉的目的是为了能够在下一代产生新的个体，因此交叉操作是遗传算法的关键部分，交叉算子的还坏，在很大程度上决定了算法性能的好坏。
由于染色体以聚类中心矩阵为基因，造成了基因串的无序性，两条染色体的等位基因之间的信息不一定相关，如果采用传统的交叉算子进行交叉，致使染色体在进行交叉时，不能很好的将基因配对起来，使生成的下一代个体的适应值普遍较差，影响了算法的效率。为了改善这种情况，又因为本文所使用的是浮点数编码方式，本文采用了一种以算术交叉为基础的混合交叉算子，即基于最短距离基因匹配的算术交叉算子[58]。
算术交叉是指由两个个体的线性组合而产生出两个新的个体。假设在两个个体X1和X2之间进行算术交叉，则交叉后产生的新个体为：
???X1??X2?(1??)X1 ?? (4-9)
??X2??X1?(1??)X2其中，?为一个参数，当?为常数时，则交叉运算为均匀交叉，否则，为非均匀交叉。
假设待交叉的两条染色体为S1?x1(1)x2(1)?xk(1)和S2?x1(2)x2(2)?xk(2)(其中
xi(i?1,2?k)为一个聚类中心)，则该混合交叉算子具体操作如下：
(1) 首先比较染色体S1?x1(1)x2(1)?xk(1)的第一个基因x1(1)与S2?x1(2)x2(2)?xk(2)上的每个基因的距离；
(2) 将S2上与x1(1)距离最近的基因xi(2)选出，并放在一条与S2等长的空染色
?上； 体S2(3) 按照上面方法依次比较S1上其他基因与S2上剩余基因的距离，并把每次
40
青岛科技大学研究生学位论文
?上，生成了一条与S1相配对的染色体选出的基因按顺序放在S2??x1S2(2)?x2(2)??xk(2)?
?进行算术交叉得到下(4) 根据交叉概率随机选取一个交叉位置j，对S1和S2一代个体S1*和S2*。
最近邻基因匹配的算术算子能够尽量保证产生有意义的新个体，以提高遗传算法的收敛速度。 4.5.8变异操作
在生物的自然进化的过程中，其细胞分裂的过程可能会出现某些差错，导致变异情况的发生。变异操作就是模仿这种情况产生的。所谓变异操作，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位来替换，从而形成一个新的个体。变异的目的有二：一是增强算法的局部搜索能力；二是增加种群的多样性，改善算法的性能，避免早熟收敛。变异操作既可以产生种群中没有的新基因又可以恢复迭代过程中被破坏的基因。
常用的变异算子有基本位变异、均匀变异、边界变异、非均匀变异和高斯近似变异。均匀变异是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码操作中各个基因座上的原有基因值。而对于浮点数编码的个体，若某一变异点处的基因的取值范围为[Umin,Umax]，变异操作就是用该范围内的一个随机数去替换原基因值。针对本文所使用的是浮点数编码方式，这里采用均匀变异算子来完成变异操作。
假设一条染色体为S?x1x2?xi?xk，则均匀变异的具体操作过程如下： (1) 依次指定个体编码串中的每个基因座为变异点，并确定每个基因点的取值范围[Umin,Umax]；
(2) 对每一个变异点，以变异概率Pm从对应基因的取值范围内取