初接触遗传算法 (二)

March 10, 2017 14:33


之前讲了如何使用遗传算法解 01背包问题,下面讲一下使用遗传算法进化扫地机器人罗比的例子。

在一个 10x10 的方格空间中,每个方格都有 50% 机率存在可乐瓶,而罗比的目标就是在规定的操作数下,尽可能的清理更多的可乐瓶;罗比只能执行这些操作:向指定方向移一格、随机方向移动一格、捡取可乐瓶。

背包问题我们可以明确的知道,解必然是给定物品中的一个组合,那么上面的罗比机器人应该如何去解呢?我们可以通过罗列出所有罗比可能出现的状况,然后为此状况指定一个操作,那么这个问题的基因组就可以这样定义:每种状况都是一条基因,状况对应的操作就是此基因的值。而我们所要做的就是进化出一组最好的基因,来应对各种状况。

罗比当前状况我们就简单的定义为罗比当前位置及上下左右四个格子的情况,如下图

     A   B   C
  /////边沿/////
1 // 0 | 0 | 0 |
  //------------
2 // 1 | 1 | 0 |
  //------------
3 // 0 | 1 | 1 |
  //------------

我们可以使用 0 表示空的格子,1 表示可乐瓶,2 表示边沿墙壁;当罗比位于A1时,上方是边沿为 2,左也是边沿,当前位置和右边都是空的为 0,下方有一个可乐瓶,为 1,按上左中右下的顺序拼接所有状态就是 22001,如果罗比位于 B2,那么当前状况就是使用 B1、A2、B2、C2、B3 连接起来的串 01101,最多有 243(3^5) 种组合,如果收集更多的信息加入,将会得到一个更大的状况集合,比如收集周围的 8 个方向状况。

然后每种状况都会执行对应的操作,操作上移、下移、左移、右移、捡取分别使用 1、2、3、4、5 来表示,最终,这个问题的解空间大小将会变成 5^243。

下面,开始使用遗传算法进化出一个会清理可乐瓶的机器,首先定义机器人的 6 种操作

# 0 random move
# 5 clear
# move:
#   1  
# 2   3
#   4  
ACTIONS = [0, 1, 2, 3, 4, 5]

GA 算法流程这里就不细说了,可以参考上一篇文章,下面会使用自己封装的一个简单 GA 框架: https://github.com/xjz19901211/ga

由于罗比所处的状况比较多,所以我们也不一一去定义了,而让罗比在进化过程中,自己去记录这些状况,下面是机器人个体的的实现代码

class Robot
  include GA

  # {env => action}
  attr_accessor :genome, :fitness
  TOTAL_VALUE_TEST = 100

  # 初始时状况基因是空的
  def self.random_new
    self.new({})
  end

  def initialize(genome)
    @genome = genome.dup
  end

  # 通过进行多次清扫工作,来对当前机器人进化进比较准确的评估
  # TOTAL_VALUE_TEST 这个例子中定义的 100, 使用进行 100 次清扫后的平均值
  # 每次清扫让机器人执行 200 次操作
  def fitness
    @fitness ||= RobotTester.test(TOTAL_TEST_TIMES, 200, self)
  end

  # 传入一下当前状况,然后返回一个操作
  # 如果这个状况不存在于基因当中,就记录此状况到基因中,并使用一个随机的操作
  def analyse_env(env)
    @genome[env] ||= ACTIONS.sample
  end

  def cross!(target)
    all_genome = (genome.keys + target.genome.keys).uniq
    len = all_genome.length

    (len / 4 + rand(len / 4)).times do
      gene = all_genome[rand(len)]
      genome[gene] ||= ACTIONS.sample
      target.genome[gene] ||= ACTIONS.sample
      genome[gene], target.genome[gene] = target.genome[gene], genome[gene]
    end
  end

  def mutate!
    all_genome = genome.keys
    len = all_genome.length

    (len / 4 + rand(len / 2)).times do
      gene = all_genome[rand(len)]
      genome[gene] = (ACTIONS - [genome[gene]]).sample
    end
  end
end

个体间的交配和背包问题差不多,随机交换 1/2 到 3/4 基因,变异也是随机变异 1/2 到 3/4 的基因

通过 RobotTester 直接让机器人去执行清扫工作,根据清扫结果来评分,评分规则为:捡到可乐瓶加 10 分,撞墙减 5 分,执行捡取操作,但地上没有可乐瓶时,减 1 分。由于机器人的行动和场景可乐瓶都是随机的,执行一次并不能准确的评估机器人的好坏,所以通过执行多次清扫不同的场景来取平均值,由于测试的计算量比较大,所以使用 C++ 实现了机器人检测程序 RobotTester,可以参考 https://github.com/xjz19901211/ga/tree/master/examples

可以为算法指定 200 个个体,跑 500 次来查看结果,下面代码基于上面提到的 GA 框架,下面使用并行库 Parallel,同时对多个机器人进行测试。

ga_zoo = Robot.new_ga_zoo
ga_zoo.debug!

ga_zoo.before_init_fitness do |units|
  vs = Parallel.map(units, in_processes: 8) do |unit|
    [unit.fitness, unit.genome]
  end
  units.each_with_index do |unit, index|
    unit.fitness, unit.genome = vs[index]
  end
end

robots = ga_zoo.evolve(200, 500, 0.8, 0.15)
robot = robots.max

在 debug 模式中,可以看到每代机器进化后的分数变化,经过几十代后,机器人已经不会撞墙了,一百代后,机器人偶尔会捡起几个可乐瓶,在 200 代后,可以拾取更多的可乐瓶。

在遗传算法的两个例子中可以看出,如果使用普通的逻辑判断来解决背包问题或是上例的机器人逻辑是非常简单的,但通过遗传算法来解的话,在性能上慢了很多。但从另一方面来看,通过几百代的进化,遗传算法就可以在 5 ^ 243 的解空间中寻找出一个较好的解,这是普通遍历无法做到的,常常可能通过进化得到出人意料的解决方式。

References

Comments: