初接触遗传算法

February 15, 2017 13:01


遗传算法(Genetic Algorithm (GA))借鉴进化生物学,通过遗传、突变、自然选择以及杂交等方式,来寻找全局最优解。

通常的算法都是确定性的,在运行过程中,每一步都是确定的,相同环境下,无论运行多少次得到的结果都是一样的,而遗传算法是属于随机化算法中的一种,运行过程中使用了随机函数,随机函数的返回值将会影响到执行结果。

遗传算法中,每个个体都是由一组基因组成的,对应了问题的一个解,多个个体组成的种群完成一次交配、变异就是进化了一代,进化过程中,在评估函数的优胜劣汰下,种群中就会出现接近最优解的个体,在达到指定条件后,中止进化过程,从当前代挑选最优秀的个体为问题的解。通过情况下,我们将条件指定为进化 N 代之后停止,当然也可以指定为其它条件,比如多长时间后。

下面通过遗传算法来解决0-1背包问题,假设我们有如下物品,要求最大重量不超过 400 的情况下,找到总价值最高的一组物品,每样物品只能选择一个

ITEMS = [
  { weight: 3, value: 200},
  { weight: 10, value: 500},
  { weight: 100, value: 30},
  { weight: 200, value: 2000},
  { weight: 300, value: 500},
  { weight: 50, value: 50},
  { weight: 190, value: 1000},
  { weight: 200, value: 1500}
]

MAX_WEIGHT = 400

首先确定一下问题的解空间,以定义个体基因;在此问题中,每样物品只有两种状态:选中和不选。那么我们的解可以用一个长度为 ITEMS.length 的数组表示,这也是问题的解空间。数组中每一个元素代表个体的一项基因,每个个体的基因组必须能与解空间所有解一一对应上。比如选了第 2、4、5、7 项物品,对应的基因表达就是 [0, 1, 0, 1, 1, 0, 1, 0],我们定了一个 Unit 类来表示一个个体

class Unit
  attr_accessor :items

  def self.random_new
    self.new(ITEMS.map do rand(2) == 1 end)
  end

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

  def length
    items.length
  end
end

接下确定评估函数,评估函数用来评估个体的好坏,越接近最优解的个体评估结果应该越好,这里我们就简单的使用物品价值做为评估结果,由于我们的解空间中也包涵了不符合要求的解:重量超过 400,或是重量为 0,如果出现这种情况,我们直接将个体的评估结果置为 1。当然也可以通过其它方式避免出现无效的解,这里为了简单起见,就直接设置评估结果为 1。评估代码如下

class Unit
  def value
    total_value = 0
    total_weight = 0
    items.each_with_index do |item, index|
      next unless item
      total_value += ITEMS[index][:value]
      total_weight += ITEMS[index][:weight]
    end
    (total_weight > MAX_WEIGHT or total_value == 0) ? 1 : total_value
  end

  def <=>(target)
    self.value <=> target.value
  end
end

然后就是产生下一代的进化过程,遗传算法的依据原则是:适应度越高,被选择的机会越高。所以评价越好的个体,遗传到下一代的机率越大,我们简单的按权评估权重来选择能进入下一代的个体,然后进行个体间的交配、变异,通常交配概率在 0.6~1之间,比如交配率为 0.8,那么每对“夫妻”都有 80% 的机率交配产生新的个体,从而替代老的个体,不交配的个体则不变;而变异率一般是0.1或更小,变异是指随机的改变一个或数个基因

遗传选择代码如下:

def select_units(units)
  total_value = units.reduce(0) {|r, u| r + u.value }

  new_units = units.map do
    Unit.new(select_unit(units, total_value).items)
  end
  new_units
end

def select_unit(units, total_value)
  p = rand(total_value)
  counter = 0

  units.each do |unit|
    counter += unit.value
    return unit if p < counter
  end
end

个体间的交配实现如下,每个个体都有一定机率和另一个同样机率选中的个体交换随机数量的基因

def exchange_units(units, rate)
  last_index = nil

  units.each_with_index do |unit, index|
    next if rand() >= rate

    if last_index
      units[last_index].exchange!(unit)
      last_index = nil
    else
      last_index = index
    end
  end
end

class Unit
  def exchange!(unit)
    (rand(length) + 1).times do
      i = rand(length)
      items[i], unit.items[i] = unit.items[i], items[i]
    end
  end
end

个体间变异代码如下:

def variation_units(units, rate)
  units.each_with_index do |unit, index|
    next if rand() >= rate
    unit.variation!
  end
end

class Unit
  def variation!
    rand(length).times { items[rand(length)] ^= true }
  end
end

接下来将上面的代码组织一下,遗传算法就完成了:

def gene(units = [], evolution = 100, exchange_rate = 0.8, variation_rate = 0.15)
  new_units = select_units(units)
  exchange_units(new_units, exchange_rate)
  variation_units(new_units, variation_rate)

  return units.sort.last if evolution <= 1

  gene(new_units, evolution - 1, exchange_rate, variation_rate)
end

# 使用 32 个个体的种群去进化,交配率为 0.8,变异率为 0.15,进化 100 代后停止
units = 32.times.map { Unit.random_new }
unit = gene(units, 100, 0.8, 0.15)

运行上面代码 100 次的话,可以看到,找到最优解的机率只有 50%,因为进化过程中会受到很多因素的影响,比如算法早熟导致收敛到局部最优解,或者评估函数在后期无法拉开最优解与非最优解的差距导致无法收敛,或是变异率过高导致无法收敛,进化代数过少等等,各方面都有非常多的地方可以去优化

比如简单的将种群规模从 32 变为 64,得到最优解的机率可以看到有少量提升,或是改变一下后代选择函数:

def select_units(units)
  total_value = units.reduce(0) {|r, u| r + u.value }

  new_units = units.map do
    Unit.new(select_unit(units, total_value).items)
  end.sort!
  new_units[0] = units.sort[-1]
  new_units
end

每次都将上一代的最好的个体替换掉下一代最差的个体,运行后,可以发现得到最优解的机率直接升到 90% 以上了

上面演示代码的 完整 Ruby 实现

References

Comments: