浜松ruby#58 その2

Genetic Algorithms

#!/usr/bin/env ruby

class Model
  attr_accessor :genomes

  def initialize(genomes)
    @genomes = genomes
  end

  def score
    [
      calc(@genomes[0], @genomes[1], @genomes[2]),
      calc(@genomes[2], @genomes[3], @genomes[4]),
      calc(@genomes[4], @genomes[5], @genomes[6]),
      calc(@genomes[6], @genomes[7], @genomes[0])
    ].inject(:+)
  end

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

  def answer
    @genomes[1] + @genomes[3] + @genomes[5] + @genomes[7]
  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(2).each_pair do |index, value|
      self.swap(index, value)
    end
    self
  end

  def mutation
    if rand(0..1000) % 2 == 0
      @genomes = @genomes[0..3].shuffle + @genomes[4..7]
    else
      @genomes = @genomes[0..3] + @genomes[4..7].shuffle
    end
    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 to_h
    {
      a: @genomes[0],
      b: @genomes[1],
      c: @genomes[2],
      d: @genomes[3],
      e: @genomes[4],
      f: @genomes[5],
      g: @genomes[6],
      h: @genomes[7]
    }
  end

  def inspect
    to_h.merge(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
    @individuals = [].tap do |o|
      o << Model.new([1, 2, 3, 4, 5, 6, 7, 8])
      o << Model.new([2, 3, 4, 5, 6, 7, 8, 1])
    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)

      puts "#{i}: #{self.inspect}"

    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, 1725)
ga.run(1000)
p ga.result