瞎折腾:遗传算法、禁忌搜索、模拟退火

April 04, 2017 12:44


先给一个 TSP(Travelling salesman problem) 题目:

给定 64 点,计算出一条经过所有的点最后返回起始点的最短路径。

经典的 TSP 问题,需要找出 64 个点的最短路径,如果使用普通的遍历的话,时间复杂度为 O(n!),需要检查 64! ≈ 1.2689E89 个组合,如果每秒遍历一亿个组合,也要算到地老天荒了,虽然有各种优化算法,但要求精确解的话,每增加一个点,算法时间通常会指数级的增加。所以像 TSP世界巡游问题 也就求求近似解了。

而智能算法通常可以在短时间内寻找一个较优解,而无法保证找到最优解,现在我们来使用智能算法来求解 TSP 问题,得到一个近似最优解,先上代码:

注:为了方便 遗传算法 以缩写 GA 来表示,禁忌搜索TS模拟退火SA.

# https://github.com/xjz19901211/ga
require 'ga'

# https://github.com/xjz19901211/tabu_search
require 'tabu_search'

# https://github.com/xjz19901211/simulated_annealing
require 'simulated_annealing'

TOTAL = 64
POINTS = TOTAL.times.map { [rand(100), rand(100)] }
POINTS_INDEX = (0..(TOTAL - 1)).to_a
MAX_DIST = (Math.sqrt(100 ** 2 * 2) * TOTAL / 2).to_i

$_dist_cache = {}
def points_dist(i1, i2)
  key = "#{i1}-#{i2}"
  return $_dist_cache[key] if $_dist_cache[key]

  p1, p2 = POINTS[i1], POINTS[i2]
  l1 = (p1[0] - p2[0]).abs
  l2 = (p1[1] - p2[1]).abs
  $_dist_cache[key] = Math.sqrt(l1 ** 2 + l2 ** 2)
end

class Unit
  include GA
  include SA
  include TabuSearch

  attr_accessor :genome, :fitness

  # SA 用
  alias state genome
  alias state= genome=

  def self.random_new
    new(POINTS_INDEX.shuffle)
  end

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

  def dist
    dist = 0
    p1 = genome[-1]
    TOTAL.times do |i|
      p2 = genome[i]
      dist += points_dist(p1, p2)
      p1 = p2
    end
    dist.to_i
  end

  # SA 用
  alias energy dist

  # TS and GA
  def fitness
    @fitness ||= MAX_DIST - dist - $fitness_correct
  end

  # GA
  def cross!(target)
    p = rand(TOTAL)
    np = (p + 1) % TOTAL

    pv1, npv1 = genome[p], genome[np]
    pv2, npv2 = target.genome[p], target.genome[np]

    genome.delete(npv2)
    genome.insert(genome.index(pv2) + 1, npv2)

    target.genome.delete(npv1)
    target.genome.insert(target.genome.index(pv1) + 1, npv1)
  end

  # GA
  def mutate!
    (TOTAL / 4).times do
      i1, i2 = rand(TOTAL), rand(TOTAL)
      genome[i1], genome[i2] = genome[i2], genome[i1]
    end
  end

  # TS
  def step(ts, data)
    id, i1, i2, new_fitness = data
    genome[i1], genome[i2] = genome[i2], genome[i1]
    print "\r[TS] #{$ts_times}"
    ts.update(id, genome, new_fitness)
  end

  # TS
  def search_neighbour(ts)
    iter_times = TOTAL * 2
    $ts_times += iter_times
    iter_times.times.map do
      i1, i2 = rand(TOTAL), rand(TOTAL)
      genome[i1], genome[i2] = genome[i2], genome[i1]
      self.fitness = nil
      new_fitness = fitness
      genome[i1], genome[i2] = genome[i2], genome[i1]
      self.fitness = nil
      ["#{i1}-#{i2}", i1, i2, new_fitness]
    end
  end

  # SA
  def sa_iteration(ctx, temp)
    iter_times = TOTAL * 2
    $sa_times += iter_times
    print "\r[SA] #{temp}"

    iter_times.times.map do
      i1 = rand(TOTAL)
      i2 = rand(TOTAL)
      state[i1], state[i2] = state[i2], state[i1]
      state[i1], state[i2] = state[i2], state[i1] unless ctx.transfer(energy, state)
    end
  end
end

total_iteration = 1000

###### GA
gz = Unit.new_ga_zoo
# gz.debug!
gz.elite_policy!

$fitness_correct = 0
gz.before_init_fitness do |units, generation|
  print "\r[GA]: #{generation}\t"
  $fitness_correct = MAX_DIST / 2 * generation / total_iteration
  units.each {|u, i| u.fitness = nil }
end

st = Time.now
ga_total_units = TOTAL * 2
puts "RUN GA\n"
ga_unit = gz.evolve(ga_total_units, total_iteration, 0.75, 0.1).max
puts "\n"
ga_time = Time.now - st
$fitness_correct = 0

# ###### TS
$ts_times = 0
st = Time.now
ts_ctx = Unit.new_ts_ctx(TOTAL ** 2)
puts "RUN TS\n"
ts_unit = ts_ctx.search(Unit.random_new, total_iteration)
puts "\n"
ts_time = Time.now - st

###### SA
$sa_times = 0
st = Time.now
puts "RUN SA\n"
sa_unit = Unit.simulated_annealing(Unit.random_new, {
  temp: 100,
  stop_temp: 0.01,
  cool: Proc.new {|t| t * 0.99 }
})
puts "\n"
sa_time = Time.now - st

###### Result
puts "-------- Result ----------"
puts "GA[#{ga_time}] #{ga_total_units * total_iteration} times => #{ga_unit.dist}"
puts "TS[#{ts_time}] #{$ts_times} times => #{ts_unit.dist}"
puts "SA[#{sa_time}] #{$sa_times} times => #{sa_unit.dist}"

# gnuplot
# [['GA', ga_unit], ['TS', ts_unit], ['SA', sa_unit]].map do |name, unit|
# data = unit.genome.map {|p| POINTS[p].join(' ') }.join("\n")
# system %Q{echo "#{data}" | gnuplot -e "plot '-' with linespoints title '#{name}-#{unit.dist}'"}
# end

三个算法的代码就这样,需要了解各框架具体实现或是算法细节的,可以通过代码注释中的链接去 Github 上看对应框架的代码。

首先是编码,三种算法使用相同的编码方式,使用索引位置代表 POINTS 中对应的点,再对这些索引进行排列组合,GA 和 TS 用的 genome 这个名字,SA 中使用了 genome 的别名 state

然后计算两点距离通过 points_dist,这个方法做了简单的缓存,避免重复计算,由于 GA 和 TS 都是定义较大的值的解是较好的,所以使用一个最大路径距离减去当前解的距离,使得越好的解 fitness 越大。对于 GA,使用 $fitness_correct 做了一点优化,在进化中逐渐增加选择压力,越好的解所占比重越大。 而 SA 算法定义的是越好的解,能量越小,所有直接使用距离来比较当前解的好坏: alias energy dist

GA 中的交叉通过交换某一点的连接顺序,比如 genome A(0 1 2 3)B(3 2 1 0) ,交换索引位置 i 为 2, 由于 A[i] 的值是 2,A[i-1] 是 1,那么在 B 中也把值 A[i] 放到 A[i-1] 后面,也就是把 B 中的 2 放到 1 的后面,同样, B[i] 为 1,B[i-1] 2,把这一顺序特性放入 A 中,也就是把 A 中的 1 放到 2 的后面。

GA 中的变异通过的随机两个索引位置,交换他们的值,重复这个操作数次。

TS 的搜索相邻解和 GA 的变异方式类似,随机两个索引位置,交换他们的值来产生一个新的相邻解。TS 框架通过 search_neighbour 取得一组相邻解后,在内部把禁忌筛选,通过调用 step 传回匹配的解,step 中再根据传回的数据更新到目标解。

SA 的热平衡迭代的也是使用与 TS 相同的方式来产生相邻的状态,然后通过 SA 框架来判断是否移动到新的解上面,如果不移动的话,就还原修改。

总的来说,上面代码都只是使用了三种算法最基本的思路,没有啥优化,也没有啥花费一堆时间来测试各种参数等,到是 GA 花了点时间做了些优化,而 GA 这门玄学我也很懵,所以就不多说了,看运行结果:

名称[运行时间(秒)] 遍历解数量 => 结果
---------------------------------
GA[6.811757] 128000 times => 1172
TS[6.124985] 128000 times => 871
SA[5.406739] 117376 times => 827

再多运行几次,结果也差不多, SA 得到的路径是最长的,TS 次之, GA 最长路径,基本都遍历了 120K 的解。

GA 我折腾了不少时间,还是很懵逼,我只能把他当玄学了, GA 最爽的地方就是天然支持并行分布式,对于之前说的扫地机器人问题,得到的解到比其它两个算法的结果要好。而且因为他的并行计算,花费的时间也少。而对于各方面的优化,反正折腾多了已经完全不懂了,最近也试着使用 GA 结合其它算法来优化性能,还在折腾。

TS 刚学会,也不是很懂了,邻域查找时,使用可以使用并行计算加速,这里的 TS 框架只用了一张记忆表,至于中期记忆表和长期记忆表或各种优化表,还没折腾过,感觉水也好深。

SA 也是刚学会,他的逻辑非常简单,得到的结果也不差,但是从算法流程来看到的就是:他只能顺序执行。每一步都是基于上一步的结果去操作的,不知道邻域搜索这个逻辑改成并行方式,对算法效果会有多大的影响。

GA 这玄学开始应该更偏向于广域搜索的,成熟时才转向局部搜索,如果出现早熟,直接进入了局部搜索,就很难找到较好的解了,由于这是门玄学,所以在各阶段情况如何,交叉变异算子的影响之类的,我也没有比较清晰的定义。

TS 更偏向于搜索相邻解,只有找不到好的相邻解时,才会向逐步跳出这个局部最优解进行广域搜索。

SA 在温度较高时,基本就是在做广域搜索,在降温过程中,广域搜索逐渐减少,局部搜索逐渐增加。

使用时,通常都是根据他们的特点,不同情况下使用不同的算法,或是相互结合成新的算法模型去折腾。

Comments: