GAでナップサック問題2

2008-07-18(Fri)に引き続き、

• http://ipr20.cs.ehime-u.ac.jp/column/ga/chapter4.html

に掲載されているナップサック問題に取り組んでみました…。

上記のサイトでは、

• 個体数：　32
• 選択：　エリート保存戦略を併用した適応度比例戦略
• 交叉：　2点交叉
• 突然変異率：　1%

でシミュレーションされていますが、私が作成したプログラムでは、選択をエリート保存戦略と単なる乱数選択の併用にしました。
あと、突然変異率ですが、いろいろ変化させてみたのですが、20%でシミュレーションしました。
他、ナップサックの最大重量は、40kgではなく80kgで行いました。

以下がシミュレーションに使用したプログラムです。汚いですが、GAやRubyに詳しい方からのアドバイスをいただければ幸いです。

knapsack_ga.rb

Item = Struct.new(:weight, :value)

class GA
  DNA = Struct.new(:evaluated_value, :chromosome)
  MUTATION_P = 0.2             # 突然変異の確率
  attr_reader :dna_set

  def initialize(population, items, max)
    @population = population
    @items = items
    @max = max
    @dna_set = Array.new(population) do
      DNA.new(0, Array.new(items.size))
    end
    t = Time.now
    srand(t.sec ^ t.usec ^ Process.pid)
    @dna_set.each_with_index do |dna, idx|
      dna.chromosome.map!{|ele| ele = rand(2)}
      evaluate(idx)
    end
    sort_dna_set
  end

  # 適応度の評価
  def evaluate(idx)
    value_sum = 0
    weight_sum = 0
    @dna_set[idx].chromosome.each_with_index do |ele, i|
        value_sum += @items[i].value if ele == 1
        weight_sum += @items[i].weight if ele == 1
    end
    if weight_sum <= @max
      @dna_set[idx].evaluated_value = value_sum
    else
      @dna_set[idx].evaluated_value = 1
    end
  end
  
  def sort_dna_set
    @dna_set = @dna_set.sort_by{|a| -a.evaluated_value}
  end

  def selection
    # エリート保存戦略
    # 適応度の高い2つの遺伝子を残し、両者を交叉させる
    crossover(0, 1, @population-1, @population-2)

    # ランダムに遺伝子を選択し、交叉
    idx1 = rand(@population-2) 
    idx2 = rand(@population-2)
    crossover(idx1, idx2, @population-3, @population-4)

    idx1 = rand(@population-4) 
    idx2 = rand(@population-4)
    crossover(idx1, idx2, @population-5, @population-6)
  end

  def crossover(p_id1, p_id2, c_id1, c_id2)
    parent1 = Marshal.load(Marshal.dump(@dna_set[p_id1].chromosome))
    parent2 = Marshal.load(Marshal.dump(@dna_set[p_id2].chromosome))

    start_idx = rand(@items.size) # 交叉のはじめのindex
    cross_len = rand(@items.size - start_idx) 

    parent1[start_idx, cross_len], 
    parent2[start_idx, cross_len] = 
      parent2[start_idx, cross_len], 
    parent1[start_idx, cross_len]

    @dna_set[c_id1].chromosome = parent1
    @dna_set[c_id2].chromosome = parent2
    evaluate(c_id1)
    evaluate(c_id2)
  end

  def mutation
    @dna_set.each_with_index do |dna, idx|
      if Range.new(1, (MUTATION_P * 100).to_i) === rand(100)
        i = rand(@items.size)
        dna.chromosome[i] = (dna.chromosome[i] - 1).abs
        evaluate(idx)
      end
    end
  end

  def next_gen
    end_cond = 0
    gen = 0
    prev = 0
    loop do
      selection
      mutation
      sort_dna_set
      if prev == @dna_set[0].evaluated_value && prev != 1
        # 適応度最大の評価値が100回連続して変わらなければ終了
        break if end_cond == 100
        end_cond += 1
      else
        end_cond = 0
      end
      prev = @dna_set[0].evaluated_value
      gen += 1
    end
  end
end

if __FILE__ == $0
  items = Array.new
  open(ARGV[0]) do |f|
    while line = f.gets
      line.chomp!
      weight, value = line.split(/,/)
      items << Item.new(weight.to_i, value.to_i)
    end
  end

  max = 80                   # ナップサックの大きさ
  population = 32            # 染色体の数

  ga = GA.new(population, items, max)
  ga.next_gen
  p ga.dna_set[0].evaluated_value
  p ga.dna_set[0].chromosome
end

item.data

2,21
10,22
7,28
2,21
4,12
9,24
10,15
7,2
8,25
5,28
3,4
10,22
9,36
8,2
8,7
5,40
7,14
3,40
9,33
7,21
2,28
10,22
7,14
9,36
7,14
2,21
10,18
4,12
9,24
10,15
4,21
7,2
8,25
5,28
2,28
3,4
10,22
9,36
7,31
8,2
8,7
5,40
7,14
5,4
7,28
3,40
9,33
7,35
7,21
9,20

シミュレーション結果

mmasa@debian:~/work/ruby/ga$ ruby knapsack_ga.rb item.data
522
[1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0]

上記の結果では、ナップサックの最大重量80kgには、522の価値の品物を詰め込むことができ、配列の0,1がある品物を詰め込む、詰め込まないを表しています。この結果はどの位、最適解に近いんだろう?