ga.rb

# randomsortする前に試してたもの
# うまく交叉させられなかったのでやめた
# via http://www.ibm.com/developerworks/jp/linux/library/l-genperl/

# -*- coding: utf-8 -*-
require 'rubygems'
require 'scissor'

beats = [56.54187, 57.45314, 58.39871, 59.33056, 60.26698, 61.17596, 62.09638, 63.00536, 63.91434, 64.82103, 65.72315, 66.6207, 67.50452, 68.39063, 69.27217, 70.06129, 70.77629, 71.66926, 72.55537, 73.49408, 74.42962, 75.40833, 76.35507, 77.26986]

# segment数は-1
$beat_index = (0..beats.length-2).map{|i| i}
$target = $beat_index
$len = $beat_index.length - 2

#rate = 0.1
$most_fitness = 0.0
$min_fitness
selected = ''
selected_beats = []
srand Time.now.to_i

def init_population(size)
  population = (1..size).map do |i|
    {
      :dna => $beat_index.shuffle,
      :survived => 1,
      :parent => 0,
      :fitness => 0,
    }
  end
end

def update_fitness(populations)
  populations.each do |po|
    po[:fitness] = fitness(po[:dna], $target, $len)
  end
end

def update_survived(populations, min_fitness)
  populations.each do |po|
    po[:survived] = po[:fitness] >= min_fitness
    po[:fitness] = 0 if po[:fitness] < min_fitness
  end
end

def update_parents(populations)
  size = populations.length
  weights = populations.find_all{|v| v[:survived]}.map{|v| v[:fitness]}
#  p "  #{weights}"
  abort "population size #{size} is too small." if size < 2
  (1..size).each do |i|
    index = sample weights
    abort "undefined index return by sample()." unless index
    abort "invalid index #{indx} returned by sample()" unless index >= 0 && index < size
    populations[index][:parent] += 1
  end
#  parents = populations.map{|po| po[:parent]}
#  p "parents = #{parents.inject(0){|r,i|r+i}}, #{parents.join(',')}"
end

def fitness_top_n(a, b, n)
#  p "  #{a.inspect} :: #{b.inspect} :: #{n.inspect}"
#  p "  #{a.length} :: #{b.length}"
  top = (0..a.length-1).map{|i| [i, b[i], (a[i] - b[i]) ** 2]}.sort{|_a,_b| _a[2] <=> _b[2]}.map{|v| v[0]}[0..n]
#  p top
  best = (0..a.length-1).map do |i|
#    p i
    result = top.include?(b[i]) ? b[i] : nil
#    p "#{i} #{result}"
    result
  end
#  p best

  other = b - best.compact
#  p other

  result = (0..a.length-1).map do |i|
    best[i] == nil ? other.shift : best[i]
  end
#  p result
  result
end

def recombine(populations)
  pop_size = populations.length
  parent_populations = []
  new_populations = []
  total_parent_slots = 1

  while total_parent_slots
    total_parent_slots = 0
    total_parent_slots = populations.inject(total_parent_slots){|r,i| r+i[:parent]}
    break if total_parent_slots == 0
    po = nil
    loop do
      po = populations[rand pop_size]
      po = nil unless po[:parent] > 0
      break if po != nil
    end

    parent_populations << po
    po[:parent] -= 1
  end

  parent_populations.each do |parent|
    parent2 = parent_populations[rand pop_size]
    child = {
      :survived => 1,
      :parent => 0,
      :fitness => 0,
    }
    # dna決定
# a
#    index = rand $len
#    child[:dna] = parent[:dna][0..index] + parent2[:dna][index+1..-1]


# b
#    child[:dna] = (0..$len).map do |i|
#      ((parent[:dna][i] + parent2[:dna][i]) / 2.0).to_i
#    end

# c
#    fa1 = [parent, :first, fitness($target, parent[:dna], $len / 2)]
#    fa2 = [parent, :last, fitness($target, parent[:dna], $len / 2, ($len/2)+1)]
#    fb1 = [parent2, :first, fitness($target, parent2[:dna], $len / 2)]
#    fb2 = [parent2, :last, fitness($target, parent2[:dna], $len / 2, ($len/2)+1)]
##    p [fa1, fa2, fb1, fb2]
#    most_fit_part = [fa1, fa2, fb1, fb2].sort{|a,b| b[2] <=> a[2]}[0]
#    part = {
#      :first => {:offset => 0, :last => $len / 2},
#      :last => {:offset => ($len / 2)+1, :last => -1},
#    }
#    most_part = most_fit_part[1]
#    other_part = most_fit_part[1] == :first ? :last : :first
#    other = most_fit_part[0][:dna][ part[other_part][:offset]..part[other_part][:last] ]
#
#    p '----'
#    p part
#    p most_fit_part[0]
#    p other_part
#    p most_fit_part[0][:dna][ part[most_part][:offset]..part[most_part][:last] ]
#    p other
#
#    child[:dna] = most_fit_part[0][:dna][ part[most_part][:offset]..part[most_part][:last] ] + other.shuffle

# e
#    child[:dna] = fitness_top_n parent[:dna], parent2[:dna], $len/2
    kai = (0..$target.length-1).map{|i|i}
    child[:dna] = fitness_top_n kai, parent[:dna], $len/2
#    p "  child.dna = #{child[:dna].length}, #{child[:dna].sort.join(',')}"

    new_populations << child
  end
  new_populations
end

def mutate(population, mut_rate)
  population.each do |po|
    next if rand > mut_rate
#    old_dna = po[:dna]
#    po[:dna] = po[:dna].map do |dna|
#      rand $len
#    end
    po[:dna] = po[:dna].shuffle
  end
end

$unique_sequence = []
def _step(population,i)
  min_fitness = 0.1
#  min_fitness = 0.7
  mut_rate = 0.01

  update_fitness population

  sorted_po = population.sort{|a,b| b[:fitness] <=> a[:fitness]}
  p "[#{i}] #{sorted_po[0].inspect}"
#  p "       #{sorted_po[-1].inspect}"
  $unique_sequence << sorted_po[0][:dna].clone

  update_survived population, min_fitness
  update_parents population
  new_population = recombine population
  mutate new_population, mut_rate
  new_population
end

def fitness(a, b, len, offset = 0)
  denominator = (len - offset) ** 2
  result = (offset..len).map do |i|
    (a[i] - b[i]) ** 2
  end.inject(0){|r,i| r + i}.to_f
  1.0 - Math.sqrt(result) / denominator
end

def sample(weights)
  count = 0
  sample = 0
  (0..weights.length-1).each do |i|
    count += weights[i]
    sample = i if rand(count) < weights[i]
  end
  sample
end

population = init_population 256

step_count = 2000
(0..step_count).each do |i|
  population = _step population, i
end

exit


# gen mp3
file = 'vera_lynn-over_the_rainbow.mp3'
file = File.expand_path file
dir = File.dirname file
basename = File.basename file
mp3 = Scissor file

prev = beats.shift
segments = beats.map do |b|
  r = {
    :start => b,
    :duration => b - prev,
  }
  prev = b
  r
end
p segments
p segments.length

#seq_count = 16
$unique_sequence.uniq! #[0..seq_count]
$unique_sequence.map do |seq|
  p "  seq = #{seq.inspect}"
  seq.map do |s|
    p s
    p segments[s]
    fragment = mp3.slice segments[s][:start], segments[s][:duration]
    fragment
  end.inject(Scissor()){|r,i| r + i}
end.inject(Scissor()){|r,i| r + i}.to_file "#{dir}/#{basename}.ga_#{step_count}steps_2.mp3"


#children = (0..1024 * 256).map do |i|
#  current = beat_index.shuffle
#  f = fitness(current, target)
##  p "current = #{current.inspect}, f = #{f}"
#
#  if f > most_fitness
#    most_fitness = f
#    selected = current
#    selected_beats.push current
#    p "[#{i}]  selected #{selected.inspect}, #{f}"
#  end
#end
#p "most_fitness = #{most_fitness}, #{selected.inspect}"


# - 種(dna)を作る
# - dnaの正規化?した値、fitnessの計算
# - fitness値を元に生存種を選出
# - 生存種から親を選択
# - 親から子を配合
# - 子を突然変異させる
# -