GA.rb

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

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 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 weight
    total_weight = 0

    items.each_with_index do |item, index|
      next unless item
      total_weight += ITEMS[index][:weight]
    end

    return total_weight
  end

  def length
    items.length
  end

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

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

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

  def inspect
    "#{object_id} #{self.value}|#{self.weight} = #{items.map {|i| i ? 1 : 0 }.join(', ')}"
  end
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 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

def exchange_units(units, rate)
  last_index = nil

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

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

def variation_units(units, rate)
  units.each_with_index do |unit, index|
    # next if index == 0
    next if rand() >= rate
    unit.variation!
  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

require 'benchmark'

r = {}
Benchmark.bm do |x|
  x.report('a') do
    puts 'start'
    100.times do
      units = 32.times.map { Unit.random_new }
      unit = gene(units, 100, 0.8, 0.15)
      print unit.inspect + "\r"
      r[unit.value] ||= 0
      r[unit.value] += 1
    end
    puts 'end'
  end
end

puts r