DS-PGA算法

DS-PGA算法

基于数据分割技术和遗传算法的 混合算法 DS-PGA,该算法结合了数据分割技术的分布式处 理和遗传算法的全局搜索最优解的优点。改进后的算法更适 合在分布式计算环境中执行。DS-PGA 算法步骤如下:

步骤 1 数据分割处理。针对 Web 日志文件的特点,对 Web 日志文件按用户和访问日期进行分割,并传输到不同的 子节点上,同时获取用户定义的支持度 S。

步骤 2 初始化群体。各子节点在 Hadoop 集群框架下利 用 Map 和 Reduce 操作将数据集转化为满足用户定义支持度 的偏爱子路径的 1-项集形式,作为遗传算法的初始种群。
步骤 3 适应度值计算。通过一条访问路径的频度衡量其 是否是用户偏爱的访问路径,因此,适应度函数定义如下:

1

其中,S’为路径的访问频度。保留 Fitness 大于 1 的个体进 入下一代。
步骤 4 若当前进化代中所有个体的适应度值 Fitness 等 于 1,表明群体经过遗传进化后得不到改善,转至步骤 7,否 则,继续。
步骤 5 对该代进行选择、交叉操作。在遗传进化过程中, 首先采取精英保留策略,保留遗传过程中的精英个体,让它 们不参与交叉操作直接进入下一代。本文将第 i 个个体的选 择概率定义为:

2

其中,S’i 为第 i 个个体的路径访问频度;Savg 为群体中所有 个体路径访问频度的平均值。
在保留的个体中,根据选择概率选取个体进行交叉操作, 当代数为 50 的倍数时,进行迁移操作,相邻 2 个子群体间联 姻,并将联姻后代中的最佳个体复制到相关的源种群中。
步骤 6 将整个子代群体替代父代群体,形成新一代,然 后转至步骤 2。
步骤 7 当经过一定遗传代数后,k 值仍无变化,则退出 进化,输出最终用户偏爱访问路径。