学习笔记——遗传算法

在人工智能领域,遗传算法(GA, Genetic Algorithm)是一种模仿自然进化过程的启发式搜索算法,该方法通常被用在优化和搜索问题中。 遗传算法属于进化算法(EA, Evolutionary Algorithms)的范畴。 常用的方法有:继承(inheritance)、变异(mutation)、选择(selection)和交叉(crossover)。

简单介绍

详细介绍

典型的遗传算法中包括:

  • 解空间的基因表达式(Genetic Representation)
  • 适应度函数(Fitness Function)

遗传算法原型

# Fitness: 适应度评分函数,为给定假设赋予一个评估函数
# Fitness_threshold: 终止判定的阈值
# p: 群体中包含的假设数量
# r: 每一步中通过交叉取代群体成员的比例
# m: 变异率
GA(Fitness, Fitness_threshold, p, r, m) {
    初始化群体: P <- 随机产生p个假设
    评估: 对于P中的每一个假设h,计算Fitness(h)
    while( `max_(h)`(Fitness(h)) < Fitness_threshold ) {
        产生新一代`P_s`:
        1. 选择: 用概率方法选择P的(1-r)p个成员加入`P_s`。从P中选择假设`h_i`的概率为:
        `Pr(h_i) = (text{Fitness}(h_i)) / (sum_(j=1)^p text{Fitness}(h_j))`
        2. 交叉: 根据上面给出的`Pr(h_i)`,从P中选择`(r*p)/2`对假设。对于每对假设`<h_1,h_2>`,应用交叉算子产生两个后代。把所有后代加入`P_s`
        3. 变异: 使用均匀概率从`P_s`中选择`m%`的成员。对于选出的每个成员,在它的表示中随机选择一个位取反
        4. 更新: `P larr P_s`
        5. 评估: 对于P中的每个h计算Fitness(h)
    }
    从P中返回适应度最高的假设
}

其他“选择”方法

在算法原型中所使用的选择方法通常被称为“适应度比例选择”(fitness proportionate selection)或者轮盘赌选择(roulette wheel selection)。另外也可以使用其他的方式来选择假设:

  • 锦标赛选择(tournament selection)
    先从当前群体中随机选取两个假设,再以事先定义的概率p选择适应度较高的假设,以概率1-p选择适应度较低的假设。锦标赛选择常常比轮盘赌方法得到更多样化的群体。
  • 排序选择(rank selection)
    当前群体中的假设先按适应度排序,某假设的概率与这个假设在排序列表中的位置成比例,而不是与它的适应度成比例。

R Packages for GA

  • GALGO:可以用来解决任何优化问题,特别适用于大数据集中的变量选择问题。
  • genalg:多维函数的优化问题。
  • mcga:处理实优化问题(real-valued optimization),使用比特而非实数的方式来表示变量,因此运算速度快。另外提供了multi_mcga函数来处理多目标优化问题。
  • rgenoud:结合遗传算法和基于微分(拟牛顿法,quasi-Newton)的方法来解决最优化问题。主要用来解决复杂函数的最大/最小问题,对于不可微的函数同样适用。

Published: May 13 2012

blog comments powered by Disqus