浜松Ruby#58 その3

1-100で同じ問題

#!/usr/bin/env ruby

class Model
  attr_accessor :genomes

  def initialize(genomes)
    @genomes = genomes
  end

  def score
    [].tap do |o|
      (@genomes.size / 2).times do |i|
        o << calc(@genomes[i*2], @genomes[i*2+1], @genomes[i*2+2] || @genomes[0])
      end
    end.inject(:+)
  end

  def calc(x, y, z)
    (100 * x) + (10 * y) + z
  end

  def answer
    [].tap do |o|
      (@genomes.size / 2).times do |i|
        o << @genomes[i*2+1]
      end
    end.inject(:+)
  end

  def clone
    Model.new(@genomes)
  end

  def self.recombination(a, b)
    r = rand(0..1000)
    if r <= 950
      a.clone.crossover(b)
    else
      a.clone.mutation
    end
  end

  def select(size)
    _selects = @genomes.dup.shuffle[0..size]
    {}.tap do |h|
      _selects.each do |v|
        h[@genomes.index(v)] = v
      end
    end
  end

  def crossover(model)
    model.select(@genomes.size / 4).each_pair do |index, value|
      self.swap(index, value)
    end
    self
  end

  def mutation
    r = rand(0..4)
    @genomes = [].tap do |obj|
      @genomes.each_slice(@genomes.size / 4).each_with_index do |collections, i|
        obj.push(i == r ? collections.shuffle : collections)
      end
    end.flatten
    self
  end

  # 指定されたindexの位置にvalueを設定する
  #  valueと同じ値の位置にindexに位置に入っていた値を設定する
  # e.g.) [1, 2, 3, 4, 5, 6, 7, 8] => swap(1, 4) => [1, 4, 3, 2, 5, 6, 7, 8]
  def swap(index, value)
    arr = @genomes.dup
    _value = arr[index]
    _index = arr.index(value)

    arr[_index] = _value
    arr[index] = value

    @genomes = arr
  end

  def inspect
    { value: self.score, answer: self.answer }
  end
end

class GA
  attr_accessor :result, :individuals
  def initialize(size, value)
    @value = value
    # number of individuals
    @size = size
  end

  def initalize_individuals
    arr = (1..100).to_a
    @individuals = [].tap do |o|
      o << Model.new(arr.shuffle)
      o << Model.new(arr.shuffle)
    end
  end

  def run(repeat)
    initalize_individuals

    i = 0
    while i <= repeat
      break if terminate?
      i += 1
      _individuals = @individuals.dup
      @individuals.combination(2).each do |a, b|
        _individuals << Model.recombination(a, b)
      end

      # selection
      @individuals = selection(_individuals)

      str = @individuals.map{|o| o.score}.join(', ')
      puts "#{i}: #{str}"

    end
  end

  def inspect
    "size: #{@individuals.size}, score: #{@individuals.first.score}"
  end

  def terminate?
    r = @individuals.select{|item| item.score == @value }
    if r.nil? || r.empty?
      false
    else
      @result = r.first
      true
    end
  end

  def selection(collections)
    return collections if collections.size < @size
    collections.sort_by{|individual| (@value - individual.score).abs }[0..(@size - 1)]
  end

end

ga = GA.new(10, 282277)
ga.run(1000)
p ga.result

# 結果
# 1: 276271, 278910, 294562
# 2: 276271, 278910, 294562, 285826, 293652, 297019
# 3: 281185, 284370, 284461, 280002, 284552, 279729, 278910, 285826, 286918, 277090
# 4: 282459, 282550, 282641, 281913, 281549, 283187, 281276, 281185, 283733, 280730
# 5: 282368, 282368, 282459, 282550, 281913, 282641, 281640, 281549, 283096, 283187
# 6: 282368, 282368, 282459, 282550, 281913, 282641, 282641, 282823, 281731, 281640
# 7: 282368, 282368, 282368, 282459, 282004, 282550, 282550, 281913, 282641, 282641
# 8: 282368, 282368, 282368, 282368, 282368, 282095, 282459, 282095, 282004, 282550
# 9: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 10: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 11: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 12: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 13: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 14: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 15: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 16: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 17: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 18: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 19: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 20: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 21: 282368, 282368, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# 22: 282277, 282186, 282368, 282368, 282368, 282186, 282368, 282368, 282368, 282368
# {:value=>282277, :answer=>2503}