DS-PGA 算法在 Hadoop 集群框架下的实现

DS-PGA 算法在 Hadoop 集群框架下的实现

DS-PGA算法与 MapReduce 结合算法的执行流程如下: (1)将测试样本集平均分割成 M 份(由 InputFormat 负责将

数据块划分为 InputSplit),并对数据格式进行统一(格式化为 <id, <A,B>>,其中,id 代表由用户名和访问日期组成的编号; B代表用户当前访问的页面;A代表参照Ref,即用户在访问 页面 B 之前停留的页面。
(2)Map 操作是对输入的每个记录进行扫描,将数据集按 照上述格式进行初始化;经过 Map 操作后,得到中间结果 <<A,B>,1>,即有一个用户从页面 A 访问了页面 B;Reduce 操作则将中间结果按照具有相同<A,B>的页面跳转访问方式 进行合并得到输出结果<<A,B>,n>,其中,n 代表访问路径 A—>B 的频度。
(3)每个子群体分别将 Reduce 操作的结果转换为链表结 构,链表头部保存 k 值。链表结构如下所示,其中,k 代表染色体的长度;A、B、D、E 代表网页。
3

(4)子群体内部进行选择、交叉等遗传进化操作。首先从 父代染色体中随机选择 2 条染色体,然后随机生成插入位置 Ins、删除位置 Del、插入删除长度 Len。接着比较 2 段染色 体是否等长,如果相等,则判断头尾是否有重合,有,则连 接生成新的染色体,否则,不生成子代染色体;如果不等长, 则判断插入和删除的 2 段基因是否相同,如果相同,则合并 为一条染色体作为新的染色体,否则,不生成子代染 色体。
(5)当遗传代数为 50 的倍数时,群体间进行联姻操作。
(6)每个子群体一直重复上述操作,直到 k 值不再变化, 退出程序。